tech guy in midtown

I thought of a simple randomized optimization algorithm today while I was working on a problem. The algorithm’s working well for me, and while I doubt it’s truly novel, it’s new to me.

Broadly speaking, I’m searching for for a vector of floating point numbers that optimizes my objective function. My objective function is complex enough to be thought of as a black box, and therefore there’s no closed-form gradient function. Although the function has no local minima, the parameters are subject to a number of boundary conditions.

I’m coding in python, so at first I tried using scipy.optimize.fmin. In the function passed to fmin, I returned a large number if the given vector violated the boundary conditions. Unfortunately those large numbers created singularities that caused fmin to get stuck. There are other functions within scipy.optimize that might work, but it wasn’t clear how to use them. This motivated me to code up my own algorithm.

The general approach is simple: at each step generate a random neighbor. If that neighbor is superior to the current point, move to it. I generate a neighbor by perturbing each element of my vector by some fixed delta. Specifically, I multiple a vector numpy.random.random_integers(low=-1, high=1, size=mysize) by delta. Then I normalize the result. Lastly, I find the closest vector point that satisfies the boundary conditions.

This has the succinctness that makes many randomized algorithm appealing. In addition, on my problem, its performance was better
than I expected. Two enhancements made it exceptional.

First, if I generate too many neighbors without finding a superior one, then I decrease delta by a factor of 10. The algorithm stops when delta drops below some threshold. This provides a natural transition between large, coarse steps for speed and small, fine steps for precision.

Second, when I’m at point x0, and I generate a superior point at x1, then I search for increasingly superior points along the trajectory from x0 to x1. Doing so yields the benefits of a poor man’s gradient.

The figure gives a rough illustration of the search technique. We start at a point with value 8, and randomly pick a neighbor using delta 4. Next we search along that trajectory and find a better point with value 4. Once again using delta 4 we pick a random superior neighbor. Note that we hop over a boundary point when we move there. Unfortunately we don’t randomly generate a better neighbor with delta 4 from that point (even though one exists). So we switch delta to 2, and continue the algorithm.

My code is currently embedded with logic that’s specific to the problem I’m solving.  If I abstract it out, I’ll post the code here.  I’m curious to hear from anybody else who’s implemented a randomized optimization algorithm like this one.