Algorithms for Minimization without Derivatives

Richard P. Brent

Publisher:

Dover Publications

Publication Date:

2013

Number of Pages:

195

Format:

Paperback

Price:

14.95

ISBN:

9780486419985

Category:

Monograph

MAA Review
Table of Contents

[Reviewed by

Allen Stenger

, on

04/16/2014

]

This is a specialized monograph in numerical analysis, developing methods for finding zeroes and minima of functions without using their derivatives. It is an expanded version of the author’s 1971 Ph.D. thesis. The present volume is an unaltered reprint of the 1973 Prentice-Hall edition, with a new preface by the author and a pointer to errata on the author’s web site.

The motivation for avoiding derivatives is that they may be difficult or time-consuming to evaluate. This book is not related to Ivan Niven’s Maxima and Minima Without Calculus, where the motivation is find extrema analytically with simpler methods than calculus.

The general idea is to develop a series of approximations to the desired point by using interpolating polynomials and finding an exact solution for each polynomial. Thus, to find a zero of a function we start with two points, find the linear function that interpolates the function from these points, and find where the interpolating function has a zero; this is the next point in the sequence. Geometrically we are drawing a secant line through the curve and expecting that the point where the secant hits the x-axis is close to a zero.

Finding minima is algorithmically similar: we interpolate through three points with a quadratic polynomial and pick the location of the minimum of the interpolating polynomial as our next estimate. These methods work well if the function is smooth and we start near the solution point, but may fail otherwise. A lot of the complication in developing an automatic algorithm is in detecting and correcting for non-convergence, and the book investigates and proves the properties of complete practical algorithms.

The book is very much oriented toward implementation of these algorithms, and in fact most are totally defined only in the ALGOL source code for them and not in the body of the text. The text does include complete proofs of convergence.

Allen Stenger is a math hobbyist and retired software developer. He is webmaster for the MAA Southwestern Section and is an editor of the Missouri Journal of Mathematical Sciences. His mathematical interests are number theory and classical analysis.

PREFACE TO DOVER EDITION
PREFACE
1 INTRODUCTION AND SUMMARY
1.1 Introduction
1.2 Summary
2 "SOME USEFUL RESULTS ON TAYLOR SERIES, DIVIDED DIFFERENCIES, AND LAGRANGE INTERPOLATION"
2.1 Introduction
2.2 Notation and definitions
2.3 Truncated Taylor series
2.4 Lagrange interpolation
2.5 Divided differences
2.6 Differentiating the error
3 THE USE OF SUCCESSIVE INTERPOLATION FOR FINDING SIMPLE ZEROS OF A FUNCTION AND ITS DERIVATIVES
3.1 Introduction
3.2 The definition of order
3.3 Convergence to a zero
3.4 Superlinear convergence
3.5 Strict superlinear convergence
3.6 The exact order of convergence
3.7 Stronger results for q = 1 and 2
3.8 Accelerating convergence
3.9 Some numerical examples
3.10 Summary
4 AN ALGORITHM WITH GUARANTEED CONVERGENCE FOR FINDING A ZERO OF A FUNCTION
4.1 Introduction
4.2 The algorithm
4.3 Convergence properties
4.4 Practical tests
4.5 Conclusion
4.6 ALGOL 60 procedures
5 AN ALGORITHM WITH GUARANTEED CONVERGENCE FOR FINDING A MINIMUM OF A FUNCTION OF ONE VARIABLE
5.1 Introduction
5.2 Fundamental limitations because of rounding errors
5.3 Unimodality and d-unimodality
5.4 An algorithm analogous to Dekker's algorithm
6 GLOBAL MINIMIZATION GIVEN AN UPPER BOUND ON THE SECOND DERIVATIVE
6.1 Introduction
6.2 The basic theorems
6.3 An algorithm for global minimization
6.4 The rate of convergence in some special cases
6.5 A lower bound on the number of function evaluations required
6.6 Practical tests
6.7 Some extensions and generalizations
6.8 An algorithm for global minimization of a function of several variables
6.9 Summary and conclusions
6.10 ALGOL 60 procedures
7 A NEW ALGORITHM FOR MINIMIZING A FUNCTION OF SEVERAL VARIABLES WITHOUT CALCULATING DERIVATIVES
7.1 Introduction and survey of the literature
7.2 The effect of rounding errors
7.3 Powell's algorithm
7.4 The main modification
7.5 The resolution ridge problem
7.6 Some further details
7.7 Numerical results and comparison with other methods
7.8 Conclusion
7.9 An ALGOL W procedure and test program
BIBLIOGRAPHY
APPENDIX: FORTRAN subroutines
INDEX