Class: Minimization::DirectSearchMinimizer

Inherits:
Object
  • Object
show all
Defined in:
lib/multidim/nelder_mead.rb

Direct Known Subclasses

NelderMead

Constant Summary collapse

EPSILON_DEFAULT = 
1e-6
MAX_ITERATIONS_DEFAULT = 
1000000

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(f, start_point, iterate_simplex_ref) ⇒ DirectSearchMinimizer

Returns a new instance of DirectSearchMinimizer.



38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
 
# File 'lib/multidim/nelder_mead.rb', line 38

def initialize(f, start_point, iterate_simplex_ref)
  @epsilon             = EPSILON_DEFAULT
  # Default number of maximum iterations
  @max_iterations      = MAX_ITERATIONS_DEFAULT
  # proc which iterates the simplex
  @iterate_simplex_ref = iterate_simplex_ref
  @relative_threshold  = 100 * @epsilon
  @absolute_threshold  = @epsilon
  @x_minimum           = nil
  @f_minimum           = nil
  @f = f

  # create and initializ start configurations
  if @start_configuration == nil
    # sets the start configuration point as unit
    self.start_configuration = Array.new(start_point.length) { 1.0 }
  end

  @iterations  = 0
  @evaluations = 0
  # create the simplex for the first time
  build_simplex(start_point)
  evaluate_simplex
end

Instance Attribute Details

#epsilon ⇒ Object (readonly)

Returns the value of attribute epsilon.



36
37
38
 
# File 'lib/multidim/nelder_mead.rb', line 36

def epsilon
  @epsilon
end

#f_minimum ⇒ Object (readonly)

Returns the value of attribute f_minimum.



35
36
37
 
# File 'lib/multidim/nelder_mead.rb', line 35

def f_minimum
  @f_minimum
end

#x_minimum ⇒ Object (readonly)

Returns the value of attribute x_minimum.



34
35
36
 
# File 'lib/multidim/nelder_mead.rb', line 34

def x_minimum
  @x_minimum
end

Class Method Details

.minimize(f, start_point) ⇒ Object

Convenience method to minimize

Parameters:

  • start_point: Starting points

  • f: Function to minimize

Usage:

minimizer=Minimization::NelderMead.minimize(proc{|x| (x[0] - 1) ** 2 + (x[1] - 5) ** 2}, [0, 0])



186
187
188
189
190
191
192
 
# File 'lib/multidim/nelder_mead.rb', line 186

def self.minimize(f, start_point)
  min=Minimization::NelderMead.new(f, start_point)
  while min.converging?
    min.iterate
  end
  return min
end

Instance Method Details

#build_simplex(start_point) ⇒ Object

Build an initial simplex

Parameters:

  • start_point: starting point of the minimization search



133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
 
# File 'lib/multidim/nelder_mead.rb', line 133

def build_simplex(start_point)
  n = start_point.length
  raise "dimension mismatch" if n != @start_configuration.length
  # set first vertex
  @simplex = Array.new(n+1)
  @simplex[0] = PointValuePair.new(start_point, Float::NAN)

  # set remaining vertices
  0.upto(n - 1) do |i|
    conf_i   = @start_configuration[i]
    vertex_i = Array.new(n)
    0.upto(n - 1) do |k|
      vertex_i[k] = start_point[k] + conf_i[k]
    end
    @simplex[i + 1] = PointValuePair.new(vertex_i, Float::NAN)
  end
end

#compare(v1, v2) ⇒ Object

compares 2 PointValuePair points



78
79
80
81
82
83
84
85
86
 
# File 'lib/multidim/nelder_mead.rb', line 78

def compare(v1, v2)
  if v1.value == v2.value
    return 0
  elsif v1.value > v2.value
    return 1
  else
    return -1
  end
end

#converging? ⇒ Boolean

checks whether the function is converging

Returns:

  • (Boolean) 


89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
 
# File 'lib/multidim/nelder_mead.rb', line 89

def converging?
  # check the convergence in a given direction comparing the previous and current values
  def point_converged?(previous, current)
    pre        = previous.value
    curr       = current.value
    diff       = (pre - curr).abs
    size       = [pre.abs, curr.abs].max
    return !((diff <= (size * @relative_threshold)) and (diff <= @absolute_threshold))
  end

  # returns true if converging is possible atleast in one direction
  if @iterations > 0
    # given direction is converged
    converged = true
    0.upto(@simplex.length - 1) do |i|
      converged &= !point_converged?(@previous[i], @simplex[i])
    end
    return !converged
  end

  # if no iterations were done, convergence undefined
  return true
