Sufficient conditions for non-convex constrained optimization (KKT)

karush kuhn tuckernonlinear optimizationoptimization

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.

Best Answer

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.