182 Beam-based Correction and Optimization for Accelerators
include pattern search, Nelder-Mead simplex search [89], and methods with
adaptive search directions.
Nelder-Mead simplex method: The Nelder-Mead simplex method, also
known as the downhill simplex method, is probably the most well-known direct
search method. This method maintains a non-degenerate simplex during the
course of the search. A simplex is an n + 1 polytope in an n-dimension space.
For example, a simplex in the 2-dimensional space is a triangle and a simplex
in a 3-dimensional space is a tetrahedron. The algorithm first builds a simplex
around the initial solution, typically with it as one vertex and generating the
other n vertices by taking a step in one of the n parameters each. During an
iteration, it performs the following operations
1. Sorts the function values on the vertices. Label the vertices 1 through
n + 1 with the corresponding function values in the ascending order,
i.e., f 1 ≤ f 2 ≤ · · · ≤ f n+1 , where f i ≡ f (x i ) and x i is the i’th vertex.
Calculate the center point of the simplex face opposite to vertex x n+1
(which has the largest function value), x c ≡
1
n
n
i=1 x i . On the line
connecting x n+1 and x c , the following points are defined:
Reflection point: x r = x c + (x c − x n+1 ).
Expansion point: x e = x c + 2(x c − x n+1 ).
Inner contraction: x ic = x c −
1
2 (x c − x n+1 ).
Outer contraction: x oc = x c +
1
2 (x c − x n+1 ).
2. Reflection: Evaluate the function value at the reflection point, f r =
f (x r ). If the value at the reflection point is better than the second
worst, but not better than the best vertex, i.e., f 1 ≤ f r < f n , replace
vertex x n+1 with x r and finish the iteration.
3. Expansion: If the reflection point is better than the best vertex, i.e.,
f r < f 1 , evaluate the expansion point. Replace x n+1 with the better of
the reflection point and the expansion point and finish the iteration.
4. Outer contraction: If f n < f r < f n+1 , evaluate the outer contraction
point. If f oc = f (x oc ) < f r , replace vertex x n+1 with x oc and finish the
iteration.
5. Inner contraction: If f r > f n+1 , evaluate the inner contraction point. If
f ic = f (x ic ) < f r , replace vertex x n+1 with x ic and finish the iteration.
6. Shrink: If none of the above operations terminates the iteration, shrink
the size of the simplex toward the best vertex, x 1 , by replacing all other
vertices with x
i = x 1 +
1
2 (x i − x 1 ), with i = 2, 3, · · · , n + 1. Evaluate
the function values on all new vertices and go on to the next iteration.
The operations of the downhill simplex method are illustrated in Figure 7.2
for the 2-dimensional case. In the above procedure, in each iteration the worst
include pattern search, Nelder-Mead simplex search [89], and methods with
adaptive search directions.
Nelder-Mead simplex method: The Nelder-Mead simplex method, also
known as the downhill simplex method, is probably the most well-known direct
search method. This method maintains a non-degenerate simplex during the
course of the search. A simplex is an n + 1 polytope in an n-dimension space.
For example, a simplex in the 2-dimensional space is a triangle and a simplex
in a 3-dimensional space is a tetrahedron. The algorithm first builds a simplex
around the initial solution, typically with it as one vertex and generating the
other n vertices by taking a step in one of the n parameters each. During an
iteration, it performs the following operations
1. Sorts the function values on the vertices. Label the vertices 1 through
n + 1 with the corresponding function values in the ascending order,
i.e., f 1 ≤ f 2 ≤ · · · ≤ f n+1 , where f i ≡ f (x i ) and x i is the i’th vertex.
Calculate the center point of the simplex face opposite to vertex x n+1
(which has the largest function value), x c ≡
1
n
n
i=1 x i . On the line
connecting x n+1 and x c , the following points are defined:
Reflection point: x r = x c + (x c − x n+1 ).
Expansion point: x e = x c + 2(x c − x n+1 ).
Inner contraction: x ic = x c −
1
2 (x c − x n+1 ).
Outer contraction: x oc = x c +
1
2 (x c − x n+1 ).
2. Reflection: Evaluate the function value at the reflection point, f r =
f (x r ). If the value at the reflection point is better than the second
worst, but not better than the best vertex, i.e., f 1 ≤ f r < f n , replace
vertex x n+1 with x r and finish the iteration.
3. Expansion: If the reflection point is better than the best vertex, i.e.,
f r < f 1 , evaluate the expansion point. Replace x n+1 with the better of
the reflection point and the expansion point and finish the iteration.
4. Outer contraction: If f n < f r < f n+1 , evaluate the outer contraction
point. If f oc = f (x oc ) < f r , replace vertex x n+1 with x oc and finish the
iteration.
5. Inner contraction: If f r > f n+1 , evaluate the inner contraction point. If
f ic = f (x ic ) < f r , replace vertex x n+1 with x ic and finish the iteration.
6. Shrink: If none of the above operations terminates the iteration, shrink
the size of the simplex toward the best vertex, x 1 , by replacing all other
vertices with x
i = x 1 +
1
2 (x i − x 1 ), with i = 2, 3, · · · , n + 1. Evaluate
the function values on all new vertices and go on to the next iteration.
The operations of the downhill simplex method are illustrated in Figure 7.2
for the 2-dimensional case. In the above procedure, in each iteration the worst