Considering interior points in solving Karush-Kuhn-Tucker (KKT) conditions

168 Views Asked by At

I'm reading a material on optimization, specifically KKT conditions. The material says to check for optima in boundary points only and not in interior points. But if we don't check interior points, won't we miss many local optima that are interior points? A detailed setup is given below.

Description Consider a non-linear constrained optimization problem with inequality conditions $g_i(\mathbf{x})$ $i = 1,2,...,m$.

I will define some notations from the material I am referencing in regards to this problem.

Let $\mathbf{x}^*$ be a point satisfying the conditions. Define $J$ as the set of indices $j$ for which $g_j(\mathbf{x}^*) = 0$. Also, we define three sets,

$S:$ set of points satisfying $g_i(\mathbf{x}^*) \leq 0$ for all $i = 1,2,...,m$

$S_{E}:$ set of points satisfying $g_i(\mathbf{x}^*) \leq 0$ for all $i = 1,2,...,m$ and $g_{j}(\mathbf{x}^*)=0$ for all $j$ in $J$

$S_{N}:$ set of points satisfying $g_i(\mathbf{x}^*) \leq 0$ for all $i = 1,2,...,m$ and $g_{j}(\mathbf{x}^*)<0$ for at least one $j \in J$

From these definitions, $S=S_{E} \cup S_{N}$ and $S_E \cap S_{N} = \emptyset$

One result in the material: If $\mathbf{x}^{*}$ is a local minimum of $f(\mathbf{x})$ within $S,$ it should be also a local minimum within $S_{E}$.

From the above result, it is sufficient if we check the Karush-Kuhn-Tucker conditions only for the set $S_E$, i.e. only border points of the constrained set.

Won't we miss some local minimum present in the interior point of the constrain set by ignoring the interior points?

Or does the result stated above hold true under certain additional conditions which has not be considered here?