Solving an equality-constrained convex quadratic program

978 Views Asked by At

There's this convex optimization problem which I got stuck after writing the Lagrange equation. I simply couldn't find a way to eliminate the Lagrange multiplier.

$$\begin{array}{ll} \text{minimize} & \frac{1}{2}x^{T} Q x\\ \text{subject to} & Ax = b\end{array}$$

where $Q \in \mathbb{R}^{n \times n}$, $Q = Q^{T} > 0$, $A \in \mathbb{R}^{m \times n}$ and $\operatorname{rank} (A) = m$

1

There are 1 best solutions below

3
On BEST ANSWER

The Lagrangian is $$L(x,\lambda) = \tfrac{1}{2} x^T Q x + \lambda^T ( A x - b)$$ The optimality conditions are $$\begin{bmatrix} Q & A^T \\ A & 0 \end{bmatrix} \begin{bmatrix} x \\ \lambda \end{bmatrix} = \begin{bmatrix} 0 \\ b \end{bmatrix}$$ This is a symmetric indefinite linear system and can be solved for the combined value of $(x,\lambda)$. But we can relate $x$ and $\lambda$ by rewriting the first block row: $$Q x + A^T \lambda = 0 \quad\Longrightarrow\quad x = - Q^{-1} A^T \lambda$$ Substituting into $Ax=b$ yields $$-AQ^{-1}A^T \lambda = b \quad\Longrightarrow\quad \lambda = -\left(AQ^{-1}A^T\right)^{-1} b$$ Finally, we return to the first equation: $$ x = - Q^{-1} A^T \lambda = Q^{-1} A^T \left(AQ^{-1}A^T\right)^{-1} b$$