# 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. – Michael Grant 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. – copper.hat Jul 25 '14 at 7:15
• Good points. I note that there is no assumption regarding the uniqueness of the dual maximizer. – Michael Grant Jul 25 '14 at 12:24
• Can I add the assumption that both the primal and dual optimal values are attained? – pterojacktyl Jul 25 '14 at 14:39