Lagrange function and strong duality in an optimization problem

convex optimizationduality-theoremsnon-convex-optimizationoptimization

Suppose we have an (not necessarily convex) optimization problem :
$$\begin{split}\min_x f_0(x)\\ f_1(x)\leq 0. \end{split}$$
Let $L(x,\lambda)=f_0(x)+\lambda(f_1(x))$. Then the above problem
can be equivalently written as: $$\min_x \max_{\lambda\geq 0} L(x,\lambda).$$
The dual of the above problem can be written as: $$\max_{\lambda \geq 0} \min_{x} L(x,\lambda).$$
We say that strong duality holds at a point when $$\min_x \max_{\lambda\geq 0} L(x,\lambda)=\max_{\lambda \geq 0} \min_{x} L(x,\lambda).$$
By weak duality, the inequality $$\min_x \max_{\lambda\geq 0} L(x,\lambda)\geq\max_{\lambda \geq 0} \min_{x} L(x,\lambda)$$ always holds true. My doubt is: suppose there exists an $x^*$ that minimizes $L(x,\lambda)$ for a fixed $\lambda$, can i say that the following inequality holds true:
$$\max_{\lambda \geq 0} \big(\min_{x} L(x,\lambda)\big)=\max_{\lambda \geq 0}L(x^*,\lambda) \geq \min_x \max_{\lambda\geq 0} L(x,\lambda).$$
If the above is true, then are we saying that if there is a primal variable that attains its minimum in the dual problem, then strong duality holds true? Somewhere this does not seem to add up.

Best Answer

No, because the last inequality, $\max_{\lambda \geq 0}L(x^*,\lambda) \geq \min_x \max_{\lambda\geq 0} L(x,\lambda)$, does not hold in general. Note that $x^*$ is a function of $\lambda$. It would have been clearer to write $x^*(\lambda)$ instead of just $x^*$.

Related Solutions

[Math] When do constraint qualifications imply strong duality

This is not a full answer, but it is relevant information. P. 30 of Convex Analysis and Nonlinear Optimization by Borwein and Lewis states:

...we need to impose a regularity condition or "constraint qualification", an approach which is another recurring theme. The easiest such condition in this context is simply the linear independence of the gradients of the active constraints $\{ \nabla g_i(\bar x) \mid i \in I(\bar x) \}$. The culminating result of this section uses the following weaker condition.

Assumption 2.3.7 (The Mangasarian-Fromovitz constraint qualification) There is a direction $d$ in $E$ satisfying $\langle \nabla g_i(\bar x), d \rangle < 0$ for all indices $i$ in the active set $I(\bar x)$.

Later, on p. 45, the book states that if the functions $f$ and $g_1,\ldots,g_m$ are differentiable at $\bar x$ then:

in this case it is easy to see that the Slater condition is equivalent to the Mangasarian-Fromovitz constraint qualification (Assumption 2.3.7).

[Math] Question about KKT conditions and strong duality

If strong duality does not hold, then we have no reason to believe there must exist Lagrange multipliers such that jointly they satisfy the KKT conditions. Here is an counter-example

${\bf counter-example 1}$ If one drops the convexity condition on objective function, then strong duality could fails even with relative interior condition.

The counter-example is the same as the following one.

${\bf counter-example 2}$ For non-convex problem where strong duality does not hold, primal-dual optimal pairs may not satisfy KKT condition.

Consider the optimization problem \begin{align} \operatorname{minimize} & \quad e^{-x_1x_2} \\ \text{subject to} & \quad x_1\le 0. \end{align} The domain for the problem is $D = \{ (x_1,x_2) \ge 0 \}$. The problem is not convex by calculating the Hessian matrix. Clearly, any $x_1 = 0, x_2 \in\mathbb R_+$ is a primal optimal solution with primal optimal value $1$ .

The Lagrangian is $$ L(x_1,x_2,\lambda) = e^{-x_1x_2} + \lambda x_1. $$ The dual function is \begin{align} G(\lambda) &= \inf L(x_1,x_2,\lambda) = \begin{cases} 0& \lambda\ge 0\\ -\infty& \lambda < 0 \end{cases} \end{align}

