Practical methods of optimization

R. Fletcher9780471494638, 0471494631

Fully describes optimization methods that are currently most valuable in solving real-life problems. Since optimization has applications in almost every branch of science and technology, the text emphasizes their practical aspects in conjunction with the heuristics useful in making them perform more reliably and efficiently. To this end, it presents comparative numerical studies to give readers a feel for possibile applications and to illustrate the problems in assessing evidence. Also provides theoretical background which provides insights into how methods are derived. This edition offers revised coverage of basic theory and standard techniques, with updated discussions of line search methods, Newton and quasi-Newton methods, and conjugate direction methods, as well as a comprehensive treatment of restricted step or trust region methods not commonly found in the literature. Also includes recent developments in hybrid methods for nonlinear least squares; an extended discussion of linear programming, with new methods for stable updating of LU factors; and a completely new section on network programming. Chapters include computer subroutines, worked examples, and study questions.

---

Table of contents :
Cover……Page 1
Title page……Page 3
Date-line……Page 4
Contents……Page 5
Preface……Page 9
Table of Notation……Page 13
PART 1 UNCONSTRAINED OPTIMIZATION……Page 15
1.1 History and Applications……Page 17
1.2 Mathematical Background……Page 20
Questions for Chapter 1……Page 25
2.1 Conditions for Local Minima……Page 26
2.2 Ad hoc Methods……Page 30
2.3 Useful Algorithmic Properties……Page 33
2.4 Quadratic Models……Page 38
2.5 Descent Methods and Stability……Page 40
2.6 Algorithms for the Line Search Subproblem……Page 47
Questions for Chapter 2……Page 54
3.1 Newton’s Method……Page 58
3.2 Quasi-Newton Methods……Page 63
3.3 Invariance, Metrics and Variational Properties……Page 71
3.4 The Broyden Family……Page 76
3.5 Numerical Experiments……Page 82
3.6 Other Formulae……Page 86
Questions for Chapter 3……Page 88
4.1 Conjugate Gradient Methods……Page 94
4.2 Direction Set Methods……Page 101
Questions for Chapter 4……Page 106
5.1 A Prototype Algorithm……Page 109
5.2 Levenberg-Marquardt Methods……Page 114
Questions for Chapter 5……Page 122
6.1 Over-determined Systems……Page 124
6.2 Well-determined Systems……Page 133
6.3 No-derivative Methods……Page 143
Questions for Chapter 6……Page 147
PART 2 CONSTRAINED OPTIMIZATION……Page 151
7.1 Preview……Page 153
7.2 Elimination and Other Transformations……Page 158
Questions for Chapter 7……Page 163
8.1 Structure……Page 164
8.2 The Simplex Method……Page 167
8.3 Other LP Techniques……Page 173
8.4 Feasible Points for Linear Constraints……Page 176
8.5 Stable and Large-scale Linear Programming……Page 182
8.6 Degeneracy……Page 191
8.7 Polynomial Time Algorithms……Page 197
Questions for Chapter 8……Page 202
9.1 Lagrange Multipliers……Page 209
9.2 First Order Conditions……Page 215
9.3 Second Order Conditions……Page 221
9.4 Convexity……Page 227
9.5 Duality……Page 233
Questions for Chapter 9……Page 238
10.1 Equality Constraints……Page 243
10.2 Lagrangian Methods……Page 250
10.3 Active Set Methods……Page 254
10.4 Advanced Features……Page 259
10.5 Special QP Problems……Page 261
10.6 Complementary Pivoting and Other Methods……Page 264
Questions for Chapter 10……Page 269
11.1 Equality Constraints……Page 273
11.2 Inequality Constraints……Page 278
11.3 Zigzagging……Page 282
Questions for Chapter 11……Page 289
12.1 Penalty and Barrier Functions……Page 291
12.2 Multiplier Penalty Functions……Page 301
12.3 The $L_1$ Exact Penalty Function……Page 310
12.4 The Lagrange-Newton Method (SQP)……Page 318
12.5 Nonlinear Elimination and Feasible Direction Methods……Page 331
12.6 Other Methods……Page 336
Questions for Chapter 12……Page 339
13.1 Integer Programming……Page 345
13.2 Geometric Programming……Page 353
13.3 Network Programming……Page 358
Questions for Chapter 13……Page 368
14.1 Introduction……Page 371
14.2 Optimality Conditions……Page 378
14.3 Exact Penalty Functions……Page 392
14.4 Algorithms……Page 396
14.5 A Globally Convergent Prototype Algorithm……Page 411
14.6 Constrained Non-Smooth Optimization……Page 416
Questions for Chapter 14……Page 428
References……Page 431
Subject Index……Page 444
Back cover……Page 451