SIMPLEX Optimization

1. The Simplex Method

The Simplex Optimization Method is basically a hill climbing strategy. Consider n-variables are defined, then a Simplex (geometrical figure) with n+1 vertices is defined, and randomly placed in the search space.

Then step-by-step the vertex with the worst "quality" is replaced by mirroring along the center of gravity of all other vertices. The quality of the new vertex is tested and eventually an expansion or shrinking of the Simplex figure is performed (especially when the Simplex approaches the optimum). This is called the dynamic Simplex optimization method.

For more information see for example [1].

Basically for using this Applet a detailed knowledge of the Simplex method is not necessary, but remember a few important points:

• Simplex is a "hill climbing" methods and detects the next best maximum or minimum.

• As a consequence of point (1) you can never be sure to detect a global maximum or minimum using the Simplex method.

• Furthermore: try to keep the search interval of the variables as small as possible. Probably you have already an idea where the maximum or minimum should be located approximatly. If e.g. the minimum is around: x~4, y~-3 and z~0.5 then enter 3.8 as lower limit for x and 4.3 as upper limit for x, and so on.

A Test-GUI Applet that allows to find Maxima or Minima of mathematical formulas is available for testing the SIMPEX library.

2. Define a new Formula

First of all define all variables of the formula by entering the names of the variables in the Variable Name field, and the lower and upper limit of each variable. Press the Add Variable button to add the definitions to the list and continue with the next variable. The Simplex algorithm will search only in the scope defined by the upper and lower limit of the variables, hence will find no optima outside these limits.
All variable names must be composed entirely of letters and contain no symbols or numbers.

Tip: As already mentioned above: Try to keep these intervals as small as possible, especially when optimizing functions with more than one minimum or maximum, as the Simplex algorithm finds the optimum located next to his starting position.

Remove a variable from the definition list by selecting this variable in the list and pressing the Remove Variable button.

Define the equation by simply entering the equation in the Enter Formula to optimize field. Remember: only declared variables may be used in this formula!

Supported binary operators are:

Supported functions are:

Define the upper and lower limit of the function results (this can be a rough estimation).

Enter an Epsilon value. The iteration will stop when the quality difference between the best and the next-best vertex of the simplex is smaller than this epsilon value, but after a maximum of Max. Iteration Steps the iteration will be terminated.
Entering 0 in the Epsilon field switches the epsilon termination criterion off and always calculates as many iteration steps as defined in the Iteration Steps field.

3. Start Optimization

Press the Start Optimization button. The result is then shown in the Result-list. Pressing the Print Complete Optimization Result prints the complete iteration data in the Java Console window, so open this window if you like to browse these results.

Tip: To test the quality of the optimization result perform more than optimation:

As the algorithm is rather fast, it should be no problem running it 3-4 times. If the results are always (almost) identically you can assume to have found the optimum. If the results nearly the same, but the deviation is too big, enter a smaller Epsilon value and/or enter a bigger number of iteration steps.

If the results are completly different something is wrong with the optimization: Check the limits of the variables, the formula definition, the upper and lower limits of the equation and so on...

Exceptions: If the variable definition is not correct, or the formula definition is not as defined in the specifiactions above an error message is shown in the result box. Correct the mistakes and retry the Optimization.

4. Example

Let´s find the maximum of the function e^(-(x^2+y^2)) in the interval (-1,1) for both variables x and y:

1. Variable Definition
   1. Enter x in the Variable Name field
   2. Enter -1 in the lower limit field in the variable definition area
   3. Enter 1 in the upper limit field in the variable definition area
   4. Press the Add Variable button
   5. Enter y in the Variable Name field
   6. Enter -1 in the lower limit field in the variable definition area
   7. Enter 1 in the upper limit field in the variable definition area
   8. Press the Add Variable button
2. Formula Definiton
   1. Enter e^(-(x^2+y^2)) in the Enter Formula to Optimize field
   2. Do not select the Minimize checkbox, as we want to find the maximum of this function.
   3. Enter 0 in the Lower Limit field of the equation definition area (the result of the equation cannot be smaller than 0)
   4. Enter 1 in the Upper Limit field of the equation definition area (the result of the equation cannot be bigger than 1, in fact the maximum is 1)
   5. Enter 0.000001 in the Epsilon field.
   6. Enter 1000 in the Max. Iteration Steps field.
3. Start Optimization
   1. Press the Start Optimization button.
   2. Results could be: x = -0.002540214276005725 and y = -2.1445771697033243E-5 which is pretty near to (0,0), which is the maximum of this function. If you need higher precision, reduce Epsilon, or set Epsilon to 0 and increase the number of iteration steps.
   3. Press the Print Complete Optimization Result button to print all the details in the Java-Console window.

5. Contact Me

If you should have some remarks to this applet, or found bugs, or have any other comments, dont hesitate to contact me via Email.

6. References

[1] Deming, S. N. and L. R. Parker Jr. (1978), A Review of SIMPLEX Optimization in Analytical Chemistry, Analytical Chemistry, 187--202