Back after a busy summer with trips and other sorts of diversions. (not all pleasant ones).
There is a class of function-value only optimizers which build a tree and use Lipschitz continuity to ensure global convergence. DIvided RECTangle algorithms recursively build a tree of rectangles. With a bit of cunning, based on Lipschitz continuity (the statement that iff it is continuous then there is a finite derivative (delta F is bounded by some K delta x)), this approach quickly finds global optima over a bounded region.
The cunning bit of this is how it searches for candidate optima for further expansion. Basically, if a box is of size X then if the function value is the lowest of all boxes of size X or bigger, then that box is a candidate for search.
It is immediately obvious that such an algorithm could efficiently search many problems that are thought to be NP complete (but aren’t really) like well protein folding, and other problems that are simply a pain – like image modeling from incomplete Fourier data.
I’ve generalized the algorithm with an amortized generic tree based on Delaunay triangulations, and get both a simpler program and somewhat better convergence (or at least what looks like better convergence). It certainly handles some very painful challenge problems quite well. The reason to use a generic tree is to handle seeding the optimizer with known potential solutions and/or to avoid having to encode the search space and function in a fairly complex manner.
So now to try more interesting problems.