multimin.texi

开放gsl矩阵运算

be substituted at runtime without modifications to the code.

@deftypefun int gsl_multimin_fdfminimizer_iterate (gsl_multimin_fdfminimizer *@var{s})
These functions perform a single iteration of the minimizer @var{s}.  If
the iteration encounters an unexpected problem then an error code will
be returned.
@end deftypefun
@noindent
The minimizer maintains a current best estimate of the minimum at all
times.  This information can be accessed with the following auxiliary
functions,

@deftypefun {gsl_vector *} gsl_multiroot_fdfsolver_x (const gsl_multiroot_fdfsolver * @var{s})
@deftypefunx double gsl_multiroot_fdfsolver_minimum (const gsl_multiroot_fdfsolver * @var{s})
@deftypefunx {gsl_vector *} gsl_multiroot_fdfsolver_gradient (const gsl_multiroot_fdfsolver * @var{s})
These functions return the current best estimate of the location of the
minimum, the value of the function at that point and its gradient, for
the minimizer @var{s}.
@end deftypefun

@deftypefun int gsl_multimin_fdfminimizer_restart (gsl_multimin_fdfminimizer *@var{s})
This function resets the minimizer @var{s} to use the current point as a
new starting point.
@end deftypefun

@node Multimin Stopping Criteria
@section Stopping Criteria

A minimization procedure should stop when one of the following
conditions is true:

@itemize @bullet
@item
A minimum has been found to within the user-specified precision.

@item
A user-specified maximum number of iterations has been reached.

@item
An error has occurred.
@end itemize

@noindent
The handling of these conditions is under user control.  The functions
below allow the user to test the precision of the current result.

@deftypefun int gsl_multimin_test_gradient (const gsl_vector * @var{g},double @var{epsabs})
This function tests the norm of the gradient @var{g} against the
absolute tolerance @var{epsabs}. The gradient of a multidimensional
function goes to zero at a minimum. The test returns @code{GSL_SUCCESS}
if the following condition is achieved,

@tex
\beforedisplay
$$
|g| < \hbox{\it epsabs}
$$
\afterdisplay
@end tex
@ifinfo
@example
|g| < epsabs
@end example
@end ifinfo
@noindent
and returns @code{GSL_CONTINUE} otherwise.  A suitable choice of
@var{epsabs} can be made from the desired accuracy in the function for
small variations in @math{x}.  The relationship between these quantities
is given by @c{$\delta f = g\,\delta x$}
@math{\delta f = g \delta x}.
@end deftypefun

@node Multimin Algorithms
@section Algorithms

There are several minimization methods available. The best choice of
algorithm depends on the problem.  Each of the algorithms uses the value
of the function and its gradient at each evaluation point.

