| 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 |
} |