13
$\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$
1
  • $\begingroup$ slater condition is not automatic in convex programing. $\endgroup$
    – Red shoes
    Nov 19, 2017 at 19:14

3 Answers 3

Reset to default
15
$\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$
4
  • $\begingroup$ slater or any other constraint qualification does hold in your example $\endgroup$
    – Red shoes
    Nov 19, 2017 at 19:17
  • $\begingroup$ @Redshoes ? simply no. please check again. the constraint says $x^2$ LESS than zero. $\endgroup$
    – daw
    Nov 20, 2017 at 7:03
  • $\begingroup$ in fact, no constraint qualification holds: Please calculate the a KKT point $\endgroup$
    – daw
    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
    Nov 21, 2017 at 7:43
7
$\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$. (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.

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.

$\endgroup$
10
  • $\begingroup$ What's an example of a problem where strong duality holds but Slater's conditions do not hold? $\endgroup$
    – Y. S.
    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
    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.
    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
    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
    Jun 25, 2021 at 14:56
0
$\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$
2
  • $\begingroup$ I think the sentence from your link "The KKT conditions are necessary to find an optimum" is just wrong. $\endgroup$
    – LKS
    Mar 19, 2018 at 3:55
  • $\begingroup$ I agree that the link is a bad source (onmyphd.com/?p=kkt.karush.kuhn.tucker). "The KKT conditions are necessary to find an optimum, but not necessarily sufficient." - besides being awkwardly phrased, this is simply not true. $\endgroup$
    – paperskilltrees
    Oct 15, 2020 at 23:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.