Why should non-convexity be a problem in optimization?

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.

• The key word here is "in general" -- you can construct arbitrarily nasty functionals, especially in very high dimensions which are basically "all saddle-points". Specific classes of nonconvex functionals, on the other hand, can be very nicely behaved, especially if you use proper globalization strategies. – Christian Clason May 10 '16 at 17:25
• I think optimal control theory and engineering/operations research applications place quite some emphasis on correctness/robustness, whereas you think that getting somewhere "good enough" is good enough. There could be performance limits (convergence has to be guaranteed, so that a robot's trajectory is calculated in time), or correctness limits (if you change problem parameters a little, you don't unexpectedly get a totally different result). So it's not enough to get some optimal points, it is also necessary for them to have some prescribed properties. – Kirill May 11 '16 at 5:53

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!

• global vs. local optimality is completely different issue. But the rest makes sense. Can say more about "cannot even guarantee that x is a local minimum based on its gradient information alone" or better illustrate that ? – Prokop Hapala May 11 '16 at 7:57
• Suppose we have the functions $f(x)=x^3$ and $g(x)=x^4$ as black boxes (i.e. we can only evaluate, but we do not get to see their form). The point $x=0$ makes both gradients vanish, i.e. $f'(x)=0$ and $g'(x)=0$, but the point is only a local minimum for $g$. Actually, their second derivatives are also zero at this point, so the two scenarios are identical from the first two derivatives alone! – Richard Zhang May 11 '16 at 12:22
• aha, OK, I always automatically assume inertia => that the algorithm would not tend to converge to point $x=0$ in $g(x)=x^3$ at all. But sure, there we use additional information (the inertia) from previous steps, not just gradient in one point. – Prokop Hapala May 11 '16 at 18:57
• I understand your point. And perhaps that is really the reason why in rigorous mathematical sense non-convex optimisation is considered hard. But, still I'm more interested in practical application, where heuristics (which I assume as natural part of the algorithm) would fail miserably. – Prokop Hapala May 11 '16 at 19:10
• What about quasiconvexity? By this logic ( ($\nabla f(x)=0$ is enough), wouldn't quasiconvex problems be as easy to optimize as convex problems?. My understanding is that the latter isn' true (convex problems are still easier). – Amelio Vazquez-Reina Sep 24 '16 at 18:39

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.

• OK, this I think is different problem ... probelm of global optimization, which is clearly hard, and unsolvable in most of the situations. But that is not what people refer to with respect to non-convex optimization, where they say that NP-hard to find a local minimum and many algorithms may get stuck at a saddle point. – Prokop Hapala May 11 '16 at 8:00
• @ProkopHapala My comments were more referring to the quote 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, especially since the OP was talking about how simple it has been for them to tackle non-convex problems in research. Solving exactly, to me, is striving for a globally optimal solution (or something close). So I wanted to paint a picture of real-world challenges related to these comments. – spektr May 11 '16 at 16:21
• I understand. Strictly speaking you are right, but still I think it does not address what I meant ... perhaps I should have formulate it better. – Prokop Hapala May 11 '16 at 19:07

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.

• yes, it is clear that from value and gradient in one point you cannot distinguish this. But I somehow don't see why common heuristics (like stochastic gradient descent or FIRE ) should fail in such situation. I'm pretty sure than it will work just fine for $x^2y+y^2$. So I'm trying to imagine some patological function were it would not work. – Prokop Hapala May 11 '16 at 18:50
• You have to look at it the other way. It's not that we know that stochastic gradient descent will fail, it's that we don't know that it will succeed. For toy problems, this is unlikely to happen in practice, but it might happen for higher dimensional problems. My bet is that for your chemistry problems, this will never happen, but I would be hard pressed to prove that. – LKlevin May 13 '16 at 9:42