module/slib/minimize.txi

   1 @noindent
   2
   3 The Golden Section Search
   4 @footnote{David Kahaner, Cleve Moler, and Stephen Nash
   5 @cite{Numerical Methods and Software}
   6 Prentice-Hall, 1989, ISBN 0-13-627258-4}
   7 algorithm finds minima of functions which
   8 are expensive to compute or for which derivatives are not available.
   9 Although optimum for the general case, convergence is slow,
  10 requiring nearly 100 iterations for the example (x^3-2x-5).
  11
  12 @noindent
  13
  14 If the derivative is available, Newton-Raphson is probably a better
  15 choice.  If the function is inexpensive to compute, consider
  16 approximating the derivative.
  17
  18
  19 @defun golden-section-search f x0 x1 prec
  20
  21
  22 @var{x_0} are @var{x_1} real numbers.  The (single argument)
  23 procedure @var{f} is unimodal over the open interval (@var{x_0},
  24 @var{x_1}).  That is, there is exactly one point in the interval for
  25 which the derivative of @var{f} is zero.
  26
  27 @code{golden-section-search} returns a pair (@var{x} . @var{f}(@var{x})) where @var{f}(@var{x})
  28 is the minimum.  The @var{prec} parameter is the stop criterion.  If
  29 @var{prec} is a positive number, then the iteration continues until
  30 @var{x} is within @var{prec} from the true value.  If @var{prec} is
  31 a negative integer, then the procedure will iterate @var{-prec}
  32 times or until convergence.  If @var{prec} is a procedure of seven
  33 arguments, @var{x0}, @var{x1}, @var{a}, @var{b}, @var{fa}, @var{fb},
  34 and @var{count}, then the iterations will stop when the procedure
  35 returns @code{#t}.
  36
  37 Analytically, the minimum of x^3-2x-5 is 0.816497.
  38 @example
  39 (define func (lambda (x) (+ (* x (+ (* x x) -2)) -5)))
  40 (golden-section-search func 0 1 (/ 10000))
  41       ==> (816.4883855245578e-3 . -6.0886621077391165)
  42 (golden-section-search func 0 1 -5)
  43       ==> (819.6601125010515e-3 . -6.088637561916407)
  44 (golden-section-search func 0 1
  45                        (lambda (a b c d e f g ) (= g 500)))
  46       ==> (816.4965933140557e-3 . -6.088662107903635)
  47 @end example
  48 @end defun