Thus, $\lambda \geq 0$ is dual optimal solution with dual optimal value $0$, so dual gap is $1$, strong duality fails. As for the KKT conditions, remember the domain is $D = \{ (x_1,x_2) \ge 0 \}$

\begin{align*} &\lambda-x_2e^{-x_1x_2}=0\\ &x_1\le 0\\ &\lambda\ge 0\\ &\lambda x_1=0\\ \end{align*}

Pick any primal-dual pair satisfying $x_1 = 0, x_2\ge 0, \lambda\ge0, \lambda\ne x_2$, the KKT conditions fail.

${\bf counter-example 3}$ For a non-convex problem, even strong duality holds, solutions for KKT conditions may not be primal-dual optimal solution.

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). $$

The dual function is \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. While the KKT conditions are

\begin{align*} &3x^2(1-\lambda)=0\\ &-x^3-1\le 0\\ &\lambda\ge 0\\ &\lambda (-x^3-1)=0\\ \end{align*}

Solutions for KKT conditions are $x=-1, \lambda=1$ or $x=0,\lambda=0$. Notice that $x=0,\lambda=0$ satisfies KKT conditions but has nothing to do with primal-dual optimal solutions.

The discussion indicates for non-convex problem, KKT conditions may be neither necessary nor sufficient conditions for primal-dual optimal solutions.

${\bf counter-example4}$ For a convex problem, even strong duality holds, there could be no solution for the KKT condition, thus no solution for Lagrangian multipliers.

Consider the optimization problem on domain $\mathbb R$ \begin{align} \operatorname{minimize} & \quad x \\ \text{subject to} & \quad x^2\le 0. \end{align}

Obviously, the problem is convex with unique primal optimal solution $x=0$ and optimal value $0$; Feasible set is $\{0\}$, therefore Slater's condition fails.

The Lagrangian is $$ L(x,\lambda) = x + \lambda x^2. $$

The dual function is \begin{align} G(\lambda) &= \inf L(x,\lambda) = \begin{cases} -\infty& \lambda\le 0\\ -\frac{1}{4\lambda} &\lambda >0 \end{cases} \end{align}

Thus, dual optimal value is $0$, so dual gap is $0$, strong duality holds. However, there are no solution for dual optimal solution because the optimal value is attained as $\lambda\rightarrow \infty$. As for the KKT conditions

\begin{align*} &1+2\lambda x=0\\ &x^2\le 0\\ &\lambda\ge 0\\ &\lambda x^2=0\\ \end{align*} No solution for KKT conditions.

This is the convex problem where the dual problem has no feasible solution and KKT conditions have no solution but the primal problem is simple to solve.

${\bf counter-example 5}$ For a differentiable convex problem, there could be no solution for the KKT conditions, even if the primal-dual pair exists. In that case, the strong duality fails.

Consider the optimization problem on domain $D:=\{(x,y):y>0\}$ \begin{align} \operatorname{minimize} & \quad e^{-x} \\ \text{subject to} & \quad \frac{x^2}{y}\le 0. \end{align}

The problem can be proved to be convex with primal optimal solution $x=0, y>0$ and optimal value $1$; Feasible set is $\{(0,y): y > 0\}$, therefore Slater's condition fails.

The Lagrangian is $$ L(x,y,\lambda) = e^{-x} + \lambda \frac{x^2}{y}. $$

After some careful calculation, the dual function is \begin{align} G(\lambda) &= \inf L(x,y,\lambda) = \begin{cases} 0& \lambda\ge 0\\ -\infty &\lambda <0 \end{cases} \end{align}

Thus, dual optimal value is $0$, so dual gap is $1$, strong duality fails. We can pick primal-dual pair to be $x=0, y=1, \lambda=2$. As for the KKT conditions

\begin{align*} &-e^{-x}+\frac{2\lambda x}{y}=0\\ &\frac{x^2}{y}\le0\\ &\lambda\ge 0\\ &\lambda \frac{x^2}{y}=0\\ \end{align*} with $y>0$, thus no solution for KKT conditions.

This counter-example warns us that we have to be careful about the strong duality condition even for differentiable convex problems.

Best Answer

Related Solutions

[Math] When do constraint qualifications imply strong duality

[Math] Question about KKT conditions and strong duality

Related Question