18
$\begingroup$

In Boyd's Convex Optimization, pp. 243,

for any optimization problem ... for which strong duality obtains, any pair of primal and dual optimal points must satisfy the KKT conditions

i.e. $\mathrm{strong ~ duality} \implies \mathrm{KKT ~ is ~ necessary ~ condition ~ for ~ optimal ~ solution}$

and in pp. 244,

(When the primal problem is convex) if $\tilde{x}, \tilde{\lambda}, \tilde{\mu}$ are any points that satisfy the KKT conditions, then $\tilde{x}$ and $(\tilde{\lambda}, \tilde{\mu})$ are primal and dual optimal, with zero duality gap.

If duality gap = 0, the problem satisfies strong duality, and in the 3rd paragraph:

If a convex optimization problem ... satisfies Slater’s condition, then the KKT conditions provide necessary and sufficient conditions for optimality

For me it means: (for any convex problems KKT is already sufficient for optimal)

$$\mathrm{KKT} \implies \mathrm{optimal ~ with ~ zero ~ duality ~ gap} \implies \mathrm{strong ~ duality} \implies \mathrm{KKT ~ is ~ also ~ necessary}$$

so KKT is necessary and sufficient for any convex problems? (Because Slater's condition can be automatically satisfied for the zero duality gap)

$\endgroup$
2
  • $\begingroup$ A very good explanation of your question can be found here. A table at the end of the explanation summarizes when the KKT conditions are necessary and sufficient. $\endgroup$
    – varunmarda
    Commented Nov 10, 2017 at 5:01
  • $\begingroup$ slater condition is not automatic in convex programing. $\endgroup$
    – Red shoes
    Commented Nov 19, 2017 at 19:14

2 Answers 2

19
$\begingroup$

The KKT conditions are not necessary for optimality even for convex problems. Consider $$ \min x $$ subject to $$ x^2\le 0. $$ The constraint is convex. The only feasible point, thus the global minimum, is given by $x=0$. The gradient of the objective is $1$ at $x=0$, while the gradient of the constraint is zero. Thus, the KKT system cannot be satisfied.

$\endgroup$
9
  • $\begingroup$ slater or any other constraint qualification does hold in your example $\endgroup$
    – Red shoes
    Commented Nov 19, 2017 at 19:17
  • $\begingroup$ @Redshoes ? simply no. please check again. the constraint says $x^2$ LESS than zero. $\endgroup$
    – daw
    Commented Nov 20, 2017 at 7:03
  • $\begingroup$ in fact, no constraint qualification holds: Please calculate the a KKT point $\endgroup$
    – daw
    Commented Nov 20, 2017 at 7:04
  • $\begingroup$ Sorry I wanted to say ,, does NOT hold.. it was a typo. That's why KKT is not satisfied in minimum point $\endgroup$
    – Red shoes
    Commented Nov 21, 2017 at 7:43
  • $\begingroup$ Isn't linear independence constraints qualification working? Gradient of x^2 is 2x is that not linear independence? $\endgroup$
    – holala
    Commented Jun 14, 2022 at 5:11
14
$\begingroup$

Boyd and Vandenberghe considers convex optimization problems of the form \begin{align} \text{minimize} &\quad f_0(x) \\ \text{subject to} & \quad f_i(x) \leq 0 \quad \text{for } i = 1,\ldots, m \\ &\quad a_i^T x = b_i \quad \text{for } i = 1,\ldots, p, \end{align} where $f_0,\ldots, f_m$ are convex functions. The optimization variable is $x \in \mathbb R^n$ and the domain of the optimization problem is $$ \mathcal D = \bigcap_{i=0}^m \textbf{dom} \,f_i. $$ (See equation (4.15), p. 136 in Boyd and Vandenberghe.)

Let $x \in \mathbb R^n$, $\lambda \in \mathbb R^m$, and $\nu \in \mathbb R^p$. Then the following two statements are equivalent:

  1. $x$ and $(\lambda,\nu)$ together satisfy the KKT conditions.
  2. $x$ and $(\lambda,\nu)$ are primal and dual optimal, and strong duality holds.

If Slater's condition is satisfied, then strong duality is guaranteed to hold, and so we can make a simpler and more useful statement. In this case, the following are equivalent:

  1. $x$ and $(\lambda,\nu)$ together satisfy the KKT conditions.
  2. $x$ and $(\lambda,\nu)$ are primal and dual optimal.

Warning: If strong duality does not hold, then it is possible for $x$ and $(\lambda,\nu)$ to be primal and dual optimal without satisfying the KKT conditions. An example where this occurs is given below.


By the way, if Slater's condition holds, then dual optimal variables $(\lambda,\nu)$ are guaranteed to exist. So if $x$ is primal optimal, then $x$ and $(\lambda,\nu)$ together satisfy the KKT conditions.


Example: [Problem 5.21 in Boyd and Vandenberghe] Consider the convex optimization problem \begin{align} \text{minimize} &\quad e^{-x} \\ \text{subject to} & \quad \frac{x^2}{y}\leq 0 \end{align} with variables $x$ and $y$ and domain $$ \mathcal D = \{ (x,y) \mid y > 0 \}. $$ The primal optimal value is $1$. The Lagrangian is $$ L(x,y,\lambda) = e^{-x} + \lambda \frac{x^2}{y}. $$ The dual function is $$ g(\lambda) = \inf_{(x,y) \in \mathcal D} L(x,y,\lambda) =\begin{cases} 0 & \quad \text{if } \lambda \geq 0, \\ -\infty & \quad \text{otherwise.} \end{cases} $$ The dual problem is \begin{align} \text{maximize} &\quad 0 \\ \text{subject to} &\quad \lambda \geq 0. \end{align} The optimization variable in the dual problem is $\lambda$. We can see that any $\lambda \geq 0$ is dual optimal.

So, any $(x,y)$ with $x = 0$ and $y > 0$ is primal optimal, and any $\lambda \geq 0$ is dual optimal. Although the primal and dual optimal values are both attained, strong duality does not hold.

$\endgroup$
12
  • $\begingroup$ What's an example of a problem where strong duality holds but Slater's conditions do not hold? $\endgroup$
    – Y. S.
    Commented Jul 27, 2018 at 2:23
  • $\begingroup$ @Y.S. I think an example is minimize $x$ subject to $x^2 \leq 0$. The Lagrangian is $L(x,z)= x+ z x^2$ and the dual function is $g(z) = -1/4z$ if $z \neq 0$ and $g(z) = -\infty$ otherwise. The dual optimal value is $0$, but the dual optimal value is not attained. Maybe you wanted an example where the dual optimal value is attained, I'll have to think about that. (Is that impossible?) $\endgroup$
    – littleO
    Commented Jul 27, 2018 at 20:24
  • $\begingroup$ Cool example! But then is slater's condition satisfied? The primal constraint has no interior. $\endgroup$
    – Y. S.
    Commented Jul 28, 2018 at 19:50
  • 2
    $\begingroup$ Btw, I realized I can simplify the above example. The primal problem could be to minimize $0$ subject to $x^2 \leq 0$. Then the Lagrangian is $L(x,z) = a x^2$ and the dual function is $g(z) = 0$ if $z \geq 0$ and $g(z) = -\infty$ otherwise. The dual optimal value is $0$, and in this case the dual optimal value is attained (for example by $z = 0$). $\endgroup$
    – littleO
    Commented Jul 28, 2018 at 21:17
  • 1
    $\begingroup$ Hi, do you have an example of the warning "If strong duality does not hold, then it is possible for 𝑥 and (𝜆,𝜈) to be primal and dual optimal without satisfying the KKT conditions"? I googled a lot but can't find one such example. $\endgroup$
    – soloice
    Commented Jun 25, 2021 at 14:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .