why do we need algorithms, and why is non-convex optimization difficult? - MathOverflow [closed] most recent 30 from http://mathoverflow.net 2013-05-19T00:40:57Z http://mathoverflow.net/feeds/question/108209 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/108209/why-do-we-need-algorithms-and-why-is-non-convex-optimization-difficult why do we need algorithms, and why is non-convex optimization difficult? Casella 2012-09-27T04:48:38Z 2012-09-28T11:50:49Z <p>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? </p> <p>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. </p> <p>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?</p> <p>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. </p> http://mathoverflow.net/questions/108209/why-do-we-need-algorithms-and-why-is-non-convex-optimization-difficult/108215#108215 Answer by Dima Pasechnik for why do we need algorithms, and why is non-convex optimization difficult? Dima Pasechnik 2012-09-27T06:22:00Z 2012-09-27T10:43:42Z <p>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. </p> <p><b>Edit</b>: 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)$.</p> http://mathoverflow.net/questions/108209/why-do-we-need-algorithms-and-why-is-non-convex-optimization-difficult/108223#108223 Answer by S. Sra for why do we need algorithms, and why is non-convex optimization difficult? S. Sra 2012-09-27T08:57:44Z 2012-09-28T11:50:49Z <p>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.</p> <p>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: <strong>even recognizing that you are at a local minimum</strong> can be hard. This problem stems from the fact that in general, there are no known <strong>simple</strong> conditions that are both necessary and sufficient for qualifying a local minimum.</p> <p>See for example <a href="http://www-personal.umich.edu/~murty/np.pdf" rel="nofollow">this excellent paper</a>, which sheds light on these issues (it has an entertaining example involving <em>Fermat's last theorem</em>).</p> <p>However, there do exist several nonconvex problems which one can solve efficiently in pseudo-polynomial time. The foremost example is the <a href="http://en.wikipedia.org/wiki/Singular_value_decomposition" rel="nofollow">SVD (Singular Value Decomposition)</a>. This is part of a broader class of problems, where the so-called <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.123.8992&amp;rep=rep1&amp;type=pdf" rel="nofollow">S-Lemma</a> applies.</p> <p>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: <em>every stationary point is a local minimum.</em></p>