Quadratic programming

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}lambdahence 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


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


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

Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • quadratic programming — Variant of linear programming in which the objective function is quadratic rather than linear. In portfolio selection, we often minimize the variance of the portfolio (which is a quadratic function) subject to constraints on the mean return of… …   Financial and business terms

  • Quadratic programming — Variant of linear programming whereby the equations are quadratic rather than linear. The New York Times Financial Glossary …   Financial and business terms

  • Sequential quadratic programming — (SQP) is one of the most popular and robust algorithms for nonlinear continuous optimization. The method is based on solving a series of subproblems designed to minimize a quadratic model of the objective subject to a linearization of the… …   Wikipedia

  • Quadratic — In mathematics, the term quadratic describes something that pertains to squares, to the operation of squaring, to terms of the second degree, or equations or formulas that involve such terms. Quadratus is Latin for square . Mathematics Algebra… …   Wikipedia

  • Quadratic probing — is a scheme in computer programming for resolving collisions in hash tables.Quadratic probing operates by taking the original hash value and adding successive values of an arbitrary quadratic polynomial to the starting value. This algorithm is… …   Wikipedia

  • Linear programming — (LP, or linear optimization) is a mathematical method for determining a way to achieve the best outcome (such as maximum profit or lowest cost) in a given mathematical model for some list of requirements represented as linear relationships.… …   Wikipedia

  • Dynamic programming — For the programming paradigm, see Dynamic programming language. In mathematics and computer science, dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems… …   Wikipedia

  • Nonlinear programming — In mathematics, nonlinear programming (NLP) is the process of solving a system of equalities and inequalities, collectively termed constraints, over a set of unknown real variables, along with an objective function to be maximized or minimized,… …   Wikipedia

  • Mathematical programming — An operations research technique that solves problems in which an optimal value is sought subject to specified constraints. Mathematical programming models include linear programming, quadratic programming, and dynamic programming. The New York… …   Financial and business terms

  • mathematical programming — An operations research technique that solves problems in which an optimal value is sought subject to specified constraints. Mathematical programming models include linear programming, quadratic programming, and dynamic programming. Bloomberg… …   Financial and business terms

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”