ALGORITHMS FOR MINIMIZATION WITHOUT DERIVATIVES

RICHARD P. BRENT

Abstract

This monograph describes and analyzes some practical methods for finding approximate zeros and minima of functions. Contents include:

1. The use of successive interpolation for finding simple zeros of a function and its derivatives.

2. An algorithm with guaranteed convergence for finding a zero of a function.

3. An algorithm with guaranteed convergence for finding a minimum of a function of one variable.

4. Global minimization given an upper bound on the second derivative.

5. A new algorithm for minimizing a function of several variables without calculating derivatives.

6. Computer programs which implement these algorithms.

Comments

Only the Abstract is given here. The full work appeared as [4]. A preliminary version appeared as [2]. For related work, see [1, 3].

References

1. R. P. Brent, “An algorithm with guaranteed convergence for finding a zero of a function”, Computer J. 14 (1971), 422–425. MR 49#4234, Zbl 231.65046. rpb005.

2. R. P. Brent, Algorithms for finding zeros and extrema of functions without calculating derivatives, Report TR CS 198, DCS, Stanford (February 1971), 313 pp. Ph. D. thesis, available from NTIS, #AD726170. rpb006.

3. R. P. Brent, “A new algorithm for minimizing a function of several variables without calculating derivatives”, in Optimization (edited by R. S. Anderssen, L. S. Jennings and D. M. Ryan), University of Queensland Press, Brisbane, 1972, 14–25. MR 52#2574, 52#9601, Zbl 311.90065. rpb007.

4. R. P. Brent, Algorithms for Minimization without Derivatives, Prentice-Hall, Englewood Cliffs, New Jersey, 1973, 195 pp. (Prentice-Hall Series in Automatic Computation, edited by George Forsythe.) ISBN 0-13-022335-2. Reviewed in: American Scientist 61 (May–June 1973), 374; Mathematical Programming 4 (1973), 349; Computer J. 16 (1973), 314; Math. Comp. 28 (1974), 865–866; CR 15#26544; MR 49#4251; Zbl 245.65032. Errata: Math. Comp. TE 520, 29 (1975), 1166. MR 51#7283. rpb011.

IBM Thomas J. Watson Research Center, Yorktown Heights, New York

1991 Mathematics Subject Classification. Primary 65K10; Secondary 65-02, 65-04, 65G05, 65H05, 65H20, 68-02, 68-04.

Key words and phrases. Optimization, zero-finding, bisection, secant method, linear interpolation, quadratic interpolation, Dekker’s method, Powell’s method.

Copyright \begin{matrix}c \\ ◯ \end{matrix} 1973, Prentice-Hall, Inc. Comments \begin{matrix}c \\ ◯ \end{matrix} 1993, R. P. Brent.

rpb011a typeset using AMS-L^{A}TEX