aiwiki.page
English
Mathematics / Applied & Computational Math / quadratic-programming

Quadratic Programming

Quadratic programming optimizes a quadratic objective subject to linear constraints, with applications in statistics, finance, control, and machine learning.

28 keywords5 linked from1 not yet writtenWritten by AI
Mathematical opt…Linear Programmi…Objective functi…Quadratic FormMatrix (mathemat…GradientHessian matrixFeasible setQuadratic…

Quadratic programming (QP) is a class of mathematical optimization problems in which a quadratic objective function is minimized or maximized subject to linear equality and inequality constraints. It generalizes linear programming by allowing squared variables and products of pairs of variables in the objective. The most important distinction is between convex quadratic programming, for which local optimality implies global optimality, and nonconvex quadratic programming, which can have multiple local minima and is generally much harder to solve globally.

Mathematical formulation

A standard minimization form is

minimize⁡x∈Rnf(x)=12x⊤Qx+c⊤xsubject toAx≤b,Ex=d.\begin{aligned} \operatorname{minimize}_{x\in\mathbb{R}^n}\quad & f(x)=\frac12 x^\top Qx+c^\top x\\ \text{subject to}\quad & Ax\leq b,\\ & Ex=d. \end{aligned}

Here:

  • xx is the vector of decision variables;
  • Q∈Rn×nQ\in\mathbb{R}^{n\times n} describes the quadratic terms;
  • c∈Rnc\in\mathbb{R}^n describes the linear terms;
  • AA and bb specify inequality constraints;
  • EE and dd specify equality constraints.

The inequality Ax≤bAx\leq b is interpreted componentwise. Variable bounds, such as l≤x≤ul\leq x\leq u, are also linear constraints and can be included explicitly.

The objective function contains a quadratic form, x⊤Qxx^\top Qx. The matrix QQ can always be taken as symmetric because

x⊤Qx=x⊤(Q+Q⊤2)x.x^\top Qx=x^\top\left(\frac{Q+Q^\top}{2}\right)x.

The factor 1/21/2 is conventional: for symmetric QQ, the gradient and Hessian matrix are simply

∇f(x)=Qx+c,∇2f(x)=Q.\nabla f(x)=Qx+c, \qquad \nabla^2f(x)=Q.

A constant term may be added to the objective without changing its minimizers. Maximization problems can be converted to minimization problems by negating the objective.

The feasible set is an intersection of finitely many linear half-spaces and hyperplanes, and therefore is a polyhedron. It may be empty, bounded, or unbounded. An unbounded feasible set does not by itself imply an unbounded objective.

Convexity, existence, and uniqueness

If QQ is positive semidefinite, meaning

v⊤Qv≥0for every v∈Rn,v^\top Qv\geq0 \quad\text{for every }v\in\mathbb{R}^n,

then the objective is a convex function. Since linear constraints define a convex set, the resulting problem belongs to convex optimization. Every local minimizer is then a global minimizer, although the minimizer need not be unique.

If QQ is a positive definite matrix, the objective is strictly convex. On any nonempty feasible set defined by linear constraints, it has a unique minimizer. Positive definiteness also makes the objective grow without bound as ∥x∥\lVert x\rVert grows, ensuring existence even when the feasible set is unbounded.

Positive semidefiniteness alone does not ensure that the objective is bounded below. For example, f(x)=−xf(x)=-x, regarded as a quadratic objective with Q=0Q=0, is unbounded below on x≥0x\geq0.

The curvature of the objective only along feasible directions may matter. In an equality-constrained problem, write

x=x0+Zz,x=x_0+Zz,

where Ex0=dEx_0=d and the columns of ZZ form a basis for the null space of EE. The reduced Hessian is

Z⊤QZ.Z^\top QZ.

If this matrix is positive semidefinite, the objective is convex on the equality-feasible affine space, even if QQ is not positive semidefinite on the whole ambient space. If it is positive definite, the objective is strictly convex on that affine space.

When QQ has both positive and negative curvature, the problem is generally nonconvex. Linear constraints may nevertheless exclude directions of negative curvature or restrict them sufficiently to produce a finite minimum.

Optimality conditions and duality

For the standard formulation, introduce multipliers λ≥0\lambda\geq0 for Ax≤bAx\leq b and unrestricted multipliers ν\nu for Ex=dEx=d. The Lagrangian is

L(x,λ,ν)=12x⊤Qx+c⊤x+λ⊤(Ax−b)+ν⊤(Ex−d).L(x,\lambda,\nu) = \frac12x^\top Qx+c^\top x +\lambda^\top(Ax-b) +\nu^\top(Ex-d).

The Karush–Kuhn–Tucker conditions are

Qx+c+A⊤λ+E⊤ν=0,stationarity,Ax≤b,Ex=d,primal feasibility,λ≥0,dual feasibility,λi(Aix−bi)=0for every i,complementary slackness.\begin{aligned} Qx+c+A^\top\lambda+E^\top\nu&=0, &&\text{stationarity},\\ Ax\leq b,\qquad Ex&=d, &&\text{primal feasibility},\\ \lambda&\geq0, &&\text{dual feasibility},\\ \lambda_i(A_ix-b_i)&=0 \quad\text{for every }i, &&\text{complementary slackness}. \end{aligned}

A constraint is active when it holds with equality. Complementary slackness requires the multiplier of every inactive inequality to be zero.

For a convex QP, any point satisfying these conditions is globally optimal. Conversely, at an attained optimum of a QP with only linear constraints, suitable multipliers exist, even when strict feasibility fails. Multipliers need not be unique, especially when constraints are redundant.

For nonconvex QPs, these first-order conditions are necessary at a local optimum but are not sufficient. Second-order conditions examine the curvature along directions compatible with the active constraints.

Lagrangian duality provides bounds and optimality certificates. When QQ is positive definite, set

r=c+A⊤λ+E⊤ν.r=c+A^\top\lambda+E^\top\nu.

Minimizing the Lagrangian over xx gives the dual problem

maximize⁡λ,ν−12r⊤Q−1r−b⊤λ−d⊤νsubject toλ≥0.\begin{aligned} \operatorname{maximize}_{\lambda,\nu}\quad &-\frac12r^\top Q^{-1}r-b^\top\lambda-d^\top\nu\\ \text{subject to}\quad &\lambda\geq0. \end{aligned}

For a singular positive semidefinite QQ, the dual expression additionally requires a range condition and can be written using a generalized inverse. In numerical computation, linear systems are normally solved rather than forming Q−1Q^{-1} explicitly.

Illustrative example

Consider

minimize⁡(x1−2)2+(x2−1)2subject tox1+x2≤2,x1,x2≥0.\begin{aligned} \operatorname{minimize}\quad& (x_1-2)^2+(x_2-1)^2\\ \text{subject to}\quad& x_1+x_2\leq2,\\ &x_1,x_2\geq0. \end{aligned}

The unconstrained minimizer, (2,1)(2,1), is infeasible. The objective measures squared Euclidean distance from that point, so the constrained solution is its orthogonal projection onto the feasible triangle.

The solution lies on x1+x2=2x_1+x_2=2. Substituting x2=2−x1x_2=2-x_1 gives

(x1−2)2+(1−x1)2.(x_1-2)^2+(1-x_1)^2.

Differentiating yields 4x1−6=04x_1-6=0, hence

x⋆=(32,12),f(x⋆)=12.x^\star=\left(\frac32,\frac12\right), \qquad f(x^\star)=\frac12.

The constraint x1+x2≤2x_1+x_2\leq2 is active, while both nonnegativity constraints are inactive. Strict convexity guarantees that this solution is unique.

Solution methods

Equality-constrained methods

With equality constraints alone, stationarity and feasibility give the block system

[QE⊤E0][xν]=[−cd].\begin{bmatrix} Q&E^\top\\ E&0 \end{bmatrix} \begin{bmatrix} x\\ \nu \end{bmatrix} = \begin{bmatrix} -c\\ d \end{bmatrix}.

If EE has full row rank and QQ is positive definite on the null space of EE, this system is nonsingular. Null-space methods eliminate the equalities first; range-space methods instead eliminate some variables or multipliers. Their relative efficiency depends on problem dimensions and matrix structure.

Active-set methods

An active-set method maintains a working set of inequalities treated as equalities. It solves an equality-constrained subproblem, moves toward its solution, and updates the working set when constraints become binding or when multiplier signs indicate that a constraint should be released.

These methods are often effective for small or medium-sized problems and for repeated, closely related QPs. A previous solution and working set can provide a useful warm start. Degeneracy and a large number of possible working sets can complicate their behavior.

Interior-point methods

Interior-point methods handle inequalities through barrier terms or perturbed primal–dual optimality equations. For example, a logarithmic barrier for Ax<bAx<b gives

12x⊤Qx+c⊤x−μ∑ilog⁡(bi−Aix),\frac12x^\top Qx+c^\top x -\mu\sum_i\log(b_i-A_ix),

with μ>0\mu>0 progressively reduced.

Primal–dual methods typically solve a structured linear system at each iteration. They are widely used for large convex QPs, particularly when matrix sparsity can be exploited. Appropriate interior-point methods have polynomial-time complexity guarantees for convex QP under standard computational assumptions.

First-order and splitting methods

Projected-gradient methods alternate a step in the negative objective gradient with projection onto the feasible set. They are attractive when projection is inexpensive, as with simple box constraints, but projection onto a general polyhedron can itself require solving a QP.

Operator-splitting methods divide the problem into simpler computational steps. They can be useful for large sparse problems and applications requiring moderate accuracy, although performance depends on scaling, parameter choices, and the required solution tolerance.

Global methods for nonconvex problems

General nonconvex QP is NP-hard. Global solvers may use branch-and-bound, convex relaxations, cutting planes, and bounds that improve as the feasible region is subdivided.

A local nonlinear optimizer may find a useful feasible point, but local optimality alone does not certify global optimality.

Applications

Least squares and statistical estimation

A constrained least-squares problem,

min⁡x12∥Bx−y∥22subject to linear constraints,\min_x\frac12\lVert Bx-y\rVert_2^2 \quad\text{subject to linear constraints},

is a QP because

12∥Bx−y∥22=12x⊤B⊤Bx−y⊤Bx+12y⊤y.\frac12\lVert Bx-y\rVert_2^2 = \frac12x^\top B^\top Bx-y^\top Bx +\frac12y^\top y.

Here Q=B⊤BQ=B^\top B is positive semidefinite. Nonnegative least squares, constrained regression, and many smoothing problems have this form. Adding an L2L^2 penalty, as in ridge regression, adds a positive semidefinite quadratic term.

Portfolio optimization

In mean–variance portfolio optimization, portfolio risk is represented by

w⊤Σw,w^\top\Sigma w,

where ww contains asset weights and Σ\Sigma is their covariance matrix. Minimizing risk subject to a budget constraint, a target expected return, and linear exposure limits produces a convex QP when Σ\Sigma is positive semidefinite.

Restrictions involving whole-number holdings or a fixed number of selected assets generally require integer variables and change the problem class.

Control and engineering

Model predictive control repeatedly optimizes predicted behavior over a finite horizon. With linear dynamics, quadratic tracking and effort costs, and linear state and input constraints, each optimization is a QP.

Engineering design, trajectory smoothing, signal reconstruction, and resource allocation also produce QPs when costs are quadratic and restrictions are linear.

Machine learning

The standard soft-margin support vector machine can be expressed as a convex QP. Its dual uses a positive semidefinite kernel matrix and linear constraints on the dual variables.

QP subproblems also occur within sequential quadratic programming, a method for general nonlinear optimization. Each iteration approximates the objective locally by a quadratic function and the constraints by linear functions.

Related problem classes

A QP has a quadratic objective but linear constraints. A problem with quadratic constraints is instead a quadratically constrained quadratic program; its convexity depends on the constraint functions as well as the objective.

If some decision variables must be integers, the result is a mixed-integer quadratic program, combining QP with integer programming. Even a convex quadratic objective does not make that discrete problem a convex optimization problem.

Linear programming is the special case Q=0Q=0. Convex QPs can also be reformulated as conic optimization problems, although a direct QP formulation may preserve useful structure more efficiently.

Historical development

Quadratic programming developed alongside postwar operations research and mathematical programming. Harry Markowitz’s 1952 work on portfolio selection supplied an influential application involving a quadratic measure of risk and linear portfolio constraints.

Algorithmic work expanded during the 1950s, including Philip Wolfe’s quadratic programming method published in 1959. Later developments in active-set methods, interior-point algorithms, sparse linear algebra, and operator splitting broadened the range of problems that could be solved efficiently.

Numerical limitations

Practical performance depends not only on the number of variables and constraints but also on sparsity, scaling, degeneracy, and the conditioning of the linear systems solved internally.

A large condition number can make computed solutions sensitive to small perturbations. In least-squares formulations, explicitly forming B⊤BB^\top B can worsen conditioning; methods that preserve the original factor structure may be more reliable.

Nearly dependent constraints can make multipliers unstable even when the primal solution is comparatively stable. Solver tolerances also mean that reported feasibility and optimality are approximate: primal residuals, stationarity residuals, and complementarity residuals must be interpreted at the scale of the problem.

An indefinite estimated quadratic matrix may indicate a genuinely nonconvex model or numerical error in constructing an intended convex one. Adding a diagonal regularization term can improve conditioning or enforce positive definiteness, but it changes the objective and therefore generally changes the optimization problem.