Classical And Modern Optimization (Advanced Textbooks In Mathematics)

✍ Scribed by Guillaume Carlier

• Publisher: WSPC (EUROPE)
• Year: 2022
• Tongue: English
• Leaves: 386
• Category: Library

✦ Synopsis

The quest for the optimal is ubiquitous in nature and human behavior. The field of mathematical optimization has a long history and remains active today, particularly in the development of machine learning. Classical and Modern Optimization presents a self-contained overview of classical and modern ideas and methods in approaching optimization problems. The approach is rich and flexible enough to address smooth and non-smooth, convex and non-convex, finite or infinite-dimensional, static or dynamic situations. The first chapters of the book are devoted to the classical toolbox: topology and functional analysis, differential calculus, convex analysis and necessary conditions for differentiable constrained optimization. The remaining chapters are dedicated to more specialized topics and applications. Valuable to a wide audience, including students in mathematics, engineers, data scientists or economists, Classical and Modern Optimization contains more than 200 exercises to assist with self-study or for anyone teaching a third- or fourth-year optimization class.

✦ Table of Contents

Contents
Preface
About the Author
1. Topological and Functional Analytic Preliminaries
1.1. Metric spaces
1.1.1. Completeness and compactness
1.1.2. Continuity, semicontinuity
1.1.3. Baire and Ekeland’s theorems
1.2. Normed vector spaces
1.2.1. Finite dimensions
1.2.2. Linear and bilinear maps
1.3. Banach spaces
1.3.1. Definitions and properties
1.3.2. Examples
1.3.3. Ascoli’s theorem
1.3.4. Linear maps in Banach Spaces
1.4. Hilbert spaces
1.4.1. Generalities
1.4.2. Projection onto a closed convex set
1.4.3. The dual of a Hilbert space
1.5. Weak convergence
1.6. On the existence and generic uniqueness of minimizers
1.6.1. Existence of minimizers: Variations on a theme
1.6.2. A generic uniqueness result
1.7. Exercises
2. Differential Calculus
2.1. First-order differential calculus
2.1.1. Several notions of differentiability
2.1.2. Calculus rules
2.1.3. Mean value inequalities
2.1.4. Partial derivatives
2.1.5. The finite-dimensional case, the Jacobian matrix
2.2. Second-order differential calculus
2.2.1. Definitions
2.2.2. Schwarz’s symmetry theorem
2.2.3. Second-order partial derivatives
2.2.4. Taylor formula
2.3. The inverse function and implicit function theorems
2.3.1. The inverse function theorem
2.3.2. The implicit function theorem
2.3.3. A local surjection theorem via Ekeland’s variational principle
2.4. Smooth functions on Rd, regularization, integration by parts
2.4.1. Test-functions, mollification
2.4.2. The divergence theorem and other integration by parts formulas
2.5. Exercises
3. Convexity
3.1. Hahn–Banach theorems
3.1.1. The analytic form of Hahn–Banach theorem
3.1.2. Separation of convex sets
3.2. Convex sets
3.2.1. Basic properties
3.2.2. Linear inequalities
3.2.3. Extreme points
3.3. Convex functions
3.3.1. Continuity properties
3.3.2. Differentiable characterizations
3.4. The Legendre transform
3.4.1. Basic properties
3.4.2. The biconjugate
3.4.3. Subdifferentiability
3.5. Exercises
4. Optimality Conditions for Differentiable Optimization
4.1. Unconstrained optimization
4.2. Equality constraints
4.2.1. Algebraic and topological preliminaries
4.2.2. Lagrange rule in the case of affine constraints
4.2.3. Lagrange rule in the finite-dimensional case
4.2.4. Lagrange rule in Banach spaces
4.2.5. Second-order conditions
4.3. Equality and inequality constraints
4.3.1. Karush–Kuhn–Tucker conditions for affine constraints
4.3.2. Karush–Kuhn–Tucker conditions in the general case
4.4. Exercises
5. Problems Depending on a Parameter
5.1. Setting and examples
5.2. Continuous dependence
5.2.1. Notions of continuity for set-valued maps
5.2.2. Semicontinuity of values
5.3. Parameter-independent constraints, envelope theorems
5.3.1. Differentiability under local uniqueness
5.3.2. Non-smooth cases
5.3.3. The envelope theorem for suprema of convex functions
5.4. Parameter-dependent constraints
5.4.1. Smoothness of Lagrange points
5.4.2. Multipliers and the marginal price of constraints
5.5. Discrete-time dynamic programming
5.5.1. Finite horizon
5.5.2. Infinite horizon
5.6. Exercises
6. Convex Duality and Applications
6.1. Generalities
6.2. Convex duality with respect to a perturbation
6.2.1. Setting
6.2.2. A general duality result
6.3. Applications
6.3.1. The Fenchel–Rockafellar theorem
6.3.2. Linear programming
6.3.3. Semidefinite programming
6.3.4. Link with KKT and Lagrangian duality
6.4. On the optimal transport problem
6.4.1. Kantorovich duality
6.4.2. Characterization of optimal plans
6.4.3. Monge solutions
6.4.4. The discrete case
6.5. Exercises
7. Iterative Methods for Convex Minimization
7.1. On Newton’s method
7.2. The gradient method
7.2.1. Convergence of iterates
7.2.2. Convergence of values
7.2.3. Nesterov acceleration
7.3. The proximal point method
7.4. Splitting methods
7.4.1. Forward–Backward splitting
7.4.2. Douglas–Rachford method
7.4.3. Link with augmented Lagrangian methods
7.5. Exercises
8. When Optimization and Data Meet
8.1. Principal component analysis
8.1.1. Singular value decomposition
8.1.2. Principal component analysis
8.2. Minimization for linear systems
8.2.1. Matrix operator norms and conditioning numbers
8.2.2. Least squares and linear regressions
8.2.3. Tikhonov regularization, the Moore–Penrose inverse
8.2.4. l1-penalization and sparse solutions
8.3. Classification
8.3.1. Logistic regression
8.3.2. Support-vector machines
8.4. Exercises
9. An Invitation to the Calculus of Variations
9.1. Preliminaries
9.1.1. On weak derivatives
9.1.2. Sobolev functions in dimension 1
9.1.3. Sobolev functions in higher dimensions
9.2. On integral functionals
9.2.1. Continuity, semicontinuity
9.2.2. The importance of being convex
9.2.3. Differentiability
9.3. The direct method
9.3.1. Obstructions to existence
9.3.2. Existence in the separable case
9.3.3. Relaxation
9.4. Euler–Lagrange equations and other necessary conditions
9.4.1. Euler–Lagrange equations
9.4.2. On existence of minimizers again
9.4.3. Examples
9.5. A focus on the case d = 1
9.5.1. Hamiltonian systems
9.5.2. Dynamic programming, Hamilton–Jacobi equations
9.5.3. A verification theorem
9.6. Exercises
Bibliography
Index