This book has two main objectives:
• to provide a concise introduction to nonlinear optimization methods, which can be used as a textbook at a graduate or upper undergraduate level;
• to collect and organize selected important topics on optimization algorithms, not easily found in textbooks, which can provide material for advanced courses or can serve as a reference text for self-study and research.
The basic material on unconstrained and constrained optimization is organized into two blocks of chapters:
• basic theory and optimality conditions
• unconstrained and constrained algorithms.
These topics are treated in short chapters that contain the most important results in theory and algorithms, in a way that, in the authors’ experience, is suitable for introductory courses.
A third block of chapters addresses methods that are of increasing interest for solving difficult optimization problems. Difficulty can be typically due to the high nonlinearity of the objective function, ill-conditioning of the Hessian matrix, lack of information on first-order derivatives, the need to solve large-scale problems.
In the book various key subjects are addressed, including: exact penalty functions and exact augmented Lagrangian functions, non monotone methods, decomposition algorithms, derivative free methods for nonlinear equations and optimization problems.
The appendices at the end of the book offer a review of the essential mathematical background, including an introduction to convex analysis that can make part of an introductory course.
Author(s): Luigi Grippo, Marco Sciandrone
Series: UNITEXT, 152
Publisher: Springer
Year: 2023
Language: English
Pages: 720
City: Cham
Preface
Contents
1 Introduction
1.1 Optimization Problems
1.2 Classification of Optimization Problems
1.3 Continuous Optimization Problems Over Rn
1.3.1 Classification
1.3.2 Examples of Continuous Problems
1.3.2.1 A Linear Programming Problem: Transportation Problem
1.3.2.2 An Unconstrained Optimization Problem: Neural Network Training
1.3.2.3 A Nonlinear Optimization Problem with Box Constraints: Design of a Compact Low Field Magnetic Resonance Imaging Magnet
1.3.2.4 A Finite-Dimensional Continuous Optimization Problem: Portfolio Selection Problem
1.3.2.5 A Convex Optimization Problem with Linear Constraints: Traffic Assignment Problem
1.3.2.6 A Constrained Optimization Problem with Nonlinear Constraints: Novelty Detection
1.4 Appendix: Examples of Problems in Different Spaces
1.4.1 An Infinite-Dimensional Optimization Problem: Control of a Dynamical System
1.4.2 An Integer Linear Programming Problem: Scheduling of Sport Tournaments
1.4.3 A Mixed Integer Programming Problem: Clustering
1.5 Notes and References
2 Fundamental Definitions and Basic Existence Results
2.1 Local and Global Minimum Points
2.2 Minimizers in Convex Programming
2.3 Minimizers in Generalized Convex Problems
2.4 Minimizers in Concave Programming
2.5 Equivalent Transformations
2.5.1 Equivalence Criterion
2.5.2 Some Basic Examples
2.5.3 Fractional Programming
2.5.4 Goal Programming
2.6 Existence Conditions
2.6.1 Existence in Unconstrained Optimization
2.6.2 Existence in Constrained Optimization
2.6.3 Feasibility Problems
2.7 Exercises
2.8 Notes and References
3 Optimality Conditions for Unconstrained Problems in Rn
3.1 Descent Directions
3.2 Optimality Conditions
3.3 Optimality Conditions in the Convex Case
3.4 Exercises
3.5 Notes and References
4 Optimality Conditions for Problems with Convex Feasible Set
4.1 Optimality Conditions Based on Feasible Directions
4.2 The Case of Feasible Set Defined by Linear Constraints
4.2.1 Feasible Directions for Problems with Box Constraints
4.3 Optimality Conditions over a Convex Set
4.4 Projection on a Convex Set
4.5 Exercises
4.6 Notes and References
5 Optimality Conditions for Nonlinear Programming
5.1 Problem Formulation and Notation
5.2 Fritz John Conditions
5.3 Constraint Qualifications and KKT Conditions
5.4 Sufficient Conditions in the Convex Case
5.5 Second Order Optimality Conditions
5.6 Linearly Constrained Problems
5.6.1 Problems with Non Negativity Constraints
5.6.2 Problems with Box Constraints
5.6.3 Problems with Simplex Constraints
5.6.4 Quadratic Programming
5.6.5 Linear Programming
5.7 Exercises
5.8 Notes and References
6 Duality Theory
6.1 The Dual Problem
6.2 Lagrangian Duality
6.2.1 Basic Concepts, Weak and Strong Lagrangian Duality
6.2.2 Saddle Point Optimality Conditions
6.3 Wolfe's Dual
6.3.1 Wolfe's Dual in Quadratic Convex Programming Problems with Linear Inequality Constraints
6.4 Appendix
6.5 Exercises
6.6 Notes and References
7 Optimality Conditions Based on Theorems of the Alternative
7.1 Introduction
7.2 Optimality Conditions for Problems with Inequality Constraints
7.3 Optimality Conditions Based on Tangent Directions
7.4 Optimality Conditions for Problems with Equality and Inequality Constraints
7.5 Fritz John Conditions Established with Motzkin Theorem
7.5.1 KKT Conditions from FJ Conditions
7.6 Appendix
7.6.1 Linear Inequalities and Theorems of the Alternative
7.6.1.1 Equivalent Transformations
7.6.1.2 A Theorem of the Alternative for Linear Equations
7.6.1.3 Implications of an Inequality System
7.6.1.4 Farkas Lemma
7.6.1.5 Other Alternative Theorems
7.6.2 Non Homogeneous Farkas Lemma and Optimality for LP
7.6.2.1 Non Homogeneous Farkas Lemma
7.6.2.2 Optimality Conditions for LP
7.7 Notes and References
8 Basic Concepts on Optimization Algorithms
8.1 Structure of Optimization Algorithms
8.2 Existence and Uniqueness of Limit Points
8.3 Convergence Towards Critical Points
8.4 Local and Global Convergence
8.5 Convergence Rate
8.6 Basic Concepts of Complexity Analysis
8.7 Notes and References
9 Unconstrained Optimization Algorithms
9.1 Preliminary Concepts
9.2 Limit Points
9.3 Convergence Towards Stationary Points
9.4 Classification of Unconstrained Algorithms
9.5 Convergence of Line Search Based Methods
9.6 Exercises
9.7 Notes and References
10 Line Search Methods
10.1 Basic Features and Classification of Line Searches
10.2 Armijo's Method
10.3 Step-Length Extension and Goldstein Conditions
10.4 Wolfe Conditions
10.5 Derivative-Free Line Searches
10.5.1 Backtracking Armijo-Type Derivative-FreeAlgorithms
10.5.2 Derivative-Free Linesearches with Step Extension
10.6 Appendix A: Algorithms Employing Wolfe Conditions
10.7 Appendix B: Implementation of Line Searches
10.7.1 Initial Interval
10.7.2 Initial Estimate of the Step-Size
10.7.3 Interpolation Formulas
10.7.3.1 Quadratic Interpolation
10.7.3.2 Cubic Interpolation
10.7.4 Application of Interpolation Formulas
10.7.5 Stopping Criteria and Failures
10.8 Exercises
10.9 Notes and References
11 Gradient Method
11.1 The Steepest Descent Direction
11.2 The Gradient Method
11.3 Gradient Method with Constant Step-Size
11.4 Convergence Rate
11.5 Finite Convergence in the Quadratic Case
11.6 Complexity of the Steepest Descent Method
11.7 Modified Gradient Methods
11.8 Exercises
11.9 Notes and References
12 Conjugate Direction Methods
12.1 The Conjugate Direction Method
12.2 The Conjugate Gradient Method (CGM): The Quadratic Case
12.3 Convergence Rate
12.4 Preconditioning
12.5 The CGM in the Non Quadratic Case
12.6 Fletcher-Reeves Method
12.7 Method of Polyak-Polak-Ribiére (PPR)
12.8 Appendix: The CG Method When the Hessian Matrix is Positive Semidefinite
12.9 Exercises
12.10 Notes and References
13 Newton's Method
13.1 The Pure Newton Iteration
13.2 Local Convergence and Convergence Rate
13.3 Shamanskii Method
13.4 Globalization of Newton's Method for Minimization
13.5 Hybrid Methods
13.6 Modification Methods
13.7 Exercises
13.8 Notes and References
14 Trust Region Methods
14.1 The General Trust Region Framework and Convergence Results
14.2 Classification of Solution Methods for the Trust Region Subproblem
14.3 The Cauchy Step-Based Method
14.4 The Dogleg Method
14.5 The Conjugate Gradient Method of Steihaug
14.6 Necessary and Sufficient Optimality Conditions for the Trust Region Subproblem
14.7 Trust Region Approach to Globalizing Newton's Method
14.8 Complexity Issues and Adaptive Regularized Methods
14.9 Appendix: Proofs of Convergence
14.10 Exercises
14.11 Notes and References
15 Quasi-Newton Methods
15.1 Preliminaries
15.2 Rank 1 Formulae
15.3 Rank Two Formulae and the BFGS Method
15.4 Global Convergence of the BFGS Method
15.5 Convergence Rate
15.6 Exercises
15.7 Notes and References
16 Methods for Nonlinear Equations
16.1 Preliminaries
16.2 Newton-Type Methods
16.3 Broyden's Method
16.4 Residual Based Methods
16.5 Notes and References
17 Methods for Least Squares Problems
17.1 Least Squares Problems
17.2 Linear Least Squares Problems
17.3 Methods for Nonlinear Least Squares Problems
17.4 Gauss-Newton Method
17.5 Levenberg-Marquardt Method
17.6 Recursive Linear Least Squares Algorithm
17.7 Some Notes on Incremental Methods for Nonlinear Problems
17.8 Exercises
17.9 Notes and References
18 Methods for Large-Scale Optimization
18.1 Solution Strategies for Large Scale Problems
18.2 Truncated Newton Method
18.3 Globally Convergent Truncated Newton Methods
18.3.1 Preliminaries
18.3.2 A Truncated Newton Method Based on a Line Search
18.4 Quasi-Newton Methods for Large-Scale Optimization
18.4.1 Preliminaries
18.4.2 Memoryless Quasi-Newton Methods
18.4.3 Limited-Memory Quasi-Newton Methods
18.5 Exercises
18.6 Notes and References
19 Derivative-Free Methods for Unconstrained Optimization
19.1 Motivation and Classification of Derivative-Free Methods
19.2 The Coordinate Method
19.2.1 Preliminary Concepts
19.2.2 Coordinate Method with Simple Decrease
19.3 The Hooke-Jeeves Method
19.4 The Nelder-Mead Method
19.5 Linesearch-Based Methods
19.5.1 Basic Assumptions and Convergence Conditions
19.5.2 Globalization of Direct Search Methods Through Line Searches
19.6 Approximation of Derivatives and Implicit Filtering
19.6.1 Simplex Gradient
19.6.2 Implicit Filtering
19.6.3 Combination with Coordinate Search
19.7 Model-Based Methods
19.8 Exercises
19.9 Notes and References
20 Methods for Problems with Convex Feasible Set
20.1 Problems with Convex Feasible Set
20.2 Line Search Along a Feasible Direction
20.3 The Frank-Wolfe Method (Conditional Gradient Method)
20.4 Gradient Projection Method
20.5 A Derivative-Free Method for Box Constrained Problems
20.6 Concave Programming for Minimizing the Zero-Norm Over Polyhedral Sets
20.7 Frank-Wolfe Method Applied to Concave Programming Problems
20.8 Exercises
20.9 Notes and References
21 Penalty and Augmented Lagrangian Methods
21.1 Basic Concepts
21.2 Sequential Penalty Functions
21.3 Augmented Lagrangian Functions
21.4 Non Differentiable Exact Penalty Functions
21.5 Continuously Differentiable Exact Penalty Functions
21.6 Exact Shifted Barrier Functions
21.7 Exact Augmented Lagrangian Functions
21.8 Exercises
21.9 Notes and References
22 SQP Methods
22.1 Newton Type Methods for the Equality Constrained Case
22.2 Extension to Inequality Constrained Problems
22.3 EQP Methods
22.4 Quasi-Newton Modification
22.5 Solution of the Quadratic Programming Subproblem
22.6 Globalization Strategies
22.6.1 Nondifferentiable Merit Functions
22.6.2 Smooth Merit Functions
22.7 Notes and References
23 Introduction to Interior Point Methods
23.1 Basic Definitions and Barrier Methods
23.2 Interior Point Methods for Linear Programming
23.2.1 Definitions and Notation
23.2.2 A Summary of Basic LP Theory
23.2.3 Main Classes of IPMs for LP and BasicAssumptions
23.2.4 Feasible Path-Following Methods
23.2.4.1 Central Path for Feasible Methods
23.2.4.2 Primal-Dual Path-Following Methods
23.2.5 Infeasible Methods
23.3 Extensions
23.3.1 Quadratic Programming
23.3.2 IPMs for Nonconvex Problems
23.4 Appendix: Regularity and Optimality
23.5 Notes and References
24 Nonmonotone Methods
24.1 Motivation and Basic Concepts
24.2 Convergence Issues in Nonmonotone Methods
24.3 Reference Values and Preliminary Results
24.4 Armijo-Type Nonmonotone Line Searches
24.5 Nonmonotone Armijo-Goldstein and Parabolic Searches
24.6 Nonmonotone Derivative-Free Linesearches
24.7 Watchdog Techniques
24.8 Nonmonotone Globalization of Newton's Method
24.9 Nonmonotone Inexact Newton-Type Methods for Nonlinear Equations
24.10 Notes and References
25 Spectral Gradient Methods
25.1 The BB Method in the Quadratic Case
25.2 Nonmonotone Globalization of the BB Method
25.3 Spectral Gradient Methods for Nonlinear Equations
25.4 Projected Spectral Gradient Method for Minimization on Convex Sets
25.5 Exercises
25.6 Notes and References
26 Decomposition Methods
26.1 Motivation and Examples
26.2 Classes of Decomposition Methods and Basic Notation
26.3 Block Gauss-Seidel (GS) Method and Extensions
26.3.1 The Basic Scheme of the GS Method
26.3.2 A Line Search Algorithm in the Component Space
26.3.3 Limit Points of the GS Algorithm
26.3.4 The Two-Block GS Method
26.3.5 Convergence of the GS Method Under Generalized Convexity Assumptions
26.3.6 Proximal-Point Modification of the GS Method
26.4 Block Descent Methods
26.4.1 A Basic Unconstrained Block Descent Algorithm
26.4.2 A Basic Constrained Block Descent Algorithm
26.5 The Gauss-Southwell Algorithm
26.6 Decomposition with Variable and Overlapping Blocks
26.7 The Jacobi Method
26.8 Algorithms for Problems with a Single Linear Equality Constraint and Box Constraints
26.9 Sequential Minimal Optimization (SMO) Algorithms
26.10 Appendix: Proof of Proposition 26.16
26.11 Exercises
26.12 Notes and References
27 Basic Concepts of Linear Algebra and Analysis
27.1 The Space Rn as Linear Space
27.2 Matrices and Systems of Linear Equalities
27.3 Norm, Metric, Topology, Scalar Product Over Rn
27.4 Notation and Results on Real Matrices
27.4.1 Determinant, Minors, Trace
27.4.2 Norm of a Matrix
27.4.3 Orthogonal Matrices
27.4.4 Eigenvalues of Symmetric Matrices
27.4.5 Singular Value Decomposition
27.5 Quadratic Forms
28 Differentiation in Rn
28.1 First Order Derivatives of a Real Function
28.2 Differentiation of a Vector Function
28.3 Second Order Derivatives of a Real Function
28.4 The Mean Value Theorem and Taylor's Theorem
28.5 Derivatives of Composite Functions
28.6 Examples
29 Introduction to Convex Analysis
29.1 Convex Sets
29.2 Convex Functions
29.3 Composition of Convex Functions
29.4 Convexity of Differentiable Functions
29.5 Monotonicity Conditions on f
29.6 Basic Notions of Generalized Convexity
References
Index
