Let an optimization problem reads
\begin{alignat}{2} \text{(P1)} \quad \text{minimize}_{x \in \mathbb{R}^{n \times 1}} \quad & f(x) \\ \text{subject to }\quad & g_m(x) \leq 0 \quad m=1,\ldots,M, \end{alignat} where $f(x)$ is a convex and differentiable function. However, $\{g_m(x)\}$ are nonconvex functions but closed (and proper if needed for the optimality condition?). ADD: Assume $g_m$ to be an indicator function but to a nonconvex set.
Forming a Lagrangian of $\text{(P1)}$, we have \begin{align} L(x, \{\lambda_m\}) = f(x) + \sum_{m=1}^M \lambda_m \ g_m(x). \end{align}
I am confused with the optimality conditions for a nonconvex optimization problem ($\text{P1}$).
Questions:
- Are KKT conditions sufficient (and necessary?) conditions for local? (or global?) optimality? If not, then what are the correct ones to characterize the optimality?
- Suppose $x^\star$ and $\{\lambda_m^\star\}$ are (local? or global?) optimal values, then does the following saddle point hold in nonconvex optimization as well? $$L(x^\star, \{\lambda_m\}) \leq L(x^\star, \{\lambda_m^\star\}) \leq L(x, \{\lambda_m^\star\})$$
KKT Conditions:
Stationarity condition: $0 \in \partial L\left( x, \{\lambda_m\}\right) {\color{red}{\Rightarrow 0 \in \nabla f(x) + \sum_{m=1}^M \lambda_m^{\star} \ \partial g_m(x) ?}} $, where $\{\lambda_m^\star \geq 0\}$ are optimal Lagrange multipliers that maximizes the Lagrangian.
Complementary slackness: $\lambda_m \ g_m(x) = 0$ for all $m=1,\ldots,M$
Primal feasibility: $g_m(x) \leq 0$ for all $m=1,\ldots,M$
Dual feasibility: $\lambda_m \geq 0$ for all $m=1,\ldots,M$