One dimensional Minimization

This chapter describes routines for finding minima of arbitrary one-dimensional functions.

Contents:

  1. Introduction

  2. GSL::Min::FMinimizer class

  3. Iteration

  4. Stopping Parameters

  5. Examples

Introduction

The minimization algorithms begin with a bounded region known to contain a minimum. The region is described by a lower bound a and an upper bound b, with an estimate of the location of the minimum x.

The value of the function at x must be less than the value of the function at the ends of the interval,

f(a) > f(x) < f(b)

This condition guarantees that a minimum is contained somewhere within the interval. On each iteration a new point x' is selected using one of the available algorithms. If the new point is a better estimate of the minimum, f(x') < f(x), then the current estimate of the minimum x is updated. The new point also allows the size of the bounded interval to be reduced, by choosing the most compact set of points which satisfies the constraint f(a) > f(x) < f(b). The interval is reduced until it encloses the true minimum to a desired tolerance. This provides a best estimate of the location of the minimum and a rigorous error estimate.

Several bracketing algorithms are available within a single framework. The user provides a high-level driver for the algorithm, and the library provides the individual functions necessary for each of the steps. There are three main phases of the iteration. The steps are,

The state of the minimizers is held in a GSL::Min::FMinimizer object. The updating procedure use only function evaluations (not derivatives). The function to minimize is given as an instance of the GSL::Function class to the minimizer.

FMinimizer class





Iteration





Stopping Parameters


Example

To find the minimum of the function f(x) = cos(x) + 1.0:

#!/usr/bin/env ruby
require("gsl")
include GSL::Min

fn1 = Function.alloc { |x| Math::cos(x) + 1.0 }

iter = 0;  max_iter = 500
m = 2.0             # initial guess
m_expected = Math::PI
a = 0.0
b = 6.0

gmf = FMinimizer.alloc(FMinimizer::BRENT)
gmf.set(fn1, m, a, b)

printf("using %s method\n", gmf.name)
printf("%5s [%9s, %9s] %9s %10s %9s\n", "iter", "lower", "upper", "min",
       "err", "err(est)")

printf("%5d [%.7f, %.7f] %.7f %+.7f %.7f\n", iter, a, b, m, m - m_expected, b - a)

begin
  iter += 1
  status = gmf.iterate
  status = gmf.test_interval(0.001, 0.0)
  puts("Converged:") if status == GSL::SUCCESS
  a = gmf.x_lower
  b = gmf.x_upper
  m = gmf.x_minimum
  printf("%5d [%.7f, %.7f] %.7f %+.7f %.7f\n",
         iter, a, b, m, m - m_expected, b - a);
end while status == GSL::CONTINUE and iter < max_iter

prev next

Reference index top