Advice for the Thirsty Triangle

A picture is worth a thousand words, but when it comes to comprehending algorithms, I think a decent visualization applet is worth even more--maybe ten thousand words--but I'll be happy if the following helps elucidate a concept for a single curious soul.

The applet du jour demonstrates the Nelder-Mead method, also called the downhill simplex method, the simplex method or the amoeba algorithm.

Suppose you're a triangle and you're thirsty. Knowing water runs downhill, you seek the lowest point you can, but what rules will you apply in finding this thirst-quenching minimum?

Let's refer to your two lowest vertices as your feet and your highest vertex as your head. Here are some of your possible power moves:

1. Stretch to twice your height and flip on your feet.
2. Flip on your feet.
3. Shrink to half your height.
4. Shrink to half your size.

Try each each move in order. If a move puts your head in a lower position, start over and keep doing it until you've shrunk yourself down to a point. Note: which vertex is your head may change after each round.

Try it here: Nelder-Mead applet

This simple algorithm is useful in finding minimums of functions when you have no information about derivatives (i.e., the slope of the surface at a given point). The value of the function at each point is all that's required. The triangle is easily extended to a simplex in higher dimensions (in 4D, it's a flipping tetrahedron, etc.), and the algorithm can be applied to find minimums in n-dimensional space.

In practice, I've used Nelder-Mead to simultaneously optimize the weighted sum of a collection of polynomial models. Because the algorithm finds local minimums, it's best to run a number of trials from random starting points--especially when the underlying space contains a lot of hills and valleys.

A competing method that is said to converge faster is Powell's method. I may see if I can come up with an applet for it in the future, but I had to do Nelder-Mead first, because I think it makes for a much more interesting animation.

fin