Editing Quadratic programming (section)

==Solution methods==

For general problems a variety of methods are commonly used, including

:*[[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]],
:*extensions of the [[simplex algorithm]].<ref name="ioe.engin.umich" />

In the case in which {{mvar|Q}} is [[positive definite matrix|positive definite]], the problem is a special case of the more general field of [[convex optimization]].

===Equality constraints===

Quadratic programming is particularly simple when {{mvar|Q}} is [[positive definite matrix|positive definite]] and there are only equality constraints; specifically, the solution process is linear. By using [[Lagrange multipliers]] and seeking the extremum of the Lagrangian, it may be readily shown that the solution to the equality constrained problem

:<math>\text{Minimize} \quad \tfrac{1}{2} \mathbf{x}^\mathrm{T} Q\mathbf{x} + \mathbf{c}^\mathrm{T} \mathbf{x}</math>

:<math>\text{subject to} \quad E\mathbf{x} =\mathbf{d}</math>

is given by the linear system

:<math>
\begin{bmatrix}
   Q & E^\top \\
   E & 0
\end{bmatrix}
\begin{bmatrix} \mathbf x \\ \lambda \end{bmatrix}
=
\begin{bmatrix} -\mathbf c \\ \mathbf d \end{bmatrix}
</math>

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.

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:

:<math>E\mathbf{x} = 0</math>

introduce a new variable {{math|'''y'''}} defined by

:<math>Z \mathbf{y} = \mathbf x</math>

where {{math|'''y'''}} has dimension of {{math|'''x'''}} minus the number of constraints. Then

:<math>E Z \mathbf{y} = \mathbf 0</math>

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{x}^\top Q\mathbf{x} + \mathbf{c}^\top \mathbf{x} \quad \implies \quad
\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''<sup>T</sup>''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>