1
$\begingroup$
  1. Is the set of KKT conditions necessary for local min, only under some regularity conditions (ie constraint qualifications)?
  2. So does this mean that when the cost functions and the functions in constraints are continuously differentiable at a point, it is possible that the point is a local min but is not regular?
  3. I am more interested in how to apply KKT to find candidates of local mins and even global mins.

    • If we use KKT conditions to find candidates of local mins, does it mean that we make a mistake of not checking if those non-regular points are local mins?
    • When trying to compute candidates for local mins by solving the KKT conditions, is it necessary to check if the computed points are regular? How to deal with those that you got but turn out to be non-regular? Shall we discard them? Does this also mean that we are making the same mistake of not checking non-regular points?

Thanks and regards!

  • 0
    @Akhil: Done as you suggested.2011-03-19

1 Answers 1

6
  1. Yes absolutely and it's worth making noise about it because it's typically overlooked. Consider for instance the problem $\min_x \ x$ subject to $x^2 = 0$. The KKT conditions have no solution. The problem, however, does: $x^*=0$ (it's the only feasible point!) Here is another example: minimize your favorite objective function subject to $x \geq 0$, $y \geq 0$ and $xy=0$. It's easy to see that those constraints never satisfy the LICQ or MFCQ (the two most widely used constraint qualification conditions (CQ) in the nonconvex world). Under these last constraints, you may find that there exist no Lagrange multipliers at all, or an unbounded set of them (they typically lie on half lines for this problem). This is due to a theorem of Gauvin from 1977: the MFCQ is satisfied at a solution if and only if the set of associated Lagrange multipliers is compact.
  2. Yes, see examples in 1. They're smooth.
  3. (a): yes, the KKT conditions will by construction "miss" solutions that aren't regular. If you want to find those, you must use other means. Note that there are methods tailored to specific constraint structures, which are able to identify local solutions where the KKT conditions fail to apply. This is more of a case-by-case game. (b): yes again. Those that you get and that aren't regular shouldn't be discarded, but a first thing to do is check their objective value. They may yield a better value than any KKT point. As a last resort, the very definition of local minimizer doesn't depend on a constraint qualification; you need to identify a feasible neighborhood of the point in which it has the lowest objective value.

Here's another example:

$ \min_{x_1,x_2} \ (x_1 - 2)^2 + x_2^2 \quad \text{s.t.} \ (1-x_1)^3 \geq x_2, \ (x_1,x_2) \geq 0. $ The solution is $(1,0)$ but the MFCQ isn't satisfied there. Such points can be very hard to detect. You can find points that don't satisfy MFCQ by trying to satisfy the Fritz-John conditions and imposing that the multiplier of the objective function be equal to zero. If you can satisfy them somewhere and there is at least one nonzero multiplier, you've found a point violating MFCQ. You should then check its objective value to see if it's even worth considering.

Unfortunately, I don't know of a general method here. The structure of the constraints dictates the method. For instance, look in the literature for problems with complementarity constraints or problems with vanishing constraints.

  • 0
    Dominique: Thanks for answering several of my optimization questions! I have upvoted every one of them. I will get back to them later when I have more time to understand your replies.2011-10-31