Class: Mopti::NelderMead

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/mopti/nelder_mead.rb

Overview

NelderMead is a class that implements multivariate optimization using the Nelder-Mead simplex method.

Reference

  1. Gao, F. and Han, L., “Implementing the Nelder-Mead simplex algorithm with adaptive parameters,” Computational Optimization and Applications, vol. 51 (1), pp. 259–277, 2012.

Examples:

require 'numo/narray'
require 'mopti'

args = Numo::DFloat[2, 3]

f = proc { |x, a| (8 * (x - a)**2).sum }

x0 = Numo::DFloat.zeros(2)

optimizer = Mopti::NelderMead.new(fnc: f, x_init: x0, args: args)
result = optimizer.map { |params| params }.last

pp result

# {:x=>Numo::DFloat(view)#shape=[2]
# [2, 3],
#  :n_fev=>165,
#  :n_iter=>84,
#  :fnc=>5.694864987422661e-13}

Instance Method Summary collapse

Constructor Details

#initialize(fnc:, x_init:, args: nil, max_iter: nil, xtol: 1e-6, ftol: 1e-6) ⇒ NelderMead

Create a new optimizer with the Nelder-Mead simplex method.

Parameters:

  • fnc (Method/Proc) —

    Method for calculating the objective function to be minimized.

  • args (Array/Hash) (defaults to: nil) —

    Arguments pass to the ‘fnc’ and ‘jcb’.

  • x_init (Numo::NArray) —

    Initial point.

  • max_iter (Integer) (defaults to: nil) —

    Maximum number of iterations. If nil is given, max_iter sets to 200 * number of dimensions.

  • xtol (Float) (defaults to: 1e-6) —

    Tolerance for termination for the optimal vector norm.

  • ftol (Float) (defaults to: 1e-6) —

    Tolerance for termination for the objective function value.



41
42
43
44
45
46
47
48
 
# File 'lib/mopti/nelder_mead.rb', line 41

def initialize(fnc:, x_init:, args: nil, max_iter: nil, xtol: 1e-6, ftol: 1e-6)
  @fnc = fnc
  @args = args
  @x_init = x_init
  @max_iter = max_iter
  @xtol = xtol
  @ftol = ftol
end

Instance Method Details

#each(&block) ⇒ Enumerator

Iteration for optimization.

Yields:

  • (Hash) —

    { x:, n_fev:, n_jev:, n_iter:, fnc:, jcb: }

    • x [Numo::NArray] Updated vector by optimization.

    • n_fev [Interger] Number of calls of the objective function.

    • n_iter [Integer] Number of iterations.

    • fnc [Float] Value of the objective function.

Returns:

  • (Enumerator) —

    If block is not given, this method returns Enumerator.



59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
 
# File 'lib/mopti/nelder_mead.rb', line 59

def each
  return to_enum(__method__) unless block_given?

  x = @x_init.dup
  n = x.size
  max_iter = @max_iter || 200 * n

  alpha = 1.0
  beta = n > 1 ? 1 + 2.fdiv(n) : 2.0
  gamma = n > 1 ? 0.75 - 1.fdiv(2 * n) : 0.5
  delta = n > 1 ? 1 - 1.fdiv(n) : 0.5

  sim = x.class.zeros(n + 1, n)
  sim[0, true] = x
  n.times do |k|
    y = x.dup
    y[k] = (y[k]).zero? ? ZERO_TAU : (1 + NON_ZERO_TAU) * y[k]
    sim[k + 1, true] = y
  end

  fsim = Numo::DFloat.zeros(n + 1)

  (n + 1).times { |k| fsim[k] = func(sim[k, true], @args) }
  n_fev = n + 1

  ind = fsim.sort_index
  fsim = fsim[ind].dup
  sim = sim[ind, true].dup

  n_iter = 0
  while n_iter < max_iter
    break if ((sim[1..-1, true] - sim[0, true]).abs.flatten.max <= @xtol) && ((fsim[0] - fsim[1..-1]).abs.max <= @ftol)

    xbar = sim[0...-1, true].sum(0) / n
    xr = xbar + alpha * (xbar - sim[-1, true])
    fr = func(xr, @args)
    n_fev += 1

    shrink = true
    if fr < fsim[0]
      xe = xbar + beta * (xr - xbar)
      fe = func(xe, @args)
      n_fev += 1
      shrink = false
      if fe < fr
        sim[-1, true] = xe
        fsim[-1] = fe
      else
        sim[-1, true] = xr
        fsim[-1] = fr
      end
    elsif fr < fsim[-2]
      shrink = false
      sim[-1, true] = xr
      fsim[-1] = fr
    elsif fr < fsim[-1]
      xoc = xbar + gamma * (xr - xbar)
      foc = func(xoc, @args)
      n_fev += 1
      if foc <= fr
        shrink = false
        sim[-1, true] = xoc
        fsim[-1] = foc
      end
    else
      xic = xbar - gamma * (xr - xbar)
      fic = func(xic, @args)
      n_fev += 1
      if fic < fsim[-1]
        shrink = false
        sim[-1, true] = xic
        fsim[-1] = fic
      end
    end

    if shrink
      (1..n).to_a.each do |j|
        sim[j, true] = sim[0, true] + delta * (sim[j, true] - sim[0, true])
        fsim[j] = func(sim[j, true], @args)
        n_fev += 1
      end
    end

    ind = fsim.sort_index
    sim = sim[ind, true].dup
    fsim = fsim[ind].dup

    n_iter += 1

    yield({ x: sim[0, true], n_fev: n_fev, n_iter: n_iter, fnc: fsim.min })
  end
end