14
$\begingroup$

I was studying Stephen Boyd's text book and got confused in the KKT part. The book says the following:

"For any convex optimization problem with differentiable objective and constraint function, any points that satisfy the KKT conditions are primal and dual optimal and have zero duality gap. "

So, it sounded like if I find any point (x,$\lambda$, $\nu$) satisfying the KKT condition, x will be a primal optimum. Then, later it says the following:

"If a convex optimization problem with differentiable objective and constraint functions satisfies Slater's condition, then the KKT conditions provide necessary and sufficient conditions for optimality: Slater's condition implies that the optimal duality gap is zero and the dual optimum is attained, so x is optimal if and only if there are ($\lambda$,$\nu$) that, together with x, satisfy the KKT condition."

The inclusion of the Slater's condition in the second statement makes me confused. The first sentence sounds like any (x, $\lambda$, $\nu$) satisfying the KKT conditions (even though the Slater's condition does not hold) is a primal optimal. Then, the second sentence says that KKT becomes the necessary and sufficient condition when the Slater's condition holds.

Can somebody clarify this? To find a primal optimal, is it ok to find just (x, $\lambda$, $\nu$) satisfying the KKT condition? Or, should I also show the Slater's condition?

$\endgroup$
12
$\begingroup$

I believe this is what he is saying (though I could be wrong):

(1) optimality + strong duality $\implies$ KKT (for all problems)

(2) KKT $\implies$ optimality + strong duality (for convex/differentiable problems)

(3) Slater's condition + convex$\implies$ strong duality, so then we have, GIVEN that strong duality holds,

(3a) KKT $\Leftrightarrow$ optimality

If, for a primal convex/differentiable problem, you find points satisfying KKT, then yes, by (2), they are optimal with strong duality.

$\endgroup$
  • 1
    $\begingroup$ To add some more clarity, (1) in the answer is not saying KKT is a necessary condition for optimality. Instead, KKT is a necessary condition when optimality and strong duality holds. Look at daw's answer in math.stackexchange.com/questions/2513300/…. $\endgroup$ – LKS Mar 19 '18 at 3:22
  • $\begingroup$ Then if the problem is convex + differentiable, KKT is a sufficient condition for optimality + strong duality (even if Slater's condition does not hold). This result is useful when there exists an instance of variables that satisfies KKT. $\endgroup$ – LKS Mar 19 '18 at 3:28
  • $\begingroup$ Also from littleO answer from the link, "By the way, if Slater's condition holds, then dual optimal variables (λ,ν) are guaranteed to exist" $\endgroup$ – LKS Mar 19 '18 at 3:42
4
$\begingroup$

Ross B.'s answer confuses me. Zheng Jia's answer is correct but not clear. Let me elaborate a little bit.

The general statement does not require differentiability, as convexity already implies the existence of subgradient. The general KKT condition can be stated in terms of subgradient. For any convex program, $(x,y)$ is a pair of primal and dual optimal solution iff it is a saddle point of the Lagrangian iff it satisfies the KKT conditions. I believe this is usually called the Saddle-point Theorem. However, a convex program may not have a dual optimal solution. But, if the convex program satisfies the Slater's condition, then a dual optimal solution exists. This is the story behind Stephen Boyd's comment.

The proof is surprisingly simple. See section 28 Convex Analysis by Rockafellar.

Best,

Xiang

$\endgroup$
  • $\begingroup$ It seems that if all the functions are considered in $C^1$, for a convex optimization problem the KKT condition is sufficient for the optimality. (See page 244 in Boyd's convex optimization book) Roughly speaking, the convexity of the Lagrangian (w.r.t. to the variables in primal problem) guarantees the zero duality gap so that everything works. $\endgroup$ – Ryan Apr 4 '16 at 6:05
  • 1
    $\begingroup$ You are absolutely correct. But, the point is, a convex program may not admit a solution to the KKT conditions. On the other hand, if the Slater's condition is satisfied, a solution to the KKT conditions must exist. I think speaking in this way might be clearer than merely speaking about necessary and sufficient conditions. $\endgroup$ – Xiang Li Oct 11 '16 at 22:23
  • 2
    $\begingroup$ It is not true that for any convex program, $(x,y)$ is a pair of primal and dual optimal solutions if and only if $x$ and $y$ together satisfy the KKT conditions. There are pathological examples of convex problems for which primal and dual optimal variables exists but strong duality does not hold. $\endgroup$ – littleO Nov 10 '17 at 8:43
2
$\begingroup$

No slater's condition, KKT is a sufficient condition. With slater's condition, KKT is a necessary and sufficient condition. Reference: page 537 in book: Lectures on Modern Convex Optimization. This is a very good reference book.

$\endgroup$
2
$\begingroup$

As a general introduction:

KKT conditions DO NOT HAVE TO BE SATISFIED at the optimal solution in general. If some conditions called regularity conditions (which depend on the specific point. In other words, for some point we may have KKT for some we my not) are satisfied, then the KKT conditions must hold at that potential optimizer. Slater's condition is one of the regularities conditions so it guarantees that the KKT conditions must hold.

Back to your question:

"For any convex optimization problem with differentiable objective and constraint function, any points that satisfy the KKT conditions are primal and dual optimal and have zero duality gap."

The above means that if one finds a point that satisfies KKT, then they can be certain that it is one of the optimizers. Notice that KKT is not necessary in general, but if one finds a point satisfying KKT, due to convexity, it is one of the optimizers. So, even none of the regularity conditions needs to be held in this case.

"If a convex optimization problem with differentiable objective and constraint functions satisfies Slater's condition, then the KKT conditions provide necessary and sufficient conditions for optimality: Slater's condition implies that the optimal duality gap is zero and the dual optimum is attained, so x is optimal if and only if there are (λλ,νν) that, together with x, satisfy the KKT condition." This simply means that for a convex problem Slater's conditions not only guarantees KKT conditions must hold but also make them to be sufficient.

Long story short, any point which satisfies KKT conditions is an optimizer when dealing with a convex problem no matter Slater's holds or not but if it holds, an optimizer must hold the KKT conditions.

$\endgroup$

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.