Joseph Li

Weak Duality for QP

Here is a quick proof of weak duality for the following general primal-dual pair of (linear equality constrained) QP problems:

Consider the following primal-dual QP pair: (Primal) Minimizec⊤x+12x⊤Qxsubject toAx=bx≽0\begin{align*} \text{Minimize}\qquad & \mathbf{c}^\top \mathbf{x} + \frac{1}{2} \mathbf{x}^\top \mathbf{Q} \mathbf{x} \newline \text{subject to}\qquad & \mathbf{A}\mathbf{x} = \mathbf{b} \newline & \mathbf{x} \succcurlyeq \mathbf{0}\end{align*} (Dual) Maximizeb⊤y−12x⊤Qxsubject toA⊤y−Qx≼c\begin{align*} \text{Maximize}\qquad & \mathbf{b}^\top \mathbf{y} - \frac{1}{2} \mathbf{x}^\top \mathbf{Q} \mathbf{x} \newline \text{subject to}\qquad & \mathbf{A}^\top \mathbf{y} - \mathbf{Q}\mathbf{x} \preccurlyeq \mathbf{c}\end{align*}

Solution #

To show any solution of the primal (minimization) is no less than any solution of the dual (maximization), we show that b⊤y≤c⊤x+x⊤Qx\mathbf{b}^\top \mathbf{y} \leq \mathbf{c}^\top \mathbf{x} + \mathbf{x}^\top \mathbf{Q} \mathbf{x}.

Using the constraint in the primal, we have y⊤Ax=b⊤y\mathbf{y}^\top \mathbf{A} \mathbf{x} = \mathbf{b}^\top \mathbf{y}. From the constraint in the dual, we have y⊤Ax−x⊤Qx≤c⊤x\mathbf{y}^\top\mathbf{A}\mathbf{x}-\mathbf{x}^\top \mathbf{Q}\mathbf{x} \leq \mathbf{c}^\top \mathbf{x}, since x≽0\mathbf{x}\succcurlyeq \mathbf{0}. Therefore, b⊤y=y⊤Ax≤c⊤x+x⊤Qx\mathbf{b}^\top \mathbf{y} = \mathbf{y}^\top \mathbf{A} \mathbf{x} \leq \mathbf{c}^\top \mathbf{x} + \mathbf{x}^\top \mathbf{Q} \mathbf{x}.

We do not need to assume anything about Q\mathbf{Q}. When Q\mathbf{Q} is the matrix of all zeros, the pair of QPs becomes the standard primal-dual pair for LPs.