fminsearch Algorithm - MATLAB & Simulink (original) (raw)

fminsearch uses the Nelder-Mead simplex algorithm as described in Lagarias et al. [57]. This algorithm uses a simplex of n + 1 points for_n_-dimensional vectors x. The algorithm first makes a simplex around the initial guess _x_0 by adding 5% of each component_x_0(i) to_x_0, and using these n vectors as elements of the simplex in addition to_x_0. (The algorithm uses 0.00025 as component i if _x_0(i) = 0.) Then, the algorithm modifies the simplex repeatedly according to the following procedure.

Note

The keywords for the fminsearch iterative display appear in bold after the description of the step.

1. Let x(i) denote the list of points in the current simplex, i = 1,...,n + 1.
2. Order the points in the simplex from lowest function value_f_(x(1)) to highest_f_(x(n + 1)). At each step in the iteration, the algorithm discards the current worst point_x_(n + 1), and accepts another point into the simplex. [Or, in the case of step 7 below, it changes all_n_ points with values above_f_(x(1))].
3. Generate the reflected point
   r = 2_m_ –x(n + 1),
   where
   m = Σ_x_(i)/n, i = 1...n,
   and calculate f(r).
4. If f(x(1)) ≤ f(r) < f(x(n)), accept r and terminate this iteration. Reflect
5. If f(r) < f(x(1)), calculate the expansion point s
   s = m + 2(m – x(n + 1)),
   and calculate f(s).
   1. If f(s) < f(r), accept s and terminate the iteration. Expand
   2. Otherwise, accept r and terminate the iteration. Reflect
6. If f(r) ≥f(x(n)), perform a_contraction_ between m and either_x_(n + 1) or_r_, depending on which has the lower objective function value.
   1. If f(r) <f(x(n + 1)) (that is, r is better than_x_(n + 1)), calculate
      c = m + (r – m)/2
      and calculate f(c). If f(c) < f(r), accept c and terminate the iteration. Contract outside
      Otherwise, continue with Step 7 (Shrink).
   2. If f(r) ≥f(x(n + 1)), calculate
      cc = m + (x(n + 1) –m)/2
      and calculate f(cc). If f(cc) < f(x(n + 1)), accept cc and terminate the iteration. Contract inside
      Otherwise, continue with Step 7 (Shrink).
7. Calculate the n points
   v(i) = x(1) + (x(i) – x(1))/2
   and calculate f(v(i)),i = 2,...,n + 1. The simplex at the next iteration is x(1),v(2),...,v(n + 1).Shrink

The following figure shows the points that fminsearch might calculate in the procedure, along with each possible new simplex. The original simplex has a bold outline. The iterations proceed until they meet a stopping criterion.

See Also

fminsearch

Topics

• Unconstrained Nonlinear Optimization Algorithms