Editing Quadratic programming (section)

===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>