Why should non-convexity be a problem in optimization?

Question

I was very surprised when I started to read something about non-convex optimization in general and I saw statements like this:

Many practical problems of importance are non-convex, and most non-convex problems are hard (if not impossible) to solve exactly in a reasonable time. (source)

or

In general it is NP-hard to find a local minimum and many algorithms may get stuck at a saddle point. (source)

I'm doing kind of non-convex optimization every day - namely relaxation of molecular geometry. I never considered it something tricky, slow and liable to get stuck. In this context, we have clearly many-dimensional non-convex surfaces ( >1000 degrees of freedom ). We use mostly first-order techniques derived from steepest descent and dynamical quenching such as FIRE, which converge in few hundred steps to a local minimum (less than number of DOFs). I expect that with the addition of stochastic noise it must be robust as hell. (Global optimization is a different story)

I somehow cannot imagine how the potential energy surface should look like, to make these optimization methods stuck or slowly convergent. E.g. very pathological PES (but not due to non-convexity) is this spiral, yet it is not such a big problem. Can you give illustrative example of pathological non-convex PES?

So I don't want to argue with the quotes above. Rather, I have feeling that I'm missing something here. Perhaps the context.

Answer 1

The misunderstanding lies in what constitutes "solving" an optimization problem, e.g. $\arg\min f(x)$. For mathematicians, the problem is only considered "solved" once we have:

1. A candidate solution: A particular choice of the decision variable $x^\star$ and its corresponding objective value $f(x^\star)$, AND
2. A proof of optimality: A mathematical proof that the choice of $x^\star$ is globally optimal, i.e. that $f(x) \ge f(x^\star)$ holds for every choice of $x$.

When $f$ is convex, both ingredients are readily obtained. Gradient descent locates a candidate solution $x^\star$ that makes the gradient vanish $\nabla f(x^\star)=0$. The proof of optimality follows from a simple fact taught in MATH101 that, if $f$ is convex, and its gradient $\nabla f$ vanishes at $x^\star$, then $x^\star$ is a global solution.

When $f$ is nonconvex, a candidate solution may still be easy to find, but the proof of optimality becomes extremely difficult. For example, we may run gradient descent and find a point $\nabla f(x^\star)=0$. But when $f$ is nonconvex, the condition $\nabla f(x)=0$ is necessary but no longer sufficient for global optimality. Indeed, it is not even sufficient for local optimality, i.e. we cannot even guarantee that $x^\star$ is a local minimum based on its gradient information alone. One approach is to enumerate all the points satisfying $\nabla f(x)=0$, and this can be a formidable task even over just one or two dimensions.

When mathematicians say that most problems are impossible to solve, they are really saying that the proof of (even local) optimality is impossible to construct. But in the real world, we are often only interested in computing a "good-enough" solution, and this can be found in an endless number of ways. For many highly nonconvex problems, our intuition tells us that the "good-enough" solutions are actually globally optimal, even if we are completely unable to prove it!

Answer 2

An example of a tricky low dimensional problem could be:

Given you hit a local minima, how can you be sure it's anything close to as good as the global minima? How do you know if your result is a unique optimal solution, given it is globally optimal? How can you create an algorithm robust to all the hills and valleys so it doesn't get stuck somewhere?

An example like this is where things can get difficult. Obviously, not all problems are like this, but some are. What's worse is, in a setting in industry, the cost function may be time consuming to compute AND have a problematic surface like the one above.

Real Problem Example

An example I could tackle at work is doing an optimization for a missile guidance algorithm that could be robust at many launch conditions. Using our cluster, I could get the performance measurements I need in about 10 minutes for a single condition. Now to adequately judge robustness, we would want at least a sample of conditions to judge against. So let's say we run six conditions, making an evaluation of this cost function take one hour.

The nonlinear missile dynamics, atmospheric dynamics, discrete time processes, etc result in a pretty nonlinear reaction to changes in the guidance algorithm, making the optimization hard to solve. The fact this cost function will be non-convex makes the fact it is time consuming to evaluate a big issue. An example like this is where we would strive to get the best we can in the time we are given.

Answer 3

The problem is that of saddle points, discussed in the post which you linked. From the abstract of one of the linked articles:

However, in general it is hard to guarantee that such algorithms even converge to a local minimum, due to the existence of complicated saddle point structures in high dimensions. Many functions have degenerate saddle points such that the first and second order derivatives cannot distinguish them with local optima. In this paper we use higher order derivatives to escape these saddle points: we design the first efficient algorithm guaranteed to converge to a third order local optimum (while existing techniques are at most second order). We also show that it is NP-hard to extend this further to finding fourth order local optima.

Essentially you can have functions where you have saddle points that are indistinguishable from local minima when looking at the 1st, 2nd and 3rd derivatives. You could solve this by going to a higher order optimizer, but they show that finidng a 4th order local minimum is NP hard.

I recommend reading the article, as they also show several examples of such functions. For instance the function $x^2y+y^2$ has such a point at (0,0).

You could use a number of heuristics to escape such points, which may work for many (most?) real world examples, but cannot be proven to always work.
In the blog post you linked they also discuss the conditions under which you can escape such saddle points in polynomial time.

Answer 4

In addition to the answers already given an additional issue is that without convexity the Hessian is not guaranteed to be positive definite. This complicates any method using a quadratic model (such as Newton's method or Quasi Newton's methods) since the quadratic model will not have a minimum to determine the appropriate search direction and step length. (There are work-arounds see for example the BFGS algorithm.)

Answer 5

This is an indirect answer. Other answers already explain in detail why it is that non-convex optimization is challenging, but to recap:

1. No solution method we have, other than brute force, is guaranteed to succeed or even make progress. Using brute force is prohibitively expensive.
2. Even if we can find a solution we do not have a guarantee that it is locally or global optimal, unless we are prepared to spend considerable resources on it.

I'm doing kind of non-convex optimization every day - namely relaxation of molecular geometry.

I'm not quite sure what "relaxation of molecular geometry" is, but it sounds like you could include the protein folding problem either within this framework or adjacent to it.

Solving the protein folding problem is one of the harder and more important problems in science. Every two years a contest called CASP is held to evaluate how good humanity is at solving the problem and to encourage additional progress.

The contest asks entrants to predict the geometry of proteins whose structure has been experimentally determined but not yet published from their amino acid sequences.

Here's a chart of progress over time, though it only shows results since 2006, the contest itself dates back to 1994:

Note that for a period of 10 years there's almost no progress until DeepMind comes along to blow the competition out of the water with AlphaFold.

This means that for 10 years brilliant people were unable to solve this non-convex problem satisfactorily. Finally making progress took:

1. Enormous improvements in GPU hardware.
2. Google's development of the TPU to improve accelerate software beyond what GPUs can do.
3. Global increases in AI/ML knowledge supported by most governments and industries.
4. Google's willingness to lose ~$500M/year funding DeepMind.

That level of resource commitment is sometimes necessary to make progress on a non-convex problem.