$\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

3 Answers

$\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$ 6 $\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$

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$ 3

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

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