Quadratic Programming

Let us consider a constrained optimization problem in the form $$\begin{array}{rl}\underset{\mathbf{x}}{\min }& \frac{1}{2}{\mathbf{x}}^{\top }\mathbf{Q}\mathbf{x}+{\mathbf{c}}^{\top }\mathbf{x}\\ \text{s.t.}& \mathbf{A}\mathbf{x}\le \mathbf{b},\end{array}$$ where $\mathbf{Q}⪰0$.

As the objective function is quadratic and the constraints linear the problem is convex. For this reason KKT conditions are not only necessary but also sufficient if a feasible $x$ w.r.t the constraints exists.

KKT Conditions

The KKT conditions of this problem can be states as: $$\begin{array}{rlr}\mathbf{Q}\mathbf{x}+\mathbf{c}+{\mathbf{A}}^{\top }\mathbf{\mu }& =0& \text{stationarity}\\ \mathbf{A}\mathbf{x}& \le \mathbf{b}& \text{primal feasibility}\\ \mathbf{\mu }& \ge 0& \text{dual feasibility}\\ {\mathbf{\mu }}^{\top }(\mathbf{A}\mathbf{x}-\mathbf{b})& =0& \text{complementary slackness}\end{array}$$

Dual problem

The dual problem of the QP problem can be written as $$\begin{array}{rl}\underset{\mathbf{\mu }}{\max }& \underset{q(\mathbf{\mu })}{\underbrace{\underset{\mathbf{x}}{\min }L(\mathbf{x},\mathbf{\mu })}},L(\mathbf{x},\mathbf{\mu })=\frac{1}{2}{\mathbf{x}}^{\top }\mathbf{Q}\mathbf{x}+{\mathbf{c}}^{\top }\mathbf{x}+{\mathbf{\mu }}^{\top }(\mathbf{A}\mathbf{x}-\mathbf{b})\\ \text{s.t.}& \mathbf{\mu }\ge 0\\ & \mathbf{\mu }\in \{\mathbf{\mu }\mid q(\mathbf{\mu })>-\infty \},\end{array}$$ where the Lagrangian can be manipulated into the form $$L(\mathbf{x},\mathbf{\mu })=\frac{1}{2}{\mathbf{x}}^{\top }\mathbf{Q}\mathbf{x}+{\mathbf{x}}^{\top }(\mathbf{c}+{\mathbf{A}}^{\top }\mathbf{\mu })-{\mathbf{b}}^{\top }\mathbf{\mu }.$$ Its critical point can be found by solving $$\frac{\partial L}{\partial \mathbf{x}}(\mathbf{x},\mathbf{\mu })=\mathbf{Q}\mathbf{x}+\mathbf{c}+{\mathbf{A}}^{\top }\mathbf{\mu }=0,$$ which yields $$\mathbf{x}=-{\mathbf{Q}}^{-1}(\mathbf{c}+{\mathbf{A}}^{\top }\mathbf{\mu }).$$ When substituted back into the original dual problem, after basic manipulations, we attain $$\begin{array}{rl}\underset{\mathbf{\mu }}{\max }& q(\mathbf{\mu })=-\frac{1}{2}(\mathbf{c}+{\mathbf{A}}^{\top }\mathbf{\mu }{)}^{\top }{\mathbf{Q}}^{-1}(\mathbf{c}+{\mathbf{A}}^{\top }\mathbf{\mu })-{\mathbf{b}}^{\top }\mathbf{\mu }\\ \text{s.t.}& \mathbf{\mu }\ge 0\\ & \mathbf{\mu }\in \{\mathbf{\mu }\mid q(\mathbf{\mu })>-\infty \}.\end{array}$$