The algorithm is stated using the term simplex (a generalized triangle in n dimensions) and will find the minimum of a function of n variables. It is effective and computationally compact.

**Initial Triangle**

Let * *be the function that is to be minimized. To start, we are given three vertices of a triangle: , for . The function * *is then evaluated at each of the three points: , for . The subscripts are then reordered so that . We use the notation

(1) , , and . to help remember that is the best vertex, is good (next to best), and is the worst vertex.

**Midpoint of the Good Side**

The construction process uses the midpoint of the line segment joining and . It is found by averaging the coordinates:

(2) .

**Reflection Using the Point **

The function decreases as we move along the side of the triangle from to , and it decreases as we move along the side from to. Hence it is feasible that * *takes on smaller values at points that lie away from on the opposite side of the line between and. We choose a test point that is obtained by “reflecting” the triangle through the side . To determine , we first find the midpoint of the side . Then draw the line segment from to and call its length d. This last segment is extended a distance d* *through to locate the point . The vector formula for is

(3) .

**Expansion Using the Point **

If the function value at is smaller than the function value at , then we have moved in the correct direction toward the minimum. Perhaps the minimum is just a bit farther than the point . So we extend the line segment through and to the point . This forms an expanded triangle . The point is found by moving an additional distance d* *along the line joining and . If the function value at is less than the function value at , then we have found a better vertex than . The vector formula for is

(4) .

**Contraction Using the Point **

If the function values at and are the same, another point must be tested. Perhaps the function is smaller at , but we cannot replace with because we must have a triangle. Consider the two midpoints and of the line segments ** **and , respectively. The point with the smaller function value is called , and the new triangle is .

Note: The choice between and might seem inappropriate for the two-dimensional case, but it is important in higher dimensions.

**Shrink Toward**

If the function value at is not less than the value at , the points and must be shrunk toward . The point is replaced with , and is replaced with , which is the midpoint of the line segment joining with .

**Logical Decisions for Each Step**

A computationally efficient algorithm should perform function evaluations only if needed. In each step, a new vertex is found, which replaces . As soon as it is found, further investigation is not needed, and the iteration step is completed. The logical details for two-dimensional cases are given in the proof.

## No comments:

## Post a Comment