Question about KKT conditions and strong duality

Question

I am confused about the KKT conditions. I have seen similar questions asked here, but I think none of the questions/answers cleared up my confusion.

In Boyd and Vandenberghe's Convex Optimization [Sec 5.5.3] , KKT is explained in the following way.

I-For any differentiable (potentially non-convex) problem: If strong duality holds, then any primal/dual (global) optimal pair must satisfy the KKT conditions (i.e., gradient of Lagrangian must vanish, points must be primal/dual feasible, and they must satisfy complementary slackness).

II-For convex problems: If the problem is convex, then (a) any (primal/dual) points that satisfy the KTT conditions (same as above) are (global) primal/dual optimal pairs and (b) strong duality holds.

Using I and II, Boyd and Vandenberghe conclude that for convex problems that satisfy the Slater's condition (hence strong duality holds), KKT conditions are both necessary and sufficient for (global) primal/dual optimality.

Now in traditional Nonlinear Programming textbooks, the same KKT conditions are presented as first-order necessary condition for local optimality for any (differentiable, but potentially non-convex) problem. In those references, there is no discussion of dual points (instead, we treat them as Lagrange multipliers) or strong duality: (III) for any regular locally optimal (primal) point, there must exist Lagrange multipliers such that jointly they satisfy the KKT conditions (same as above).

I have three related questions:

(Q1) does III imply that the strong duality requirement in I was unnecessary? (edit: I realized that III is a necessary condition for regular local optima - but still, it would be great to hear about the relation between I and III)

(Q2) What can be said in general about the KKT conditions in differentiable nonlinear programs that do not satisfy strong duality?

(Q3) Consider a general nonlinear program (primal) with differentiable cost and constraints where strong duality does not hold. Now imagine I have found all KKT pairs for the primal. The Lagrange multipliers in my KKT pairs are clearly feasible for the dual problem. But is it also guaranteed that every regular local optima of the dual problem appears in my KKT pairs of the primal?

My guess: I guess the answer to Q1 is negative - if strong duality does not hold, regular primal (global/local) optimal points must still satisfy the KKT conditions with some Lagrange multipliers that may not have anything to do with (optimal) dual points (?).

Answer 1

I think that your guess in (Q1) is correct.

Consider the following optimization problem: \begin{align} &\min_{x\in \mathbb{R}^n}\ f_0(x)\\ &\mathrm{s.t.}\ \ f_i(x) \le 0, \ i=1,2, \cdots,m\\ &\qquad h_j(x) = 0, \ j=1,2,\cdots, p \end{align} where $f_0$, $f_i, \forall i$ and $h_j, \forall j$ are all differentiable. The KKT conditions are the following \begin{align} \nabla f_0(x^\ast) + \sum_{i=1}^m \lambda_i^\ast \nabla f_i(x^\ast) + \sum_{j=1}^p \mu_j^\ast \nabla h_j(x^\ast) &= 0, \\ f_i(x^\ast) &\le 0, \ i = 1, 2, \cdots, m\\ h_j(x^\ast) &= 0, \ j=1, 2, \cdots, p\\ \lambda_i^\ast &\ge 0, \ i=1, 2, \cdots, m\\ \lambda_i^\ast f_i(x^\ast) &= 0, \ i = 1, 2, \cdots, m. \end{align}

See: [1], and [2], page 356, Ch. 9.

The Lagrangian is given by $$L(x, \lambda, \mu) = f_0(x) + \sum_{i=1}^m \lambda_i f_i(x) + \sum_{j=1}^p \mu_i h_i(x)$$ with $\lambda \in \mathbb{R}^m$ and $\mu \in \mathbb{R}^p$.

The Lagrange dual function is given by $$g(\lambda, \mu) = \inf_{x} L(x, \lambda, \mu).$$

Let $x^\ast$ and $(\lambda^\ast, \mu^\ast)$ be primal and dual optimal, respectively.

It holds that $g(\lambda, \mu) \le f(x^\ast)$ for all dual feasible $(\lambda, \mu)$, i.e. $\lambda \ge 0$ and $(\lambda, \mu) \in \mathrm{dom}\, g$. This property is called weak duality.

If $f(x^\ast) = g(\lambda^\ast, \mu^\ast)$, the strong duality holds (zero duality gap).

We have:

1. If $x^\ast$ is locally optimal and $x^\ast$ is regular (regularity conditions, or constraint qualifications), then there exists $(\lambda^\ast, \mu^\ast)$ such that the KKT conditions hold.

2. If strong duality holds, the KKT conditions are necessary optimality conditions: if $x^\ast$ and $(\lambda^\ast, \mu^\ast)$ are primal and dual optimal, then the KKT conditions hold.

3. For convex problems with strong duality (e.g., when Slater's condition is satisfied), the KKT conditions are sufficient and necessary optimality conditions, i.e., $x^\ast$ and $(\lambda^\ast, \mu^\ast)$ are primal and dual optimal if and only if the KKT conditions hold.

Reference

[1] https://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions

[2] Chong-Yung Chi, Wei-Chiang Li, Chia-Hsiang Lin, "Convex Optimization for Signal Processing and Communications: From Fundamentals to Applications", 2017.

Answer 2

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.