Does KKT works for non-convex problems as well?

Question

I want to make sure that the following claim is correct. Please let me know what you think.

"Let us assume that we have a constrained non-convex and nonlinear minimization problem. The objective function and all the constraints are differentiable. First of all, I can show that LICQ holds in all the points of the space. Then, I apply the first order necessary conditions (KKT) and find all the points satisfy these conditions. My claim is that it is enough to check the value of objective function at these points (that satisfy the KKT conditions) and pick the one which lead to the least objective value. That point (or maybe points) would be the global minimum of the problem."

Edit: Let's assume that the problem has a minimun.

Is anything wrong with above claim? Does non-convexity make any problem for using KKT conditions? BTW, I use KKT conditions from this page.

Answer 1

You are correct if there exists an optimum (it is sufficient if e.g. the feasible set is compact). The first order conditions are necessary conditions, hence a global optimum must satisfy them. If you have finitely many points that satisfy the necessary conditions it is enough to check all of them.

However, for convex (and some other) problems, the conditions are also sufficient meaning that any such point satisfying the conditions much necessarily be global optimum.

Answer 2

This claim it's not true. KKT conditions are only necessary for optimality. Example: consider the problem

$min\; f(x)=x^3,$ s.t $\;x\leq 1.$ This problem satisfies LICQ at every point. Furthermore, the problem is unbounded, so no KKT point(x=0 is at least one of them) is a minimum of the function.

$\textbf{EDIT:}$ Even if the function is bounded from below, the statement it is not true. Example:

$min\; \frac{1}{x^2+1},$ s.t $x\leq 0.$

On the other hand, KKT conditions are sufficient for optimality when the objective function and the inequality constraints are convex, and the equality constraints are affine.