Unclear points in derivation of Lagrange duality for a quadratic optimization problem

20 Views Asked by At

Problem0: $\displaystyle \min_{\mathbf{u} \in \mathbf{R}^L}\frac{1}{2}\mathbf{u}^TQ\mathbf{u}+\mathbf{p}^T\mathbf{u}$ $\,$ subject to $\,$ $\mathbf{a}^T\mathbf{u} \ge c$

Problem1: $\displaystyle \min_{\mathbf{u} \in \mathbf{R}^L}\bigg[\frac{1}{2}\mathbf{u}^TQ\mathbf{u}+ \mathbf{p}^T\mathbf{u}+\max_{\alpha \ge 0 }(c-\mathbf{a}^T\mathbf{u})\bigg]$ (Lagrange dual)

Let $\mathbf{u}_0$ be optimal for Problem0 and $\mathbf{u}_1$ be optimal for Problem1.

(a) Show that $\displaystyle \max_{\alpha \ge 0} \alpha (\mathbf{c}-\mathbf{a}^T\mathbf{u}_0)=0$. [Hint: $\mathbf{c}-\mathbf{a}^T\mathbf{u}_0 \le 0$].

(b) Show that $\mathbf{u}_1$ is feasible for Problem0. To show this suppose on the contrary that $\mathbf{c}-\mathbf{a}^T\mathbf{u}_1 > 0$. Show that the objective function in Problem 1 is infinite (Why?), whereas $\mathbf{u}_0$ attains a finite objective of $\frac{1}{2}\mathbf{u}_0^TQ\mathbf{u}_0+ \mathbf{p}^T\mathbf{u}_0$, which conradicts the optimality of $\mathbf{u}_1$.

(c) Show that $\frac{1}{2}\mathbf{u}_1^TQ\mathbf{u}_1+ \mathbf{p}^T\mathbf{u}_1=\frac{1}{2}\mathbf{u}_0^TQ\mathbf{u}_0+ \mathbf{p}^T\mathbf{u}_0$, and hence that $\mathbf{u}_1$ is optimal for Problem0 and $\mathbf{u}_0$ is optimal for Problem1.

My questions:

1-) In part (b), what is the explanation for the "Why" in this part?

2-) Why does $\frac{1}{2}\mathbf{u}_1^TQ\mathbf{u}_1+ \mathbf{p}^T\mathbf{u}_1=\frac{1}{2}\mathbf{u}_0^TQ\mathbf{u}_0+ \mathbf{p}^T\mathbf{u}_0$ enforces optimality of $\mathbf{u}_0$ for Problem1?