Quadratic programming

Quadratic programming (QP) is a special type of mathematical optimization problem. It is the problem of optimizing (minimizing or maximizing) a quadratic function of several variables subject to linear constraints on these variables.

The quadratic programming problem can be formulated as: [Citation | last1=Nocedal | first1=Jorge | last2=Wright | first2=Stephen J. | title=Numerical Optimization | publisher=Springer-Verlag | location=Berlin, New York | edition=2nd | isbn=978-0-387-30303-1 | year=2006 | page=449 .]

Assume x belongs to $mathbb\{R\}^\{n\}$ space. The "n"×"n" matrix "Q" is symmetric, and c is any "n"×1 vector.

Minimize (with respect to x):$f(mathbf\{x\})\; =\; frac\{1\}\{2\}\; mathbf\{x\}^T\; Qmathbf\{x\}\; +\; mathbf\{c\}^T\; mathbf\{x\}$

Subject to one or more constraints of the form::$Amathbf\{x\}\; leqslant\; b$ (inequality constraint):$Emathbf\{x\}\; =\; d$ (equality constraint)

where $mathbf\{v\}^T$ indicates the vector transpose of $mathbf\{v\}$. The notation $Ax\; leqslant\; b$ means that every entry of the vector "Ax" is less than or equal to the corresponding entry of the vector "b".

If "Q" is a positive semidefinite matrix, then "f"(x) is a convex function. In this case the quadratic program has a global minimizer if there exists at least one vector x satisfying the constraints and "f"(x) is bounded below on the feasible region. If the matrix "Q" is positive definite then this global minimizer is unique. If "Q" is zero, then the problem becomes a linear program. From optimization theory, a necessary condition for a point x to be a global minimizer is for it to satisfy the Karush-Kuhn-Tucker (KKT) conditions. The KKT conditions are also sufficient when "f"(x) is convex.

If there are only equality constraints, then the QP can be solved by a linear system. Otherwise, a variety of methods for solving the QP are commonly used, including interior point, active set and conjugate gradient methods.

Convex quadratic programming is a special case of the more general field of convex optimization.

The dual

The dual of a QP is also a QP. To see that let us focus on the case where $c=0$ and Q is positive definite. We write the Lagrangian:$L(x,lambda)\; =\; frac\{1\}\{2\}\; x^\{T\}Qx\; +\; lambda^\{T\}(Ax-b)$To calculate the dual function $g(lambda)$, defined as $g(lambda)\; =\; inf\_\{x\}\; L(x,lambda)$ we find the infimum of $L$, using $abla\_\{x\}\; L(x,lambda)=0$:

:$x*\; =\; -\; Q^\{-1\}A^\{T\}lambda$, hence the dual function is :$g(lambda)\; =\; -\; frac\{1\}\{2\}lambda^\{T\}AQ^\{-1\}A^\{T\}lambda\; -\; b^\{T\}lambda$hence the dual of the QP is

maximize :$-\; frac\{1\}\{2\}lambda^\{T\}AQ^\{-1\}A^\{T\}lambda\; -\; b^\{T\}lambda$

subject to :$lambda\; geqslant\; 0$

Complexity

For positive definite "Q", the ellipsoid method solves the problem in polynomial time. [Kozlov, M.K.; Tarasov, S.P.; Khachiyan, L.G. "Polynomial solvability of convex quadratic programming," in Sov. Math., Dokl. 20, 1108-1111 (1979). This is a translation from Dokl. Akad. Nauk SSSR 248, 1049-1051 (1979). ISSN: 0197-6788] If, on the other hand, "Q" is negative definite, then the problem is NP-hard. [Sahni, S. "Computationally related problems," in SIAM Journal on Computing, 3, 262--279, 1974.] In fact, even if "Q" has only one negative eigenvalue, the problem is NP-hard. [Quadratic programming with one negative eigenvalue is NP-hard, Panos M. Pardalos and Stephen A. Vavasis in Journal of Global Optimization, Volume 1, Number 1, 1991, pg.15-22.] If the objective function is purely quadratic, negative semidefinite and has fixed rank, then the problem can be solved in polynomial time [Allemand, K. (Doctoral thesis 2496, 'Optimisation quadratique en variables binaires : heuristiques et cas polynomiaux'), Swiss Federal Institute of Technology, [http://library.epfl.ch/theses/?nr=2496 www.epfl.ch] ] .

References

* A6: MP2, pg.245.

ee also

*Linear programming
*Support vector machine

External links

* [http://www.numerical.rl.ac.uk/qp/qp.html A page about QP]
* [http://www-fp.mcs.anl.gov/otc/Guide/OptWeb/continuous/constrained/qprog NEOS guide to QP]

;Software packages that include QP solvers
* [http://www.aimms.com/ AIMMS Optimization Modeling] , the AIMMS software
* [http://www.ilog.com/products/cplex/ CPLEX]
* [http://www.gams.com/ GAMS] , see also GAMS
* [http://www.mosek.com MOSEK]
* free implementations of the algorithm of Goldfarb and Idnani (1982, 1983):
** [http://cran.r-project.org/web/packages/quadprog/index.html QuadProg] in R (a port from S)
** [http://www.diegm.uniud.it/digaspero/index.php?page=software QuadProg++] in C++
** [http://www.lis.deis.unical.it/~furfaro/uQuadProg/uQuadProg.php uQuadProg] a port of QuadProg++ that uses BLAS
* [http://www.mat.univie.ac.at/~neum/software/minq MINQ] Matlab program
* [http://www.cgal.org/Pkg/QPSolver Linear and Quadratic Programming Solver in CGAL, the Computational Geometry Algorithms Library]