Quadratic Programming (QP)
Also known as: QP Optimization, Quadratic Optimization, Convex Quadratic Programming, İkinci Dereceden Programlama
Quadratic Programming (QP) is a class of constrained mathematical optimization in which the objective function is quadratic and the constraints are linear. Formalized by Frank and Wolfe (1956) through their gradient-based feasible-direction algorithm, QP is foundational in operations research, finance, machine learning, and engineering design wherever one must minimize a convex (or non-convex) quadratic cost subject to linear feasibility conditions.
Key highlights
- Polynomial-time solvability for convex QP guarantees efficient, globally optimal solutions.
- Handles both equality and inequality constraints natively through KKT multipliers.
- Widely supported by mature, high-performance solvers applicable to large sparse problems.
- Bridges linear programming (degenerate QP) and general nonlinear optimization in a tractable middle ground.
Intuition
This section is available to Pro members. Upgrade to Pro
How it works
This section is available to Pro members. Upgrade to Pro
When to use it
Use QP when your objective is genuinely quadratic (e.g., variance minimization, least-squares with constraints, margin maximization in SVMs) and your constraints are linear. Convex QP guarantees a global optimum; non-convex QP (indefinite Q) may require branch-and-bound. Prefer linear programming if the objective is linear, and second-order cone or semidefinite programming when constraints themselves are quadratic or matrix-valued. Problem size, sparsity of Q, and available solvers (OSQP, Gurobi, CPLEX, quadprog) should guide the implementation choice.
Strengths & limitations
- Polynomial-time solvability for convex QP guarantees efficient, globally optimal solutions.
- Handles both equality and inequality constraints natively through KKT multipliers.
- Widely supported by mature, high-performance solvers applicable to large sparse problems.
- Bridges linear programming (degenerate QP) and general nonlinear optimization in a tractable middle ground.
- Non-convex QP (indefinite or non-positive-semi-definite Q) is NP-hard in the worst case.
- Memory and computational cost scale quadratically with problem dimension for dense Q matrices.
- Numerical instability can arise when Q is nearly singular or constraints are nearly redundant.
- The Frank–Wolfe method converges slowly (sublinearly) near the optimum compared to active-set or interior-point methods.
Common pitfalls
This section is available to Pro members. Upgrade to Pro
Applications
This section is available to Pro members. Upgrade to Pro
Frequently asked
How does QP differ from linear programming?
In linear programming both the objective and the constraints are linear, so the optimal solution always lies at a vertex of the feasible polytope. In QP the objective is quadratic, so the optimum may lie in the interior. This richer structure enables QP to model variance, energy, and margin problems that LP cannot, but it also demands more sophisticated algorithms to solve.
When is a QP problem guaranteed to have a unique global minimum?
A QP problem has a unique global minimum when the objective's Hessian matrix Q is strictly positive definite (all eigenvalues strictly positive) and the feasible region is non-empty. If Q is only positive semi-definite the minimum may not be unique; if Q is indefinite the problem may be non-convex with multiple local minima, and global solution is generally NP-hard.
Which solver should I use for practical QP problems?
For small to medium dense problems, quadprog (MATLAB/R) or scipy.optimize.minimize with the SLSQP method are accessible choices. For large sparse convex QP, OSQP (open-source) and Gurobi or CPLEX (commercial) offer state-of-the-art interior-point and active-set implementations. The choice depends on problem size, sparsity structure, real-time requirements, and licensing constraints.
Sources
- 1.Frank, M., & Wolfe, P. (1956). An algorithm for quadratic programming. Naval Research Logistics Quarterly, 3(1–2), 95–110.
You have read it. What now?
Cite this page
ScholarGate. (2026, June 2). Quadratic Programming. ScholarGate. https://scholargate.app/optimization/quadratic-programming