Function Minimization Module Reference
Minimization of functions of one or more variables, with and without a derivative/gradient.
More...
#include <fct.min.h>
Structures
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
• |
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
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.
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.
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.
|