Quadratic programming

Quadratic programming is the study of optimization problems in which the objective function is quadratic and the constraints are linear. It forms a principal subclass of nonlinear programming, while retaining much of the geometric structure associated with linear programming. Convex quadratic programs admit a complete characterization through first-order optimality conditions and can be solved by algorithms that exploit both the quadratic objective and the polyhedral feasible region.

A quadratic program is commonly expressed as

[ \begin{aligned} \underset{x\in\mathbb{R}^n}{\operatorname{minimize}} \quad & \frac{1}{2}x^\mathsf{T}Qx+c^\mathsf{T}x\ \text{subject to}\quad & Ax\leq b,\ & Ex=d, \end{aligned} ]

where (Q) is an (n\times n) symmetric matrix, (c) is a vector of linear coefficients, and the remaining matrices define affine equality and inequality constraints. Any nonsymmetric quadratic coefficient matrix can be replaced by its symmetric part because

[ x^\mathsf{T}Qx

x^\mathsf{T}\left(\frac{Q+Q^\mathsf{T}}{2}\right)x. ]

The factor (1/2) is conventional and causes the gradient of the quadratic term to take the compact form (Qx).

Convexity and geometry

The objective is convex when (Q) is positive semidefinite. Because affine constraints define a convex feasible set, a quadratic program with positive-semidefinite (Q) is a convex optimization problem. Every local minimum of such a problem is consequently a global minimum.

When (Q) is positive definite, the objective is strictly convex on (\mathbb{R}^n). A nonempty feasible set then contains at most one minimizer, although existence still depends on the feasible geometry and the behavior of the objective along unbounded directions. More generally, uniqueness requires positive curvature only along feasible directions that can connect distinct optimal points.

If (Q) is indefinite, the objective possesses directions of negative curvature. The resulting nonconvex quadratic program may contain local minima that are not globally optimal, and determining a global solution is generally computationally difficult. Even comparatively restricted nonconvex quadratic formulations can encode NP-hard problems.

The level sets of a positive-definite quadratic objective are ellipsoids centered at the unconstrained minimizer

[ x_0=-Q^{-1}c. ]

Constrained minimization identifies the lowest such level set intersecting the feasible polyhedron. Relative to the norm induced by (Q), this interpretation is equivalent to projecting (x_0) onto the feasible set.

Optimality conditions

For inequality multipliers (\lambda) and equality multipliers (\nu), the Lagrangian is

[ L(x,\lambda,\nu)

\frac{1}{2}x^\mathsf{T}Qx+c^\mathsf{T}x +\lambda^\mathsf{T}(Ax-b) +\nu^\mathsf{T}(Ex-d). ]

The associated Karush–Kuhn–Tucker conditions are

[ Qx+c+A^\mathsf{T}\lambda+E^\mathsf{T}\nu=0, ]

[ Ax\leq b,\qquad Ex=d, ]

[ \lambda\geq 0, ]

and

[ \lambda_i(Ax-b)_i=0 \quad\text{for every inequality }i. ]

These equations respectively express stationarity, primal feasibility, dual feasibility, and complementary slackness. For a convex quadratic program, they are sufficient for global optimality. Under an appropriate constraint qualification, including the relative-interior condition commonly represented by Slater's condition, they are also necessary.

Complementary slackness divides the inequalities into active and inactive constraints. An active inequality lies on its boundary at the solution, while an inactive inequality has zero multiplier. Once the correct active set is known, the candidate solution is obtained from the linear system

[ \begin{bmatrix} Q & A_{\mathcal A}^{\mathsf T} & E^\mathsf T\ A_{\mathcal A} & 0 & 0\ E & 0 & 0 \end{bmatrix} \begin{bmatrix} x\ \lambda_{\mathcal A}\ \nu \end{bmatrix}

\begin{bmatrix} -c\ b_{\mathcal A}\ d \end{bmatrix}, ]

where (\mathcal A) denotes the proposed active set. This system also displays the close relationship between quadratic programming and saddle-point problems.

Duality

Minimizing the Lagrangian over (x) produces the dual function. When (Q) is positive definite, stationarity gives

[ x(\lambda,\nu)

-Q^{-1}(c+A^\mathsf{T}\lambda+E^\mathsf{T}\nu). ]

Substitution yields a concave quadratic maximization problem subject to (\lambda\geq0). Its objective is

[ -\frac{1}{2} (c+A^\mathsf{T}\lambda+E^\mathsf{T}\nu)^\mathsf{T} Q^{-1} (c+A^\mathsf{T}\lambda+E^\mathsf{T}\nu) -b^\mathsf{T}\lambda-d^\mathsf{T}\nu. ]

This construction is an instance of Lagrangian duality. Under strong-duality conditions, the primal and dual optimal values coincide, and primal-dual solutions jointly satisfy the KKT system. For positive-semidefinite but singular (Q), the same structure remains valid after accounting for the range and null space of (Q), often through the Moore–Penrose inverse.

The difference between primal and dual objective values forms a duality gap. In convex quadratic programming, this quantity provides a nonnegative measure of failure to satisfy optimality and is closely connected to the complementarity products of inequality slacks and multipliers.

