# 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. May 10, 2016 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. May 11, 2016 at 5:53
• Came across this post on the main page and noticed you do molecular simulations. I don't know if you have come across it, but there is relatively new site on the network called Matter Modeling which focuses on molecular/materials/etc simulations. Just wanted to point it out in case had any interest in joining. Aug 4, 2021 at 20:50

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 ? May 11, 2016 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! May 11, 2016 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. May 11, 2016 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. May 11, 2016 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). Sep 24, 2016 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. May 11, 2016 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. May 11, 2016 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. May 11, 2016 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. May 11, 2016 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. May 13, 2016 at 9:42

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.)

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.