Numerical optimization. Theoretical and practical aspects. Transl. from the French. (English) Zbl 1014.65045

Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude; Sagastizábal, Claudia A.

Universitext. Berlin: Springer. xiii, 419 p. (2003).

The purpose of the book is best described by the authors themselves:
“This book is entirely devoted to numerical algorithms for optimization, their theoretical foundations and convergence properties, as well as their implementation, their use, and other practical aspects. The aim is to familiarize the reader with the numerical algorithms: understanding their behaviour in practice, properly using existing software libraries, adequately designing and implementing home made methods, correctly diagnosing the causes of possible difficulties. Expected readers are engineers, Master or Ph.D students, confirmed researchers, in applied mathematics or from various other disciplines where optimization is a need.
Our aim is therefore not to give most accurate results in optimization, nor to detail the latest refinements of such and such method. First of all, little is said concerning optimization theory proper (optimality conditions, constraint qualification, stability theory). As for algorithms, we limit ourselves most of the time to stable and well-established material. Throughout we keep as a leading thread the actual practical value of optimization methods, in terms of their efficiency to solve real-world problems. Nevertheless, serious attention is paid to the theoretical properties of optimization methods: this book is mainly based upon theorems. Besides, some new and promising results or approaches could not be completely discarded; they are also presented, generally in the form of special sections, mainly aimed at orienting the reader to the relevant bibliography.”
The considered topics are:
1. General introduction; 2. Basic methods; 3. Line-searches; 4. Newtonian methods; 5. Conjugate gradient; 6. Special methods; 7. Some theory of nonsmooth optimization; 8. Some methods of nonsmooth optimization; 9. Bundle methods. The quest of descent; 10. Decomposition and duality; 11. Background; 12. Local methods for problems with equality constraints; 13. Local methods for problems with equality and inequality constraints; 14. Exact penalization; 15. Globalization by line-search; 16. Quasi-Newton versions; 17. Linearly constrained optimization and simplex algorithm; 18. Linear monotone complementarity and associated vector fields; 19. Predictor-corrector algorithms; 20. Non-feasible algorithms; 21. Self-duality; 22. One-step methods; 23. Complexity of linear optimization problems with integer data; 24. Karmarkar’s algorithm.
The book is an excellent basis for studying and implementing optimization algorithms. Old and well-established techniques are included, as long as they are still in practical use. But also relevant new technologies are outlined, for example interior point algorithms and complexity issues.
The referee enjoyed the reading very much. The topics are presented in a clear and a mathematically rigorous way. The broad expert knowledge of the authors and their great experience in mathematical optimizion, especially in the design of numerical algorithms, is visible in each line. The book comes with 319 references and numerous examples and exercises.

Reviewer: Klaus Schittkowski (Bayreuth)

MSC:

65K05	Numerical mathematical programming methods
65-02	Research exposition (monographs, survey articles) pertaining to numerical analysis
90-08	Computational methods for problems pertaining to operations research and mathematical programming
90C05	Linear programming
90C20	Quadratic programming
90C30	Nonlinear programming
90C51	Interior-point methods
90C53	Methods of quasi-Newton type
65Y15	Packaged methods for numerical algorithms
65Y20	Complexity and performance of numerical algorithms

Keywords:

nonlinear programming; unconstrained optimization; nonsmooth optimization; Newton’s method; interior point methods; linear programming; quadratic programming; complexity; textbook; numerical algorithms; software libraries; line-searches; conjugate gradient; exact penalization; simplex algorithm; linear monotone complementarity; predictor-corrector algorithms; non-feasible algorithms; one-step methods; Karmarkar’s algorithm; examples; exercises

Software:

PLCP; SQPlab