Bonnans / Gilbert / Lemarechal Numerical Optimization

Theoretical and Practical Aspects
2003
ISBN: 978-3-662-05078-1
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 423 Seiten, eBook

Reihe: Universitext

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.

Zielgruppe

Graduate

Autoren/Hrsg.

Bonnans, Joseph-Frédéric

Gilbert, Jean Charles

Lemarechal, Claude

Sagastizábal, Claudia A.

Inhaltsverzeichnis

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

Über Autor(innen)

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.