-8
$\begingroup$

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.

Improve this question
$\endgroup$
10
  • 10
    $\begingroup$ It's never been clear to me in what sense the quadratic formula actually solves a quadratic equation. What does it mean to say that $x = \sqrt{2}$ is the (positive) solution to $x^2 = 2$? Well, this is almost a tautology. The only content in this statement is that there is a unique positive solution. But this requires some work to prove (one must prove that the solution actually exists in $\mathbb{R}$) and then it's still not clear (to me) in what sense you've found the answer until you write down, at the very least, an algorithm giving you the digits of $\sqrt{2}$. $\endgroup$
    – Qiaochu Yuan
    Commented Sep 27, 2012 at 4:54
  • 7
    $\begingroup$ By the way, this last phrase "screw around with algorithms" strikes me as deeply disrespectful to people who work with algorithms, so if you expect any of those people to answer this question you should probably remove it. $\endgroup$
    – Qiaochu Yuan
    Commented Sep 27, 2012 at 5:00
  • 2
    $\begingroup$ Let $X$ be the set of equations with clean analytic solutions, and let $Y$ be the set of equations that are interesting to mathematicians. Experience suggests $X \cap Y$ is a rather small subset of $Y$. $\endgroup$
    – S. Carnahan ♦
    Commented Sep 27, 2012 at 8:07
  • 4
    $\begingroup$ Nitpick/clarification of Qiaochu's first remark: the quadratic formula is irrelevant to saying that $x=\sqrt{2}$ is the positive solution to $x^2=2$, of course. That's how the square root function is defined; what the quadratic formula does is solve more general equations in terms of square roots. Tying this in with the original question: the quadratic formula does not give "boom, instant solution", because you need an algorithm to compute the square root. And if you say: "I can leave the square root as is", then you're comparing apples and oranges... Sorry, but very naive question IMHO. $\endgroup$
    – Thierry Zell
    Commented Sep 27, 2012 at 15:13
  • 2
    $\begingroup$ The question seems to presuppose that algorithms necessarily run forever, producing better and better approximations to a solution. Many algorithms are indeed like that, but many others are finite procedures that produce exact solutions. $\endgroup$
    – Andreas Blass
    Commented Sep 28, 2012 at 12:03

2 Answers 2

Reset to default
10
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 4
    $\begingroup$ Exponentially in $n$? Is it easy to give examples of this? $\endgroup$
    – Mariano Suárez-Álvarez
    Commented Sep 27, 2012 at 6:53
  • 3
    $\begingroup$ $\sum_{i=1}^n (x_i^4 - 2 x_i^2)$ has local minima at $(\pm 1, ..., \pm 1)$. Even in one dimension, $\arg \min x^4 - x^2 + ax$ is a discontinuous function of $a$. $\endgroup$
    – Douglas Zare
    Commented Sep 27, 2012 at 8:30
7
$\begingroup$

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.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged .