Starting with illustrative real-world examples, this book exposes in a tutorial way algorithms for numerical optimization: fundamental ones (Newtonian methods, line-searches, trust-region, sequential quadratic programming, etc.), as well as more specialized and advanced ones (nonsmooth optimization, decomposition techniques, and interior-point methods). Most of these algorithms are explained in a detailed manner, allowing straightforward implementation. Theoretical aspects are addressed with care, often using minimal assumptions.

The present version contains substantial changes with respect to the first edition. Part I on unconstrained optimization has been completed with a section on quadratic programming. Part II on nonsmooth optimization has been thoroughly reorganized and expanded. In addition, nontrivial application problems have been inserted, in the form of computational exercises. These should help the reader to get a better understanding of optimization methods beyond their abstract description, by addressing important features to be taken into account when passing to implementation of any numerical algorithm.

This level of detail is intended to familiarize the reader with some of the crucial questions of numerical optimization: how algorithms operate, why they converge, difficulties that may be encountered and their possible remedies.

Autorentext

The four authors are leading international specialists in various branches of nonlinear optimization (one of them received the Dantzig Prize). They are working - or have worked - at INRIA, the French National Institute for Research in Computer Science and Control, and they also teach in various universities and "Grandes Écoles". All of them continually collaborate with industry on problems dealing with optimization, in fields such as energy management, geoscience, life sciences, etc.

Klappentext

This book starts with illustrations of the ubiquitous character of optimization, and describes numerical algorithms in a tutorial way. It covers fundamental algorithms as well as more specialized and advanced topics for unconstrained and constrained problems. This new edition contains computational exercises in the form of case studies which help understanding optimization methods beyond their theoretical description when coming to actual implementation.

Inhalt

Preliminaries 1 General Introduction 1.1 Generalities on Optimization 1.2 Motivation and Examples 1.3 General Principles of Resolution 1.4 General Convergence Theorem: Zangwill 1.5 Generalities on Convergence 1.6 Computing the Gradient Part I - Unconstrained Problems 2 Basic Methods 2.1 Existence Questions 2.2 Optimality Conditions 2.3 First-Order Methods 2.4 Link with the General Descent Scheme 2.5 Steepest-Descent Method 2.6 Implementation 3 Line-Searches 3.1 General Scheme 3.2 Computing the New t 3.3 Optimal Stepsize (for the record only) 3.4 Modern Line-Search: Wolfe's Rule 3.5 Other Line-Searches: Goldstein and Price, Armijo 3.6 Implementation Considerations 4 Newtonian Methods 4.1 Preliminaries 4.2 Forcing Global Convergence 4.3 Alleviating the Method 4.4 Quasi-Newton Methods 4.5 Global Convergence 4.6 Local Convergence: Generalities 4.7 Local Convergence: BFGS 5 Conjugate Gradient 5.1 Outline of Conjugate Gradient 5.2 Developing the Method 5.3 Computing the Direction 5.4 The Algorithm Seen as an Orthogonalization Process 5.5 Application to Non-Quadratic Functions 5.6 Relation with Quasi-Newton 6 Special Methods 6.1 Trust-Regions 6.2 Least-Squares Problems: Gauss-Newton 6.3 Large-Scale Problems: Limited-Memory Quasi-Newton 6.4 Truncated Newton Part II - Nonsmooth Optimization 7 Some Theory of Nonsmooth Optimization 7.1 First Elements of Convex Analysis 7.2 Lagrangian Relaxation and Duality 7.3 Two Convex Nondifferentiable Functions 8 Some Methods in Nonsmooth Optimization 8.1 Why Special Methods? 8.2 Descent Methods 8.3 Two Black-Box Methods 9 Bundle Methods. The Quest of Descent 9.1 Stabilization. A Primal Approach 9.2 Some Examples of Stabilized Problems 9.3 Penalized Bundle Methods 10 Decomposition and Duality 10.1 Primal-DualRelations 10.2 Back to the Primal. Recovering Primal Solutions 10.3 Price Decomposition 10.4 Resource Decomposition 10.5 Other Decomposition Techniques Part III - Newton's Methods in Constrained Optimization 11 Background 11.1 Differential Calculus 11.2 Existence and Uniqueness of Solutions 11.3 First-Order Optimality Conditions 11.4 Second-Order Optimality Conditions 11.5 Speed of Convergence 11.6 Projection onto a Closed Convex Set 11.7 The Newton Method Exercises 12 Local Methods for Problems with Equality Constraints 12.1 Newton's Method 12.2 Adapted Decompositions of {@mathbb R}^n 12.3 Local Analysis of Newton's Method 12.4 Computation of the Newton Step 12.5 Reduced Hessian Algorithm 12.6 A Comparison of the Algorithms Notes Exercises 13 Local Methods for Problems with Equality and Inequality Constraints 13.1 The SQP Algorithm 13.2 Primal-Dual Quadratic Convergence 13.3 Primal Superlinear Convergence Notes 14 Exact Penalization 14.1 Overview 14.2 The Lagrangian 14.3 The Augmented Lagrangian 14.4 Nondifferentiable Augmented Function Notes Exercises 15 Globalization by Line-Search 15.1 Line-Search SQP Algorithms 15.2 Truncated SQP 15.3 From Global to Local Notes Exercises 16 Quasi-Newton Versions 16.1 Principles 16.2 Quasi-Newton SQP 16.3 Reduced Quasi-Newton Algorithm Part IV - Interior-Point Algorithms for Linear and Quadratic Optimization 17 Linearly Constrained Optimization and Simplex Algorithm 17.1 Existence of Solutions 17.2 Duality 17.3 The Simplex Algorithm 17.4 Comments 18 Linear Monotone Complementarity and Associated Vector Fields 18.1 Logarithmic Penalty and Central Path 18.2 Linear Monotone Complementarity 18.3 Vector Fields Associated with the Central Path 18.4 Continuous Trajectories 18.5 Comments 19 Predictor-Corrector