Home · Pages · Index · Overviews

Function Minimization Module Reference

Minimization of functions of one or more variables, with and without a derivative/gradient. More...

 #include <fct.min.h>

Structures

  Minimum_Bundle : struct
lft : double
mid : double
rgt : double
A bracket for function minimization:
    lft < mid < rgt and f(mid) < f(lft), f(rgt)
 

Routines

Minimum_Bundle * Find_Min_Bracket (Minimum_Bundle *brack RM, double xin, double step,
                                                                                 double (*f)(double x))
double Minimize_Fct (Minimum_Bundle *brack, double (*f)(double x), double (*df)(double x))
Double_Vector * Powell_Minimizer (Double_Vector *xio RM, double step, double (*f)(double *x))
Double_Vector * Polak_Ribier_Minimizer (Double_Vector *xio RM, double (*f)(double *x),
                                                                                  double (*df)(double *x, double *g RO))

Detailed Description

This module contains numerical routines for finding a local minimum of a function. For functions of a single variable, the module provides a single routine Minimize_Fct that employs different strategies depending on whether you supply it with a function for the derivative. In either case, the function needs a triple of points that bracket a minimum, modeled by a Minimum_Bundle, that can be computed in the vicinity of a point of interest with Find_Min_Bracket.

For n-ary functions the module provides a separate routine Powell_Minimizer for finding a minimum without having an analytically computable gradient vector, and Polak_Ribier_Minimizer for find a minimum when supplied with such a gradient function.

The unary methods utilize the Golden section search accelerated with the parabolic interpolation method of Brent when possible (Press, Vetterling, Teukolsky and Flannery, Numerical Recipes in C (Cambridge University Press, 1992), Chapter 10.1-3). For a description of Powell's method see Chapter 10.5 of this reference, and for the Polak_Ribier method see Chapter 10.6.


Structure Documentation

Minimum_Bundle : struct
lft: double
mid: double
rgt: double

A bracket for minimization purposes is 3 points lft < mid < rgt that straddle at least one local minimum of the 1-dimensional function f in question. This is true if and only if f(mid) < f(lft) and f(mid < f(rgt).


Routine Documentation

Minimum_Bundle * Find_Min_Bracket (Minimum_Bundle *brack RM, double xin, double step,
                                                                                 double (*f)(double x))

Given a function f of one argument, a point xin, and a step size step, Find_Min_Bracket attempts to find a bracket about a minimum in the downhill direction from xin. Fill in the Minimum_Bundle with the bracket that is found and return a pointer to it for convenience. If a bracket cannot reasonably be found, then NULL is returned. It is generally a good idea to keep the step size small as it determines the jump sizes for the search, which can overshoot if it's too big.

double Minimize_Fct (Minimum_Bundle *brack, double (*f)(double x), double (*df)(double x))

Given a minimization bracket brack, Minimzie_Fct returns a point within the bracket at which a locally minimumal value of the unary function f is acheived. Accurate to first 8 digits (half double-precision). If the derivative of f, df, is NULL, then parabolic estimation is used to accelerate convergence, otherwise the secant method is employed. In the event df is used, one may take advantage of the fact that a call to df with a value x, always follows a prior call to f with the same value. So one may, via globally shared values, optimize the computation of f and df by sharing the computation of any common sub-expressions.

Double_Vector * Powell_Minimizer (Double_Vector *xio RM, double step, double (*f)(double *x))

Finds a minimum of the n-ary function f with Powell's method (that does not use the gradient of f). The dimensionality n is inferred from the size of xio. Start the search at the point xio with an initial set of n axis-oriented descent vectors of size step. The point at which the minimum is acheived is returned in the vector xio and a pointer to it is returned as a convenience.

Double_Vector * Polak_Ribier_Minimizer (Double_Vector *xio RM, double (*f)(double *x),
                                                                                  double (*df)(double *x, double *g RO))

Finds a point at which a minimum of the n-ary function f is acheived with the conjugate gradient method of Polak and Rabier (that does require the gradient of f). The search is started at point xio whose value will be the point at which the minimum is acheived upon completion of the search. Note carefully that the gradient function df, takes both the vector x at which the gradient is desired, and a vector g that will be returned holding the gradient value in each of the n directions. This is necessary so that g can be re-entrant, in keeping with all the functions in the library.