multimin.texi

开放gsl矩阵运算

@cindex minimization, multidimensional

This chapter describes routines for finding minima of arbitrary
multidimensional 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, while providing
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 minimization
algorithms can be used to maximize a function by inverting its sign.

The header file @file{gsl_multimin.h} contains prototypes for the
minimization functions and related declarations.  

@menu
* Multimin Overview::       
* Multimin Caveats::        
* Initializing the Multidimensional Minimizer::  
* Providing a function to minimize::  
* Multimin Iteration::      
* Multimin Stopping Criteria::  
* Multimin Algorithms::     
* Multimin Examples::       
* Multimin References and Further Reading::  
@end menu

@node Multimin Overview
@section Overview

The problem of multidimensional minimization requires finding a point
@math{x} such that the scalar function,

@tex
\beforedisplay
$$
f(x_1, \dots, x_n)
$$
\afterdisplay
@end tex
@ifinfo
@example
f(x_1, @dots{}, x_n)
@end example
@end ifinfo
@noindent
takes a value which is lower than at any neighboring point. For smooth
functions the gradient @math{g = \nabla f} vanishes at the minimum. In
general there are no bracketing methods available for the minimization
of @math{n}-dimensional functions.  All algorithms proceed from an
initial guess using a search algorithm which attempts to move in a
downhill direction. A one-dimensional line minimisation is performed
along this direction until the lowest point is found to a suitable
tolerance. The search direction is then updated with local information
from the function and its derivatives, and the whole process repeated
until the true @math{n}-dimensional minimum is found.

Several minimization algorithms are available within a single
framework. The user provides a high-level driver for the algorithms, 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
Each iteration step consists either of an improvement to the
line-mimisation in the current direction or an update to the search
direction itself.  The state for the minimizers is held in a
@code{gsl_multimin_fdfminimizer} struct.

@node Multimin Caveats
@section Caveats
@cindex Multimin, caveats

Note that the minimization algorithms can only search for one local
minimum at a time.  When there are several local 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.  In most cases,
no error will be reported if you try to find a local minimum in an area
where there is more than one.

It is also important to note that the minimization algorithms find local
minima; there is no way to determine whether a minimum is a global
minimum of the function in question.

@node Initializing the Multidimensional Minimizer
@section Initializing the Multidimensional Minimizer

The following function initializes a multidimensional minimizer.  The
minimizer itself depends only on the dimension of the problem and the
algorithm and can be reused for different problems.

@deftypefun {gsl_multimin_fdfminimizer *} gsl_multimin_fdfminimizer_alloc (const gsl_multimin_fdfminimizer_type *@var{T}, size_t @var{n})
This function returns a pointer to a a newly allocated instance of a
minimizer of type @var{T} for an @var{n}-dimension function.  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_multimin_fdfminimizer_set (gsl_multimin_fdfminimizer * @var{s}, gsl_multimin_function_fdf *@var{fdf}, const gsl_vector * @var{x}, double @var{step_size}, double @var{tol})
This function initializes the minimizer @var{s} to minimize the function
@var{fdf} starting from the initial point @var{x}.  The size of the
first trial step is given by @var{step_size}.  The accuracy of the line
minimization is specified by @var{tol}.  The precise meaning of this
parameter depends on the method used.  Typically the line minimization
is considered successful if the gradient of the function @math{g} is
orthogonal to the current search direction @math{p} to a relative
accuracy of @var{tol}, where @c{$p\cdot g < tol |p| |g|$} 
@math{dot(p,g) < tol |p| |g|}.
@end deftypefun

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

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

@example
printf("s is a '%s' minimizer\n", 
       gsl_multimin_fdfminimizer_name (s));
@end example
@noindent
would print something like @code{s is a 'conjugate_pr' minimizer}.
@end deftypefun

@node Providing a function to minimize
@section Providing a function to minimize

You must provide a parametric function of @math{n} variables for the
minimizers to operate on.  You also need to provide a routine which
calculates the gradient of the function and a third routine which
calculates both the function value and the gradient together.  In order
to allow for general parameters the functions are defined by the
following data type:

@deftp {Data Type} gsl_multimin_function_fdf
This data type defines a general function of @math{n} variables with
parameters and the corresponding gradient vector of derivatives,

@table @code
@item double (* f) (const gsl_vector * @var{x}, void * @var{params})
this function should return the result
@c{$f(x,\hbox{\it params})$}
@math{f(x,params)} for argument @var{x} and parameters @var{params}.

@item int (* df) (const gsl_vector * @var{x}, void * @var{params}, gsl_vector * @var{g})
this function should store the @var{n}-dimensional gradient
@c{$g_i = \partial f(x,\hbox{\it params}) / \partial x_i$}
@math{g_i = d f(x,params) / d x_i} in the vector @var{g} for argument @var{x} 
and parameters @var{params}, returning an appropriate error code if the
function cannot be computed.

@item int (* fdf) (const gsl_vector * @var{x}, void * @var{params}, double * f, gsl_vector * @var{g})
This function should set the values of the @var{f} and @var{g} as above,
for arguments @var{x} and parameters @var{params}.  This function provides
an optimization of the separate functions for @math{f(x)} and @math{g(x)} -- 
it is always faster to compute the function and its derivative at the
same time. 

@item size_t @var{n}
the dimension of the system, i.e. the number of components of the
vectors @var{x}.

@item void * @var{params}
a pointer to the parameters of the function.
@end table
@end deftp
@noindent
The following example function defines a simple paraboloid with two
parameters,

@example
/* Paraboloid centered on (dp[0],dp[1]) */

double
my_f (const gsl_vector *v, void *params)
@{
  double x, y;
  double *dp = (double *)params;
  
  x = gsl_vector_get(v, 0);
  y = gsl_vector_get(v, 1);
 
  return 10.0 * (x - dp[0]) * (x - dp[0]) +
           20.0 * (y - dp[1]) * (y - dp[1]) + 30.0; 
@}

/* The gradient of f, df = (df/dx, df/dy). */
void 
my_df (const gsl_vector *v, void *params, 
       gsl_vector *df)
@{
  double x, y;
  double *dp = (double *)params;
  
  x = gsl_vector_get(v, 0);
  y = gsl_vector_get(v, 1);
 
  gsl_vector_set(df, 0, 20.0 * (x - dp[0]));
  gsl_vector_set(df, 1, 40.0 * (y - dp[1]));
@}

/* Compute both f and df together. */
void 
my_fdf (const gsl_vector *x, void *params, 
        double *f, gsl_vector *df) 
@{
  *f = my_f(x, params); 
  my_df(x, params, df);
@}
@end example
@noindent
The function can be initialized using the following code,

@example
gsl_multimin_function_fdf my_func;

double p[2] = @{ 1.0, 2.0 @}; /* center at (1,2) */

my_func.f = &my_f;
my_func.df = &my_df;
my_func.fdf = &my_fdf;
my_func.n = 2;
my_func.params = (void *)p;
@end example

@node Multimin Iteration
@section Iteration

The following function drives the iteration of each algorithm.  The
function performs one iteration to update the state of the minimizer.
The same function works for all minimizers so that different methods can