simionx.SimplexOptimizer - Simplex optimizer¶

simionx.SimplexOptimizer - Simplex optimization routine (Nelder-Mead downhill).

SYNOPSIS¶

-- Usage in a loop.

local SimplexOptimizer = require "simionx.SimplexOptimizer"
local opt = SimplexOptimizer {
              start = {10, 20}, step = {5,5}}
while opt:running() do
  local x, y = opt:values()
  local metric = (x-4)^2 + (y-7)^2
  print(string.format("x=%f,y=%f,metric=%f", x, y, metric))
  opt:result(metric)
end
print("done")

-- Alternate usage using explicit function "func":

local opt = SimplexOptimizer {
  start = {10,20},
  func = function(x,y) return (x-4)^2 + (y-7)^2 end
}
opt:run()
print(opt:values()) --> 4.0000000868672 6.9999998212389

DESCRIPTION¶

This module provides a simplex optimization routine (Nelder-Mead downhill type). It can be used to search for a set of input values to a given function that locally minimizes the function. A typical application for this in SIMION is to find a set of lens voltages (the input variables) that minimize beam spot size (which is a function of those voltages), but the routine is general and can be used for many other situations such as geometry optimization.

Mathematically, we assume f is a function of n input variables (for n >= 1) and one output variable, where all the variables are real numbers. The optimization routine aims to find (x_1’, x_2’, …, x_n’) such that f(x_1’, x_2’, …, x_n’) represents a local minimum of f. If f has more than one local minimum, the algorithm is not guaranteed to find the global minimum but rather the local minimum close to a starting point you give it.

The algorithm works by repeatedly evaluating different values of f. It starts by evaluating f at a given starting point and then evaluates f as various surrounding points withing a step size also given. The algorithm can then see which direction tends to reduce f, and it uses a point in that direction as its new starting point (and also adjusts its step size) and repeats the process. The continues in such a way that the the current point converges to a nearby local minimum. For details, see Wikipedia: Nelder-Mead_method and Numerical Methods Using Matlab.

The algorithm requires the following input:

The starting point.
The step size (can be different for each input variable).
The function, or at least a way to evaluate it at the values required by the algorithm.

Some additional parameters can optionally also be used to limit the number of iterations.

The simplex optimization routine does have its limitations. As noted above, it only find local minimums, not necessarily the global minimum of your function. You may want to restart the optimization routine at different starting points (and step sizes) to discover any other local minimums that may be better. If your function is not smooth (but rather is rough and bumpy), then there is a danger that the optimization routine will converge to a small local minimum (dent in the surface) when there is a much more significant local minimum nearby. In that case, it is recommended to use a sufficiently large initial step size and retry the optimization routine. If your function has no local minimum but rather has a saddle point, then there is no solution and the optimization will fail (probably at a distant point).

If you have any issue with finding extrema, check the values passed to your SimplexOptimizer constructor (i.e. start, step, func, maxcalls, and minradius). These values control the stop condition for the iterations. For example, the initial step vector corresponds to approximately the initial radius in the point set measured; this radius decreases across iterations, and when this radius becomes smaller than minradius distance, the optimization will be terminated. So, if step is not much larger than minradius, then the optimization will terminate quickly. step should be about the same order of magnitude as the size of the domain you want to search, and minradius should be about the precision you want in the control variables. Different parameters can affect this though: for example, if you were to set minradius very small (even 0 or negative, which will never be satisfied) but set maxcalls to some fixed number, then it will always iterate for exactly that fixed number of iterations. This is not to say you want to do this though, but it’s just an example. The simplex routine does not guarantee that the metric monotonically decreases as each new point is visited in the optimization, although it tends to go in that direction assuming sufficient smoothness in the metric function being optimized. It may very well be that the last point is not better than the second-to-last point when the stop condition is reached. However the difference should be small given a small value of minradius. An Internet search for “Nelder-Mead method”, as well as a peak at the SimplexOptimizer.lua code, will provide some useful background on this.

See also SIMION Example: hda, which provides a good example of using this module.

Note

This page is abridged from the full SIMION "Supplemental Documentation" (Help file). The following additional sections can be found in the full version of this page accessible via the "Help > Supplemental Documentation" menu in SIMION 8.1.1 or above:

INTERFACE

Changes¶

20170106 - Fixed stability of optimizer for dimensions > 2,: particulary in computing mid-point and more closely following Lagarias et al. Example: optimizing f(x,y,a,b) = (x-x0)^2 + (y-y0)^2 + (a+a0)^2 + (b+b0)^2

SOURCE¶

version: 20170106


[Optional] Your name:	email:	phone: