Practical Methods of Optimization

by Fletcher, R.

• ISBN13: 9780471494638
• ISBN10: 0471494631
• Edition: 2nd
• Format: Paperback
• Copyright: 2000-07-26
• Publisher: WILEY

Summary

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.

Author Biography

About the author Professor Roger Fletcher completed his MA at the University of Cambridge in 1960 and his PhD at the University of Leeds in 1963. He was a lecturer at the University of Leeds from 1963 to 1969, then Principal Scientific Officer at AERE Harwell until 1973. He then joined the University of Dundee where he is Professor of Optimization and holds the Baxter Chair of Mathematics. In 1997 he was awarded the prestigious Dantzig Prize for fundamental contributions to algorithms for nonlinear optimization, awarded jointly by the Society for Industrial and Applied Mathematics and the Mathematical Programming Society. He is a Fellow of the Royal Society of Edinburgh and of the Institute of Mathematics and its Applications.

Table of Contents

Preface	ix
Table of Notation	xiii
PART 1 UNCONSTRAINED OPTIMIZATION	1	(136)
Introduction	3	(9)
History and Applications	3	(3)
Mathematical Background	6	(6)
Questions for Chapter 1	11	(1)
Structure of Methods	12	(32)
Conditions for Local Minima	12	(4)
Ad hoc Methods	16	(3)
Useful Algorithmic Properties	19	(5)
Quadratic Models	24	(2)
Descent Methods and Stability	26	(7)
Algorithms for the Line Search Subproblem	33	(11)
Questions for Chapter 2	40	(4)
Newton-like Methods	44	(36)
Newton's Method	44	(5)
Quasi-Newton Methods	49	(8)
Invariance, Metrics and Variational Properties	57	(5)
The Broyden Family	62	(6)
Numerical Experiments	68	(4)
Other Formulae	72	(8)
Questions for Chapter 3	74	(6)
Conjugate Direction Methods	80	(15)
Conjugate Gradient Methods	80	(7)
Direction Set Methods	87	(8)
Questions for Chapter 4	92	(3)
Restricted Step Methods	95	(15)
A Prototype Algorithm	95	(5)
Levenberg-Marquardt Methods	100	(10)
Questions for Chapter 5	108	(2)
Sums of Squares and Nonlinear Equations	110	(27)
Over-determined Systems	110	(9)
Well-determined Systems	119	(10)
No-derivative Methods	129	(8)
Questions for Chapter 6	133	(4)
PART 2 CONSTRAINED OPTIMIZATION	137	(280)
Introduction	139	(11)
Preview	139	(5)
Elimination and Other Transformations	144	(6)
Questions for Chapter 7	149	(1)
Linear Programming	150	(45)
Structure	150	(3)
The Simplex Method	153	(6)
Other LP Techniques	159	(3)
Feasible Points for Linear Constraints	162	(6)
Stable and Large-scale Linear Programming	168	(9)
Degeneracy	177	(6)
Polynomial Time Algorithms	183	(12)
Questions for Chapter 8	188	(7)
The Theory of Constrained Optimization	195	(34)
Lagrange Multipliers	195	(6)
First Order Conditions	201	(6)
Second Order Conditions	207	(6)
Convexity	213	(6)
Duality	219	(10)
Questions for Chapter 9	224	(5)
Quadratic Programming	229	(30)
Equality Constraints	229	(7)
Lagrangian Methods	236	(4)
Active Set Methods	240	(5)
Advanced Features	245	(2)
Special QP Problems	247	(3)
Complementary Pivoting and Other Methods	250	(9)
Questions for Chapter 10	255	(4)
General Linearly Constrained Optimization	259	(18)
Equality Constraints	259	(5)
Inequality Constraints	264	(4)
Zigzagging	268	(9)
Questions for Chapter 11	275	(2)
Nonlinear Programming	277	(54)
Penalty and Barrier Functions	277	(10)
Multiplier Penalty Functions	287	(9)
The L1 Exact Penalty Function	296	(8)
The Lagrange-Newton Method (SQP)	304	(13)
Nonlinear Elimination and Feasible Direction Methods	317	(5)
Other Methods	322	(9)
Questions for Chapter 12	325	(6)
Other Optimization Problems	331	(26)
Integer Programming	331	(8)
Geometric Programming	339	(5)
Network Programming	344	(13)
Questions for Chapter 13	354	(3)
Non-Smooth Optimization	357	(60)
Introduction	357	(7)
Optimality Conditions	364	(14)
Exact Penalty Functions	378	(4)
Algorithms	382	(15)
A Globally Convergent Prototype Algorithm	397	(5)
Constrained Non-Smooth Optimization	402	(15)
Questions for Chapter 14	414	(3)
References	417	(13)
Subject Index	430