Downhill Simplex method

1  Introduction

The downhill simplex method is one of the most efficient optimization algorithm. This method is widely used as an optimization algorithm that does not require derivatives, especially in the field of CFD (Computational Fluid Dynamics). In this report, we explain the algorithm, and discuss verification of its performance for a mathematical test function.

2  Downhill Simplex method

2.1  Concept

The downhill simplex method is an optimization algorithm that requires only function evaluations, and not calculation of derivatives.^[1] In the N-dimensional space, a simplex is a polyhedron with N+1 vertices. We chose the N+1 points and defined an initial simplex. The method iteratively updates the worst point by four operations: reflection, expansion, one-dimensional contraction, and multiple contraction. Fig.1 illustrates these operations in three-dimensional variable space.

Fig.1: Four basic operations in the downhill simplex method.

Reflection involves moving the worst point (vertice) of the simplex (where the value of the objective function is the highest) to a point reflected through the remaining N points. If this point is better than the best point, then the method attempts to expand the simplex along this line. This operation is called expansion.

On the other hand, if the new point is not much better than the previous point, then the simplex is contracted along one dimension from the highest point. This procedure is called contraction. Moreover, if the new point is worse than the previous points, the simplex is contracted along all dimensions toward the best point and steps down the valley. By repeating this series of operations, the method finds the optimal solution.

2.2  Algorithm

The downhill simplex method repeats a series of the following steps:

1. Order and re-label the N+1 points so that f(x_N+1) > ... > f(x₂) > f(x₁)

2. Generate a trial point x_r by reflection, such that x_r = x_g + a* (x_g - x_N+1), where x_g is the centroid of the N best points in the vertices of the simplex

3. If f(x₁) < f(x_r) < f(x_N), replace x_N+1 by x_r

4. If f(x_r) < f(x₁), generate a new point x_e by expansion, such that x_e = x_r + b* (x_r - x_g)

5. If f(x_e) < f(x_r), replace x_N+1 by x_e, otherwise replace x_N+1 by x_r

6. If f(x_r) > f(x_N), generate a new point x_c by contraction, such that x_e = x_g + g* (x_N+1 - x_g)

7. If f(x_c) < f(x_N+1), replace x_N+1 by x_e

8. If f(x_c) > f(x_N+1), contract along all dimensions toward x₁. Evaluate the objective function values at the N new vertices, x_i = x₁ + h* (x_i - x₁)

It has been reported that efficient values of a, b, g, and h are a = 1.0, b = 1.0, g = 0.5, and h = 0.5. In this report, we use these parameter settings.

3  Numerical Experiments

3.1  Test Function and Experimental Setup

To verify the performance of the downhill simplex method, we applied the method to a mathematical test function for continuous optimization problems - the Rosenbrock function:

(1)

The Rosenbrock function is known as the Banana function. The global optimum is inside a long, narrow, parabolic shaped flat valley. To find the valley is trivial: however, convergence to the global optimum is difficult and hence this problem has been repeatedly used to assess the performance of optimization algorithms.^[2]

In this report, the dimension of the function is two. The initial vertices of the simplex are randomly generated in the feasible region.

3.2  Experimental Results

Fig.2(a) shows the history of the design variables of the best vertice. The downhill simplex method reaches the optimum along the valley. Moreover, the initial simplex is plotted in Fig.2(b) , and the summary of results of 10 trials are listed in Table 1 .

(a)History of the design variables of the best vertice

(b)Initial simplex

Fig.2: History of the design variables

3.3  Consideration of the Results

The experimental results showed the efficiency of the downhill simplex method for the Rosenbrock function. However, from Fig.2 , it can be seen that the downhill simplex method moves outside of the feasible region. To search only in the feasible region, it is necessary to apply a penalty method, etc., so that the downhill simplex method can deal with constraints.

4  Conclusions

In this report, we explained the downhill simplex algorithm, and verified its performance for a mathematical test function - the Rosenbrock function. The experimental results showed that the method is effective for unconstrained optimization.

References

[1]

Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery, William H. Press.
Numerical Recipes in C++: The Art of Scientific Computing, Pearson Education, 1992.

[2]

Rosenbrock's valley (De Jong's function 2), GEA Toolbox - Examples of Objective Functions.
http://www.systemtechnik.tu-ilmenau.de/~pohlheim/GA_Toolbox/fcnfun2.html

Copyright

Copyright (C) 2006 Satoru Hiwa, All rights reserved.
Copyright (C) 2006 Tomoyuki Hiroyasu, All rights reserved.
Copyright (C) 2006 Mitsunori Miki, All rights reserved.

No part of this document may be reproduced, copied, distributed,
transferred, modified, or transmitted, in any form or by any means,
without the prior written permission of the authors.
In no event shall the authors be liable for any damages caused in any way
out of the use of this document．