← back

Lagrange Multipliers for Constrained Quadratic Optimization

#314 · Machine Learning · Medium

⊣ Solve on deep-ml.com

Problem

Implement the method of Lagrange multipliers to solve a constrained quadratic optimization problem. Given a quadratic objective function and equality constraints, find the optimal point.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import numpy as np

def lagrange_quadratic(Q: np.ndarray, c: np.ndarray,
                       A: np.ndarray, b: np.ndarray) -> dict:
    """
    Solve: minimize (1/2) x^T Q x + c^T x
    subject to: A x = b

    Q: (n, n) positive definite matrix
    c: (n,) linear cost vector
    A: (m, n) constraint matrix
    b: (m,) constraint values

    Uses KKT system:
    [Q  A^T] [x]   = [-c]
    [A   0 ] [lam]   = [ b]
    """
    n = Q.shape[0]
    m = A.shape[0]

    # Build KKT system
    KKT = np.zeros((n + m, n + m))
    KKT[:n, :n] = Q
    KKT[:n, n:] = A.T
    KKT[n:, :n] = A

    rhs = np.zeros(n + m)
    rhs[:n] = -c
    rhs[n:] = b

    solution = np.linalg.solve(KKT, rhs)
    x_opt = solution[:n]
    lambdas = solution[n:]

    obj_value = 0.5 * x_opt @ Q @ x_opt + c @ x_opt

    return {
        "x": x_opt,
        "lambdas": lambdas,
        "objective_value": float(obj_value),
    }

Explanation

  1. The Lagrangian is L(x, lam) = (1/2)x^T Q x + c^T x + lam^T (A x - b).
  2. Setting gradients to zero: dL/dx = Qx + c + A^T lam = 0 and dL/dlam = Ax - b = 0.
  3. This gives the KKT system, a linear system of n + m equations.
  4. Solving the KKT system yields the optimal x and the Lagrange multipliers lambda.
  5. The multipliers indicate the sensitivity of the objective to changes in the constraints.

Complexity

  • Time: O((n + m)^3) for solving the linear system
  • Space: O((n + m)^2) for the KKT matrix
← #313#315 →