Debian Codegraph @

query/neldermead/neldermead.go

raw
1 // Package neldermead is an implementation of the Nelder-Mead optimization method.
2 // Based on work by Michael F. Hutt: http://www.mikehutt.com/neldermead.html
3 package neldermead
4
5 import "math"
6
7 const (
8 defaultMaxIterations = 1000
9 // reflection coefficient
10 defaultAlpha = 1.0
11 // contraction coefficient
12 defaultBeta = 0.5
13 // expansion coefficient
14 defaultGamma = 2.0
15 )
16
17 // Optimizer represents the parameters to the Nelder-Mead simplex method.
18 type Optimizer struct {
19 // Maximum number of iterations.
20 MaxIterations int
21 // Reflection coefficient.
22 Alpha,
23 // Contraction coefficient.
24 Beta,
25 // Expansion coefficient.
26 Gamma float64
27 }
28
29 // New returns a new instance of Optimizer with all values set to the defaults.
30 func New() *Optimizer {
31 return &Optimizer{
32 MaxIterations: defaultMaxIterations,
33 Alpha: defaultAlpha,
34 Beta: defaultBeta,
35 Gamma: defaultGamma,
36 }
37 }
38
39 // Optimize applies the Nelder-Mead simplex method with the Optimizer's settings.
40 func (o *Optimizer) Optimize(
41 objfunc func([]float64) float64,
42 start []float64,
43 epsilon,
44 scale float64,
45 ) (float64, []float64) {
46 n := len(start)
47
48 //holds vertices of simplex
49 v := make([][]float64, n+1)
50 for i := range v {
51 v[i] = make([]float64, n)
52 }
53
54 //value of function at each vertex
55 f := make([]float64, n+1)
56
57 //reflection - coordinates
58 vr := make([]float64, n)
59
60 //expansion - coordinates
61 ve := make([]float64, n)
62
63 //contraction - coordinates
64 vc := make([]float64, n)
65
66 //centroid - coordinates
67 vm := make([]float64, n)
68
69 // create the initial simplex
70 // assume one of the vertices is 0,0
71
72 pn := scale * (math.Sqrt(float64(n+1)) - 1 + float64(n)) / (float64(n) * math.Sqrt(2))
73 qn := scale * (math.Sqrt(float64(n+1)) - 1) / (float64(n) * math.Sqrt(2))
74
75 for i := 0; i < n; i++ {
76 v[0][i] = start[i]
77 }
78
79 for i := 1; i <= n; i++ {
80 for j := 0; j < n; j++ {
81 if i-1 == j {
82 v[i][j] = pn + start[j]
83 } else {
84 v[i][j] = qn + start[j]
85 }
86 }
87 }
88
89 // find the initial function values
90 for j := 0; j <= n; j++ {
91 f[j] = objfunc(v[j])
92 }
93
94 // begin the main loop of the minimization
95 for itr := 1; itr <= o.MaxIterations; itr++ {
96
97 // find the indexes of the largest and smallest values
98 vg := 0
99 vs := 0
100 for i := 0; i <= n; i++ {
101 if f[i] > f[vg] {
102 vg = i
103 }
104 if f[i] < f[vs] {
105 vs = i
106 }
107 }
108 // find the index of the second largest value
109 vh := vs
110 for i := 0; i <= n; i++ {
111 if f[i] > f[vh] && f[i] < f[vg] {
112 vh = i
113 }
114 }
115
116 // calculate the centroid
117 for i := 0; i <= n-1; i++ {
118 cent := 0.0
119 for m := 0; m <= n; m++ {
120 if m != vg {
121 cent += v[m][i]
122 }
123 }
124 vm[i] = cent / float64(n)
125 }
126
127 // reflect vg to new vertex vr
128 for i := 0; i <= n-1; i++ {
129 vr[i] = vm[i] + o.Alpha*(vm[i]-v[vg][i])
130 }
131
132 // value of function at reflection point
133 fr := objfunc(vr)
134
135 if fr < f[vh] && fr >= f[vs] {
136 for i := 0; i <= n-1; i++ {
137 v[vg][i] = vr[i]
138 }
139 f[vg] = fr
140 }
141
142 // investigate a step further in this direction
143 if fr < f[vs] {
144 for i := 0; i <= n-1; i++ {
145 ve[i] = vm[i] + o.Gamma*(vr[i]-vm[i])
146 }
147
148 // value of function at expansion point
149 fe := objfunc(ve)
150
151 // by making fe < fr as opposed to fe < f[vs],
152 // Rosenbrocks function takes 63 iterations as opposed
153 // to 64 when using double variables.
154
155 if fe < fr {
156 for i := 0; i <= n-1; i++ {
157 v[vg][i] = ve[i]
158 }
159 f[vg] = fe
160 } else {
161 for i := 0; i <= n-1; i++ {
162 v[vg][i] = vr[i]
163 }
164 f[vg] = fr
165 }
166 }
167
168 // check to see if a contraction is necessary
169 if fr >= f[vh] {
170 if fr < f[vg] && fr >= f[vh] {
171 // perform outside contraction
172 for i := 0; i <= n-1; i++ {
173 vc[i] = vm[i] + o.Beta*(vr[i]-vm[i])
174 }
175 } else {
176 // perform inside contraction
177 for i := 0; i <= n-1; i++ {
178 vc[i] = vm[i] - o.Beta*(vm[i]-v[vg][i])
179 }
180 }
181
182 // value of function at contraction point
183 fc := objfunc(vc)
184
185 if fc < f[vg] {
186 for i := 0; i <= n-1; i++ {
187 v[vg][i] = vc[i]
188 }
189 f[vg] = fc
190 } else {
191 // at this point the contraction is not successful,
192 // we must halve the distance from vs to all the
193 // vertices of the simplex and then continue.
194
195 for row := 0; row <= n; row++ {
196 if row != vs {
197 for i := 0; i <= n-1; i++ {
198 v[row][i] = v[vs][i] + (v[row][i]-v[vs][i])/2.0
199 }
200 }
201 }
202 f[vg] = objfunc(v[vg])
203 f[vh] = objfunc(v[vh])
204 }
205 }
206
207 // test for convergence
208 fsum := 0.0
209 for i := 0; i <= n; i++ {
210 fsum += f[i]
211 }
212 favg := fsum / float64(n+1)
213 s := 0.0
214 for i := 0; i <= n; i++ {
215 s += math.Pow((f[i]-favg), 2.0) / float64(n)
216 }
217 s = math.Sqrt(s)
218 if s < epsilon {
219 break
220 }
221 }
222
223 // find the index of the smallest value
224 vs := 0
225 for i := 0; i <= n; i++ {
226 if f[i] < f[vs] {
227 vs = i
228 }
229 }
230
231 parameters := make([]float64, n)
232 for i := 0; i < n; i++ {
233 parameters[i] = v[vs][i]
234 }
235
236 min := objfunc(v[vs])
237
238 return min, parameters
239 }