5.7 Quadratic Programming

 

Consider the case of a convex quadratic objective function, where the constraints are affine i.e.,

$min_{x \in \mathbb{R}^d} \quad \frac{1}{2}x^TQx+c^Tx$

subject to $Ax \le b$

Where $A \in \mathbb{R}^{m \times d},b \in \mathbb{R}^m$ and $c \in \mathbb{R}^d$. The square symmetric matrix $Q \in \mathbb{R}^{d \times d}$ is positive definite, and therefore the objective function is convex.This is known as a quadratic program. Observe that it has $d$ variables and $m$ linear constraints.

Consider the quadratic program of two variables

$min_{x \in \mathbb{R}^2}\frac{1}{2}\begin{bmatrix} x_1\\ x_2 \end{bmatrix}^T\begin{bmatrix} 2 & 1\\ 1 & 4 \end{bmatrix} \begin{bmatrix} x_1\\ x_2 \end{bmatrix}+\begin{bmatrix} 5\\ 3 \end{bmatrix}^T\begin{bmatrix} x_1\\ x_2 \end{bmatrix}$

subject to
$\begin{bmatrix} 1 & 0\\ -1& 0\\ 0& 1\\ 0& -1 \end{bmatrix}\begin{bmatrix} x_1\\ x_2 \end{bmatrix} \le \begin{bmatrix} 1\\ 1\\ 1\\ 1 \end{bmatrix}$

This is illustrated in figure

The objective function is quadratic with a positive semidefinite matrix $Q$, resulting in elliptical contour lines. The optimal value must lie in the shaded (feasible) region, and is indicated by the star.

The Lagrangian is given by

$L(x,\lambda)=\frac{1}{2}x^TQx+c^Tx+\lambda^T(Ax-b)$

$\quad=\frac{1}{2}x^TQx+(c+A^T\lambda)^Tx-\lambda^Tb$

where again, we have re arranged the terms.Taking the derivative of $L(x,\lambda)$ with respect to $x$ and setting it to zero gives

$Qx+(c+A^T\lambda)=0$

Assuming that $Q$ is invertible, we get

$x = -Q^{-1}(c + A^T\lambda)$

Substituting  into the primal Lagrangian $L(x,\lambda)$, we get the dual Lagrangian

$D(\lambda)=-\frac{1}{2}(c+A^T\lambda)^TQ^{-1}(c+A^T\lambda)-\lambda^Tb$

Therefore the dual optimization problem is given by

$max_{\lambda \in \mathbb{R}^m}\quad  -\frac{1}{2}(c+A^T\lambda)^TQ^{-1}(c+A^T\lambda)-\lambda^Tb$

subject to $\lambda \ge 0$

Example: Consider the above problem

Provide necessary and sufficient conditions under which a quadratic optimization problem be written as a linear least squares problem. 

Solution 

Consider $min_{x \in R^n} \frac{1}{2} x^ TQx + g^T x$, then the necessary and sufficient condition is $Q$ is PSD and $g \in Ran(Q)$. Indeed, if $Q$ is PSD, then $Q$ has a Cholesky factorization $Q = LL^T$ where $L \in R^{ n×k}$ with $k = rank(Q)$. Since $g \in Ran(Q) = Ran(L)$, there is a vector $b \in R^ k$ such that $−g = Lb$. 

Then $\frac{1}{2} x^TQx + g ^T x = \frac{1}{2} x^TLL^T x − (Lb)^ T x$

  $= || \frac{1}{2} (L^T x) ^T (L^T x) − b^T (L^T x) + \frac{1}{2} b^T b || − \frac{1}{2} b^T b$

$= \frac{1}{2} ||L^T x − b||^T_ 2 −\frac{1}{2} b^Tb$