# 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