why do we need algorithms, and why is non-convex optimization difficult? - MathOverflow [closed]

why do we need algorithms, and why is non-convex optimization difficult?

2012-09-27T04:48:38Z

A simple question, but (I'm quite sure) not a superficial one: is the basic distinction between algorithms and much of the rest of math that algorithms try to tackle problems for which we lack global information, or alternatively, lack a complete, instantaneous understanding of the structure of the problem?

A concrete example: consider any simple quadratic polynomial function. If I wanted to know its zeroes, I could just solve for x. Boom: instant analytic solution. Or I could use the Netwon-Raphson method, algorithmically getting closer to the final solution, step-by-step, in accordance with a simple rule.

Obviously there are more complex problems where I can do something like the second approach (use some algorithm), but nothing like the first approach (no clean, instant analytical solution). So is the implication of this that the basic point of algorithms are the problems for which we lack complete, global information, which in turn prevents us from quickly producing the clean analytical solution?

This question is motivated by a recent encounter with the subject of non-convex optimization. A peer explained to me that non-convex optimization is so difficult (and requires difficult algorithms) because basically, you never know if a local optimum is also a global optimum. This remark confused me, because if you had global information, aka the functional form of whatever you were trying to optimize, you could just get an analytical solution. The only way I can make sense of this remark is if we just don't have the functional form -> we don't have global information -> we have to try to screw around with algorithms.

Answer by Dima Pasechnik for why do we need algorithms, and why is non-convex optimization difficult?

2012-09-27T06:22:00Z

An $n$-variate polynomial of degree 4 can have exponentially many local minima. Indeed, they can be "written down" as solutions of the the corresponding systems of cubic equations, but this doesn't really help you to find a global minimum.

Edit: e.g. take $f(x_1,\dots x_n)=\sum_{k=1}^n (1-x_k^2)^2.$ Then the minima of $f$ are in the points $(\pm 1,\dots,\pm 1)$.

Answer by S. Sra for why do we need algorithms, and why is non-convex optimization difficult?

2012-09-27T08:57:44Z

The question really makes no clear sense, and should be revised to ask something more precise. In any case, let me try to partially disabuse the OP of a few things.

Not all of non-convex optimisation is difficult; large parts of it are. A key difficulty comes not just from having a large number of local minima, but something even more fundamental: even recognizing that you are at a local minimum can be hard. This problem stems from the fact that in general, there are no known simple conditions that are both necessary and sufficient for qualifying a local minimum.

See for example this excellent paper, which sheds light on these issues (it has an entertaining example involving Fermat's last theorem).

However, there do exist several nonconvex problems which one can solve efficiently in pseudo-polynomial time. The foremost example is the SVD (Singular Value Decomposition). This is part of a broader class of problems, where the so-called S-Lemma applies.

Matrix analysis abounds with nonconvex problems which can still be solved globally. A key factor in many of these prolems turns out to be the restrictive sounding, yet quite frequent happenstance: every stationary point is a local minimum.