Recovering Primal Solution from Dual solution

Question

Consider the problem \begin{align*} &\min f(x)\\ & \ \text{s.t.} \ \ \ Ax = b \end{align*}

In this expository paper, Boyd claims (top of page $8$) that if:

1. $\lambda^*$ is a dual optimal solution
2. There is no duality gap
3. $L(x, \lambda^*)$ has a unique minimizer $x^*$ (which can happen, for example, if $f$ is strongly convex)

then $x^*$ is primal optimial.

I've played around with the Lagrangian for some time, but I have not been able to show that $x^*$ is primal feasible, nor that $f(x^*)$ is the primal optimal value.

I am also wondering: if $L(x, \lambda^*)$ does not have a unique minimizer, must a primal optimal solution $x^*$ be among them?

Thank you in advance for any help.

Answer 1

A proof that $x^*$ is optimal can be achieved by a Taylor expansion around $x^*$ at optimality. Observe that $$f(x^*+p) = f(x^*) + p^\top f'(x^*) + \frac12p^\top f''(x^*)p$$

Note that at a local optimum $\nabla f=0$ and given that $f$ is strictly convex it is a PD matrix with positive eigenvalues. Thus the third argument involving the Hessian $>0$ thereby implies that $f(x^*+p) > f(x^*)$ and thus proves that $x^*$ is a global minimum on $f$.

As to your question on how to prove $x^*$ is feasible I think you can prove that by contradiction assuming $A(x^*) \ne b$ and then the KKT conditions under that assumption will not be satisfied.