What exactly is non-convex optimization

I am coming across the term: non-convex optimization problem.

What exactly is this non-convex structure, and how do I know by only looking at the structure of the problem, I could tell it is non-convex and thus difficult to solve?

Solution 1:

In a convex optimization problem, you are minimizing a convex function (or maximizing a concave function) on a convex feasible region. The feasible region might be defined by constraints of the form $g(x) \le c$ where $g$ is a convex function.

A non-convex optimization problem is any optimization problem that is not convex.

Solution 2:

To check convexity of a problem, you can check if the objective function and the constraints are convex.

One really good property of convex problems is that any local optimum is also a global optimum. Therefore, when an optimization algorithm gives a local optimum, you know it is also a global one. In this way, the problem is easier to solve.

To prove, let $x$ be a local minimum, and let $y$ be a point with a lower value of objective function, that is $f(y) < f(x)$. From convexity of the objective function, we know $f(y)\geq f(x)+{\nabla f(x)}^T (y-x)$, then we can tell ${\nabla f(x)}^T (y-x) < 0$.

As the feasibility set is also convex, we know any point between $x$ and $y$ is in the feasibility set, e.g. $x+t(y-x)$ for a sufficiently small $t$. Then from first-order Taylor expansion, $f(x+t(y-x))=f(x)+t{\nabla f(x)}^T (y-x) < f(x)$. Thus, $x$ is not a local optimum.