Nicolas Boumal

Click
here to download the book. Last update: Sep. 11, 2020.

This advanced
draft may still change. Please e-mail
me about any mistakes you spot or suspect, be it typos or
more serious things, and about suggestions for improvements or
missing references: I appreciate your input. For general
questions about geometry and optimization, please use the Manopt forum, MathOverflow or Math StackExchange, and feel free to let
me know about it.

To hear about
updates, fill in the form below. This also helps me know my
audience.

In a
one-semester graduate course of the mathematics department at
Princeton University in 2019 and 2020, I covered much of
Chapters 1–6 and select parts of Chapter 7 before the
midterm break, then much of Chapters 8–9 and select parts
of Chapters 10–11 after the break. The course is popular
with applied mathematicians and mathematically inclined
engineering students, at the graduate and advanced undergraduate
level.

You may also be interested in the Manopt toolboxes (Matlab, Python, Julia) and in the book Optimization Algorithms on Matrix Manifolds by Absil, Mahony and Sepulchre (Princeton University Press, 2008), all freely available online.

These
slides hold a summary of the basic geometric tools and
algorithms from Chapters 3 and 5. Here are a one-hour video and a two-hour video introducing the basics of
differential geometry and Riemannian geometry for optimization
on smooth manifolds, using a variation of those slides.

title = {An introduction to optimization on smooth manifolds},

author = {Boumal, Nicolas},

howpublished = {Available online},

month = {Aug},

year = {2020},

url = {http://www.nicolasboumal.net/book},

}

Section numbers should be fairly stable at this point. Other numbered elements (equations, theorems, ...) are more likely to change slightly. Page numbers are likely to change a lot.

- Preface
- 1. Introduction
- 2. Simple examples
- 2.1 Logistic regression
- 2.2 Sensor network localization from directions
- 2.3 Single extreme eigenvalue or singular value
- 2.4 Dictionary learning
- 2.5 Principal component analysis
- 2.6 Synchronization of rotations
- 2.7 Low-rank matrix completion
- 2.8 Gaussian mixture models
- 2.9 Smooth semidefinite programs

- 3. Embedded geometry: first order
- 3.1 Euclidean space
- 3.2 Embedded submanifolds of Euclidean space
- 3.3 Smooth maps on embedded submanifolds
- 3.4 The differential of a smooth map
- 3.5 Vector fields and the tangent bundle
- 3.6 Moving on a manifold: retractions
- 3.7 Riemannian manifolds and submanifolds
- 3.8 Riemannian gradients
- 3.9 Local frames*
- 3.10 Notes and references

- 4. First-order optimization algorithms
- 4.1 A first-order Taylor expansion on curves
- 4.2 First-order optimality conditions
- 4.3 Riemannian gradient descent
- 4.4 Regularity conditions and iteration complexity
- 4.5 Backtracking line-search
- 4.6 Local convergence*
- 4.7 Computing gradients
- 4.8 Numerically checking a gradient
- 4.9 Notes and references

- 5. Embedded geometry: second order
- 5.1 The case for another derivative of vector fields
- 5.2 Another look at differentials of vector fields in linear spaces
- 5.3 Differentiating vector fields on manifolds: connections
- 5.4 Riemannian connections
- 5.5 Riemannian Hessians
- 5.6 Connections as pointwise derivatives*
- 5.7 Differentiating vector fields on curves
- 5.8 Acceleration and geodesics
- 5.9 A second-order Taylor expansion on curves
- 5.10 Second-order retractions
- 5.11 Notes and references

- 6. Second-order optimization algorithms
- 6.1 Second-order optimality conditions
- 6.2 Riemannian Newton's method
- 6.3 Computing Newton steps: conjugate gradients
- 6.4 Riemannian trust regions
- 6.5 The trust-region subproblem: truncated CG
- 6.6 Local convergence
- 6.7 Numerically checking a Hessian
- 6.8 Notes and references

- 7. Embedded submanifolds: examples
- 7.1 Euclidean spaces as manifolds
- 7.2 The unit sphere in a Euclidean space
- 7.3 The Stiefel manifold: orthonormal matrices
- 7.4 The orthogonal group and rotation matrices
- 7.5 Fixed-rank matrices
- 7.6 The hyperboloid model
- 7.7 Manifolds defined by $h(x) = 0$
- 7.8 Notes and references

- 8. General manifolds
- 8.1 A permissive definition
- 8.2 The atlas topology, and a final definition
- 8.3 Embedded submanifolds are manifolds
- 8.4 Tangent vectors and tangent spaces
- 8.5 Differentials of smooth maps
- 8.6 Tangent bundles and vector fields
- 8.7 Retractions
- 8.8 Coordinate vector fields as local frames
- 8.9 Riemannian metrics and gradients
- 8.10 Lie brackets as vector fields
- 8.11 Riemannian connections and Hessians
- 8.12 Covariant derivatives, velocity and geodesics
- 8.13 Taylor expansions and second-order retractions
- 8.14 Submanifolds embedded in manifolds
- 8.15 Notes and references

- 9. Quotient manifolds
- 9.1 A definition and a few facts
- 9.2 Quotient manifolds through group actions
- 9.3 Smooth maps to and from quotient manifolds
- 9.4 Tangent, vertical and horizontal spaces
- 9.5 Vector fields
- 9.6 Retractions
- 9.7 Riemannian quotient manifolds
- 9.8 Gradients
- 9.9 A word about Riemannian gradient descent
- 9.10 Connections
- 9.11 Hessians
- 9.12 A word about Riemannian Newton's method
- 9.13 Total space embedded in a linear space
- 9.14 Horizontal curves and covariant derivatives
- 9.15 Acceleration, geodesics and second-order retractions
- 9.16 Notes and references

- 10. Additional tools
- 10.1 Distance, geodesics and completeness
- 10.2 Exponential and logarithmic maps
- 10.3 Parallel transport
- 10.4 Lipschitz conditions and Taylor expansions
- 10.5 Transporters
- 10.6 Finite difference approximation of the Hessian
- 10.7 Tensor fields and their covariant differentiation
- 10.8 Notes and references

- 11. Geodesic convexity
- 11.1 Convex sets and functions
- 11.2 Geodesically convex sets and functions
- 11.3 Differentiable geodesically convex functions
- 11.4 Positive reals and geometric programming
- 11.5 Positive definite matrices
- 11.6 Notes and references

- Bibliography