Convex duality and applications in mass transport and calculus of variations"
Preview:
Convexity and the theory of convex duality is at the heart of modern numerical methods to solve efficiently optimization problems arising in applied contexts such as image processing or machine learning. The optimal mass transportation problem also illustrates how powerful this theory can be and is a particularly active field of modern research. These lectures will cover in details convex duality theory and its use in optimization, the calculus of variations and mass transportation problems.
Contents:
Chapter: Convex sets, convex functions, separation theorems
Convex sets, separation theorems, the case of Hilbert spaces, projections, Farkas Lemma, convex functions, continuity properties, differentiability and subdifferentiability .
Chapter: Legendre duality
The Legendre transform, basic examples, operations on convex functions (sums, infimal convolutions…), link with subdifferentiability, convex envelopes. Convex optimization, value functions, Fenchel-Rockafellar Theorem and applications to linear programming. Connections with the min-max theorem and saddle-point problems.
Chapter: Variational problems
A short review of Sobolev Spaces, the direct methods in the calculus of variations, the classical method and Euler-Lagrange equations. Relaxation and convex variational problems, duality. Applications: obstacle problem, max flow/min cut duality, elliptic PDEs of Euler-Lagrange type.
Chapter: Mass transport, Kantorovich duality and applications
Monge, Monge-Kantorovich mass transport problems, basic examples (discrete case, one-dimensional case, the assignment problem, extreme points of bistochastic matrices are permutation matrices). The Kantorovich duality formula: applications to convex costs and in particular the quadratic cost (Brenier's theorem, connections with Monge-Ampère and the isoperimetric inequality). The distance cost case and its minimal flow counterpart.
Chapter: The dynamical formulation of mass transport
The method of characteristics and the continuity equation, Benamou-Brenier's formula, connection with geodesics. Wasserstein gradient flows and the Jordan-Kinderlehrer Otto scheme.
Chapter: Numerical methods for optimal transport
The linear programming approach, the auction algorithm, entropic regularization, the Sinkhorn-IPFP algorithm. Semi-discrete optimal transport and computational geometry methods. Solving the Benamou-Brenier problem with an Augmented Lagrangian method.
ECTS Credits:
Prerequisites:
MA1001 Analysis 1, MA1002 Analysis 2, MA2003 Measure and Integration, MA3001
Functional Analysis.
Suggested optional: MA2504 Convex Optimization, MA3005 Partial Differential Equations,
MA3504 Convex Analysis.
The parallel course by F.Santambrogio complements this lecture nicely,
attendance to that parallel course is recommended but not necessary for successful
completion of this course.