| @cindex optimization, see minimization |
| @cindex maximization, see minimization |
| @cindex minimization, one-dimensional |
| @cindex finding minima |
| @cindex nonlinear 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 a lower bound @math{a} and an |
| upper bound @math{b}, with an estimate of the location of the minimum |
| @math{x}. |
| |
| @iftex |
| @sp 1 |
| @center @image{min-interval,3.4in} |
| @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, |
| @tex |
| $$f(a) > f(x) < f(b)$$ |
| @end tex |
| @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, i.e.@: where @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, |
| @tex |
| $$ |
| y = f(x^*) + {1 \over 2} f''(x^*) (x - x^*)^2 |
| $$ |
| @end tex |
| @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 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{x_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{x_minimum}. |
| |
| If the interval given does not contain a minimum, then the function |
| returns an error code of @code{GSL_EINVAL}. |
| @end deftypefun |
| |
| @deftypefun int gsl_min_fminimizer_set_with_values (gsl_min_fminimizer * @var{s}, gsl_function * @var{f}, double @var{x_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(x_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 position 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_x_minimum (const gsl_min_fminimizer * @var{s}) |
| This function returns the current estimate of the position of the |
| minimum for the minimizer @var{s}. |
| @end deftypefun |
| |
| @deftypefun double gsl_min_fminimizer_x_upper (const gsl_min_fminimizer * @var{s}) |
| @deftypefunx double 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 |
| |
| @deftypefun double gsl_min_fminimizer_f_minimum (const gsl_min_fminimizer * @var{s}) |
| @deftypefunx double gsl_min_fminimizer_f_upper (const gsl_min_fminimizer * @var{s}) |
| @deftypefunx double gsl_min_fminimizer_f_lower (const gsl_min_fminimizer * @var{s}) |
| These functions return the value of the function at the current estimate |
| of the minimum and at the upper and lower bounds of the interval for the |
| minimizer @var{s}. |
| @end deftypefun |
| |
| @node Minimization Stopping Parameters |
| @section Stopping Parameters |
| @cindex minimization, stopping parameters |
| |
| 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 function |
| below allows the user to test the precision of the current result. |
| |
| @deftypefun int gsl_min_test_interval (double @var{x_lower}, double @var{x_upper}, double @var{epsabs}, double @var{epsrel}) |
| This function tests for the convergence of the interval [@var{x_lower}, |
| @var{x_upper}] with absolute error @var{epsabs} and relative error |
| @var{epsrel}. The test returns @code{GSL_SUCCESS} if the following |
| condition is achieved, |
| @tex |
| \beforedisplay |
| $$ |
| |a - b| < \hbox{\it epsabs} + \hbox{\it epsrel\/}\, \min(|a|,|b|) |
| $$ |
| \afterdisplay |
| @end tex |
| @ifinfo |
| |
| @example |
| |a - b| < epsabs + epsrel min(|a|,|b|) |
| @end example |
| |
| @end ifinfo |
| @noindent |
| when the interval @math{x = [a,b]} does not include the origin. If the |
| interval includes the origin then @math{\min(|a|,|b|)} is replaced by |
| zero (which is the minimum value of @math{|x|} over the interval). This |
| ensures that the relative error is accurately estimated for minima close |
| to the origin. |
| |
| This condition on the interval also implies that any estimate of the |
| minimum @math{x_m} in the interval satisfies the same condition with respect |
| to the true minimum @math{x_m^*}, |
| @tex |
| \beforedisplay |
| $$ |
| |x_m - x_m^*| < \hbox{\it epsabs} + \hbox{\it epsrel\/}\, x_m^* |
| $$ |
| \afterdisplay |
| @end tex |
| @ifinfo |
| |
| @example |
| |x_m - x_m^*| < epsabs + epsrel x_m^* |
| @end example |
| |
| @end ifinfo |
| @noindent |
| assuming that the true minimum @math{x_m^*} is contained within the interval. |
| @end deftypefun |
| |
| @comment ============================================================ |
| |
| @node Minimization Algorithms |
| @section Minimization Algorithms |
| |
| The minimization algorithms described in this section require an initial |
| interval which is guaranteed to contain a minimum---if @math{a} and |
| @math{b} are the endpoints of the interval and @math{x} is an estimate |
| of the minimum then @math{f(a) > f(x) < f(b)}. This ensures that the |
| function has at least one minimum somewhere in the interval. If a valid |
| initial interval is used then these algorithm cannot fail, provided the |
| function is well-behaved. |
| |
| @deffn {Minimizer} gsl_min_fminimizer_goldensection |
| |
| @cindex golden section algorithm for finding minima |
| @cindex minimum finding, golden section algorithm |
| |
| The @dfn{golden section algorithm} is the simplest method of bracketing |
| the minimum of a function. It is the slowest algorithm provided by the |
| library, with linear convergence. |
| |
| On each iteration, the algorithm first compares the subintervals from |
| the endpoints to the current minimum. The larger subinterval is divided |
| in a golden section (using the famous ratio @math{(3-\sqrt 5)/2 = |
| 0.3189660}@dots{}) and the value of the function at this new point is |
| calculated. The new value is used with the constraint @math{f(a') > |
| f(x') < f(b')} to a select new interval containing the minimum, by |
| discarding the least useful point. This procedure can be continued |
| indefinitely until the interval is sufficiently small. Choosing the |
| golden section as the bisection ratio can be shown to provide the |
| fastest convergence for this type of algorithm. |
| |
| @end deffn |
| |
| @comment ============================================================ |
| |
| @deffn {Minimizer} gsl_min_fminimizer_brent |
| @cindex Brent's method for finding minima |
| @cindex minimum finding, Brent's method |
| |
| The @dfn{Brent minimization algorithm} combines a parabolic |
| interpolation with the golden section algorithm. This produces a fast |
| algorithm which is still robust. |
| |
| The outline of the algorithm can be summarized as follows: on each |
| iteration Brent's method approximates the function using an |
| interpolating parabola through three existing points. The minimum of the |
| parabola is taken as a guess for the minimum. If it lies within the |
| bounds of the current interval then the interpolating point is accepted, |
| and used to generate a smaller interval. If the interpolating point is |
| not accepted then the algorithm falls back to an ordinary golden section |
| step. The full details of Brent's method include some additional checks |
| to improve convergence. |
| @end deffn |
| |
| @comment ============================================================ |
| |
| @node Minimization Examples |
| @section Examples |
| |
| The following program uses the Brent algorithm to find the minimum of |
| the function @math{f(x) = \cos(x) + 1}, which occurs at @math{x = \pi}. |
| The starting interval is @math{(0,6)}, with an initial guess for the |
| minimum of @math{2}. |
| |
| @example |
| @verbatiminclude examples/min.c |
| @end example |
| |
| @noindent |
| Here are the results of the minimization procedure. |
| |
| @smallexample |
| $ ./a.out |
| @verbatiminclude examples/min.out |
| @end smallexample |
| |
| @node Minimization References and Further Reading |
| @section References and Further Reading |
| |
| Further information on Brent's algorithm is available in the following |
| book, |
| |
| @itemize @asis |
| @item |
| Richard Brent, @cite{Algorithms for minimization without derivatives}, |
| Prentice-Hall (1973), republished by Dover in paperback (2002), ISBN |
| 0-486-41998-3. |
| @end itemize |
| |