Practical methods of optimization

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. 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