2
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .