Quadratic Programming
Minimize a quadratic objective subject to linear constraints: convex when the quadratic term is positive semidefinite.
The problem
A quadratic program (QP) minimizes (1/2) x^T Q x + c^T x subject to linear constraints A x <= b and possibly E x = d. The objective is quadratic and the constraints are linear. When Q is positive semidefinite the objective is convex, the feasible set is a polyhedron, and any local minimum is global.
Convex versus nonconvex
If Q has negative eigenvalues the QP is nonconvex and can have many local minima; solving it to global optimality is NP-hard. The convex case (Q positive semidefinite) is solved efficiently and reliably, so recognizing the sign definiteness of Q is the first modeling question.
Solution methods
- Active-set methods guess which inequality constraints are tight, solve an equality-constrained QP, and update the guess.
- Interior-point methods follow a central path, effective for large sparse QPs.
- For equality-only constraints the KKT conditions form a single linear system solved directly.
Where QPs arise
QPs are ubiquitous: least squares with linear constraints, support vector machine training, portfolio-style variance minimization, and the inner subproblem of sequential quadratic programming for nonlinear optimization. Model predictive control solves a QP at every time step to compute control actions subject to physical limits.
KKT for QP
The optimum satisfies the linear stationarity condition Q x + c + A^T lambda + E^T nu = 0 together with primal feasibility, dual feasibility (lambda >= 0), and complementary slackness. For convex QPs these conditions are necessary and sufficient, which is why solvers can certify optimality.
# min 0.5 x^T Q x + c^T x s.t. Gx <= h, Ax = b
# solved by e.g. cvxopt.solvers.qp or OSQPQuadratic programs appear in trajectory planning, constrained least-squares calibration, and the control loops that keep physical systems within operating limits.