@deffn {Minimizer} gsl_multimin_fdfminimizer_conjugate_fr
This is the Fletcher-Reeves conjugate gradient algorithm. The conjugate
gradient algorithm proceeds as a succession of line minimizations. The
sequence of search directions to build up an approximation to the
curvature of the function in the neighborhood of the minimum.  An
initial search direction @var{p} is chosen using the gradient and line
minimization is carried out in that direction.  The accuracy of the line
minimization is specified by the parameter @var{tol}.  At the minimum
along this line the function gradient @var{g} and the search direction
@var{p} are orthogonal.  The line minimization terminates when
@c{$p\cdot g < tol |p| |g|$} 
@math{dot(p,g) < tol |p| |g|}.  The
search direction is updated  using the Fletcher-Reeves formula
@math{p' = g' - \beta g} where @math{\beta=-|g'|^2/|g|^2}, and
the line minimization is then repeated for the new search
direction.
@end deffn

@deffn {Minimizer} gsl_multimin_fdfminimizer_conjugate_pr
This is the Polak-Ribiere conjugate gradient algorithm.  It is similar
to the Fletcher-Reeves method, differing only in the choice of the
coefficient @math{\beta}. Both methods work well when the evaluation
point is close enough to the minimum of the objective function that it
is well approximated by a quadratic hypersurface.
@end deffn

@deffn {Minimizer} gsl_multimin_fdfminimizer_vector_bfgs
This is the vector Broyden-Fletcher-Goldfarb-Shanno conjugate gradient
algorithm.  It is a quasi-Newton method which builds up an approximation
to the second derivatives of the function @math{f} using the difference
between successive gradient vectors.  By combining the first and second
derivatives the algorithm is able to take Newton-type steps towards the
function minimum, assuming quadratic behavior in that region.
@end deffn

@deffn {Minimizer} gsl_multimin_fdfminimizer_steepest_descent
The steepest descent algorithm follows the downhill gradient of the
function at each step. When a downhill step is successful the step-size
is increased by factor of two.  If the downhill step leads to a higher
function value then the algorithm backtracks and the step size is
decreased using the parameter @var{tol}.  A suitable value of @var{tol}
for most applications is 0.1.  The steepest descent method is
inefficient and is included only for demonstration purposes.
@end deffn

@node Multimin Examples
@section Examples

This example program finds the minimum of the paraboloid function
defined earlier.  The location of the minimum is offset from the origin
in @math{x} and @math{y}, and the function value at the minimum is
non-zero. The main program is given below, it requires the example
function given earlier in this chapter.

@smallexample
int
main (void)
@{
  size_t iter = 0;
  int status;

  const gsl_multimin_fdfminimizer_type *T;
  gsl_multimin_fdfminimizer *s;

  /* Position of the minimum (1,2). */
  double par[2] = @{ 1.0, 2.0 @};

  gsl_vector *x;
  gsl_multimin_function_fdf my_func;

  my_func.f = &my_f;
  my_func.df = &my_df;
  my_func.fdf = &my_fdf;
  my_func.n = 2;
  my_func.params = &par;

  /* Starting point, x = (5,7) */

  x = gsl_vector_alloc (2);
  gsl_vector_set (x, 0, 5.0);
  gsl_vector_set (x, 1, 7.0);

  T = gsl_multimin_fdfminimizer_conjugate_fr;
  s = gsl_multimin_fdfminimizer_alloc (T, 2);

  gsl_multimin_fdfminimizer_set (s, &my_func, x, 0.01, 1e-4);

  do
    @{
      iter++;
      status = gsl_multimin_fdfminimizer_iterate (s);

      if (status)
        break;

      status = gsl_multimin_test_gradient (s->gradient, 1e-3);

      if (status == GSL_SUCCESS)
        printf ("Minimum found at:\n");

      printf ("%5d %.5f %.5f %10.5f\n", iter,
              gsl_vector_get (s->x, 0), 
              gsl_vector_get (s->x, 1), 
              s->f);

    @}
  while (status == GSL_CONTINUE && iter < 100);

  gsl_multimin_fdfminimizer_free (s);
  gsl_vector_free (x);

  return 0;
@}
@end smallexample  
@noindent
The initial step-size is chosen as 0.01, a conservative estimate in this
case, and the line minimization parameter is set at 0.0001.  The program
terminates when the norm of the gradient has been reduced below
0.001. The output of the program is shown below,

@example
         x       y         f
    1 4.99629 6.99072  687.84780
    2 4.98886 6.97215  683.55456
    3 4.97400 6.93501  675.01278
    4 4.94429 6.86073  658.10798
    5 4.88487 6.71217  625.01340
    6 4.76602 6.41506  561.68440
    7 4.52833 5.82083  446.46694
    8 4.05295 4.63238  261.79422
    9 3.10219 2.25548   75.49762
   10 2.85185 1.62963   67.03704
   11 2.19088 1.76182   45.31640
   12 0.86892 2.02622   30.18555
Minimum found at:
   13 1.00000 2.00000   30.00000
@end example
@noindent
Note that the algorithm gradually increases the step size as it
successfully moves downhill, as can be seen by plotting the successive
points.

@iftex
@sp 1
@center @image{multimin,4in}
@end iftex
@noindent
The conjugate gradient algorithm finds the minimum on its second
direction because the function is purely quadratic. Additional
iterations would be needed for a more complicated function.

@node Multimin References and Further Reading
@section References and Further Reading
@noindent
A brief description of multidimensional minimization algorithms and
further references can be found in the following book,

@itemize @asis
@item C.W. Ueberhuber,
@cite{Numerical Computation (Volume 2)}, Chapter 14, Section 4.4
"Minimization Methods", p. 325---335, Springer (1997), ISBN
3-540-62057-5.
@end itemize
@noindent