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}$?

  • 4
    $\begingroup$ 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. $\endgroup$ Jul 25 '14 at 3:32
  • 1
    $\begingroup$ @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. $\endgroup$
    – copper.hat
    Jul 25 '14 at 7:15
  • $\begingroup$ Good points. I note that there is no assumption regarding the uniqueness of the dual maximizer. $\endgroup$ Jul 25 '14 at 12:24
  • $\begingroup$ Can I add the assumption that both the primal and dual optimal values are attained? $\endgroup$ Jul 25 '14 at 14:39

This is entirely possible, and happens all the time. In order to guarantee that the subproblem solution obtained at the dual optimum corresponds to the true primal optimum, you need the dual to be differentiable which is equivalent to the primal problem being strictly convex. In the context of linear programming, this is called the "problem of non-coordinability".

It has been a fairly active area of research actually, see for example http://link.springer.com/article/10.1007%2Fs10107-014-0772-2#/page-1 for a decent exposition.


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^*$


Your Answer

