- 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 aconvex 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 theKarush-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 inpolynomial 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" isnegative definite , then the problem isNP-hard . [*Sahni, S. "Computationally related problems," in SIAM Journal on Computing, 3, 262--279, 1974.*] In fact, even if "Q" has only one negativeeigenvalue , the problem isNP-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 inpolynomial 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*] , theAIMMS 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 usesBLAS

* [*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*]

*Wikimedia Foundation.
2010.*