Quadratic programming: Difference between revisions

Revision as of 09:12, 13 May 2021

Latest revision as of 05:55, 18 July 2025

(46 intermediate revisions by 27 users not shown)

Line 9:

The quadratic programming problem with {{mvar|n}} variables and {{mvar|m}} constraints can be formulated as follows.<ref>{{Cite book | last1=Nocedal | first1=Jorge | last2=Wright | first2=Stephen J. | title=Numerical Optimization | url=https://archive.org/details/numericaloptimiz00noce_639 | url-access=limited | publisher=[[Springer-Verlag]] | ___location=Berlin, New York | edition=2nd | isbn=978-0-387-30303-1 | year=2006 | page=[https://archive.org/details/numericaloptimiz00noce_639/page/n469 449] }}.</ref>

Given:

* a [[real number|real]]-valued, {{mvar|n}}-dimensional vector {{math|'''c'''}},

* an {{math|''n'' × ''n''}}-dimensional real [[symmetric matrix]] {{mvar|Q}},

* an {{math|''m'' × ''n''}}-dimensional real [[matrix (mathematics)|matrix]] {{mvar|A}}, and

* an {{mvar|m}}-dimensional real vector {{math|'''b'''}},

the objective of quadratic programming is to find an {{mvar|n}}-dimensional vector {{math|'''x'''}}, that will

Line 23:

| <math>A \mathbf{x} \preceq \mathbf{b},</math>

|}

where {{math|'''x'''^T}} denotes the vector [[transpose]] of {{math|'''x'''}}., Theand the notation {{math|''A'''''x''' ⪯ '''b'''}} means that every entry of the vector {{math|''A'''''x'''}} is less than or equal to the corresponding entry of the vector {{math|'''b'''}} (component-wise inequality).

===LeastConstrained least squares===

As a special case when {{math|''Q''}} is [[positive definite matrix|symmetric positive-definite]], the cost function reduces to least squares:

:{| cellspacing="10"

|-

Line 36:

| <math>A \mathbf{x} \preceq \mathbf{b},</math>

|}

where {{math|1=''Q'' = ''R''^T''R''}} follows from the [[Cholesky decomposition]] of {{math|''Q''}} and {{math|1='''c''' = −''R''^T '''d'''}}. Conversely, any such [[constrained least squares]] program can be equivalently framed as a QPquadratic programming problem, even for a generic non-square {{math|''R''}} matrix.

===Generalizations===

When minimizing a function {{mvar|f}} in the neighborhood of some reference point {{math|''x''₀}}, {{mvar|Q}} is set to its [[Hessian matrix]] {{math|'''H'''(''f''&hairsp;('''x'''₀))}} and {{math|'''c'''}} is set to its [[gradient]] {{math|∇''f''&hairsp;('''x'''₀)}}. A related programming problem, [[quadratically constrained quadratic program]]ming, can be posed by adding quadratic constraints on the variables.

==Solution methods==

Line 48:

:*[[interior point method|interior point]],

:*[[active set]],<ref name="ioe.engin.umich">{{cite book|last=Murty|first=Katta G.|title=Linear complementarity, linear and nonlinear programming|series=Sigma Series in Applied Mathematics|volume=3|publisher=Heldermann Verlag|___location=Berlin|year=1988|pages=xlviii+629 pp|isbn=978-3-88538-403-8|url=http://ioe.engin.umich.edu/people/fac/books/murty/linear_complementarity_webbook/|mr=949214|url-status=dead|archive-url=https://web.archive.org/web/20100401043940/http://ioe.engin.umich.edu/people/fac/books/murty/linear_complementarity_webbook/|archive-date=2010-04-01}}</ref>

:*[[Augmented Lagrangian method|augmented Lagrangian]],<ref>{{cite journal | first1 = F. | last1 = Delbos | first2 = J.Ch. | last2 = Gilbert | year = 2005 | title = Global linear convergence of an augmented Lagrangian algorithm for solving convex quadratic optimization problems | journal = Journal of Convex Analysis | volume = 12 | pages = 45–69 |url=http://www.heldermann-verlag.de/jca/jca12/jca1203_b.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://www.heldermann-verlag.de/jca/jca12/jca1203_b.pdf |archive-date=2022-10-09 |url-status=live}}</ref>

:*[[Conjugate gradient method|conjugate gradient]],

:*[[Gradient projection method|gradient projection]],

Line 77:

where {{math|λ}} is a set of Lagrange multipliers which come out of the solution alongside {{math|'''x'''}}.

The easiest means of approaching this system is direct solution (for example, [[LU factorization]]), which for small problems is very practical. For large problems, the system poses some unusual difficulties, most notably that the problem is never positive definite (even if {{mvar|Q}} is), making it potentially very difficult to find a good numeric approach, and there are many approaches to choose from dependent on the problem.<ref>[https://scholar.google.com/scholar?hl=en&q=saddle+point+indefinite+constrained+linear Google search.]</ref>

If the constraints don't couple the variables too tightly, a relatively simple attack is to change the variables so that constraints are unconditionally satisfied. For example, suppose {{math|1='''d''' = 0}} (generalizing to nonzero is straightforward). Looking at the constraint equations:

Line 93:

and if {{mvar|Z}} is chosen so that {{math|1=''EZ'' = 0}} the constraint equation will be always satisfied. Finding such {{mvar|Z}} entails finding the [[null space]] of {{mvar|E}}, which is more or less simple depending on the structure of {{mvar|E}}. Substituting into the quadratic form gives an unconstrained minimization problem:

:<math>\tfrac{1}{2} \mathbf{yx}^\top Z^\top Q Z \mathbf{yx} + \left(Zmathbf{c}^\top \mathbf{cx} \right)^quad \topimplies \mathbf{y}quad

:<math>

\tfrac{1}{2} \mathbf{xy}^\top Z^\top Q Z \mathbf{xy} + \mathbf{c}left(Z^\top \mathbf{xc} \quad right)^\impliestop \quadmathbf{y}</math>

\tfrac{1}{2} \mathbf{y}^\top Z^\top Q Z \mathbf{y} + \left(Z^\top \mathbf{c}\right)^\top \mathbf{y}

</math>

the solution of which is given by:

:<math> Z^\top Q Z \mathbf{y} = -Z^\top \mathbf{c} </math>

Under certain conditions on {{mvar|Q}}, the reduced matrix {{math|''Z''^T''QZ''}} will be positive definite. It is possible to write a variation on the [[conjugate gradient method]] which avoids the explicit calculation of {{mvar|Z}}.<ref>{{Cite journal | last1 = Gould| first1 = Nicholas I. M.| last2 = Hribar| first2 = Mary E.| last3 = Nocedal| first3 = Jorge|date=April 2001| title = On the Solution of Equality Constrained Quadratic Programming Problems Arising in Optimization| journal = SIAM J. Sci. Comput.| pages = 1376–1395| volume = 23| issue = 4| citeseerx = 10.1.1.129.7555| doi = 10.1137/S1064827598345667| bibcode = 2001SJSC...23.1376G}}</ref>

==Lagrangian duality==

{{See also|Dual problem}}

The Lagrangian [[Dual problem|dual]] of a QPquadratic programming problem is also a QPquadratic programming problem. To see thatthis let us focus on the case where {{math|1=''c'' = 0}} and {{mvar|Q}} is positive definite. We write the [[Lagrange multipliers|Lagrangian]] function as

:<math>L(x,\lambda) = \tfrac{1}{2} x^\top Qx + \lambda^\top (Ax-b). </math>

Defining the (Lagrangian) dual function {{math|''g''(λ)}} as <math>g(\lambda) = \inf_{x} L(x,\lambda) </math>, we find an [[infimum]] of {{mvar|L}}, using <math>\nabla_{x} L(x,\lambda)=0</math> and positive-definiteness of {{mvar|Q}}:

:<math> x^* = -Q^{-1} A^\top \lambda.</math>

Hence the dual function is

:<math>g(\lambda) = -\tfrac{1}{2} \lambda^\top AQ^{-1}A^\top \lambda - \lambda^\top b,</math>

and so the Lagrangian dual of the QPquadratic programming problem is

:<math>\text{maximize}_{\lambda\geq 0} \quad -\tfrac{1}{2} \lambda^\top AQ^{-1} A^\top \lambda - \lambda^\top b.</math>

Besides the Lagrangian duality theory, there are other duality pairings (e.g. [[Wolfe duality|Wolfe]], etc.).

==Run-time complexity==

==Complexity==

=== Convex quadratic programming ===

For [[positive-definite matrix|positive definite]] {{mvar|Q}}, the [[ellipsoid method]] solves the problem in (weakly) [[polynomial time]].<ref>{{cite journal| last=Kozlov | first=M. K. |author2=S. P. Tarasov | author3-link=Leonid Khachiyan |author3=Leonid G. Khachiyan | year=1979 | title=[Polynomial solvability of convex quadratic programming] | journal=[[Doklady Akademii Nauk SSSR]] | volume=248 | pages=1049–1051}} Translated in: {{cite journal| journal=Soviet Mathematics - Doklady | volume=20 | pages=1108–1111}}</ref> If, on the other hand, {{mvar|Q}} is indefinite, then the problem is [[NP-hard]].<ref>{{cite journal | last = Sahni | first = S. | title = Computationally related problems | journal = SIAM Journal on Computing | volume = 3 | issue = 4 | pages = 262–279 | year = 1974 | doi=10.1137/0203021| url = http://www.cise.ufl.edu/~sahni/papers/comp.pdf | citeseerx = 10.1.1.145.8685 }}</ref> In fact, even if {{mvar|Q}} has only one negative [[eigenvalue]], the problem is (strongly) [[NP-hard]].<ref>{{cite journal | title = Quadratic programming with one negative eigenvalue is (strongly) NP-hard | first1 = Panos M. | last1 = Pardalos | first2 = Stephen A. | last2 = Vavasis | journal = Journal of Global Optimization | volume = 1 | issue = 1 | year = 1991 | pages = 15–22 | doi=10.1007/bf00120662| s2cid = 12602885 }}</ref>

For [[positive-definite matrix|positive definite]] {{mvar|Q}}, when the problem is convex, the [[ellipsoid method]] solves the problem in (weakly) [[polynomial time]].<ref>{{cite journal| last=Kozlov | first=M. K. |author2=S. P. Tarasov | author3-link=Leonid Khachiyan |author3=Leonid G. Khachiyan | year=1979 | title=[Polynomial solvability of convex quadratic programming] | journal=[[Doklady Akademii Nauk SSSR]] | volume=248 | pages=1049–1051}} Translated in: {{cite journal| journal=Soviet Mathematics - Doklady | volume=20 | pages=1108–1111}}</ref>

Ye and Tse<ref>{{Cite journal |last1=Ye |first1=Yinyu |last2=Tse |first2=Edison |date=1989-05-01 |title=An extension of Karmarkar's projective algorithm for convex quadratic programming |url=https://doi.org/10.1007/BF01587086 |journal=Mathematical Programming |language=en |volume=44 |issue=1 |pages=157–179 |doi=10.1007/BF01587086 |s2cid=35753865 |issn=1436-4646|url-access=subscription }}</ref> present a polynomial-time algorithm, which extends [[Karmarkar's algorithm]] from linear programming to convex quadratic programming. On a system with ''n'' variables and ''L'' input bits, their algorithm requires O(L n) iterations, each of which can be done using O(L n³) arithmetic operations, for a total runtime complexity of O(''L''² ''n''⁴).

== Integer constraints ==

There are some situations where one or more elements of the <math>x\in\R^n</math> vector will need to take on integer values. This leads to the formulation of a mixed-integer quadratic programming (MIQP) problem.<ref>{{Cite journal|last=Lazimy|first=Rafael|date=1982-12-01|title=Mixed-integer quadratic programming|journal=Mathematical Programming| language=en| volume=22| issue=1| pages=332–349| doi=10.1007/BF01581047| s2cid=8456219|issn=1436-4646}}</ref> Applications of MIQP include [[water resources]]<ref>{{Cite journal|last1=Propato Marco|last2=Uber James G.|date=2004-07-01|title=Booster System Design Using Mixed-Integer Quadratic Programming|journal=Journal of Water Resources Planning and Management|volume=130|issue=4|pages=348–352|doi=10.1061/(ASCE)0733-9496(2004)130:4(348)}}</ref> and the [[Tracking error#Index fund creation|construction of index funds]].<ref>{{Cite book|last1=Cornuéjols|first1=Gérard|url=https://www.cambridge.org/core/books/optimization-methods-in-finance/8A4996C5DB2006224E4D983B5BC95E3B|title=Optimization Methods in Finance|last2=Peña|first2=Javier|last3=Tütüncü|first3=Reha|publisher=Cambridge University Press|year=2018|isbn=9781107297340|edition=2nd|___location=Cambridge, UK|pages=167–168}}</ref>

Kapoor and Vaidya<ref>{{Cite book |last1=Kapoor |first1=S |last2=Vaidya |first2=P M |chapter=Fast algorithms for convex quadratic programming and multicommodity flows |date=1986-11-01 |title=Proceedings of the eighteenth annual ACM symposium on Theory of computing - STOC '86 |chapter-url=https://dl.acm.org/doi/10.1145/12130.12145 |___location=New York, NY, USA |publisher=Association for Computing Machinery |pages=147–159 |doi=10.1145/12130.12145 |isbn=978-0-89791-193-1|s2cid=18108815 }}</ref> present another algorithm, which requires O(''L'' * log ''L'' ''* n''^3.67 * log ''n'') arithmetic operations.

=== Non-convex quadratic programming ===

If {{mvar|Q}} is indefinite, (so the problem is non-convex) then the problem is [[NP-hard]].<ref>{{cite journal | last = Sahni | first = S. | title = Computationally related problems | journal = SIAM Journal on Computing | volume = 3 | issue = 4 | pages = 262–279 | year = 1974 | doi=10.1137/0203021| url = http://www.cise.ufl.edu/~sahni/papers/comp.pdf | citeseerx = 10.1.1.145.8685 }}</ref> A simple way to see this is to consider the non-convex quadratic constraint ''x_i''² = ''x_i''. This constraint is equivalent to requiring that ''x_i'' is in {0,1}, that is, ''x_i'' is a binary integer variable. Therefore, such constraints can be used to model any [[Integer programming|integer program]] with binary variables, which is known to be NP-hard.

Moreover, these non-convex problems might have several stationary points and local minima. In fact, even if {{mvar|Q}} has only one negative [[eigenvalue]], the problem is (strongly) [[NP-hard]].<ref>{{cite journal | title = Quadratic programming with one negative eigenvalue is (strongly) NP-hard | first1 = Panos M. | last1 = Pardalos | first2 = Stephen A. | last2 = Vavasis | journal = Journal of Global Optimization | volume = 1 | issue = 1 | year = 1991 | pages = 15–22 | doi=10.1007/bf00120662| s2cid = 12602885 }}</ref>

Moreover, finding a KKT point of a non-convex quadratic program is CLS-hard.<ref>{{Cite arXiv |eprint=2311.13738 |last1=Fearnley |first1=John |last2=Goldberg |first2=Paul W. |last3=Hollender |first3=Alexandros |last4=Savani |first4=Rahul |title=The Complexity of Computing KKT Solutions of Quadratic Programs |date=2023 |class=cs.CC }}</ref>

== Mixed-integer quadratic programming ==

There are some situations where one or more elements of the <vector {{math>|'''x\in\R^n</math> vector'''}} will need to take on [[integer]] values. This leads to the formulation of a mixed-integer quadratic programming (MIQP) problem.<ref>{{Cite journal|last=Lazimy|first=Rafael|date=1982-12-01|title=Mixed-integer quadratic programming|journal=Mathematical Programming| language=en| volume=22| issue=1| pages=332–349| doi=10.1007/BF01581047| s2cid=8456219|issn=1436-4646}}</ref> Applications of MIQP include [[water resources]]<ref>{{Cite journal|last1=Propato Marco|last2=Uber James G.|date=2004-07-01|title=Booster System Design Using Mixed-Integer Quadratic Programming|journal=Journal of Water Resources Planning and Management|volume=130|issue=4|pages=348–352|doi=10.1061/(ASCE)0733-9496(2004)130:4(348)}}</ref> and the [[Tracking error#Index fund creation|construction of index funds]].<ref>{{Cite book|last1=Cornuéjols|first1=Gérard|url=https://www.cambridge.org/core/books/optimization-methods-in-finance/8A4996C5DB2006224E4D983B5BC95E3B|title=Optimization Methods in Finance|last2=Peña|first2=Javier|last3=Tütüncü|first3=Reha|publisher=Cambridge University Press|year=2018|isbn=9781107297340|edition=2nd|___location=Cambridge, UK|pages=167–168}}</ref>

==Solvers and scripting (programming) languages==

Line 155 ⟶ 165:

|[[GNU Octave]]|| A free (its licence is [[GPL]]v3) general-purpose and matrix-oriented programming-language for numerical computing, similar to MATLAB. Quadratic programming in GNU Octave is available via its [https://www.gnu.org/software/octave/doc/interpreter/Quadratic-Programming.html qp] command

|-

|[[HiGHS optimization solver|HiGHS]]|| Open-source software for solving linear programming (LP), mixed-integer programming (MIP), and convex quadratic programming (QP) models

|[[Gurobi]]|| Solver with parallel algorithms for large-scale linear programs, quadratic programs and mixed-integer programs. Free for academic use.

|-

|[[IMSL Numerical Libraries|IMSL]]|| A set of mathematical and statistical functions that programmers can embed into their software applications.

|-

|[[IPOPT]]|| IPOPT (Interior Point OPTimizer) is a software package for large-scale nonlinear optimization.

|-

|[[Julia (programming language)|Julia]]

|A high-level programming language with notable solving package being [https://jump.dev/JuMP.jl/stable/ JuMP]

|-

|[[Maple (software)|Maple]]|| General-purpose programming language for mathematics. Solving a quadratic problem in Maple is accomplished via its [http://www.maplesoft.com/support/help/Maple/view.aspx?path=Optimization/QPSolve QPSolve] command.

Line 176 ⟶ 189:

|-

|[[SAS System|SAS]]/OR|| A suite of solvers for Linear, Integer, Nonlinear, Derivative-Free, Network, Combinatorial and Constraint Optimization; the [[Algebraic modeling language]] OPTMODEL; and a variety of vertical solutions aimed at specific problems/markets, all of which are fully integrated with the [[SAS System]].

|-

|[[SuanShu numerical library|SuanShu]]|| an open-source suite of optimization algorithms to solve [[Linear programming|LP]], QP, [[SOCP]], [[Semidefinite programming|SDP]], [[Sequential quadratic programming|SQP]] in Java

|-

|[[TK Solver]]|| Mathematical modeling and problem solving software system based on a declarative, rule-based language, commercialized by Universal Technical Systems, Inc..

|-

|[[TOMLAB]]||Supports global optimization, integer programming, all types of least squares, linear, quadratic and unconstrained programming for [[MATLAB]]. TOMLAB supports solvers like [[Gurobi]], [[CPLEX]], [[SNOPT]] and [[KNITRO]].

|-

|[[FICO Xpress|XPRESS]]||Solver for large-scale linear programs, quadratic programs, general nonlinear and mixed-integer programs. Has API for several programming languages, also has a modelling language Mosel and works with AMPL, [[General Algebraic Modeling System|GAMS]]. Free for academic use.

|}

== Extensions ==

'''Polynomial optimization'''<ref>{{Citation |last=Tuy |first=Hoang |title=Polynomial Optimization |date=2016 |url=https://doi.org/10.1007/978-3-319-31484-6_12 |work=Convex Analysis and Global Optimization |pages=435–452 |editor-last=Tuy |editor-first=Hoang |access-date=2023-12-16 |series=Springer Optimization and Its Applications |volume=110 |place=Cham |publisher=Springer International Publishing |language=en |doi=10.1007/978-3-319-31484-6_12 |isbn=978-3-319-31484-6|url-access=subscription }}</ref> is a more general framework, in which the constraints can be [[polynomial function]]s of any degree, not only 2.

==See also==

Line 201 ⟶ 219:

|publisher=RAL Numerical Analysis Group Internal Report 2000-1

|url=ftp://ftp.numerical.rl.ac.uk/pub/qpbook/qp.pdf

|archive-url=https://web.archive.org/web/20170705054523/ftp://ftp.numerical.rl.ac.uk/pub/qpbook/qp.pdf|archive-date=2017-07-05|url-status=dead|date=2000

|date=2000

}}

==External links==

*[http://www.numerical.rl.ac.uk/qp/qp.html A page about QPquadratic programming] {{Webarchive|url=https://web.archive.org/web/20110607212051/http://www.numerical.rl.ac.uk/qp/qp.html |date=2011-06-07 }}

*[https://neos-guide.org/content/quadratic-programming NEOS Optimization Guide: Quadratic Programming]

*[https://www.math.uh.edu/~rohop/fall_06/Chapter3.pdf Quadratic Programming] {{Webarchive|url=https://web.archive.org/web/20230408093722/https://www.math.uh.edu/~rohop/fall_06/Chapter3.pdf |date=2023-04-08 }}

*[https://or.stackexchange.com/q/989/2576 Cubic programming and beyond], in Operations Research stack exchange

{{Mathematical programming}}

{{Optimization algorithms}}

{{Authority control}}

[[Category:Optimization algorithms and methods]]