end

#evaluate_simplex ⇒ Object

Evaluate all the non-evaluated points of the simplex



152
153
154
155
156
157
158
159
160
161
162
163
 
# File 'lib/multidim/nelder_mead.rb', line 152

def evaluate_simplex
  # evaluate the objective function at all non-evaluated simplex points
  0.upto(@simplex.length - 1) do |i|
    vertex = @simplex[i]
    point  = vertex.point
    if vertex.value.nan?
      @simplex[i] = PointValuePair.new(point, f(point))
    end
  end
  # sort the simplex from best to worst
  @simplex.sort!{ |x1, x2| x1.value <=> x2.value }
end

#f(x) ⇒ Object 



63
64
65
 
# File 'lib/multidim/nelder_mead.rb', line 63

def f(x)
  return @f.call(x)
end

#increment_iterations_counter ⇒ Object

increment iteration counter by 1



72
73
74
75
 
# File 'lib/multidim/nelder_mead.rb', line 72

def increment_iterations_counter
  @iterations += 1
  raise "iteration limit reached" if @iterations > @max_iterations
end

#iterate ⇒ Object

Iterate the simplex one step. Use this when iteration needs to be done manually

Usage:

minimizer=Minimization::NelderMead.new(proc{|x| (x[0] - 1) ** 2 + (x[1] - 5) ** 2}, [0, 0])
while minimizer.converging?
  minimizer.Iterate
end
minimizer.x_minimum
minimizer.f_minimum



203
204
205
206
207
208
209
210
211
212
213
214
215
 
# File 'lib/multidim/nelder_mead.rb', line 203

def iterate
  # set previous simplex as the current simplex
  @previous = Array.new(@simplex.length)
  0.upto(@simplex.length - 1) do |i|
    point = @simplex[i].point                                # clone require?
    @previous[i] = PointValuePair.new(point, f(point))
  end
  # iterate simplex
  iterate_simplex
  # set results
  @x_minimum = @simplex[0].point
  @f_minimum = @simplex[0].value
end

#iterate_simplex ⇒ Object 



67
68
69
 
# File 'lib/multidim/nelder_mead.rb', line 67

def iterate_simplex
  return iterate_simplex_ref.call
end

#point_converged?(previous, current) ⇒ Boolean

check the convergence in a given direction comparing the previous and current values

Returns:

  • (Boolean) 


91
92
93
94
95
96
97
 
# File 'lib/multidim/nelder_mead.rb', line 91

def point_converged?(previous, current)
  pre        = previous.value
  curr       = current.value
  diff       = (pre - curr).abs
  size       = [pre.abs, curr.abs].max
  return !((diff <= (size * @relative_threshold)) and (diff <= @absolute_threshold))
end

#replace_worst_point(point_value_pair) ⇒ Object

Replace the worst point of the simplex by a new point

Parameters:

  • point_value_pair: point to insert



169
170
171
172
173
174
175
176
177
 
# File 'lib/multidim/nelder_mead.rb', line 169

def replace_worst_point(point_value_pair)
  n = @simplex.length - 1
  0.upto(n - 1) do |i|
    if (compare(@simplex[i], point_value_pair) > 0)
      point_value_pair, @simplex[i] = @simplex[i], point_value_pair
    end
  end
  @simplex[n] = point_value_pair
end

#start_configuration=(steps) ⇒ Object

only the relative position of the n vertices with respect to the first one are stored



115
116
117
118
119
120
121
122
123
124
125
126
127
 
# File 'lib/multidim/nelder_mead.rb', line 115

def start_configuration=(steps)
  n = steps.length
  @start_configuration = Array.new(n) { Array.new(n, 0) }
  0.upto(n - 1) do |i|
    vertex_i = @start_configuration[i]
    0.upto(i) do |j|
      raise "equals vertices #{j} and #{j+1} in simplex configuration" if steps[j] == 0.0
      0.upto(j) do |k|
        vertex_i[k] = steps[k]
      end
    end
  end
end