Quadratic programming (QP) is a type of mathematical optimization problem in which a quadratic objective function is minimized or maximized subject to linear equality and inequality constraints. It is a fundamental subfield of nonlinear programming and convex optimization, with broad applications in finance, engineering, machine learning, and operations research. A QP problem is said to be convex if the objective function is convex (or, equivalently, its Hessian matrix is positive semidefinite), guaranteeing that any local optimum is also global; nonconvex QPs are NP-hard in general. Key solution methods include active-set, interior-point, and gradient projection algorithms.
1 Problem formulation
1.1 Standard form
The standard form of a quadratic program is:
\[ \begin{aligned} \min_{x \in \mathbb{R}^n} \quad & \frac{1}{2} x^T Q x + c^T x \\ \text{subject to} \quad & A x = b, \\ & G x \leq h, \end{aligned} \]
where \(Q \in \mathbb{R}^{n \times n}\) is symmetric (often assumed so without loss of generality), \(c \in \mathbb{R}^n\), \(A \in \mathbb{R}^{m \times n}\), \(b \in \mathbb{R}^m\), \(G \in \mathbb{R}^{p \times n}\), and \(h \in \mathbb{R}^p\). The constant term in the objective is omitted as it does not affect the solution.
1.2 Canonical form
In the canonical form, the inequality constraints are often expressed in non‑negativity form, and the equality constraints may be embedded differently. One common canonical representation is:
\[ \begin{aligned} \min_{x} \quad & \frac{1}{2} x^T Q x + c^T x \\ \text{s.t.} \quad & x \geq 0, \\ & A x = b. \end{aligned} \]
This form is convenient for duality theory and for certain interior‑point methods.
1.3 Variables and parameters
- \(x\): decision variables of dimension \(n\).
- \(Q\): symmetric Hessian matrix. Its definiteness determines convexity.
- \(c\): linear cost vector.
- \(A, b\): define \(m\) equality constraints.
- \(G, h\): define \(p\) inequality constraints.
- Active constraints: those constraints satisfied with equality at the optimum.
2 Classification
2.1 Convex quadratic programming
A QP is convex if \(Q\) is positive semidefinite (\(Q \succeq 0\)). In this case the objective function is convex, and the feasible set (intersection of affine half‑spaces) is convex. Every local minimum is a global minimum. Convex QPs are solvable in polynomial time.
2.1.1 Strictly convex QP
If \(Q\) is positive definite (\(Q \succ 0\)), the objective is strictly convex, and the problem has a unique optimal solution (if feasible). This case is common in regularized least‑squares problems.
2.1.2 Positive semidefinite case
When \(Q\) is positive semidefinite but not definite, the objective may have multiple minimizers (e.g., a flat valley). The solution set is convex; any minimizer can be found via appropriate methods.
2.2 Nonconvex quadratic programming
If \(Q\) is indefinite or negative semidefinite, the QP is nonconvex. Such problems may have multiple local minima, and finding the global optimum is NP‑hard in general.
2.2.1 Indefinite QP
\(Q\) has both positive and negative eigenvalues. The objective is neither convex nor concave. Examples arise in certain portfolio optimization variants and in molecular conformation.
2.2.2 Negative semidefinite QP
Here \(Q\) is negative semidefinite (all eigenvalues ≤ 0). The objective is concave, so the minimum over a convex set is attained at an extreme point (if the feasible region is bounded). Such problems are still computationally challenging for large dimensions.
2.3 Equality-constrained QP
If only equality constraints are present (\(G, h\) absent), the problem reduces to:
\[ \min_x \; \frac{1}{2} x^T Q x + c^T x \quad \text{s.t.} \quad A x = b. \]
This can be solved analytically via the KKT system (see Section 4.1.1) provided the reduced Hessian is positive definite on the nullspace of \(A\).
2.4 Inequality-constrained QP
The presence of inequality constraints introduces combinatorial complexity because one must determine which constraints are active at the optimum. This is the typical form tackled by active‑set and interior‑point methods.
3 Duality theory
3.1 Lagrangian dual
For a QP in standard form, the Lagrangian is:
\[ L(x, \lambda, \nu) = \frac{1}{2} x^T Q x + c^T x + \lambda^T (G x - h) + \nu^T (A x - b), \]
with multipliers \(\lambda \geq 0\) and \(\nu\) free. The dual function \(g(\lambda, \nu) = \inf_x L(x, \lambda, \nu)\) is a concave quadratic function.
3.2 Dual problem for convex QP
When \(Q\) is positive semidefinite, the dual problem is:
\[ \max_{\lambda \geq 0, \; \nu} \; -\frac{1}{2} (c + G^T \lambda + A^T \nu)^T Q^\dagger (c + G^T \lambda + A^T \nu) - h^T \lambda - b^T \nu, \]
where \(Q^\dagger\) is the pseudo‑inverse. The dual provides lower bounds on the primal optimum.
3.3 Strong duality and Slater’s condition
For convex QPs, strong duality (primal optimum = dual optimum) holds if Slater’s condition is satisfied: there exists a strictly feasible point where all inequality constraints are satisfied strictly. For equality‑constrained convex QPs, strong duality holds if the primal is feasible.
4 Solution methods
4.1 Direct methods
4.1.1 KKT system solution
The Karush–Kuhn–Tucker (KKT) conditions for a convex QP with equality constraints \(A x = b\) and inequality constraints \(G x \leq h\) (with multipliers \(\lambda\)) form a linear‑complementarity system:
\[ \begin{bmatrix} Q & A^T & G^T \\ A & 0 & 0 \\ G & 0 & 0 \end{bmatrix} \begin{bmatrix} x \\ \nu \\ \lambda \end{bmatrix} = \begin{bmatrix} -c \\ b \\ h \end{bmatrix}, \quad \lambda \geq 0,\; G x \leq h,\; \lambda_i (G_i x - h_i)=0. \]
Direct methods solve this system after guessing the active set.
4.1.2 Active-set method
The active‑set method iteratively maintains a working set \(W\) of constraints believed to be active at the optimum. At each iteration, it solves an equality‑constrained QP using those constraints.
4.1.2.1 Working set updates
A constraint may be added to the working set if its violation is detected, or removed if its Lagrange multiplier becomes negative. The update ensures that the objective decreases or remains constant.
4.1.2.2 Phase I and Phase II
- Phase I: Find an initial feasible point (if none is known) by solving a linear or quadratic auxiliary problem.
- Phase II: Starting from a feasible point, perform active‑set iterations to converge to the optimum.
4.2 Iterative methods
4.2.1 Interior-point methods
Interior‑point (IP) methods solve QPs by applying Newton‑type steps to a perturbed KKT system, maintaining strict feasibility with respect to inequalities.
4.2.1.1 Barrier function approach
A logarithmic barrier term is added to the objective: \(\phi(x) = \frac{1}{2} x^T Q x + c^T x - \mu \sum_i \log(h_i - G_i x)\), where \(\mu > 0\) is a barrier parameter. As \(\mu \to 0\), the solution approaches the true optimum.
4.2.1.2 Newton-type iterations
The barrier subproblem is solved via a sequence of damped Newton steps. Primal‑dual IP methods treat both primal and dual variables symmetrically, achieving superlinear convergence.
4.2.2 Gradient projection method
For bound‑constrained QPs (e.g., \(l \leq x \leq u\)), the gradient projection method takes a step in the negative gradient direction and projects onto the feasible box. It is simple and effective for large‑scale problems, especially when combined with acceleration (e.g., FISTA).
4.2.3 Sequential quadratic programming (SQP) for QP subproblems
In nonlinear programming, SQP solves a sequence of QP approximations of the original problem. Each QP subproblem is convex (if the Hessian is approximated positively). QP solvers are therefore internal workhorses of SQP methods.
5 Special cases and extensions
5.1 Quadratic programs with box constraints
Box constraints have the form \(l \leq x \leq u\). This subclass is simpler because only bound constraints are present, enabling specialized methods such as gradient projection and projected conjugate gradient.
5.2 Quadratically constrained quadratic programs (QCQP)
A QCQP generalizes QP by allowing quadratic inequality constraints:
\[ \min_x \; \frac{1}{2} x^T Q_0 x + c_0^T x \quad \text{s.t.} \quad \frac{1}{2} x^T Q_i x + c_i^T x + d_i \leq 0,\; i=1,\dots,m. \]
If all \(Q_i\) are positive semidefinite, the problem is convex and can be reformulated as a second‑order cone program.
5.3 Second-order cone programming (SOCP) relation
| A convex QP can be reformulated as an SOCP by introducing a new variable \(t\) and constraint \(\|Q^{1/2}x\|^2 \leq t\). This equivalence allows the use of SOCP solvers for QP problems. |
|---|
5.4 Mixed-integer quadratic programming (MIQP)
MIQP imposes integrality constraints on some variables (e.g., \(x_j \in \mathbb{Z}\)). Such problems are NP‑hard in general and are solved by branch‑and‑bound or branch‑and‑cut methods, often relying on convex QP solvers for lower bounds.
6 Applications
6.1 Portfolio optimization (Markowitz model)
The Markowitz mean‑variance model minimizes portfolio variance \(\frac{1}{2} x^T \Sigma x\) subject to a target expected return \(\mu^T x \geq R\) and a full‑investment constraint \(1^T x = 1\), where \(x\) are asset weights and \(\Sigma\) is the covariance matrix. This is a convex QP.
6.2 Support vector machines (SVM)
In classification, the soft‑margin SVM solves the convex QP:
\[
| \min_{w,b,\xi} \; \frac{1}{2} \|w\|^2 + C \sum_i \xi_i \quad \text{s.t.} \quad y_i (w^T x_i + b) \geq 1 - \xi_i,\; \xi_i \geq 0. |
|---|
\]
The dual is also a QP involving inner products, allowing kernelization.
6.3 Model predictive control (MPC)
In MPC, a finite‑horizon optimal control problem is solved at each time step. The objective (tracking error plus control effort) is often quadratic, and constraints are linear. This leads to a convex QP that must be solved in real time.
6.4 Least squares with linear constraints
| Constrained least‑squares problems, e.g., \(\min_x \|A x - b\|^2\) s.t. \(C x = d\), are equivalent to a QP with \(Q = A^T A\) and \(c = -A^T b\). Such problems arise in signal processing, geophysics, and econometrics. |
|---|
7 Software and implementations
7.1 Commercial solvers (e.g., CPLEX, Gurobi)
CPLEX (IBM) and Gurobi are high‑performance commercial solvers that handle convex QP (and MIQP) efficiently. They use advanced presolve, barrier, and active‑set methods. Both provide interfaces for C, C++, Java, Python, and MATLAB.
7.2 Open-source libraries (e.g., OSQP, qpOASES)
- OSQP (Operator Splitting QP) is an open‑source solver based on the alternating direction method of multipliers (ADMM), designed for large‑scale convex QPs.
- qpOASES is an open‑source active‑set solver tailored for real‑time MPC applications, supporting parametric QP.
7.3 Interfaces in Python (CVXOPT, scipy.optimize)
- CVXOPT provides a QP solver (via
cvxopt.solvers.qp) that implements interior‑point methods for convex QPs. - SciPy (
scipy.optimize.minimize) can solve QPs via thetrust-constrmethod or vialinprogfor special cases, but dedicated QP routines are also available (e.g.,scipy.optimize.minimize(method='SLSQP')can handle small QPs).