GNU Info

(slib.info)Minimizing

---

Next: Commutative Rings Prev: Root Finding Up: Mathematical Packages

---

Enter node , (file) or (file)node

Minimizing
==========

  `(require 'minimize)'

The Golden Section Search (1) algorithm finds minima of functions which
are expensive to compute or for which derivatives are not available.
Although optimum for the general case, convergence is slow, requiring
nearly 100 iterations for the example (x^3-2x-5).

If the derivative is available, Newton-Raphson is probably a better
choice.  If the function is inexpensive to compute, consider
approximating the derivative.

 - Function: golden-section-search f x0 x1 prec
     X_0 are X_1 real numbers.  The (single argument) procedure F is
     unimodal over the open interval (X_0, X_1).  That is, there is
     exactly one point in the interval for which the derivative of F is
     zero.

     `golden-section-search' returns a pair (X . F(X)) where F(X) is
     the minimum.  The PREC parameter is the stop criterion.  If PREC
     is a positive number, then the iteration continues until X is
     within PREC from the true value.  If PREC is a negative integer,
     then the procedure will iterate -PREC times or until convergence.
     If PREC is a procedure of seven arguments, X0, X1, A, B, FA, FB,
     and COUNT, then the iterations will stop when the procedure
     returns `#t'.

     Analytically, the minimum of x^3-2x-5 is 0.816497.
          (define func (lambda (x) (+ (* x (+ (* x x) -2)) -5)))
          (golden-section-search func 0 1 (/ 10000))
                ==> (816.4883855245578e-3 . -6.0886621077391165)
          (golden-section-search func 0 1 -5)
                ==> (819.6601125010515e-3 . -6.088637561916407)
          (golden-section-search func 0 1
                                 (lambda (a b c d e f g ) (= g 500)))
                ==> (816.4965933140557e-3 . -6.088662107903635)

  ---------- Footnotes ----------

  (1) David Kahaner, Cleve Moler, and Stephen Nash `Numerical Methods
and Software' Prentice-Hall, 1989, ISBN 0-13-627258-4