When are KKT conditions indeed necessary first order conditions?

Question

Somewhat based on: Reformulation of optimization problem using kkt and lagrange conditions

Say I have the following optimization problem: $$ \begin{aligned} \min_{z}\min_{y} \, &\frac{1}{2} y^T \bar{H}y,\\ &\begin{aligned} \text{s.t. } &\bar{E}y = 0,\\ &\bar{A}y \leq \bar{b} + \bar{d}z, \end{aligned} \end{aligned} $$ (with $y \in \mathbb{R}^{n}, z\in \{0,1\}^{2r},\bar{H}\in \mathbb{R}^{n\times n},\bar{E} \in \mathbb{R}^{m_1\times n},\bar{A}\in \mathbb{R}^{m_2\times n},\bar{b} \in \mathbb{R}^{m_2},\bar{d} \in \mathbb{R}^{m_2\times 2r}).$

Also, importantly, $\bar{H}$ is indefinite.

My goal is to reformulate the inner minimization problem over $y$ using the KKT conditions.

I am wondering under which circumstances the KKT conditions are actually first order necessary conditions. From my understanding and from what I gathered from my previous question (see link above), the minimum has to exist in order for the KKT conditions to be necessary. Thus, I would say that in the following cases they are indeed necessary:

• $\bar{H}$ is semidefinite on the feasible set $\mathcal{F} = \left\{y \, \middle| \, \bar{E}y = 0 \, \land \, \bar{A}y \leq \bar{b} + \bar{d}z\right\}$
• the feasible set $\mathcal{F}$ is bounded

Are there any other situations which I did not mention (assuming my findings are correct) under which I can apply the KKT conditions to the optimization problem at hand?

Answer 1

The constraints in your problem are affine linear, hence KKT conditions are necessary for local optimality. That is, every local minimum also satisfies the KKT conditions (together with appropriate multipliers). The KKT conditions do not tell you anything about the existence of minimizers.

Assume the inner problem has feasible points. Then it is solvable if and only if there exists no vector $v$ such that $v^THv<0$, $Ev=0$, and $Av\le 0$.

If there is such $v$, then clearly the function is unbounded on the feasible set: Take a feasible point $y$, define $y_t:= y + tv$. Then $y_t$ is feasible for all $t>0$, and $y_t^THy_t\to\infty$ for $t\to\infty$.

Conversely, assume the inner problem has no solution for some $z$. Then there is a sequence $(y_n)$ such that $y_n^THy_n\to-\infty$. Hence $y_n$ has to be unbounded. Set $v_n:= \|y_n\|^{-1}y_n$. Then $v_n\to v$ along a subsequence, and the limit $v$ satisfies $v^THv<0$, $Ev=0$, and $Av\le 0$.