This book is a standard for a complete description of the methods for unconstrained optimization and the solution ofnonlinear equations....this republication is most welcome and this volume should be in every library. Of course, there exist more recent books on the topics and somebody interested in the subject cannot be satiated by looking only at this book. However, it contains much quite-well-presented material and I recommend reading it before going ,to other.publications.

PREFACE TO THE CLASSICS EDITION   xi

PREFACE  xiii

1  INTRODUCTION  2

1.1 Problems to be considered 2

1.2 Characteristics of"real-world" problems 5

1.3 Finite-precision arithmetic and measurement of error 10

1.4 Exercises 13

2  NONLINEAR PROBLEMS IN ONE VARIABLE    15

2.1 What is not possible 15

2.2 Newton's method for solving one equation in one unknown 16

2.3 Convergence of sequences of real numbers 19

2.4 Convergence of Newton's method 21

2.5 Globally convergent methods for solving one equation in one unknown 24

2.6 Methods when derivatives are unavailable 27

2.7 Minimization of a function of one variable 32

2.8 Exercises 36

3  NUMERICAL LINEAR

ALGEBRA BACKGROUND   40

3.1 Vector and matrix norms and orthogonality 41

3.2 Solving systems of linear equations--matrix factorizations 47

3.3 Errors in solving linear systems 51

3.4 Updating matrix factorizations 55

3.5 Eigenvalues and positive definiteness 58

3.6 Linear least squares 60

3.7 Exercises 66

4  MULTIVARIABLE CALCULUS BACKGROUND     69

4.1 Derivatives and multivariable models 69

4.2 Multivariable finite-difference derivatives 77

4.3 Necessary and sufficient conditions for unconstrained minimization 80

4.4 Exercises 83

5  NEWTON'S METHOD FOR NONLINEAR EQUATIONS AND UNCONSTRAINED MINIMIZATION   86

5.1 Newton's method for systems of nonlinear equations 86

5.2 Local convergence of Newton's method 89

5.3 The Kantorovich and contractive mapping theorems 92

5.4 Finite-difference derivative methods for systems of nonlinear equations 94

5.5 Newton's method for unconstrained minimization 99

5.6 Finite-difference derivative methods for unconstrained minimization 103

5.7 Exercises 107

6  GLOBALLY CONVERGENT MODIFICATIONS OF NEWTON'S METHOD        111

6.1 The quasi-Newton framework 112

6.2 Descent directions 113

6.3 Line searches 116

6.3.1 Convergence results for properly chosen steps 120

6.3.2 Step selection by backtracking 126

6.4 The model-trust region approach 129

6.4.1 The locally constrained optimal ("hook") step 134

6.4.2 The double dogleg step 139

6.4.3 Updating the trust region 143

6.5 Global methods for systems of nonlinear equations 147

6.6 Exercises 152

7  STOPPING, SCALING, AND TESTING     155

7.1 Scaling 155

7.2 Stopping criteria 159

7.3 Testing 161

7.4 Exercises 164

8  SECANT METHODS FOR SYSTEMS OF NONLINEAR EQUATIONS    168

8.1 Broyden's method 169

8.2 Local convergence analysis of Broyden's method 174

8.3 Implementation of quasi-Newton algorithms using Broyden's update 186

8.4 Other secant updates for nonlinear equations 189

8.5 Exercises 190

9  SECANT METHODS FOR UNCONSTRAINED MINIMIZATION   194

9.1 The symmetric secant update of Powell 195

9.2 Symmetric positive definite secant updates 198

9.3 Local convergence of positive definite secant methods 203

9.4 Implementation of quasi-Newton algorithms using the positive definite secant update 208

9.5 Another convergence result for the positive definite secant method 210

9.6 Other secant updates for unconstrained minimization 211

9.7 Exercises 212

10  NONLINEAR LEAST SQUARES     218

10.1 The nonlinear least-squares problem 218

10.2 Gauss-Newton-type methods 221

10.3 Full Newton-type methods 228

10.4 Other considerations in solving nonlinear least-squares problems 233

10.5 Exercises 236

11  METHODS FOR PROBLEMS WITH SPECIAL STRUCTURE   239

11.1 The sparse finite-difference Newton method 240

! 1.2 Sparse secant methods 242

11.3 Deriving least-change secant updates 246

11.4 Analyzing least-change secant methods 251

11.5 Exercises 256

A  APPENDIX: A MODULAR SYSTEM OF ALGORITHMS FOR UNCONSTRAINED MINIMIZATION AND NONLINEAR EQUATIONS     259

(by Robert Schnabel)

B  APPENDIX: TEST PROBLEMS   361

(by Robert SchnabeI)

REFERENCES   364

AUTHOR INDEX  371

SUBJECT INDEX   373