School of Mathematics

OptimizEd wORld Seminar

A double seminar series where PhD students in OOR present side-by-side with a world-renowned guest speaker. Find information on upcoming events as well as details and photos of past events.

Events

2022

Date: 28th of September 2022, 10:00-12:00 (BST)

Location: Maths Seminar Room (5323 JCMB) and Zoom

Speaker Talk
Filippo Zanetti(1)

Interior Point Methods for Optimal Transport with imaging applications

Discrete Optimal Transport problems give rise to very large linear programs (LP) with a particular structure of the constraint matrix. In this paper we present an interior point method (IPM) specialized for the LP originating from the Kantorovich Optimal Transport problem. Knowing that optimal solutions of such problems display a high degree of sparsity, we propose a column-generation-like technique to force all intermediate iterates to be as sparse as possible. The algorithm is implemented nearly matrix-free. Indeed, most of the computations avoid forming the huge matrices involved and solve the Newton system using only a much smaller Schur complement of the normal equations. We prove theoretical results about the sparsity pattern of the optimal solution, exploiting the graph structure of the underlying problem. We use these results to mix iterative and direct linear solvers efficiently, in a way that avoids producing preconditioners or factorizations with excessive fill-in and at the same time guaranteeing a low number of conjugate gradient iterations. We compare the proposed sparse IPM method with a state-of-the-art solver and show that it can compete with the best network optimization tools in terms of computational time and memory usage. We perform experiments with problems reaching more than a billion variables and demonstrate the robustness of the proposed method.

Enrico Facca​​​​​(2)

The numerical solution of the L1 and L2 Optimal Transport problem. Differences, analogies, and open problems.

The Optimal Transport problem studies how to find the optimal strategy of moving resources. When the cost of moving one unit of mass is proportional to the distance or the square distance, they are called L1 and L2 problem, respectively. I will give an overview of the PDE-based formulations of the two problems and their applications. I will then focus on the open problems arising from their numerical solution.

​​​​​Affiliation:

(1) PhD Student - University of Edinburgh

(2) Postdoc Researcher - RAPSODI project-team at INRIA Lille Nord