Algorithms for Minimization Without Derivatives

by Brent, Richard P.

• ISBN13: 9780486419985
• ISBN10: 0486419983
• Format: Paperback
• Copyright: 2013-04-17
• Publisher: Dover Publications

Summary

Outstanding text for graduate students and research workers proposes improvements to existing algorithms, extends their related mathematical theories, and offers details on new algorithms for approximating local and global minima. Many numerical examples, along with complete analysis of rate of convergence for most of the algorithms and error bounds that allow for the effect of rounding errors.

Table of Contents

Preface to Dover Edition	viii
Preface	ix
Introduction and Summary	1	(8)
Introduction	1	(3)
Summary	4	(5)
Some Useful Results on Taylor Series, Divided Differences, and Lagrange Interpolation	9	(10)
Introduction	9	(1)
Notation and definitions	10	(1)
Truncated Taylor series	11	(1)
Lagrange interpolation	12	(1)
Divided differences	13	(2)
Differentiating the error	15	(4)
The Use of Successive Interpolation for Finding Simple Zeros of a Function and its Derivatives	19	(28)
Introduction	19	(2)
The definition of order	21	(1)
Convergence to a zero	22	(2)
Superlinear convergence	24	(2)
Strict superlinear convergence	26	(3)
The exact order of convergence	29	(5)
Stronger results for q = 1 and 2	34	(6)
Accelerating convergence	40	(3)
Some numerical examples	43	(2)
Summary	45	(2)
An Algorithm with Guaranteed Convergence for Finding a Zero of a Function	47	(14)
Introduction	47	(1)
The Algorithm	48	(5)
Convergence properties	53	(1)
Practical tests	54	(2)
Conclusion	56	(2)
ALGOL 60 procedures	58	(3)
An Algorithm with Guaranteed Convergence for Finding a Minimum of a Function of one Variable	61	(20)
Introduction	61	(2)
Fundamental limitations because of rounding errors	63	(2)
Unimodality and δ-unimodality	65	(7)
An algorithm analogous to Dekker's algorithm	72	(3)
Convergence properties	75	(1)
Practical tests	76	(2)
Conclusion	78	(1)
An ALGOL 60 procedure	79	(2)
Global Minimization Given an Upper Bound on the Second Derivative	81	(35)
Introduction	81	(3)
The basic theorems	84	(2)
An algorithm for global minimization	86	(11)
The rate of convergence in some special cases	97	(3)
A lower bound on the number of function evaluations required	100	(3)
Practical tests	103	(2)
Some extensions and generalizations	105	(2)
An algorithm for global minimization of a function of several variables	107	(4)
Summary and conclusions	111	(1)
ALGOL 60 procedures	112	(4)
A New Algorithm for Minimizing a Function of Several Variables Without Calculating Derivatives	116	(53)
Introduction and survey of the literature	116	(6)
The effect of rounding errors	122	(2)
Powell's algorithm	124	(4)
The main modification	128	(4)
The resolution ridge problem	132	(3)
Some further details	135	(2)
Numerical results and comparison with other methods	137	(17)
Conclusion	154	(1)
An ALGOL W procedure and test program	155	(14)
Bibliography	169	(18)
Appendix: Fortran subroutines	187	(6)
Index	193