Skip to content
Tutorials Center
My learning

Topics

Lesson 26 of 38 · Linear and Quadratic Programs

Quadratic Programs

Solve quadratic programs: write the problem in matrix form, solve the equality-constrained case with one linear system, and handle inequalities with an active-set search.

A quadratic program (QP) minimizes a quadratic function over a polyhedron:

Text
minimize    ½ xᵀP x + qᵀx
subject to  G x ≤ h
            A x = b

If P is positive semidefinite, the objective is convex and the QP is a convex problem (all the duality theory applies, and Slater's condition holds whenever a feasible point exists, because the constraints are affine). QPs are the next step after LPs. Least squares with bounds, support vector machines and portfolio selection are QPs.

Equality constraints: one linear system

Start with equality constraints only: minimize ½xᵀPx + qᵀx subject to Ax = b. The Lagrangian is ½xᵀPx + qᵀx + νᵀ(Ax - b). The KKT conditions are two linear equations:

Text
P x + q + Aᵀν = 0       (stationarity)
A x         = b         (feasibility)

Stack them into one square system:

Text
[ P   Aᵀ ] [ x ]   [ -q ]
[ A   0  ] [ ν ] = [  b ]

One call to a linear solver finds both the optimum x and its multipliers ν. If P is positive definite on the null space of A and A has full row rank, the matrix is invertible.

Example: the closest point to the origin on the line x₁ + x₂ = 2. Here P = 2I, q = 0, A = [1 1], b = 2. The answer is x = (1, 1) with ν = -2, matching the dual function lesson.

Python Equality-constrained QP via the KKT system

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For example 2 you can verify by hand: stationarity gives 2x₁ - 2 + ν = 0, 4x₂ + ν = 0, 2x₃ + ν = 0. With x₁ = 1 - ν/2, x₂ = -ν/4, x₃ = -ν/2, the sum is 1 - ν/2 - ν/4 - ν/2 = 1 - 5ν/4 = 1, so ν = 0 and x = (1, 0, 0). The printed answer should match.

Inequalities: the active-set idea

With inequalities, the difficulty is that we do not know which constraints are tight at the optimum. An active-set method guesses a set S of active constraints (treated as equalities), solves the resulting equality QP, and checks KKT:

  • All inactive constraints must be satisfied (primal feasibility).
  • All active multipliers must be ≥ 0 (dual feasibility).

If a check fails, adjust the guess. For small problems we can simply try every guess. Consider:

Text
minimize    ½ xᵀP x + qᵀx    with  P = [[2, 1], [1, 2]],  q = (-2, -6)
subject to  x ≥ 0

Without constraints, the minimum is at x = -P⁻¹q = (-2/3, 10/3), which breaks x₁ ≥ 0. So x₁ = 0 should be active. Then the objective in x₂ is x₂² - 6x₂, minimized at x₂ = 3. The gradient Px + q = (1, 0): the multiplier for x₁ ≥ 0 is the matching gradient entry 1 ≥ 0, so KKT holds and x* = (0, 3) with value -9.

Python Try every active set

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Only one guess passes both checks. The others fail either because a variable goes negative or because a multiplier would be negative (meaning the constraint should be released).

Because the QP is convex, that KKT point is the global minimum.

Using a general solver

For real problems, use a solver that implements active-set or interior-point methods. SciPy's minimize with SLSQP handles small QPs; for large ones, specialized packages (OSQP, Gurobi, CVXOPT) are used. The check below confirms our hand result.

Python Confirm with SLSQP

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

If P is not positive semidefinite, the QP is non-convex. It may have several local minima, and a KKT point is no longer guaranteed to be optimal. Check the eigenvalues of P with np.linalg.eigvalsh(P) before trusting a QP solver's answer.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. How is a QP with only equality constraints Ax = b solved?

    Stationarity and feasibility are both linear in (x, ν), so one linear solve gives the exact optimum.
  2. 2. When is a QP a convex problem?

    A quadratic form xᵀPx is convex exactly when P is positive semidefinite.
  3. 3. In an active-set method, what shows that a guessed active constraint should be released?

    Dual feasibility needs λ ≥ 0. A negative multiplier means the objective would improve by moving into the interior.
  4. 4. For P = [[2,1],[1,2]], q = (-2,-6) and x ≥ 0, which constraint is active at the optimum?

    The unconstrained minimum has x₁ < 0, so x₁ = 0 becomes active. Then x₂ = 3 > 0 is inactive.

Summary

  • A QP minimizes ½xᵀPx + qᵀx over linear constraints; it is convex when P ⪰ 0.
  • With equality constraints only, solve the KKT linear system for x and ν at once.
  • With inequalities, guess an active set, solve, and check feasibility and the signs of the multipliers.
  • Always cross-check small hand solutions with a numerical solver.

Next: Portfolio Optimization as a QP