I'm confused about sufficiency of KKT conditions for optimality.
In http://www.stat.cmu.edu/~ryantibs/convexopt/scribes/kkt-scribed.pdf, page 3, Section 12.1.3 it is stated that
For any optimization problem, if $x^\star$ and $(u^\star,v^\star)$
(optimal lagrange multipliers) satisfy KKT conditions for the problem,
then satisfying those KKT conditions is sufficient to imply that
$x^\star$ and $(u^\star,v^\star)$ are the optimal solutions for the
primal and it’s dual. This statement is equivalent to saying
satisfying KKT conditions is always sufficient for optimality.
The argument is based on the fact that if $(x^\star,u^\star,v^\star)$ is a KKT point, then it must hold $g(u^\star,v^\star)=f(x^\star)$ because of primal/dual feasibility and complementary slackness. Hence, I would deduce that if there is a KKT point, then strong duality holds and the global optimum is found.
However, I thought that KKT conditions are only necessary for optimality under the assumption that strong duality holds – thus my confusion.
Could someone clarify? Also, supposing that strong duality does not hold, what can we say about KKT points? Thanks.
Best Answer
It is not well written there. KKT condition is, in general, only necessary condition. It is in a way similar to the "gradient is zero" for unconstrained case. It is no way sufficient, unless the problem is convex. I guess the text implicitly assumes convexity. Otherwise, (12.14) is not true that stationarity implies minimum. However, if the problem is convex then it is true that the KKT condition implies saddle point and, hence, strong duality.
P.S. The word "convexopt" in the link reveals that the text is likely a part of a convex optimization course. It explains "sloppiness" in not mentioning convexity.