Forum Numerical Method Optimization

Workflow of Stop Criterial with NMSearch or Brent

totonParticipant 2012-01-07 at 3:01 pm
Hi,

I am planing to use your toolbox (the optimisation part) during my research and requested an academic license which I already received. Thank you for this fast response. Currently I am just testing all the function etc. I am a bit confused generally about the “tol” and “iteration” parameter of the search command, currently I tested Brent and NM search.

Here my code:
```
UnivariateRealFunction r = new UnivariateRealFunction() {
   private int i = 1;
   @Override
   public double evaluate(double x) {
      double r = (x – 1) * (x – 1);
      System.out.println(String.format(“Iter: %3dtX: %-19sttValue: %-19s”, i, x, r));
      i++;
      return r;
   }
};
```
```
Brent instance = new Brent();
instance.solve(r, 1e-5, 100);
double xmin = instance.search(-100, 100);
double fmin = r.evaluate(xmin);
```
Actually I am really confused how do you use the “iteration” and “tol” parameter. Could you explain to me, where you are using this in the algorithm? Another example, if I am using the NMSearch with this code:
```
NelderMead nm = new NelderMead();
nm.solve(f2, 1e-5, 40);
```
I would expect maximal 40 or 43 iteration, with my three initial values. But the algorithms is calculating 82. Very confusing for me right now.
RyuParticipant 2012-01-07 at 4:38 pm
Hello,

For Brent optimization algorithm, the iteration stops either the “tol” criteria are satisfied or max number of iterations is reached. For the “tol” criteria, we have (as in the javadoc):

* We stop the search when * 1. (xu – xl) < 2 * |x| * tol * 2. |xmin – mid| < |x| * tol * * Hence, * (xu – xl)/2 + |xmin – mid| < 2 * |x| * tol ≈ tol2 * * @see “Chapter 10.3, Numerical Recipes.”

The code we use is:
```
 
 @Override 
 boolean isMinFound() { 
 boolean result = false; 
 double mid = 0.5 * (xu - xl);//xu: upper bound, xl: lower bound 
 double tol1 = tol * abs(xmin) + EPSILON;//the machine tol is to protect against when the minimum happens to be at exactly 0, c.f., Chapter 10.3, Numerical Recipes 
 double tol2 = 2 * tol1; 
 if (0.5 * (xu - xl) + abs(xmin - mid) < = tol2) { 
 result = true; 
 } 
 
 return result; 
 } 
```
For your question on Nelder-Mead, your way of counting the number of iterations is wrong. This line has problem:
```
 
 System.out.println(String.format("Iter: %3dtX: %-19sttValue: %-19s", i, x, r)); 
```
Each Nelder-Mead iteration may consist of the reflection, expansion, contraction and reduction step. The objective function may be called multiple times during each iteration. For more information, please see: http://en.wikipedia.org/wiki/Nelder%E2%80%93Mead_method

In your example, the objective function is called 82 times in (possibly fewer than) 40 Nelder-Mead iterations.

As a side note: Nelder-Mead is notoriously known to perform poorly for univariate function optimisation.
totonParticipant 2012-01-07 at 5:20 pm

Hi,

oh thank you very much for this fast and very good answer. Oh right, I really forgot about this, I just compared it with MATLAB and there it is counting the evaluation instead of iterations. Yes for univariable function it is unreliable, thank for the note.

Do you have any sugest for an univariable optimisation without setting a range?

Cheers Chris
RyuParticipant 2012-01-08 at 1:58 pm
Without setting a range is difficult for all kinds of optimization except the most trivial ones.

If you must, you can considering the following: 1. running a very coarse grid search http://www.numericalmethod.com/javadoc/suanshu/com/numericalmethod/suanshu/optimization/univariate/GridSearch.html
pick the best point, and do a fine optimization around that point using, e.g., Brent http://www.numericalmethod.com/javadoc/suanshu/com/numericalmethod/suanshu/optimization/univariate/bracketsearch/Brent.html

Hope this helps.