Is all non-convex optimization heuristic?

Question

Convex Optimization is a mathematically rigorous and well-studied field. In linear programming a whole host of tractable methods give your global optimums in lightning fast times. Quadratic programming is almost as easy, and there's a good deal of semi-definite, second-order cone and even integer programming methods that can do quite well on a lot of problems.

Non-convex optimization (and particularly weird formulations of certain integer programming and combinatorial optimization problems), however, are generally heuristics like "ant colony optimization". Essentially all generalizable non-convex optimization algorithms I've come across are some (often clever, but still) combination of gradient descent and genetic algorithms.

I can understand why this is - in non-convex surfaces local information is a lot less useful - but I would figure that there would at least be an algorithm that provably learns for a broad class of functions whether local features indicate a nearby global optimum or not. Also, perhaps, general theories of whether and how you can project a non-convex surface into higher dimensions to make it convex or almost convex.

Edit: An example. A polynomial of known degree k only needs k + 1 samples to reconstruct - does this also give you the minimum within a given range for free, or do you still need to search for it manually? For any more general class of functions, does "ability to reconstruct" carry over at all to "ability to find global optima"?

Answer 1

If the question is "Are there non-convex global search algorithms with provably nice properties?" then the answer is "Yes, lots." The algorithms I'm familiar with use interval analysis. Here's a seminal paper from 1979: Global Optimization Using Interval Analysis. And here's a book on the topic. The requirements on the function are that it be Lipschitz or smooth to some order, and that it not have a combinatorial explosion of local optima. These techniques aren't as fast as linear or convex programming, but they're solving a harder problem, so you can't hold it against them. And from a practical point of view, for reasonable functions, they converge plenty fast.

Answer 2

I think you will be interested in the work of Parrilo, Lasserre, Putinar, Sturmfels, Nie, Helton, etc., on sums-of-squares and moment methods for polynomial optimization. They look at principled ways of turning general (nonconvex) optimization of polynomials with polynomial constraints into sequences of (convex) semidefinite programs.

The general idea is as follows. Suppose we wish to minimize $f$ over $X$. Assume for simplicity that $X$ is compact and $f$ is continuous. We can turn this into a convex problem by extending it to the set of $\Delta(X)$ of Borel probability measures over $X$ and defining $f(\sigma)=\int f d\sigma$ for $\sigma\in\Delta(X)$. The resulting optimization problem is convex, has the same global optimum value as the original problem, and from any optimal solution $\sigma$ one can easily extract an optimal solution to the original problem (just take any any element of the support of $\sigma$).

The problem of course is that our new convex problem is infinite-dimensional. However, in case all the problem data are polynomial there are a number of nice ways of approximating the infinite-dimensional problem from the outside by semidefinite programs. In particular, we can find sequences of such SDPs in successively higher dimensions whose values increase monotonically to the global minimum value of the original problem.

This is in stark contrast to local methods in which we try to decrease toward the minimum value, and nonconvexity more or less ensures that we cannot do this monotonically. Furthermore, while local methods easily give you upper bounds on the minimum value (just evaluate f anywhere to get such a bound), it is very hard to get any information about matching lower bounds out of local methods.

Of course the downside is that when the SDP gives you a value which is strictly lower than the global minimum then it by definition cannot give you an $x$ where this value is achieved. However, if one of the SDPs in the sequence gives the exact global minimum then a value of $x$ where this is reached can be extracted from the dual SDP, at which point one has matching upper and lower bounds on the optimum, hence a certificate that this $x$ is optimal. Alternatively, once you feel that you have a "good" lower bound you could use local methods to try to find an $x$ which gets close enough to that value for your purposes.

Of course NP-completeness issues ensure that in general there's not much we can say about the convergence rate of such procedures. However, in practice they work amazingly well. Explaining this is an important open problem.

There is an excellent introduction to such techniques on MIT OCW in the form of lecture notes for Parrilo's course (full disclosure: he is one of my thesis advisors).

Answer 3

In some sense, the fundamental difficulty with non-convex optimization is that you very quickly run up against NP-completeness. If $P\ne NP$, then there's not going to be any efficient, general-purpose method to solve non-convex optimization problems or convert them into convex ones.

Having said that, as Carl wrote, of course there are plenty of interesting things to prove about non-convex optimization, if you're willing to give up on a fast algorithm that always works! For example, approximation guarantees, convergence in mild exponential time...

