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
Here:
- is the vector of decision variables;
- describes the quadratic terms;
- describes the linear terms;
- and specify inequality constraints;
- and specify equality constraints.
The inequality is interpreted componentwise. Variable bounds, such as , are also linear constraints and can be included explicitly.
The objective function contains a quadratic form, . The matrix can always be taken as symmetric because
The factor is conventional: for symmetric , the gradient and Hessian matrix are simply
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 is positive semidefinite, meaning
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 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 grows, ensuring existence even when the feasible set is unbounded.
Positive semidefiniteness alone does not ensure that the objective is bounded below. For example, , regarded as a quadratic objective with , is unbounded below on .
The curvature of the objective only along feasible directions may matter. In an equality-constrained problem, write
where and the columns of form a basis for the null space of . The reduced Hessian is
If this matrix is positive semidefinite, the objective is convex on the equality-feasible affine space, even if is not positive semidefinite on the whole ambient space. If it is positive definite, the objective is strictly convex on that affine space.
When 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 for and unrestricted multipliers for . The Lagrangian is
The Karush–Kuhn–Tucker conditions are
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 is positive definite, set
Minimizing the Lagrangian over gives the dual problem
For a singular positive semidefinite , 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 explicitly.
Illustrative example
Consider
The unconstrained minimizer, , 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 . Substituting gives
Differentiating yields , hence
The constraint 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
If has full row rank and is positive definite on the null space of , 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 gives
with 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,
is a QP because
Here is positive semidefinite. Nonnegative least squares, constrained regression, and many smoothing problems have this form. Adding an penalty, as in ridge regression, adds a positive semidefinite quadratic term.
Portfolio optimization
In mean–variance portfolio optimization, portfolio risk is represented by
where contains asset weights and is their covariance matrix. Minimizing risk subject to a budget constraint, a target expected return, and linear exposure limits produces a convex QP when 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 . 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 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.