Optimization: principles and algorithms, by Michel Bierlaire
Go to the documentation of this file.
1 %> \file
2 %> Algorithm 15.1: Nelder-Mead algorithm. Implementation of algorithm 15.1 of \cite Bier15-book
3 %>
4 %> @note Tested with \ref run1502nelderMead.m
5 %> @note Tested with \ref run1503nelderMead.m
6 %>
7 %> @author Michel Bierlaire
8 %> @date Sat Mar 21 18:23:57 2015
9 %> @ingroup Algorithms
10 %> @ingroup chap15
11
12 %> Applies the Nelder-Mead algorithm to solve \f$\min_x f(x)\f$ where \f$f:\mathbb{R}^n\to\mathbb{R}\f$.
13 %> @param obj the name of the Octave function defining f(x)
14 %> @param x0 matrix nx(n+1) containnig the initial simplex
15 %> @param eps algorithm stops if \f$\|d_k\| \leq \varepsilon \f$.
16 %> @param maxiter maximum number of iterations (Default: 100)
17 %> @return [solution,simplex]: the solution and the final simplex.
19  x = x0 ;
20  [n,m] = size(x0) ;
21  if (m != n+1)
22  error("Incorrect size") ;
23  endif
24
25  iter = 0 ;
26  do
27  iter = iter + 1 ;
28  f = [] ;
29  for k = 1:n+1
30  f = [ f ; feval(obj,x(:,k)) ] ;
31  endfor
32
33  ## Worst value
34  [worst,worstindex] = max(f) ;
35  ## Best value
36  [best,bestindex] = min(f) ;
37  tmp = f ;
38  tmp(worstindex) = best - 10.0 ;
39  xworst = x(:,worstindex) ;
40  [secondworst,secondworstindex] = max(tmp) ;
41
42  xc = (sum(x,2) - xworst) / n;
43  d = xc - x(:,worstindex) ;
44  xr = 2 * xc - xworst ;
45  fxr = feval(obj,xr) ;
46  if (fxr < best)
47  xe = 2 * xr - xc ;
48  fxe = feval(obj,xe) ;
49  if (fxe < fxr)
50  xnew = xe ;
51  else
52  xnew = xr ;
53  endif
54  else
55  if (secondworst > fxr)
56  xnew = xr ;
57  else
58  if (fxr >= worst)
59  xnew = 0.5 * (xworst + xc) ;
60  else
61  xnew = 0.5 * (xr + xc) ;
62  endif
63  endif
64  endif
65  fxnew = feval(obj,xnew) ;
66  printf("%d\t",iter) ;
67  for k = 1:n+1
68  printf("%e\t",x(1,k))
69  endfor
70  printf("%e\t",xr(1)) ;
71  printf("%e\n",xnew(1)) ;
72  printf("\t") ;
73  for k = 1:n+1
74  printf("%e\t",x(2,k))
75  endfor
76  printf("%e\t",xr(2)) ;
77  printf("%e\n",xnew(2)) ;
78  printf("---------------------\n") ;
79  printf("f\t") ;
80  for k = 1:n+1
81  printf("%e\t",f(k))
82  endfor
83  printf("%e\t",fxr) ;
84  printf("%e\n",fxnew) ;
85  printf("---------------------\n") ;
86  x(:,worstindex) = xnew ;
87
88  until (norm(d) < eps || iter >= maxiter)
89  solution = x(:,bestindex) ;
90  simplex = x ;
91 endfunction
function nelderMead(in obj, in x0, in eps, in maxiter)
Applies the Nelder-Mead algorithm to solve where .
function simplex(in A, in b, in c, in basis)
Applies the simplex method to solve subject to and , where , , and .