Consider the non-convex optimization problem:
$$\underset{x\in \mathbb{R}^n}{\min} ~f(x) \\
\mbox{s.t.}~h_i(x)=0 ~~~\mbox{for}~~~i=1,\ldots,p \\
~~~~~~ g_j(x)\leq0 ~~~\mbox{for}~~~j=1,\ldots,m$$
where $f(x),h_i(x)$ and $g_j(x)$ are continuously differential functions, but not necessarily convex. Let's say $\bar{x}$ is a global minimizer of the problem, and $\bar{x}$ is a KKT point (i.e., the KKT conditions hold at $\bar{x}$) with some constraint qualification (e.g: Mangasarian-Fromovitz constraint qualification holds at $\bar{x}$). What can be said about the duality gap (assuming that the dual solution exists and is attainable)? Does strong duality hold?
Duality gap in non-convex optimization: Do KKT conditions+constraint qualification imply strong duality
duality-theoremsnon-convex-optimizationnonlinear optimizationoptimization
Best Answer
Presume $f(x),h_i(x)$ and $g_j(x)$ are continuously differential function, then
A constraint qualification is necessary to guarantee that local minimum implies KKT point. I.e., constraint qualification is required to make KKT conditions necessary for minimum.
If one or more of $f(x),h_i(x)$ and $g_j(x)$ are non-convex, then (in general) strong duality does not necessarily hold. That's what makes non-convex optimization difficult.
See https://en.wikipedia.org/wiki/Strong_duality