Class: Minimization::Powell

Inherits:
ConjugateDirectionMinimizer show all
Defined in:
lib/multidim/powell.rb

Overview

Powell’s Minimizer.

A multidimensional minimization methods

Usage.

require 'minimization'
f = proc{ |x| (x[0] - 1)**2 + (2*x[1] - 5)**2 + (x[2]-3.3)**2}
min = Minimization::Powell.minimize(f, [1, 2, 3], [0, 0, 0], [5, 5, 5])
min.f_minimum
min.x_minimum

Constant Summary collapse

RELATIVE_THRESHOLD_DEFAULT =

default of relative threshold

0.1
ABSOLUTE_THRESHOLD_DEFAULT =

default of absolute threshold

0.1

Constants inherited from ConjugateDirectionMinimizer

ConjugateDirectionMinimizer::MAX_BRENT_ITERATION_DEFAULT, ConjugateDirectionMinimizer::Max_Iterations_Default

Instance Attribute Summary collapse

Attributes inherited from ConjugateDirectionMinimizer

#f_minimum, #max_brent_iterations, #max_iterations, #x_minimum

Class Method Summary collapse

Instance Method Summary collapse

Methods inherited from ConjugateDirectionMinimizer

#brent_search, #check_parameters, #converging?, #f

Constructor Details

#initialize(f, initial_guess, lower_bound, upper_bound) ⇒ Powell

Parameters:

  • f: Minimization function

  • initial_guess: Initial position of Minimization

  • lower_bound: Lower bound of the minimization

  • upper_bound: Upper bound of the minimization



169
170
171
172
173
 
# File 'lib/multidim/powell.rb', line 169

def initialize(f, initial_guess, lower_bound, upper_bound)
  super(f, initial_guess.clone, lower_bound, upper_bound)
  @relative_threshold = RELATIVE_THRESHOLD_DEFAULT
  @absolute_threshold = ABSOLUTE_THRESHOLD_DEFAULT
end

Instance Attribute Details

#absolute_threshold ⇒ Object

Returns the value of attribute absolute_threshold.



156
157
158
 
# File 'lib/multidim/powell.rb', line 156

def absolute_threshold
  @absolute_threshold
end

#relative_threshold ⇒ Object

Returns the value of attribute relative_threshold.



155
156
157
 
# File 'lib/multidim/powell.rb', line 155

def relative_threshold
  @relative_threshold
end

Class Method Details

.minimize(f, starting_point, lower_bound, upper_bound) ⇒ Object

Convenience method to minimize

Parameters:

  • f: Function to minimize

  • starting_point: starting point

  • lower_bound: Lowest possible values of each direction

  • upper_bound: Highest possible values of each direction

Usage:

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



310
311
312
313
314
315
316
 
# File 'lib/multidim/powell.rb', line 310

def self.minimize(f, starting_point, lower_bound, upper_bound)
  min = Minimization::Powell.new(f, starting_point, lower_bound, upper_bound)
  while min.converging?
    min.iterate
  end
  return min
end

Instance Method Details

#iterate ⇒ Object

Iterate Powell’s minimizer one step

Parameters:

  • f: Function to minimize

  • starting_point: starting point

  • lower_bound: Lowest possible values of each direction

  • upper_bound: Highest possible values of each direction

Usage:

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



208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
 
# File 'lib/multidim/powell.rb', line 208

def iterate 
  @iterations += 1

  # set initial configurations
  if(@iterations <= 1)
    guess = @start
    @n     = guess.length
    # initialize all to 0
    @direc = Array.new(@n) { Array.new(@n) {0} }
    0.upto(@n - 1) do |i|
      # set diagonal values to 1
      @direc[i][i] = 1
    end

    @x     = guess
    @f_val = f(@x)
    @x1    = @x.clone
  end

  fx        = @f_val
  fx2       = 0
  delta     = 0
  big_ind   = 0
  alpha_min = 0

  0.upto(@n - 1) do |i|
    direction = @direc[i].clone
    fx2       = @f_val
    # Find line minimum
    minimum   = brent_search(@x, direction)
    @f_val    = minimum[:f_val]
    alpha_min = minimum[:alpha_min]
    # Obtain new point and direction
    new_pnd   = new_point_and_direction(@x, direction, alpha_min)
    new_point = new_pnd[:point]
    new_dir   = new_pnd[:dir]
    @x         = new_point

    if ((fx2 - @f_val) > delta) 
      delta   = fx2 - @f_val
      big_ind = i
    end
  end

  # convergence check
  @converging = !(2 * (fx - @f_val) <= (@relative_threshold * (fx.abs + @f_val.abs) + @absolute_threshold))

  # storing results
  if((@f_val < fx))
    @x_minimum = @x
    @f_minimum = @f_val
  else
    @x_minimum = @x1
    @f_minimum = fx
  end

  direction  = Array.new(@n)
  x2         = Array.new(@n)
  0.upto(@n -1) do |i|
    direction[i]  = @x[i] - @x1[i]
    x2[i]         = 2 * @x[i] - @x1[i]
  end

  @x1  = @x.clone
  fx2 = f(x2)

  if (fx > fx2)
    t    = 2 * (fx + fx2 - 2 * @f_val)
    temp = fx - @f_val - delta
    t   *= temp * temp
    temp = fx - fx2
    t   -= delta * temp * temp

    if (t < 0.0)
      minimum   = brent_search(@x, direction)
      @f_val     = minimum[:f_val]
      alpha_min = minimum[:alpha_min]
      # Obtain new point and direction
      new_pnd   = new_point_and_direction(@x, direction, alpha_min)
      new_point = new_pnd[:point]
      new_dir   = new_pnd[:dir]
      @x         = new_point

      last_ind        = @n - 1
      @direc[big_ind]  = @direc[last_ind]
      @direc[last_ind] = new_dir
    end
  end
end

#new_point_and_direction(point, direction, minimum) ⇒ Object

Obtain new point and direction from the previous point, previous direction and a parameter value

Parameters:

  • point: Previous point

  • direction: Previous direction

  • minimum: parameter value



182
183
184
185
186
187
188
189
190
191
 
# File 'lib/multidim/powell.rb', line 182

def new_point_and_direction(point, direction, minimum)
  n         = point.length
  new_point = Array.new(n)
  new_dir   = Array.new(n)
  0.upto(n - 1) do |i|
    new_dir[i]   = direction[i] * minimum
    new_point[i] = point[i] + new_dir[i]
  end
  return {:point => new_point, :dir => new_dir}
end