2
$\begingroup$

I am trying to solve an inequality-constrained minimization problem. My objective and constraints are infinitely differentiable but not necessarily convex.

I found exactly 1 point $\mathbf{x}^{*}$ that satisfies the KKT necessary conditions. To make sure this point is a minimizer, is it sufficient to show that $\nabla^2\mathcal{L}(\mathbf{x}^{*}, \mathbf{\lambda})$ is PSD, or do I need something stronger?

I tried doing some reading about this online but a lot of sources I see focus on the case where the objective and constraints are convex. The ones that don't go over my head with discussion about tangent cones and different types of constraint qualification, terms that I haven't encountered before.

$\endgroup$
14
  • 1
    $\begingroup$ It is more involved than that. However, if you know that there is a minimiser (not always easy to establish) and the active gradients are linearly independent, then $x^*$ must be the minimiser. $\endgroup$
    – copper.hat
    Jan 26, 2022 at 22:13
  • 1
    $\begingroup$ Well, if you know that exactly one point satisfies the KKT necessary conditions and you know a minimiser exists then that must be that point. $\endgroup$
    – copper.hat
    Jan 26, 2022 at 22:36
  • 1
    $\begingroup$ Maybe web.stanford.edu/class/msande311/lecture07.pdf $\endgroup$
    – copper.hat
    Jan 26, 2022 at 22:37
  • 1
    $\begingroup$ The geometric idea is straightforward, but the mathematical expression awkward. $\endgroup$
    – copper.hat
    Jan 26, 2022 at 22:38
  • 1
    $\begingroup$ It is a bit too involved for a comment, and I am fairly sure Yinyu addresses the issue. I would expect that $L_{xx}$ needs to be strictly positive definite on a certain space for sufficiency to hold, not just PSD. $\endgroup$
    – copper.hat
    Jan 26, 2022 at 23:07

1 Answer 1

Reset to default
1
$\begingroup$

Yes, something stronger is needed. The difficulty with your question is that it's possible that global minimizers do not satisfy KKT, and yet there exists one point satisfying the KKT conditions. For example, the problem \begin{align} \text{min } & -x^2+x^3 \\ \text{s.t. } & x^3(x+1)^3\leq 0 \end{align} has only one global minimizer and only one KKT point, the origin, which is not the global minimizer. This is because minimizers require a constraint qualification to satisfy the KKT conditions. In order for your assertion to be true, you require that all points, and not only one, of the feasible set also satisfy a constraint qualification, like MFCQ. In such context, the result is true because if your problem admits a minimum since every point satisfies MFCQ, this global minimum must satisfy KKT. The global minimizer satisfies KKT, and If your problem has only one KKT point, that KKT point must be the global minimizer. Now you could ask me:

It's really required that all points satisfy a constraint qualification?

Yes, it's needed. That's because even if only one point does not satisfy a constraint qualification, the global minimizer might be that point, and such a point might not be a KKT one. Now, you could turn back to me again and ask me:

What about PSD? Does it help?

No, it does not help at all. The PSD says that your point is a local minimizer, and being a local minimizer does not imply that it is the global minimizer, since you don't know whether your problem has only one local minimizer.

You could ask:

Is there a solution?

Yes, you need to test whether your point is the only one satisfying a genuine optimality condition, i.e., a condition that holds for every local minimizer of your problem. In such a case, I would test if there exists another point such that $$\text{it does not satisfy MFCQ at x or the KKT conditions holds at that point x}$$ or, roughly and in symbols, $$x \text{ is KKT or MFCQ does not hold at } x.$$ This last condition holds for every optimal point and being that point unique, this point must be a global minimizer, whenever it exists.

Now you could ask me:

What are constraint qualifications?

That type of question is exactly what I have done here. I am not aware of a precise definition of constraint qualification. I, and as far I know only myself, would assume that a constraint qualification is any mathematical assertion/proposition that implies Guignard constraint qualification. Quite artificial, but extremely precise, since I would bet that there will never be one constraint qualification that does not imply Guignard constraint qualification, due to Gould and Tolle result.

$\endgroup$
2
  • 1
    $\begingroup$ Thanks! Your post clears up a lot of confusion that I had on the matter. Does this mean that the global solution may not necessarily satisfy KKT conditions? And can I interpret KKT as a method of finding local minima among points that satisfy the constraint qualification (CQ)? KKT misses points that do not satisfy the CQ, so I need to handle those points separately. $\endgroup$
    – bandicoot12
    Jan 27, 2022 at 19:13
  • 1
    $\begingroup$ Yes, you can think of KKT as a way of finding a solution that satisfies a constraint qualification, but note that there are problems that do not meet MFCQ in any feasible point, but, yes, you got the point! To optimize the problem, you need to deal with nonqualified points separately. $\endgroup$
    – R. W. Prado
    Feb 7 at 9:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .