Quadratic Programming (QP)

A quadratic programming (QP) problem is to minimize a quadratic function subject to some equality and/or inequality constraints:

$\displaystyle \begin{tabular}{ll}
min: &
$f({\bf x})=\frac{1}{2}[{\bf x}-{\bf m...
s. t.: & ${\bf A}{\bf x}\le{\bf b}$
\end{tabular}$ (233)

where ${\bf Q}={\bf Q}^T$ is an $N\times N$ positive definite matrix, ${\bf A}$ an $M\times N$ matrix, and ${\bf b}$ is an M-D vector. Also, ${\bf c}=-{\bf Qm}, \;c={\bf m}^T{\bf Q}{\bf m}/2$. Here the scalar constant $c$ can be dropped as it does not play any role in the optimization. Note that ${\bf x}^T{\bf Q}{\bf x}$ is a hyper elliptic paraboloid with the minimum at point ${\bf m}$ in the N-D space.

We first consider the special case where the QP problem is only subject to equality constraints and we assume $m\le N$, i.e., the number of constraints is smaller than the number of unknowns in ${\bf x}$. Then the solution ${\bf x}$ has to satisfy ${\bf Ax}-{\bf b}={\bf0}$, i.e., it has to be on $M$ hyper planes in the N-D space.

The Lagrangian function of the QP problem is:

$\displaystyle L({\bf x},{\bf\lambda})=f({\bf x})+{\bf\lambda}^T({\bf Ax}-{\bf b...
...1}{2}{\bf x}^T{\bf Q}{\bf x}+{\bf c}^T{\bf x}
+{\bf\lambda}^T({\bf Ax}-{\bf b})$ (234)

To find the optimal solution, we first equate the derivatives of the Lagrangian with respect to both ${\bf x}$ and ${\bf\lambda}$ to zero:
$\displaystyle \bigtriangledown_{\bf x}L({\bf x},{\bf\lambda})$ $\displaystyle =$ $\displaystyle {\bf Qx}+{\bf c}+{\bf A}^T{\bf\lambda}={\bf0}$  
$\displaystyle \bigtriangledown_{\bf\lambda}L({\bf x},{\bf\lambda})$ $\displaystyle =$ $\displaystyle {\bf Ax}-{\bf b}={\bf0}$ (235)

These two equations can be combined and expressed in matrix form as:

$\displaystyle \left[\begin{array}{cc}{\bf Q}&{\bf A}^T\\ {\bf A}&{\bf0}\end{arr...
=\left[\begin{array}{c}-{\bf c}\\ {\bf b}\end{array}\right]$ (236)

We then solve this system of $m+N$ equations to get the optimal solution ${\bf x}^*$ and the corresponding ${\bf\lambda}^*$.


$\displaystyle \begin{tabular}{ll}
Minimize: & $f(x_1,x_2)=x^2_1+x^2_2
...t[\begin{array}{c}x_1\\ x_2\end{array}\right]
=x_1+x_2={\bf b}=1$


$\displaystyle {\bf Q}=\left[\begin{array}{cc}2&0\\ 0&2\end{array}\right],\;\;\;...
{\bf c}=\left[\begin{array}{c}0\\ 0\end{array}\right],\;\;\;\;\;
{\bf b}=1;$    

$\displaystyle \left[\begin{array}{rrr}2&0&1\\ 0&2&1\\ 1&1&0\end{array}\right]
...\\ \lambda\end{array}\right]
=\left[\begin{array}{r}0\\ 0\\ 1\end{array}\right]$    

Solving this equation we get the solution $x^*_1=x^*_2=0.5$ and $\lambda^*=-1$, at which the function $f(x^*_1,x^*_2)=0.5$ is minimized subject to $x_1+x_2=1$.

If $M=N$, i.e., the number of equality constraints is the same as the number of variables, then the variable ${\bf x}$ is uniquely determined by the linear system ${\bf Ax}={\bf b}$, as the intersect of $M=N$ hyper planes, independent of the objective function $f({\bf x})$. Further if $M>N$, i.e., the system ${\bf Ax}={\bf b}$ is over constrained, and its solution does not exist in general. It is therefore more interesting to consider QP problems subject to both equality and inequality constraints:

$\displaystyle \begin{tabular}{ll}
min: &
$f({\bf x})=\frac{1}{2}{\bf x}^T{\bf Q...
s. t.: & ${\bf Ax}\le{\bf b}$