Iterative Methods for Optimization

C.T. Kelley

Frontiers in Applied Mathematics 18


This book on unconstrained and bound constrained optimization can be used as a tutorial for self-study or a reference by those who solve such problems in their work. It can also serve as a textbook in an introductory optimization course.

As in my earlier book on linear and nonlinear equations, we treat a small number of methods in depth, giving a less detailed description of only a few (for example, the nonlinear conjugate gradient method and the DIRECT algorithm). We aim for clarity and brevity rather than complete generality and confine our scope to algorithms that are easy to implement (by the reader!) and understand.

One consequence of this approach is that the algorithms in this book are often special cases of more general ones in the literature. For example, in Chapter 3, we provide details only for trust region globalizations of Newton's method for unconstrained problems and line search globalizations of the BFGS quasi-Newton method for unconstrained and bound constrained problems. We refer the reader to the literature for more general results. Our intention is that both our algorithms and proofs, being special cases, are more concise and simple than others in the literature and illustrate the central issues more clearly than a fully general formulation.

Part II of this book covers some algorithms for noisy or global optimization or both. There are many interesting algorithms in this class, and this book is limited to those deterministic algorithms that can be implemented in a more-or-less straightforward way. We do not, for example, cover simulated annealing, genetic algorithms, response surface methods, or random search procedures.

The reader of this book should be familiar with the material in an elementary graduate level course in numerical analysis, in particular direct and iterative methods for the solution of linear equations and linear least squares problems. The material in texts such as [127] and [264] is sufficient.

A suite of MATLAB* codes has been written to accompany this book. These codes were used to generate the computational examples in the book, but the algorithms do not depend on the MATLAB environment and the reader can easily implement the algorithms in another language, either directly from the algorithmic descriptions or by translating the MATLAB code. The MATLAB environment is an excellent choice for experimentation, doing the exercises, and small-to-medium-scale production work. Large-scale work on high-performance computers is best done in another language. The reader should also be aware that there is a large amount of high-quality software available for optimization. The book [195], for example, provides pointers to several useful packages.

Parts of this book are based upon work supported by the National Science Foundation over several years, most recently under National Science Foundation grants DMS-9321938, DMS-9700569, and DMS-9714811, and by allocations of computing resources from the North Carolina Supercomputing Center. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author and do not necessarily reflect the views of the National Science Foundation or of the North Carolina Supercomputing Center.

The list of students and colleagues who have helped me with this project, directly, through collaborations/discussions on issues that I treat in the manuscript, by providing pointers to the literature, or as a source of inspiration, is long. I am particularly indebted to Tom Banks, Jim Banoczi, John Betts, David Bortz, Steve Campbell, Tony Choi, Andy Conn, Douglas Cooper, Joe David, John Dennis, Owen Eslinger, Jörg Gablonsky, Paul Gilmore, Matthias Heinkenschlob, Laura Helfrich, Lea Jenkins, Vickie Kearn, Carl and Betty Kelley, Debbie Lockhart, Casey Miller, Jorge Moré, Mary Rose Muccie, John Nelder, Chung-Wei Ng, Deborah Poulson, Ekkehard Sachs, Dave Shanno, Joseph Skudlarek, Dan Sorensen, John Strikwerda, Mike Tocci, Jon Tolle, Virginia Torczon, Floria Tosca, Hien Tran, Margaret Wright, Steve Wright, and Kevin Yoemans.

C. T. Kelley
Raleigh, North Carolina

*MATLAB is a registered trademark of The MathWorks, Inc



Donate · Contact Us · Site Map · Join SIAM · My Account
Facebook Twitter Youtube linkedin google+