Karush Kuhn Tucker and Optimal Minimum

Question

I am a little not clear on the solutions of KKT Conditions. Suppose we have a convex function $f(x)$ and at a specific $x$ are our KKT conditions fulfilled. Does this make this point a global minimum of our function, or just a local minimum that happens to be our optimum under the linear condition say for example $x\in [1,10]$.

Answer 1

When the program is convex, any point that satisfies all the conditions is a global minimum. Specifically, suppose we are minimizing $f(\mathbf x)$ subject to constraints $g_1(\mathbf x) \le 0, \dots, g_m(\mathbf x) \le 0$, where $f, g_1, \dots, g_m$ are convex. Suppose $\mathbf x^*$ and $\boldsymbol \lambda^*$ satisfy:

1. $\nabla f(\mathbf x^*) + \sum_{i=1}^m \lambda_i^* \nabla g_i(\mathbf x^*) = \mathbf 0$ (the gradient equation).
2. $\mathbf x^*$ actually satisfies the constraints, and $\boldsymbol{\lambda}^* \ge \mathbf 0$.
3. Complementary slackness holds: for each $i$, either $\lambda_i^* = 0$ or $g_i(\mathbf x^*) = 0$.

Then $\mathbf x^*$ is a global minimum.

You may have heard of other things to check, such as for example Slater's condition (that there is a point $\mathbf x$ at which $g_i(\mathbf x) < 0$ for all $i$). Slater's condition (together with convexity) actually guarantees the converse: that any global minimum will be found by trying to solve the equations above.

Without Slater's condition, it's possible that there's a global minimum somewhere, but no solution to the equations. So if you don't find a solution to the equations, that's when you would want to know if Slater's condition holds: if it does, that lets you conclude that there's no global minimum at all.

---

A comment on the non-convex case: in general, we can conclude that $\mathbf x^*$ is a global minimum if there is a $\boldsymbol \lambda^* \ge \mathbf 0$ such that $$L(\mathbf x, \boldsymbol \lambda) = f(\mathbf x) + \sum_{i=1}^m \lambda_i g_i(\mathbf x)$$ satisfies

1. $L(\mathbf x^*, \boldsymbol \lambda^*) \le L(\mathbf x, \boldsymbol \lambda^*)$ for all $\mathbf x$
2. $L(\mathbf x^*, \boldsymbol \lambda^*) \le L(\mathbf x^*, \boldsymbol \lambda)$ for all $\boldsymbol \lambda \ge \mathbf 0$

and if complementary slackness holds between $\mathbf x^*$ and $\boldsymbol \lambda^*$. This does not require convexity. (Essentially, this saddle-point form of the KKT theorem lets us turn a minimization problem with constraints to one without constraints.) Convexity is used to conclude the inequalities 1 and 2 from the gradient equation $\nabla L(\mathbf x^*, \boldsymbol \lambda^*) = \mathbf 0$.

If the problem satisfies some other regularity conditions, but is not convex, typically we guarantee that by solving the gradient equation, we will find the global minimum, as well as possibly some local minima. But without some regularity conditions, even convexity isn't enough to guarantee that we will find the global minimum by solving the gradient equation.