Part I. Black-Box Optimization
1 Nonlinear Optimization
1.1 The World of Nonlinear Optimization
1.1.1 General Formulation of the Problem
1.1.2 Performance of Numerical Methods
1.1.3 Complexity Bounds for Global Optimization
1.1.4 Identity Cards of the Fields
1.2 Local Methods in Unconstrained Minimization
1.2.1 Relaxation and Approximation
1.2.2 Classes of Differentiable Functions
1.2.3 The Gradient Method
1.2.4 Newton's Method
1.3 First-Order Methods in Nonlinear Optimization
1.3.1 The Gradient Method and Newton's Method: What Is Different?
1.3.2 Conjugate Gradients
1.3.3 Constrained Minimization
2 Smooth Convex Optimization
2.1 Minimization of Smooth Functions
2.1.1 Smooth Convex Functions
2.1.2 Lower Complexity Bounds for FL∞,1(Rn)
2.1.3 Strongly Convex Functions
2.1.4 Lower Complexity Bounds for Sμ,L∞,1(Rn)
2.1.5 The Gradient Method
2.2 Optimal Methods
2.2.1 Estimating Sequences
2.2.2 Decreasing the Norm of the Gradient
2.2.3 Convex Sets
2.2.4 The Gradient Mapping
2.2.5 Minimization over Simple Sets
2.3 The Minimization Problem with Smooth Components
2.3.1 The Minimax Problem
2.3.2 Gradient Mapping
2.3.3 Minimization Methods for the Minimax Problem
2.3.4 Optimization with Functional Constraints
2.3.5 The Method for Constrained Minimization
3 Nonsmooth Convex Optimization
3.1 General Convex Functions
3.1.1 Motivation and Definitions
3.1.2 Operations with Convex Functions
3.1.3 Continuity and Differentiability
3.1.4 Separation Theorems
3.1.5 Subgradients
3.1.6 Computing Subgradients
3.1.7 Optimality Conditions
3.1.8 Minimax Theorems
3.1.9 Basic Elements of Primal-Dual Methods
3.2 Methods of Nonsmooth Minimization
3.2.1 General Lower Complexity Bounds
3.2.2 Estimating Quality of Approximate Solutions
3.2.3 The Subgradient Method
3.2.4 Minimization with Functional Constraints
3.2.5 Approximating the Optimal Lagrange Multipliers
3.2.6 Strongly Convex Functions
3.2.7 Complexity Bounds in Finite Dimension
3.2.8 Cutting Plane Schemes
3.3 Methods with Complete Data
3.3.1 Nonsmooth Models of the Objective Function
3.3.2 Kelley's Method
3.3.3 The Level Method
3.3.4 Constrained Minimization
4 Second-Order Methods
4.1 Cubic Regularization of Newton's Method
4.1.1 Cubic Regularization of Quadratic Approximation
4.1.2 General Convergence Results
4.1.3 Global Efficiency Bounds on Specific Problem Classes
4.1.4 Implementation Issues
4.1.5 Global Complexity Bounds
4.2 Accelerated Cubic Newton
4.2.1 Real Vector Spaces
4.2.2 Uniformly Convex Functions
4.2.3 Cubic Regularization of Newton Iteration
4.2.4 An Accelerated Scheme
4.2.5 Global Non-degeneracy for Second-Order Schemes
4.2.6 Minimizing Strongly Convex Functions
4.2.7 False Acceleration
4.2.8 Decreasing the Norm of the Gradient
4.2.9 Complexity of Non-degenerate Problems
4.3 Optimal Second-Order Methods
4.3.1 Lower Complexity Bounds
4.3.2 A Conceptual Optimal Scheme
4.3.3 Complexity of the Search Procedure
4.4 The Modified Gauss–Newton Method
4.4.1 Quadratic Regularization of the Gauss–Newton Iterate
4.4.2 The Modified Gauss–Newton Process
4.4.3 Global Rate of Convergence
4.4.4 Discussion
Part II. Structural Optimization
5 Polynomial-Time Interior-Point Methods
5.1 Self-concordant Functions
5.1.1 The Black Box Concept in Convex Optimization
5.1.2 What Does the Newton's Method Actually Do?
5.1.3 Definition of Self-concordant Functions
5.1.4 Main Inequalities
5.1.5 Self-Concordance and Fenchel Duality
5.2 Minimizing Self-concordant Functions
5.2.1 Local Convergence of Newton's Methods
5.2.2 Path-Following Scheme
5.2.3 Minimizing Strongly Convex Functions
5.3 Self-concordant Barriers
5.3.1 Motivation
5.3.2 Definition of a Self-concordant Barrier
5.3.3 Main Inequalities
5.3.4 The Path-Following Scheme
5.3.5 Finding the Analytic Center
5.3.6 Problems with Functional Constraints
5.4 Applications to Problems with Explicit Structure
5.4.1 Lower Bounds for the Parameter of a Self-concordant Barrier
5.4.2 Upper Bound: Universal Barrier and Polar Set
5.4.3 Linear and Quadratic Optimization
5.4.4 Semidefinite Optimization
5.4.5 Extremal Ellipsoids
5.4.6 Constructing Self-concordant Barriers for Convex Sets
5.4.7 Examples of Self-concordant Barriers
5.4.8 Separable Optimization
5.4.9 Choice of Minimization Scheme
6 The Primal-Dual Model of an Objective Function
6.1 Smoothing for an Explicit Model of an Objective Function
6.1.1 Smooth Approximations of Non-differentiable Functions
6.1.2 The Minimax Model of an Objective Function
6.1.3 The Fast Gradient Method for Composite Minimization
6.1.4 Application Examples
6.1.5 Implementation Issues
6.2 An Excessive Gap Technique for Non-smooth ConvexMinimization
6.2.1 Primal-Dual Problem Structure
6.2.2 An Excessive Gap Condition
6.2.3 Convergence Analysis
6.2.4 Minimizing Strongly Convex Functions
6.3 The Smoothing Technique in Semidefinite Optimization
6.3.1 Smooth Symmetric Functions of Eigenvalues
6.3.2 Minimizing the Maximal Eigenvalue of the Symmetric Matrix
6.4 Minimizing the Local Model of an Objective Function
6.4.1 A Linear Optimization Oracle
6.4.2 The Method of Conditional Gradients with Composite Objective
6.4.3 Conditional Gradients with Contraction
6.4.4 Computing the Primal-Dual Solution
6.4.5 Strong Convexity of the Composite Term
6.4.6 Minimizing the Second-Order Model
7 Optimization in Relative Scale
7.1 Homogeneous Models of an Objective Function
7.1.1 The Conic Unconstrained Minimization Problem
7.1.2 The Subgradient Approximation Scheme
7.1.3 Direct Use of the Problem Structure
7.1.4 Application Examples
7.2 Rounding of Convex Sets
7.2.1 Computing Rounding Ellipsoids
7.2.2 Minimizing the Maximal Absolute Value of Linear Functions
7.2.3 Bilinear Matrix Games with Non-negative Coefficients
7.2.4 Minimizing the Spectral Radius of Symmetric Matrices
7.3 Barrier Subgradient Method
7.3.1 Smoothing by a Self-Concordant Barrier
7.3.2 The Barrier Subgradient Scheme
7.3.3 Maximizing Positive Concave Functions
7.3.4 Applications
7.3.5 Online Optimization as an Alternative to Stochastic Programming
7.4 Optimization with Mixed Accuracy
7.4.1 Strictly Positive Functions
7.4.2 The Quasi-Newton Method
7.4.3 Interpretation of Approximate Solutions
Appendix A. Solving Some Auxiliary Optimization Problems
A.1 Newton's Method for Univariate Minimization
A.2 Barrier Projection onto a Simplex
Bibliographical Comments
Chapter 1: Nonlinear Optimization
Chapter 2: Smooth Convex Optimization
Chapter 3: Nonsmooth Convex Optimization
Chapter 4: Second-Order Methods
Chapter 5: Polynomial-Time Interior-Point Methods
Chapter 6: The Primal-Dual Model of an Objective Function
Chapter 7: Optimization in Relative Scale
References
Index
· · · · · · (收起)