Some months ago, I’ve finished my manifold learning posts serie. As support for the manifold learning toolkit, I’ve also developed an optimization framework, which I’ll be blogging about, starting now.

The goal was to provide a general way of designing the optimization procedure one needed for his cost function. The development is more or less stopped at the moment, but it does not mean that it is not usable, as you may have seen in the manifold learning posts.

A function to optimize

The function I’ll be trying to optimize is the following one:

class Function(object):
  def __call__(self, x):
    t = numpy.sqrt((x[0]*x[0]+x[1]*x[1]))
    return -numpy.sinc(numpy.pi * t)

This function is a 2D sinc function for which I try to find the maximum, which is in (0,0). To do so, I’ll be minimizing the opposite function.

The simplex method

The simplex method, or polytope or Nelder Mead method, uses a simplex/polytope in the parameters space to search for the global minimum of a function.

The set of current points is sorted, and a mean parameter point is computed with the n best points. The symmetric point of the worst/unsued point with respect to the mean point is compared to the current set, and depending on the result, additional steps of expansion or contraction are taken.

At the end, unless the symmetric point, the expanded or the contracted points do not enhance the solution, the mean cost of the simplex points is always enhanced.

The polytope optimizer usage

The framework is based on several principles I’ll will talk about later. I will only explain what I will be doing.

Once the function is defined, I’m set to optimize it:

  from scikits.optimization.optimizer import PolytopeOptimizer
  from scikits.optimization import criterion
 
  from function import Function
 
  import numpy
 
  optimizer = PolytopeOptimizer(function = Function(),
                                x0 = numpy.random.randn(3, 2) * .5,
                                criterion = criterion.OrComposition(criterion.RelativeParametersCriterion(0.00001), criterion.IterationCriterion(20)))
  optimizer.optimize()
  print numpy.mean(optimizer.state['new_parameters'], axis=0)

The creation of the optimizer is done by calling PolytopeOptimizer with several arguments:

• function which is the instance of the function to optimize
• x0 is the array of starting points (n+1 points of n-dimension points)
• criterion is the stopping criterion, a complex criterion indicating to stop when some iterations are done or if the set of optimal points does not change much

Then, I can call the actual optimization, and display the mean of the set of optimal points.

To end this post, here is a video of the evolution of the optimization.

All the code is available freely on the scikits SVN and the tutorials repository on Launchpad.