min.texi

开放gsl矩阵运算

@cindex optimization, see minimization
@cindex maximization, see minimization
@cindex minimization, one-dimensional
@cindex finding minima
@cindex non-linear functions, minimization

This chapter describes routines for finding minima of arbitrary
one-dimensional functions.  The library provides low level components
for a variety of iterative minimizers and convergence tests.  These can be
combined by the user to achieve the desired solution, with full access
to the intermediate steps of the algorithms.  Each class of methods uses
the same framework, so that you can switch between minimizers at runtime
without needing to recompile your program.  Each instance of a minimizer
keeps track of its own state, allowing the minimizers to be used in
multi-threaded programs.

The header file @file{gsl_min.h} contains prototypes for the
minimization functions and related declarations.  To use the minimization
algorithms to find the maximum of a function simply invert its sign.

@menu
* Minimization Overview::       
* Minimization Caveats::        
* Initializing the Minimizer::  
* Providing the function to minimize::  
* Minimization Iteration::      
* Minimization Stopping Parameters::  
* Minimization Algorithms::     
* Minimization Examples::       
* Minimization References and Further Reading::  
@end menu

@node Minimization Overview
@section Overview
@cindex minimization, overview

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

@iftex
@sp 1
@center @image{min-interval}
@end iftex

@noindent
The value of the function at @math{x} must be less than the value of the
function at the ends of the interval,

@iftex
@tex
$$f(a) > f(x) < f(b)$$
@end tex
@end iftex
@ifinfo
@example
f(a) > f(x) < f(b)
@end example
@end ifinfo

@noindent
This condition guarantees that a minimum is contained somewhere within
the interval.  On each iteration a new point @math{x'} is selected using
one of the available algorithms.  If the new point is a better estimate
of the minimum, @math{f(x') < f(x)}, then the current estimate of the
minimum @math{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 @math{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,

@itemize @bullet
@item
initialize minimizer state, @var{s}, for algorithm @var{T}

@item
update @var{s} using the iteration @var{T}

@item
test @var{s} for convergence, and repeat iteration if necessary
@end itemize

@noindent
The state for the minimizers is held in a @code{gsl_min_fminimizer}
struct.  The updating procedure uses only function evaluations (not
derivatives).

@node Minimization Caveats
@section Caveats
@cindex Minimization, caveats

Note that minimization functions can only search for one minimum at a
time.  When there are several minima in the search area, the first
minimum to be found will be returned; however it is difficult to predict
which of the minima this will be. @emph{In most cases, no error will be
reported if you try to find a minimum in an area where there is more
than one.}

With all minimization algorithms it can be difficult to determine the
location of the minimum to full numerical precision.  The behavior of the
function in the region of the minimum @math{x^*} can be approximated by
a Taylor expansion,

@iftex
@tex
$$
y = f(x^*) + {1 \over 2} f''(x^*) (x - x^*)^2
$$
@end tex
@end iftex
@ifinfo
@example
y = f(x^*) + (1/2) f''(x^*) (x - x^*)^2
@end example
@end ifinfo

@noindent
and the second term of this expansion can be lost when added to the
first term at finite precision.  This magnifies the error in locating
@math{x^*}, making it proportional to @math{\sqrt \epsilon} (where
@math{\epsilon} is the relative accuracy of the floating point numbers).
For functions with higher order minima, such as @math{x^4}, the
magnification of the error is correspondingly worse.  The best that can
be achieved is to converge to the limit of numerical accuracy in the
function values, rather than the location of the minimum itself.

@node Initializing the Minimizer
@section Initializing the Minimizer

@deftypefun {gsl_min_fminimizer *} gsl_min_fminimizer_alloc (const gsl_min_fminimizer_type * @var{T})
This function returns a pointer to a a newly allocated instance of a
minimizer of type @var{T}.  For example, the following code
creates an instance of a golden section minimizer,

@example
const gsl_min_fminimizer_type * T 
  = gsl_min_fminimizer_goldensection;
gsl_min_fminimizer * s 
  = gsl_min_fminimizer_alloc (T);
@end example

If there is insufficient memory to create the minimizer then the function
returns a null pointer and the error handler is invoked with an error
code of @code{GSL_ENOMEM}.
@end deftypefun

@deftypefun int gsl_min_fminimizer_set (gsl_min_fminimizer * @var{s}, gsl_function * @var{f}, double @var{minimum}, double @var{x_lower}, double @var{x_upper})
This function sets, or resets, an existing minimizer @var{s} to use the
function @var{f} and the initial search interval [@var{x_lower},
@var{x_upper}], with a guess for the location of the minimum
@var{minimum}.

If the interval given does not contain a minimum, then the function
returns an error code of @code{GSL_FAILURE}.
@end deftypefun

@deftypefun int gsl_min_fminimizer_set_with_values (gsl_min_fminimizer * @var{s}, gsl_function * @var{f}, double @var{minimum}, double @var{f_minimum}, double @var{x_lower}, double @var{f_lower}, double @var{x_upper}, double @var{f_upper})
This function is equivalent to @code{gsl_min_fminimizer_set} but uses
the values @var{f_minimum}, @var{f_lower} and @var{f_upper} instead of
computing @code{f(minimum)}, @code{f(x_lower)} and @code{f(x_upper)}.
@end deftypefun


@deftypefun void gsl_min_fminimizer_free (gsl_min_fminimizer * @var{s})
This function frees all the memory associated with the minimizer
@var{s}.
@end deftypefun

@deftypefun {const char *} gsl_min_fminimizer_name (const gsl_min_fminimizer * @var{s})
This function returns a pointer to the name of the minimizer.  For example,

@example
printf("s is a '%s' minimizer\n",
       gsl_min_fminimizer_name (s));
@end example

@noindent
would print something like @code{s is a 'brent' minimizer}.
@end deftypefun

@node Providing the function to minimize
@section Providing the function to minimize
@cindex minimization, providing a function to minimize

You must provide a continuous function of one variable for the
minimizers to operate on.  In order to allow for general parameters the
functions are defined by a @code{gsl_function} data type
(@pxref{Providing the function to solve}).

@node Minimization Iteration
@section Iteration

The following functions drive the iteration of each algorithm.  Each
function performs one iteration to update the state of any minimizer of the
corresponding type.  The same functions work for all minimizers so that
different methods can be substituted at runtime without modifications to
the code.

@deftypefun int gsl_min_fminimizer_iterate (gsl_min_fminimizer * @var{s})
This function performs a single iteration of the minimizer @var{s}.  If the
iteration encounters an unexpected problem then an error code will be
returned,

@table @code
@item GSL_EBADFUNC
the iteration encountered a singular point where the function evaluated
to @code{Inf} or @code{NaN}.

@item GSL_FAILURE
the algorithm could not improve the current best approximation or
bounding interval.
@end table
@end deftypefun

The minimizer maintains a current best estimate of the minimum at all
times, and the current interval bounding the minimum.  This information
can be accessed with the following auxiliary functions,

@deftypefun double gsl_min_fminimizer_minimum (const gsl_min_fminimizer * @var{s})
This function returns the current estimate of the minimum for the minimizer
@var{s}.
@end deftypefun

@deftypefun double gsl_interval gsl_min_fminimizer_x_upper (const gsl_min_fminimizer * @var{s})
@deftypefunx double gsl_interval gsl_min_fminimizer_x_lower (const gsl_min_fminimizer * @var{s})
These functions return the current upper and lower bound of the interval
for the minimizer @var{s}.
@end deftypefun