# Sufficient conditions for non-convex constrained optimization (KKT)

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.

• 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. Jan 26, 2022 at 22:13
• 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. Jan 26, 2022 at 22:36
• Jan 26, 2022 at 22:37
• The geometric idea is straightforward, but the mathematical expression awkward. Jan 26, 2022 at 22:38
• 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. Jan 26, 2022 at 23:07

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.

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.