# Strong duality: When does the optimal primal variable coincide with the primal variable giving the dual function.

I'm considering the inequality-constrained optimization problem of finding $$x^{\star} = \arg \min_{x} f(x) \;\; \text{s.t.} \;\; h(x) \le 0$$ which is assumed to have a unique minimizer. The objective $f$ maps $R^{n} \rightarrow R$ and $h$ maps $R^{n} \rightarrow R^m$ capturing multiple constraints. This problem has Lagrangian $L(x, \lambda) = f(x) + \lambda^{T} h(x)$ and the associated dual problem is to find some $$\lambda^{\star} \in \arg \max_{\lambda} g(\lambda) \;\; \text{s.t.} \;\; \lambda\ge 0$$ where the dual function is defined $g(\lambda) = \min_{x} L(x, \lambda)$.

Assuming that strong duality holds, the optimal value of the primal problem $p^{\star} = f(x^{\star})$ and that of the dual problem $d^{\star} = g(\lambda^{\star})$ are equal.

QUESTION: If we define $\hat{x}(\lambda) \in \arg \min_{x} L(x, \lambda)$ to be a value of the primal variable $x$ which yields the dual function $g(\lambda) = L(\hat{x}(\lambda), \lambda)$, then do there exist functions $(f, h)$ for which this is not necessarily equal to the solution, i.e. $\hat{x}(\lambda^{\star}) \ne x^{\star}$?

• Strong duality does not guarantee that the optimal values are attained. That is: it's entirely possible that $$\inf_{x:~h(x)\leq0} f(x) = \sup_{\lambda\geq 0}\inf_x L(x,\lambda)$$but there is no $x^*$ and/or $\lambda^*$ that achieves these optima. Strict primal feasibility implies dual attainment, and vice versa. Jul 25 '14 at 3:32
• @MichaelGrant: The OP assumed that $f$ has a unique minimiser, so the primal optimal is attained. Presumably by the $\min$ in the definition of $g$ this means that the dual optimal value is also attained. So there is a saddle point, we have $g(\lambda^*) = L(x^*, \lambda^*) = f(x^*)$. However, while I suspect that it is possible that $\hat{x}(\lambda^*) \neq x^*$, it is at best a hunch. Jul 25 '14 at 7:15
• Good points. I note that there is no assumption regarding the uniqueness of the dual maximizer. Jul 25 '14 at 12:24
• Can I add the assumption that both the primal and dual optimal values are attained? Jul 25 '14 at 14:39

It is possible that $$\hat{x}(\lambda^∗)\ne x^∗$$
Consider the optimization problem on $$\mathbb R$$ \begin{align} \operatorname{minimize} & \quad x^3 \\ \text{subject to} & -x^3-1\le 0. \end{align} The objective function is not convex by calculating the Hessian matrix. Clearly, $$x^*=-1$$ is the unique primal optimal solution with primal optimal value $$-1$$.
The Lagrangian is $$L(x,\lambda) = x^3 - \lambda (x^3+1).$$ Values of the primal variable $$x$$ which yields the dual function is easy to obtain $$\begin{cases} \hat{x}(\lambda)=\mathbb R& \lambda=1\\ \hat{x}(\lambda)=\emptyset& \lambda\ne 1 \end{cases}$$
Yield the dual function \begin{align} G(\lambda) &= \inf L(x,\lambda) = \begin{cases} -1& \lambda=1\\ -\infty& otherwise \end{cases} \end{align} Thus, $$\lambda = 1$$ is dual optimal solution with dual optimal value $$-1$$, so dual gap is $$0$$, strong duality holds. However, $$\hat{x}(\lambda^⋆)\ne x^*$$