2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ so Does KKT works for non-convex problems as well? $\endgroup$ – Shine Sun Dec 5 '18 at 7:08
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I know that my objective function is not unbounded. So I guess that case would not happen. Am I right? $\endgroup$ – Shahram Shahsavari Aug 10 '17 at 19:29
  • $\begingroup$ No, even then it may happen that the minimum is not attainable. It would be sufficient that the feasible set is compact. $\endgroup$ – John D Aug 10 '17 at 19:31
  • $\begingroup$ If there is a minimum, should not it satisfy the KKT conditions? $\endgroup$ – Shahram Shahsavari Aug 10 '17 at 19:33
  • $\begingroup$ check the edit. In that case, the function is not unbounded but there is no minimum $\endgroup$ – John D Aug 10 '17 at 19:35
  • $\begingroup$ In that case there is even no KKT point, but you get the idea $\endgroup$ – John D Aug 10 '17 at 19:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.