Quadratic Programs & QCQP

Minimize a convex quadratic over a polyhedron — and unlike a linear program, the optimum need not be at a corner.

The idea

A quadratic program minimizes a convex quadratic over a polyhedron:

$\begin{aligned} \text{minimize} \quad & \tfrac{1}{2}x^{T}Px + q^{T}x + r \\ \text{subject to} \quad & Gx \preceq h \\ & Ax = b. \end{aligned}$

The requirement that $P$ be symmetric positive semidefinite makes the objective convex; without it the problem is far harder.

Two familiar problems are the extreme cases. Drop the constraints and set $P = 2A^{T}A$, $q = -2A^{T}b$, $r = b^{T}b$: the objective becomes exactly $\|Ax - b\|_{2}^{2}$, so least squares is an unconstrained quadratic program. Set $P = 0$ instead and a linear objective remains over a polyhedron, so a linear program is a quadratic program as well.

Keeping both the curvature and the constraints changes where the optimum can sit. A linear program can always be solved at a vertex of its polyhedron, because a linear objective decreases at a constant rate across a flat face and never prefers an interior point of one. A quadratic objective has a preferred point: its contours are nested ellipses growing outward from the unconstrained minimizer, and the optimum is the point where the smallest ellipse that meets the feasible set touches it — often partway along a face rather than at a vertex.

Ways to work on it

• Walkthrough. Build one two-variable QP from scratch, solve it, and watch its optimum beat every vertex.
• Practice. Classify optimization problems by type and solve small quadratic programs.
• Hardest. Compute the distance between two polyhedra as a quadratic program.

Not sure where to start? Take the ten-question placement test.