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_0arex_1real numbers. The (single argument) procedurefis unimodal over the open interval (x_0,x_1). That is, there is exactly one point in the interval for which the derivative offis zero.

`golden-section-search`

returns a pair (x.f(x)) wheref(x) is the minimum. Theprecparameter is the stop criterion. Ifprecis a positive number, then the iteration continues untilxis withinprecfrom the true value. Ifprecis a negative integer, then the procedure will iterate-prectimes or until convergence. Ifprecis a procedure of seven arguments,x0,x1,a,b,fa,fb, andcount, 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)

[1] David Kahaner, Cleve Moler, and Stephen Nash Numerical Methods and Software Prentice-Hall, 1989, ISBN 0-13-627258-4