Quadratic programming

From Wikipedia, the free encyclopedia

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:^[1]

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}) = \tfrac{1}{2} \mathbf{x}^T Q\mathbf{x} + \mathbf{c}^T \mathbf{x}$

Subject to one or more constraints of the form:

$A\mathbf{x} \leq \mathbf b$ (inequality constraint)

$E\mathbf{x} = \mathbf d$ (equality constraint)

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

If $Q\;$ is a positive semidefinite matrix, then $f(\mathbf 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(\mathbf 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 $\mathbf x$ to be a global minimizer is for it to satisfy the Karush–Kuhn–Tucker conditions. These conditions are also sufficient when $f(\mathbf x)$ is convex.

[edit] Solution methods

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

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

[edit] 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) = \tfrac{1}{2} x^{T}Qx + \lambda^{T}(Ax-b)$

To calculate the dual function $g (λ)$ , defined as $g(\lambda) = \inf_{x} L(x,\lambda)$ we find the infimum of $L$ , using $\nabla_{x} L(x,\lambda)=0$ :

x * = - Q - 1 A T λ

, hence the dual function is

$g(\lambda) = -\tfrac{1}{2}\lambda^{T}AQ^{-1}A^{T}\lambda - b^{T}\lambda$

hence the dual of the QP is

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

subject to : $\lambda \geqslant 0$

[edit] Complexity

For positive definite Q, the ellipsoid method solves the problem in polynomial time.^[2] If, on the other hand, Q is indefinite, then the problem is NP-hard.^[3] In fact, even if Q has only one negative eigenvalue, the problem is NP-hard.^[4] If the objective function is purely quadratic, negative semidefinite and has fixed rank, then the problem can be solved in polynomial time^[5].

[edit] Software packages that include QP solvers

1. Free and opensource, with OSI-Approved licenses

Name	License	Brief info
CVXOPT	GPL	source language: C, Python; API: Python
OpenOpt	BSD	universal cross-platform Python-written numerical optimization framework; see its QP page and full list of problems
QuadProg	GPL2	source language: R (a port from S), algorithm of Goldfarb and Idnani (1982, 1983)
QuadProg++	GPLv3	C++, algorithm of Goldfarb and Idnani (1982, 1983)
uQuadProg	GPLv2+	a port of QuadProg++ that uses BLAS

2. Commercial

AIMMS Optimization Modeling, the AIMMS software
CPLEX (convex problems only)
GAMS, see also GAMS
MOSEK (convex problems only)
The Galahad library (free for academic) features solvers for nonconvex quadratic programs
MINQ Matlab program
Linear and Quadratic Programming Solver in CGAL, the Computational Geometry Algorithms Library

[edit] References

^ Nocedal, Jorge; Wright, Stephen J. (2006), Numerical Optimization (2nd ed.), Berlin, New York: Springer-Verlag, p. 449, ISBN 978-0-387-30303-1 .
^ 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
^ Sahni, S. "Computationally related problems," in SIAM Journal on Computing, 3, 262--279, 1974.
^ 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.
^ Allemand, K. (Doctoral thesis 2496, 'Optimisation quadratique en variables binaires : heuristiques et cas polynomiaux'), Swiss Federal Institute of Technology, www.epfl.ch

Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A6: MP2, pg.245.

[edit] See also

[edit] External links

[0] Nocedal, Jorge; Wright, Stephen J. (2006), Numerical Optimization (2nd ed.), Berlin, New York: Springer-Verlag, p. 449, ISBN 978-0-387-30303-1 .

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

[2] Sahni, S. "Computationally related problems," in SIAM Journal on Computing, 3, 262--279, 1974.

[3] 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.

[4] Allemand, K. (Doctoral thesis 2496, 'Optimisation quadratique en variables binaires : heuristiques et cas polynomiaux'), Swiss Federal Institute of Technology, www.epfl.ch

[1]

[2]

[3]

[4]

[5]

Quadratic programming

From Wikipedia, the free encyclopedia

Contents

[edit] Solution methods

[edit] The dual

[edit] Complexity

[edit] Software packages that include QP solvers

[edit] References

[edit] See also

[edit] External links

Views

Personal tools

Navigation

Search

Interaction

Toolbox

Languages