Kochenderfer & Wheeler, Chapter 13

Quadratic Programming

Minimize a quadratic objective with linear constraints — the natural home of least-squares problems.

Prerequisites: Chapter 10 (Constraints), Chapter 12 (Linear Programming).

Chapters

Simulations

Quizzes

Chapter 0: What Is a QP?

A quadratic program (QP) minimizes a quadratic objective subject to linear constraints:

minimize ||Ax − b||² subject to Cx ≤ d, Ex = f

QPs arise naturally whenever you fit a model to data with constraints — regression with non-negativity, portfolio optimization with budget limits, support vector machines.

The core idea: Quadratic programs sit between linear programs (linear objective) and general nonlinear programs. They are convex (when the quadratic is positive semidefinite), so any local minimum is global. The key technique is a chain of reductions: QP → least squares with inequalities → least distance program → nonnegative least squares.

A quadratic program has a:

Quadratic objective with linear constraints Linear objective with quadratic constraints Quadratic objective with quadratic constraints

Chapter 1: Unconstrained Least Squares

Without constraints, minimizing ||Ax − b||² has the closed-form solution via the normal equations:

x* = (A^>A)⁻¹A^>b

Using the singular value decomposition A = UΣV^>, the solution can also be written as x* = VΣ⁻¹U^>b, which is numerically more stable.

Key insight: The SVD decomposes the problem into independent 1D problems. Each singular value scales one dimension. Small singular values indicate near-dependencies — directions where the data provides little information. Regularization (adding λ||x||² to the objective) stabilizes these directions.

The normal equations give x* = (A^>A)⁻¹A^>b. This requires that:

A^>A is invertible (A has full column rank) A is square b is zero

Chapter 2: Least Squares + Inequalities

Adding inequality constraints Cx ≥ d to the least-squares problem prevents the closed-form solution. The strategy is to first remove any equality constraints via the LQ decomposition (reducing the number of variables), then solve the remaining problem with inequalities only.

The equality constraints Ex = f reduce the degrees of freedom. After an LQ decomposition of E, some variables are determined by the constraints and only the remaining "free" variables need to be optimized subject to the inequalities.

Think of it this way: Equality constraints pin down some coordinates. Inequality constraints fence in the rest. The LQ decomposition handles the pinning; the nonnegative least-squares solver handles the fencing.

Equality constraints in a QP are handled by:

Using LQ decomposition to eliminate constrained variables Adding a penalty term Ignoring them

Chapter 3: Least Distance Programs

A least distance program finds the point closest to the origin that satisfies linear inequalities:

minimize ||x||² subject to Gx ≥ h

Any least-squares problem with inequalities can be transformed into this form through the SVD-based change of variables z = T·v_fixed − U₁^>b. The key: rewrite the objective so the "target" is the origin, and the inequalities constrain which region you can search.

Key insight: The chain of reductions (QP → least squares with inequalities → least distance → NNLS) progressively simplifies the problem structure. Each step removes one source of complexity until we reach a form with a known efficient algorithm.

A least distance program seeks the point closest to:

The origin, subject to linear inequalities A given target, without constraints Any vertex of a polytope

Chapter 4: Nonnegative Least Squares

The final link in the chain: nonnegative least squares (NNLS) minimizes ||Ex − f|| subject to x ≥ 0. The NNLS problem has an elegant active-set algorithm:

Partition

Split variables into passive (free) set P and zero set Z.

↓

Solve

Solve the unconstrained least squares on the passive variables.

↓

Update

Move variables between P and Z based on gradient and feasibility.

Think of it this way: NNLS guesses which variables should be positive (passive) and which should be zero. It solves the unconstrained problem for the passive set, then adjusts its guess. The algorithm converges because each step either improves the objective or changes the partition.

NNLS requires all design variables to be:

Non-negative (x ≥ 0) Positive (x > 0) Integers

Chapter 5: Solving NNLS

The Lawson-Hanson algorithm for NNLS maintains a passive set P (variables free to be positive) and a zero set Z (variables forced to zero). At each step:

1. Compute the gradient w = E^>(f − Ex). If all gradient components for Z-variables are ≤ 0, the solution is optimal.

2. Otherwise, move the Z-variable with the most positive gradient into P.

3. Solve the unconstrained least squares on P. If any resulting value is negative, interpolate back to feasibility and move that variable to Z.

Convergence: The algorithm terminates in finitely many steps because each step either strictly improves the objective or changes the active set, and there are only finitely many possible active sets.

In the NNLS algorithm, a variable moves from Z to P when:

Its gradient component is the most positive among Z-variables Its value is already positive A random selection is made

Chapter 6: Dual Certificates

As with linear programs, we can verify QP solutions using dual certificates. The KKT conditions for a QP provide the necessary conditions. For an NNLS solution x*:

1. Feasibility: x* ≥ 0

2. Complementary slackness: x_i* · w_i = 0 for all i

3. Stationarity: w = E^>(f − Ex*) ≤ 0 for zero-set variables

Think of it this way: Dual certificates let you audit the solution. Pass the solution to an independent checker that verifies KKT conditions without re-solving the problem. If the checks pass, the solution is provably optimal.

For NNLS, the KKT conditions require the gradient to be:

Non-positive for all variables at zero (no incentive to increase them) Zero for all variables Positive for all variables

Chapter 7: Connections

Problem	Converts To	Method
General QP	Least squares + inequalities	LQ decomposition
LS + inequalities	Least distance program	SVD change of variables
Least distance	NNLS	Dual transformation
NNLS	(solved directly)	Lawson-Hanson active set

The power of reductions: Instead of developing a separate algorithm for each problem type, we reduce everything to NNLS. This is a common pattern in optimization: find one well-understood primitive and reduce everything else to it.

The solution chain for quadratic programs ultimately reduces to:

Nonnegative least squares (NNLS) Linear programming Gradient descent

Chapter 8: Summary

Concept	Key Fact
Quadratic programs	Quadratic objective + linear constraints; convex when PSD
Unconstrained LS	Closed form via normal equations or SVD
Reduction chain	QP → LS+ineq → least distance → NNLS
NNLS	Active-set method; finite convergence guaranteed
Dual certificates	KKT conditions verify optimality independently

Looking ahead: Chapter 14 introduces disciplined convex programming, a framework for automatically verifying and solving convex optimization problems using composition rules.

A positive semidefinite quadratic program has:

A unique global minimum (any local minimum is global) Multiple local minima No feasible solution