Quadratic Programming (QP)

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

$$\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:

$$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:

$$\bigtriangledown_{\bf x}L({\bf x},{\bf\lambda}) = {\bf Qx}+{\bf c}+{\bf A}^T{\bf\lambda}={\bf0}$$

$$\bigtriangledown_{\bf\lambda}L({\bf x},{\bf\lambda}) = {\bf Ax}-{\bf b}={\bf0}$$ (235)

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

$$\left[\begin{array}{cc}{\bf Q}&{\bf A}^T\\ {\bf A}&{\bf0}\end{arr... ...}\end{array}\right] =\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}^*$.

Example

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

where

$${\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;$$

$$\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:

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