How to solve the primal problem via Lagrangian directly?

Question

From section 5.5.5 of Convex Optimization by Stephen Boyd and Lieven Vandenberghe https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf, consider the primal problem $$\begin{cases} \min:\ f_0(x)\\ \mathrm{s.t.\ }f_i(x)\leq 0,i=1,\dots,m; h_i(x)=0,i=1,\dots,p. \end{cases}$$ The book in page 248 of section 5.5.5 says that "Suppose we have strong duality and an optimal $(\lambda^{\star}, \nu^{\star})$ is known. Suppose that the minimizer of Lagrangian $L(x, \lambda^{\star}, \nu^{\star})$, i.e., the solution of $${\min}:f_0(x) + \sum_{i=1}^m \lambda_i^{\star}f_i(x) + \sum_{i=1}^p \nu_i^{\star} h_i(x)\ \ \tag{5.55}$$ is unique. Then if the solution of (5.55) is primal feasible, it must be primal optimal.

I am confused about why the solution of (5.55) is the primal optimal if it is unique and feasible.

Answer 1

This is a counterexample. Set \begin{align*} f(x) &:= x^2 \exp(-x^2) - (x-1) \exp(x)\\ g(x) &:= f_1(x) := (x-1) \exp(x). \end{align*}

For the primal problem, the feasible set is $(-\infty, 1]$ and the infimal value $0$ is not achieved (consider $x \to -\infty$).

The Lagrangian is $L(x,\lambda) := f(x) + \lambda g(x)$. For $\lambda^* = 1$, we have $$ L(x,\lambda^*) = x^2 \exp(-x^2)$$ and this function has a unique minimizer at $x_0 := 0$ with $L(x_0,\lambda^*) = 0$. Via weak duality, $\lambda^*$ is a dual solution. (Actually, it can be checked that this dual solution is also unique.) Since the primal and dual optimal values coincide, we have strong duality. Note that $x_0$ is feasible (but complementary slackness is violated).

One should also note that all functions are smooth and at the boundary point $x = 1$, $g'(x) \ne 0$, i.e., a CQ is satisfied.

What can be shown? If we add the assumption of complementary slackness, i.e., $f_i(x_0) \lambda^*_i = 0$ for all $i$, then the assertion of the book holds, but we can drop uniqueness and strong duality: Let $(\lambda^*, \mu^*)$ be dual optimal and let $x_0$ be a(!) solution of (5.55), which is primal feasible and satisfies strict complementarity. Let $p^*$, $d^*$ be the optimal objective value of the primal and dual program, respectively. We have $$ p^* \ge d^* = L(x_0, \lambda^*, \mu^*) = f(x_0).$$ Here, the identities are:

• weak duality,
• optimality of $(\lambda^*, \mu^*)$ and definition of $x_0$,
• strict complementarity.

Hence, $x_0$ is primal optimal.