KKT and Slater's condition

Solution 1:

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.

Solution 2:

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

Solution 3:

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).

Solution 4:

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.