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?
Best Answer
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.