Introduction to Optimization
Nelder-Mead Downhill Simplex Method
Download 229.98 Kb. Pdf ko'rish
|
0471671746.ch1
1.2.3
Nelder-Mead Downhill Simplex Method The development of computers spurred a flurry of activity in the 1960s. In 1965 Nelder and Mead introduced the downhill simplex method (Nelder and Mead, 1965), which doesn’t require the calculation of derivatives. A simplex is the most elementary geometrical figure that can be formed in dimension N and has N + 1 sides (e.g., a triangle in two-dimensional space). The downhill simplex method starts at N + 1 points that form the initial simplex. Only one point of the simplex, P 0 , is specified by the user. The other N points are found by (1.9) where e n are N unit vectors and c s is a scaling constant. The goal of this method is to move the simplex until it surrounds the minimum, and then to contract the simplex around the minimum until it is within an acceptable error. The steps used to trap the local minimum inside a small simplex are as follows: 1. Creation of the initial triangle. Three vertices start the algorithm: A = (x 1 ,y 1 ), B = (x 2 ,y 2 ), and C = (x 3 ,y 3 ) as shown in Figure 1.5. 2. Reflection. A new point, D = (x 4 ,y 4 ), is found as a reflection of the lowest minimum (in this case A) through the midpoint of the line connecting the other two points (B and C). As shown in Figure 1.5, D is found by (1.10) 3. Expansion. If the cost of D is smaller than that at A, then the move was in the right direction and another step is made in that same direction as shown in Figure 1.5. The formula is given by (1.11) E B C A = + ( ) - 3 2 2 D B C A = + - P P c e n s n = + 0 10 INTRODUCTION TO OPTIMIZATION 4. Contraction. If the new point, D, has the same cost as point A, then two new points are found (1.12) The smallest cost of F and G is kept, thus contracting the simplex as shown in Figure 1.5. 5. Shrinkage. If neither F nor G have smaller costs than A, then the side connecting A and C must move toward B in order to shrink the simplex. The new vertices are given by (1.13) Each iteration generates a new vertex for the simplex. If this new point is better than at least one of the existing vertices, it replaces the worst vertex. This way the diameter of the simplex gets smaller and the algorithm stops when the diameter reaches a specified tolerance. This algorithm is not known for its speed, but it has a certain robustness that makes it attractive. Figures 1.6 and 1.7 demonstrate the Nelder-Mead algorithm in action on a bowl- shaped surface. Note how the triangle gradually flops down the hill until it surrounds the bottom. The next step would be to shrink itself around the minimum. Since the Nelder-Mead algorithm gets stuck in local minima, it can be combined with the random search algorithm to find the minimum to (1.1) subject to (1.2). Assuming that there is no prior knowledge of the cost surface, a random first guess is as good as any place to start. How close H A B I B C = + = + 2 2 F A B C G B C A = + + = + ( ) - 2 4 3 2 2 MINIMUM-SEEKING ALGORITHMS Download 229.98 Kb. Do'stlaringiz bilan baham: |
Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling
ma'muriyatiga murojaat qiling