KKT and Slater's condition
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$4 Answers
$\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$ 3 $\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$ 3 $\begingroup$Suppose we have $C^1$ functions involved in the optimization problem:
In general, the KKT conditions DO NOT HAVE TO BE SATISFIED at an optimal solution. Nonetheless, Fritz John's conditions must always be satisfied. In fact, Fritz John's condition is a generalization of the KKT conditions. Fritz John's conditions reduce to the KKT conditions if some regularity conditions are satisfied at that point. Slater's condition is a regularity condition that guarantees reducing Fritz John's conditions to the KKT conditions, that is, the KKT conditions must hold if Slater's condition is satisfied.
Notice that KKT is not necessary even if we have a convex problem. But, if one finds a point that satisfies the KKT conditions of a convex problem, then it is one of the optimizers even if none of the regularity conditions is held. In other words, we have:
(1) Fritz John's MUST hold at a stationary point.
(2) A regularity condition (like Slater) $\implies$ KKT conditions.
(3) KKT + convexity $\implies$ optimality (with zero duality gap).
Consequently:
(4) A regularity condition (like Slater) + convexity $\implies$ optimality (with zero duality gap).
$\endgroup$ 1 $\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$
