Quadratic Programming

The quadratic programming (QP) problem involves minimizing a quadratic function subject to linear constraints. A general formulation is
\[ \begin{array}{lcll}
\mbox{minimize} & \frac{1}{2} x^T Q x + c^T x & & \\
\mbox{subject to} & a_i^T x = b_i & \forall i \in \mathcal{E} \\
& a_i^T x \geq b_i & \forall i \in \mathcal{I}
\end{array}
\] where \(Q \in R^{n\times n}\) is symmetric, and the index sets \(\mathcal{E}\) and \(\mathcal{I} \,\) specify the equality and inequality constraints, respectively. Quadratic programs are an important class of problems on their own and as subproblems in methods for general constrained optimization problems, such as sequential quadratic programming (SQP) and augmented Lagrangian methods.

The difficulty of solving the QP problem depends largely on the nature of the matrix \(Q\). For convex QPs, the matrix \(Q\) is positive semidefinite on the feasible set; there are polynomial-time algorithms to solve these relatively easy problems. For non-convex QPs in which the matrix \(Q\) has negative eigenvalues, the objective function may have more than one local minimizer; in this case, the problem is NP-complete. An extreme example is the problem
\[ \begin{array}{lllll}
\mbox{minimize} & – x^T x & & & \\
\mbox{subject to} & -1 \leq & x_i & \leq 1, & \forall i=1,\ldots,n
\end{array}
\] which has a minimizer at any \(x\) with \(|x_i| \,=1\) for \(i = 1,…, n \,\). In this extreme case, there are \(\, 2^n_{} \,\) local minimizers.

Optimality conditions

The necessary optimality conditions for vector \(x^*_{}\) to be a local minimizer are
(1) that it should be primal feasible:

\(a_i^T x^* = b_i\) for \(i \in \mathcal{E}\) and \(a_i^T x^* \geq b_i\) for \(i \in \mathcal{I}\),

(2) that it should be dual feasible:
\(Q x^* + c = \sum_{i \in \mathcal{E} \cup \mathcal{I}} a_i y_i^* \,\) and \(y_i^* \geq 0\) for \(i \in I\),
for some vector of Lagrange multipliers \(y^*_{} \,\), and

(3) that the complementary slackness condition holds:
\(( a_i^T x^* – b_i ) y_i^* = 0\) for all \(i \in \mathcal{I}\).

These requirements are commonly known as the Karush-Kuhn-Tucker (KKT) conditions.

A KKT point is a local minimizer if and only if \(s^T H s \geq 0\) for all vectors \(s \in \mathcal{S}\), where
\[
\mathcal{S} = \left\{\begin{array}{ll}
s : & a_i^T s = 0 \, \mbox{for } \, i \in \mathcal{E} \, \mbox{and } \, i \in \mathcal{I} \, \mbox{such that } \, a_i^T x^* = b_i \, \mbox{and } \, y^*_i > 0 \, \mbox{and } \\
& a_i^T s \geq 0 \, \mbox{for } \, i \in \mathcal{I} \, \mbox{such that } \, a_i^T x^* = b_i \, \mbox{and } \, y^*_i = 0 \end{array} \right\}
\]

This second-order condition is trivially satisfied for convex problems but may be hard (NP-complete) to check for non-convex ones if there are many \(i \in \mathcal{I}\) for which \(a_i^T x^* = b_i\) and \(y^*_i = 0\).

Algorithms

Linear programming is a special case of quadratic programming when the matrix \(Q = 0\). Linear least squares problems are QPs; Levenberg-Marquardt and Gauss-Newton are specialized methods for solving them. If there are no constraints in the QP, then the problem is similar to solving a system of equations, for which there are many techniques (e.g. Conjugate Gradient Method or direct factorizations such as LU or Cholesky Decompositions).

Quadratic programming (QP) problems can be viewed as special types of more general problems, so they can be solved by software packages for these more general problems. Quadratically constrained quadratic programming (QCQP) problems generalize QPs in that the constraints are quadratic instead of linear. Second order cone programming (SOCP) problems generalize QCQPs, and nonlinear programming (NLP) problems generalize SOCPs.

Online and Software Resources
Test Problems
References
  1. Altman, A. and Gondzio, J. 1999. Regularized symmetric indefinite systems in interior point methods for linear and quadratic optimization. Optimization Methods and Software 11: 275-302.
  2. Fletcher, R. 1971. A general quadratic programming algorithm. Journal of the Institute of Mathematics and its Applications 7: 76-91.
  3. Friedlander, M. P. and Orban, D. 2012. A primal-dual regularized interior-point method for convex quadratic programs. Mathematical Programming Computation 4: 71-107.
  4. Gill, P.E., Murray, W., Saunders, M. A. and Wright, M. H. 1991. Inertia-controlling methods for general quadratic programming. SIAM Review 33: 1-36.
  5. Goldfarb, D. and Idnani, A. U. 1983. A numerically stable dual method for solving strictly convex quadratic programs. Mathematical Programming 27: 1-33.
  6. Gould, N. I. M. and Toint, P. L. 2002. An iterative working-set method for large-scale non-convex quadratic programming. Applied Numerical Mathematics 43: 109-128.
  7. Gould, N. I. M., Orban, D., Sartenaer, A. and Toint, P. L. 2001. Superlinear convergence of primal-dual interior point algorithms for nonlinear programming. SIAM Journal on Optimization 11: 974-1002.
  8. Kozlov, M. K., Tarasov, S. P. and Khachiyan, L. G. 1979. Polynomial solvability of convex quadratic programming. Soviet Mathematics Doklady 20: 1108-1111
  9. Murty, K. G. and Kabadi, S. N. 1987. Some NP-complete problems in quadratic and nonlinear programming. Mathematical Programming 39: 117-129.
  10. Nocedal, J. and Wright, S. J. 2006. Numerical Optimization, Springer.
  11. Potra, F. A. and Stoer, J. 2009. On a class of superlinearly convergent polynomial time interior point methods for sufficient LCP. SIAM Journal on Optimization 20: 1333-1363.
  12. Stoer, J. and Wechs, M. 1998. Infeasible-interior-point paths for sufficient linear complementarity problems and their analyticity. Mathematical Programming 83: 407-423.
  13. Stoer, J. and Wechs, M. 1999. On the analyticity properties of infeasible-interior-point paths for monotone linear complementarity problems. Numerische Mathematik 81: 631-645.
  14. Vanderbei, R. J. 1999. LOQO: An interior point code for quadratic programming. Optimization Methods and Software 12: 451–484.
  15. Vavasis, S. A. 1991. Nonlinear Optimization: Complexity Issues, Oxford University Press, Oxford, England.
  16. Zhang, Y. 1994. On the convergence of a class of infeasible interior-point methods for the horizontal linear complementarity problem. SIAM Journal on Optimization 4: 208-227.
  17. Zhao, G. and Sun, J. 1999. On the rate of local convergence of high-order-infeasible-path- following algorithms for \(p_*\)-linear complementarity problems. Computational Optimization and Applications 14: 293-307.