Answer 4

Hi there, I'm coming to this from a practitioner's point of view. Your question as to whether non-convex optimization is always heuristically driven can be answered as follows:

No.

There are many gradient-based techniques for nonconvex global optimization out there that DO NOT rely on any heuristics at all. They are usually based on partitioning the solution space, and performing some sort of branch and bound search using tight convex relaxations (the tightest relaxations obtainable for nonlinear functions are McCormick relaxations). As mentioned, these algorithms have a worst case exponential complexity, but they are rigorous (non-heuristic) and are able to give you a provably global solution.

Global nonconvex optimization is an active area of research: http://www.mat.univie.ac.at/~neum/glopt/techniques.html#branch

The well-known BARON software for instance, can rigorously find the global optimum of a nonlinear nonconvex problem.

Other software/algorithms include:

LaGO https://projects.coin-or.org/LaGO

Couenne https://projects.coin-or.org/Couenne

Papers that provide mathematical details for all the above solvers can be found in the open literature.

Practitioners in this area have come to realize that procedures for finding the global solution to a general nonconvex problem are usually NP-hard (so far no exceptions have been found).

A special case of this can be seen in polynomial programming, where a nonconvex polynomial optimization problem can be solved by decomposing its KKT (optimality) conditions into its Groebner basis. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.6266

On the surface, this looks attractive because it would seem that any nonconvex optimization problem can then be approximated as a polynomial programming problem by taking its Taylor expansion. However, the computation of Groebner bases is NP-hard.

I hope that gives you a few leads.

Answer 5

There has been recently a flurry of new results on provable nonconvex methods which can be guaranteed to converge to the global optimum. In other cases, the non-convex problem itself is shown to have no spurious local optima. The classical case is the singular value decomposition (SVD) which is non-convex but yet solvable. This is because only the top eigenvector is the global and local optimum and all the other eigenvectors are saddlepoints (assuming eigen gap). We have recently been studying tensor SVD problems. While general tensors are hard to decompose, for an orthogonal tensor, there are no spurious local optima and thus, we can find the correct decomposition. You can refer to our paper for more details.

http://newport.eecs.uci.edu/anandkumar/pubs/AnandkumarEtal_Tensor12.pdf

To give more examples of non-convex methods which can be analyzed, we have recently shown that the problem of dictionary learning or sparse coding can also be solved correctly. This is the problem where we want to fit the data as a sparse combination of an unknown dictionary. The challenging regime is the overcomplete or the under-determined setting where there are more dictionary elements than the dimension of the observed data. More details can be found at

http://newport.eecs.uci.edu/anandkumar/pubs/Anandkumar-COLT2014.pdf

Finally, most recently, we have shown global convergence for a natural non-convex method for robust PCA. This is the problem of finding a low rank approximation of the data after removing sparse corruptions. We have recently shown that our non-convex method is guaranteed to work in the same regime as the convex method, and with far lower computational complexity. Details can be found at my website.

Anima Anandkumar U.C. Irvine

Answer 6

Well, there is at least one nonconvex problem, that we can solve exactly and fast: lower rank approximation. Find matrix $B$ such that $rank(B)=k$ "nearest" to matrix $A$ of rank $m>k$. That problem can be solved with SVD.

Answer 7

Of course, generally the optimization is NP-hard. However there is a couple tricks that can be played in non-convex case. First, if $d$ is domain dimension, the probability of, say, gradient descent getting stuck in local minimum decreases exponentially as $d \rightarrow \infty$ Thus, the main obstacle are, in this case, saddle points.

To escape the saddle points one may use the modified Newton method, that, instead of taking steps $-\alpha H^{-1}\nabla f$ takes steps of $-\alpha |H|^{-1}\nabla f.$

This is so-called Saddle-free Newton, which requires $O(d^3)$ time to take a step (matrix inversion is slow). One can use a version that approximates the subspace containing eigenvectors corresponding to largest (by absolute value) eigenvalues with technique similar to Lanzchos procedure. Time constraint becomes $O(kd)$ for some constant $k.$

Both methods were intorduced and proved in this article: https://arxiv.org/abs/1406.2572

As for public implementation, there is one here: https://github.com/smdrozdov/saddle_free_newton