This book includes a thorough theoretical and computational analysis of unconstrained and constrained optimization algorithms and combines and integrates the most recent techniques and advanced computational linear algebra methods. Nonlinear optimization methods and techniques have reached their maturity and an abundance of optimization algorithms are available for which both the convergence properties and the numerical performances are known. This clear, friendly, and rigorous exposition discusses the theory behind the nonlinear optimization algorithms for understanding their properties and their convergence, enabling the reader to prove the convergence of his/her own algorithms. It covers cases and computational performances of the most known modern nonlinear optimization algorithms that solve collections of unconstrained and constrained optimization test problems with different structures, complexities, as well as those with large-scale real applications.
The book is addressed to all those interested in developing and using new advanced techniques for solving large-scale unconstrained or constrained complex optimization problems. Mathematical programming researchers, theoreticians and practitioners in operations research, practitioners in engineering and industry researchers, as well as graduate students in mathematics, Ph.D. and master in mathematical programming will find plenty of recent information and practical approaches for solving real large-scale optimization problems and applications.
Author(s): Neculai Andrei
Series: Springer Optimization and Its Applications, 195
Publisher: Springer
Year: 2022
Language: English
Pages: 823
City: Cham
Preface
Contents
List of Algorithms
List of Applications
List of Figures
List of Tables
1: Introduction
1.1 Mathematical Modeling: Linguistic Models Versus Mathematical Models
1.2 Mathematical Modeling and Computational Sciences
1.3 The Modern Modeling Scheme for Optimization
1.4 Classification of Optimization Problems
1.5 Optimization Algorithms
1.6 Collections of Applications for Numerical Experiments
1.7 Comparison of Algorithms
1.8 The Structure of the Book
2: Fundamentals on Unconstrained Optimization. Stepsize Computation
2.1 The Problem
2.2 Fundamentals on the Convergence of the Line-Search Methods
2.3 The General Algorithm for Unconstrained Optimization
2.4 Convergence of the Algorithm with Exact Line-Search
2.5 Inexact Line-Search Methods
2.6 Convergence of the Algorithm with Inexact Line-Search
2.7 Three Fortran Implementations of the Inexact Line-Search
2.8 Numerical Studies: Stepsize Computation
3: Steepest Descent Methods
3.1 The Steepest Descent
Convergence of the Steepest Descent Method for Quadratic Functions
Inequality of Kantorovich
Numerical Study
Convergence of the Steepest Descent Method for General Functions
3.2 The Relaxed Steepest Descent
Numerical Study: SDB Versus RSDB
3.3 The Accelerated Steepest Descent
Numerical Study
3.4 Comments on the Acceleration Scheme
4: The Newton Method
4.1 The Newton Method for Solving Nonlinear Algebraic Systems
4.2 The Gauss-Newton Method
4.3 The Newton Method for Function Minimization
4.4 The Newton Method with Line-Search
4.5 Analysis of Complexity
4.6 The Modified Newton Method
4.7 The Newton Method with Finite-Differences
4.8 Errors in Functions, Gradients, and Hessians
4.9 Negative Curvature Direction Methods
4.10 The Composite Newton Method
5: Conjugate Gradient Methods
5.1 The Concept of Nonlinear Conjugate Gradient
5.2 The Linear Conjugate Gradient Method
The Linear Conjugate Gradient Algorithm
Convergence Rate of the Linear Conjugate Gradient Algorithm
Preconditioning
Incomplete Cholesky Factorization
Comparison of the Convergence Rate of the Linear Conjugate Gradient and of the Steepest Descent
5.3 General Convergence Results for Nonlinear Conjugate Gradient Methods
Convergence Under the Strong Wolfe Line-Search
Convergence Under the Wolfe Line-Search
5.4 Standard Conjugate Gradient Methods
Conjugate Gradient Methods with gk+12 in the Numerator of βk
The Fletcher-Reeves Method
The CD Method
The Dai-Yuan Method
Conjugate Gradient Methods with in the Numerator of βk
The Polak-Ribière-Polyak Method
The Hestenes-Stiefel Method
The Liu-Storey Method
Numerical Study: Standard Conjugate Gradient Methods
5.5 Hybrid Conjugate Gradient Methods
Hybrid Conjugate Gradient Methods Based on the Projection Concept
Numerical Study: Hybrid Conjugate Gradient Methods
Hybrid Conjugate Gradient Methods as Convex Combinations of the Standard Conjugate Gradient Methods
The Hybrid Convex Combination of LS and DY
Numerical Study: NDLSDY
5.6 Conjugate Gradient Methods as Modifications of the Standard Schemes
The Dai-Liao Conjugate Gradient Method
The Conjugate Gradient with Guaranteed Descent (CG-DESCENT)
Numerical Study: CG-DESCENT
The Conjugate Gradient with Guaranteed Descent and Conjugacy Conditions and a Modified Wolfe Line-Search (DESCON)
Numerical Study: DESCON
5.7 Conjugate Gradient Methods Memoryless BFGS Preconditioned
The Memoryless BFGS Preconditioned Conjugate Gradient (CONMIN)
Numerical Study: CONMIN
The Conjugate Gradient Method Closest to the Scaled Memoryless BFGS Search Direction (DK / CGOPT)
Numerical Study: DK/CGOPT
5.8 Solving Large-Scale Applications
6: Quasi-Newton Methods
6.1 DFP and BFGS Methods
6.2 Modifications of the BFGS Method
6.3 Quasi-Newton Methods with Diagonal Updating of the Hessian
6.4 Limited-Memory Quasi-Newton Methods
6.5 The SR1 Method
6.6 Sparse Quasi-Newton Updates
6.7 Quasi-Newton Methods and Separable Functions
6.8 Solving Large-Scale Applications
7: Inexact Newton Methods
7.1 The Inexact Newton Method for Nonlinear Algebraic Systems
7.2 Inexact Newton Methods for Functions Minimization
7.3 The Line-Search Newton-CG Method
7.4 Comparison of TN Versus Conjugate Gradient Algorithms
7.5 Comparison of TN Versus L-BFGS
7.6 Solving Large-Scale Applications
8: The Trust-Region Method
8.1 The Trust-Region
8.2 Algorithms Based on the Cauchy Point
8.3 The Trust-Region Newton-CG Method
8.4 The Global Convergence
8.5 Iterative Solution of the Subproblem
8.6 The Scaled Trust-Region
9: Direct Methods for Unconstrained Optimization
9.1 The NELMED Algorithm
9.2 The NEWUOA Algorithm
9.3 The DEEPS Algorithm
9.4 Numerical Study: NELMED, NEWUOA, and DEEPS
10: Constrained Nonlinear Optimization Methods: An Overview
10.1 Convergence Tests
10.2 Infeasible Points
10.3 Approximate Subproblem: Local Models and Their Solving
10.4 Globalization Strategy: Convergence from Remote Starting Points
10.5 The Refining the Local Model
11: Optimality Conditions for Nonlinear Optimization
11.1 General Concepts in Nonlinear Optimization
11.2 Optimality Conditions for Unconstrained Optimization
11.3 Optimality Conditions for Problems with Inequality Constraints
11.4 Optimality Conditions for Problems with Equality Constraints
11.5 Optimality Conditions for General Nonlinear Optimization Problems
11.6 Duality
12: Simple Bound Constrained Optimization
12.1 Necessary Conditions for Optimality
12.2 Sufficient Conditions for Optimality
12.3 Methods for Solving Simple Bound Optimization Problems
12.4 The Spectral Projected Gradient Method (SPG)
Numerical Study-SPG: Quadratic Interpolation versus Cubic Interpolation
12.5 L-BFGS with Simple Bounds (L-BFGS-B)
Numerical Study: L-BFGS-B Versus SPG
12.6 Truncated Newton with Simple Bounds (TNBC)
12.7 Applications
Application A1 (Elastic-Plastic Torsion)
Application A2 (Pressure Distribution in a Journal Bearing)
Application A3 (Optimal Design with Composite Materials)
Application A4 (Steady-State Combustion)
Application A6 (Inhomogeneous Superconductors: 1-D Ginzburg-Landau)
13: Quadratic Programming
13.1 Equality Constrained Quadratic Programming
Factorization of the Full KKT System
The Schur-Complement Method
The Null-Space Method
Large-Scale Problems
The Conjugate Gradient Applied to the Reduced System
The Projected Conjugate Gradient Method
13.2 Inequality Constrained Quadratic Programming
The Primal Active-Set Method
An Algorithm for Positive Definite Hessian
Reduced Gradient for Inequality Constraints
The Reduced Gradient for Simple Bounds
The Primal-Dual Active-Set Method
13.3 Interior Point Methods
Stepsize Selection
13.4 Methods for Convex QP Problems with Equality Constraints
13.5 Quadratic Programming with Simple Bounds: The Gradient Projection Method
The Cauchy Point
Subproblem Minimization
13.6 Elimination of Variables
14: Penalty and Augmented Lagrangian Methods
14.1 The Quadratic Penalty Method
14.2 The Nonsmooth Penalty Method
14.3 The Augmented Lagrangian Method
14.4 Criticism of the Penalty and Augmented Lagrangian Methods
14.5 A Penalty-Barrier Algorithm (SPENBAR)
The Penalty-Barrier Method
Global Convergence
Numerical Study-SPENBAR: Solving Applications from the LACOP Collection
14.6 The Linearly Constrained Augmented Lagrangian (MINOS)
MINOS for Linear Constraints
Numerical Study: MINOS for Linear Programming
MINOS for Nonlinear Constraints
Numerical Study-MINOS: Solving Applications from the LACOP Collection
15: Sequential Quadratic Programming
15.1 A Simple Approach to SQP
15.2 Reduced-Hessian Quasi-Newton Approximations
15.3 Merit Functions
15.4 Second-Order Correction (Maratos Effect)
15.5 The Line-Search SQP Algorithm
15.6 The Trust-Region SQP Algorithm
15.7 Sequential Linear-Quadratic Programming (SLQP)
15.8 A SQP Algorithm for Large-Scale-Constrained Optimization (SNOPT)
15.9 A SQP Algorithm with Successive Error Restoration (NLPQLP)
15.10 Active-Set Sequential Linear-Quadratic Programming (KNITRO/ACTIVE)
16: Primal Methods: The Generalized Reduced Gradient with Sequential Linearization
16.1 Feasible Direction Methods
16.2 Active Set Methods
16.3 The Gradient Projection Method
16.4 The Reduced Gradient Method
16.5 The Convex Simplex Method
16.6 The Generalized Reduced Gradient Method (GRG)
16.7 GRG with Sequential Linear or Sequential Quadratic Programming (CONOPT)
17: Interior-Point Methods
17.1 Prototype of the Interior-Point Algorithm
17.2 Aspects of the Algorithmic Developments
17.3 Line-Search Interior-Point Algorithm
17.4 A Variant of the Line-Search Interior-Point Algorithm
17.5 Trust-Region Interior-Point Algorithm
17.6 Interior-Point Sequential Linear-Quadratic Programming (KNITRO/INTERIOR)
18: Filter Methods
18.1 Sequential Linear Programming Filter Algorithm
18.2 Sequential Quadratic Programming Filter Algorithm
19: Interior-Point Filter Line-Search
19.1 Basic Algorithm IPOPT
The Primal-Dual Barrier Approach
Solving the Barrier Problem
Line-Search Filter Method
Second-Order Corrections
The Algorithm
19.2 Implementation Details
General Lower and Upper Bounds
Initialization
Handling Unbounded Solution Sets
Inertia Correction
Automatic Scaling of the Problem
Feasibility Restoration Phase
Numerical Study-IPOPT: Solving Applications from the LACOP Collection
20: Direct Methods for Constrained Optimization
20.1 COBYLA Algorithm
Numerical Study-COBYLA Algorithm
20.2 DFL Algorithm
Numerical Study-DFL Algorithm
Appendix A: Mathematical Review
A1. Elements of Applied Numerical Linear Algebra
Vectors
Norms of Vectors
Matrices
Matrix Norms
Subspaces
Inverse of a Matrix
Orthogonality
Eigenvalues
Positive Definite Matrices
Gaussian Elimination (LU Factorization)
Gaussian Elimination with Partial Pivoting
Gaussian Elimination with Complete Pivoting
Cholesky Factorization
Modified Cholesky Factorization
QR Decomposition
Singular Value Decomposition
Spectral Decomposition (Symmetric Eigenvalue Decomposition)
Elementary Matrices
Conditioning and Stability
Determinant of a Matrix
Trace of a matrix
A2. Elements of Analysis
Rates of Convergence
Finite-Difference Derivative Estimates
Automatic Differentiation
Order Notation
A3. Elements of Topology in the Euclidian Space n
A4. Elements of Convexity:Convex Sets and Convex Functions
Convex Sets
Convex Functions
Strong Convexity
Appendix B: The SMUNO Collection
Small-Scale Continuous Unconstrained Optimization Applications
Appendix C: The LACOP Collection
Large-Scale Continuous Nonlinear Optimization Applications
Appendix D: The MINPACK-2 Collection
Large-Scale Unconstrained Optimization Applications
References
Author Index
Subject Index