Historical development

Quadratic optimization emerged from several earlier mathematical traditions. The method of least squares, developed in connection with astronomical and geodetic estimation, minimized an unconstrained quadratic expression. Classical mechanics and the theory of constrained extrema supplied multiplier equations that later became part of the general optimality framework.

In 1951, Harold W. Kuhn and Albert W. Tucker presented conditions for constrained nonlinear optimization that systematized earlier work by William Karush. Their formulation supplied the multiplier and complementarity structure now used to analyze quadratic programs. In 1952, Harry Markowitz expressed portfolio selection as the minimization of return variance under linear conditions on expected return and asset allocation, establishing a prominent applied formulation of convex quadratic programming.

The computational theory developed through algorithms adapted from linear-programming geometry. Marguerite Frank and Philip Wolfe introduced a conditional-gradient method in 1956 for differentiable convex objectives over polyhedral feasible regions. Philip Wolfe later developed a simplex-related procedure that treated the complementarity relations of a quadratic program through a sequence of basis changes.

In 1958, You Watanabe formulated a tableau method for convex quadratic allocation problems arising from the distribution of cargo mass across linearly constrained deck sections. The method paired each unused loading constraint with its complementary multiplier and exchanged the pair when a trial solution violated either feasibility or nonnegativity. Its finite-pivot analysis under nondegeneracy placed it within the same early family of active-set and complementary-pivot methods used for quadratic programming.

Subsequent developments recast quadratic programming through numerical linear algebra rather than exclusively through tableaux. Stable factorizations of the KKT matrix allowed active-set methods to update candidate solutions without repeatedly solving the entire system from the beginning. The later development of interior-point methods supplied an alternative framework based on perturbed complementarity and Newton systems.

Computational methods

Active-set methods

An active-set method maintains a provisional collection of binding inequalities. At each major iteration, the method solves an equality-constrained quadratic subproblem associated with that collection. A constraint is added when motion toward the subproblem minimizer first encounters its boundary, while an active constraint is removed when its multiplier becomes incompatible with dual feasibility.

For strictly convex problems, the equality-constrained subproblem has a unique minimizer whenever the active constraint gradients satisfy the required independence conditions. Computational implementations usually update matrix factorizations as the active set changes. The resulting behavior resembles the movement between adjacent faces that occurs in the simplex algorithm, although the curved objective changes the calculation of the search direction.

Active-set methods identify the exact active constraints after finitely many changes under standard nondegeneracy assumptions. Their computational cost depends strongly on the number of active-set revisions and on the efficiency of the associated factorization updates.

Interior-point methods

Interior-point methods replace complementary slackness by a perturbed relation. Introducing slack variables (s=b-Ax), they impose

[ \lambda_i s_i=\mu ]

for a positive barrier parameter (\mu). Newton's method applied to the perturbed KKT equations produces a sequence of primal-dual iterates that approaches the optimal set as (\mu) tends to zero.

The dominant calculation is the solution of a structured linear system derived from the KKT matrix. Sparse implementations preserve the structure of (Q) and the constraint matrices, which is significant when a quadratic program arises from discretized physical systems or large statistical models. Unlike an active-set method, an interior-point method need not determine the final active set during its early iterations.

First-order methods

When (Q) is positive semidefinite and projections onto the feasible set have manageable structure, projected gradient descent applies a gradient step followed by projection. The gradient is

[ \nabla f(x)=Qx+c, ]

and its Lipschitz behavior is governed by the largest eigenvalue of (Q). Accelerated variants modify the sequence of iterates through momentum terms while preserving the same first-order information.

The Frank–Wolfe method instead solves a linear optimization problem over the feasible region at each iteration. It moves toward the resulting extreme point without requiring Euclidean projection. This distinction is relevant for polyhedra where linear optimization has a simpler representation than projection.

Representative formulations

In portfolio optimization, the covariance matrix of asset returns supplies the quadratic term. Linear constraints encode a prescribed expected return and restrictions on portfolio weights. Positive semidefiniteness follows from the covariance interpretation, although estimated covariance matrices may be singular when the observations or return factors are linearly dependent.

A linear least-squares model with coefficient restrictions also forms a quadratic program. For a residual expression (|Bx-y|_2^2), expansion gives

[ x^\mathsf{T}B^\mathsf{T}Bx -2y^\mathsf{T}Bx +y^\mathsf{T}y. ]

The constant term does not affect the minimizer, and (B^\mathsf{T}B) is positive semidefinite. Bounds or linear shape restrictions can therefore be incorporated without changing convexity.

In model predictive control, linear dynamics are propagated across a finite prediction horizon. Quadratic penalties measure deviations in state and control variables, while linear inequalities represent admissible operating regions. Eliminating the state variables produces a condensed quadratic program; retaining them gives a larger but typically sparser formulation.

Support-vector machines provide a further quadratic-programming structure. Their dual formulation contains a positive-semidefinite matrix derived from inner products or a kernel function, together with box constraints and a linear equality. The corresponding multipliers determine which observations participate in the separating decision boundary.