← Luca Nenna
Research

Generalized optimal transport

Optimal transport starts from a very concrete question, first asked by Monge in 1781: given a pile of sand and a hole of the same volume, what is the cheapest way to move the sand into the hole? In modern language: given two probability distributions and a cost for moving a unit of mass from one point to another, find the transport plan of minimal total cost. This simple question connects geometry, PDEs, probability, physics and economics. My work is about generalisations of this problem, and about how to compute their solutions.
A cloud of particles transported onto a crescent
Optimal transport moves a cloud of particles (left) onto a crescent (right). Each particle keeps its colour: the optimal plan tells every particle where to go, and the intermediate snapshots show the optimal way of getting there.

Many marginals, and the price of blurring

In the classical problem one matches two distributions. Many applications need to match several at once: the positions of N electrons, or N populations of agents. This is multi-marginal optimal transport: the unknown becomes a joint distribution of N variables whose marginals are prescribed.

These problems are hard to solve exactly. A standard trick is to add a small amount of entropy, which blurs the optimal plan: the blurred problem can be solved by a simple and fast rescaling procedure, the Sinkhorn algorithm. The price is that the answer is slightly off. A large part of my work measures this error: how fast the blurred cost approaches the true one as the blur ε goes to zero (convergence rates), and, when the original problem has several solutions, which one the blurred problem picks out in the limit (selection principles).

ε = 20ε = 20
ε = 5ε = 5
ε = 1ε = 1
ε = 0.01ε = 0.01
ε = 0.002ε = 0.002
Support of the entropic transport plan for the Coulomb cost as the blur ε decreases. As ε goes to zero, the blurred plan concentrates on thin curves: the solution of the original problem.

Electrons as a transport problem

In a molecule, electrons are described by a density ρ: how likely it is to find one at each point of space. Density functional theory, the workhorse of quantum chemistry, tries to compute the energy of a molecule from ρ alone.

When the repulsion between electrons dominates, they arrange themselves as far apart from each other as ρ allows: knowing where one electron is essentially tells you where all the others are. Finding this arrangement is exactly a multi-marginal transport problem, with N copies of ρ as marginals and the Coulomb repulsion as the cost. I study this connection and its extensions: what happens when the number of electrons may vary (grand-canonical transport, with S. Di Marino and M. Lewin), whether the energy is convex as a function of the number of electrons (it is not always!), and how to approximate the full quantum Lieb functional using only a few well-chosen configurations (with V. Ehrlacher).

Electrons:
Try it: drag the large electron along the line (or use the arrow keys). The density is cut into N parts of equal mass and the other electrons sit at the same “relative position” in the other parts, as far away as the density allows. On the right, their positions as a function of the first one: the curves are the co-motion functions, the support of the optimal multi-marginal transport plan.

Crowds, games and random motion

Think of a crowd leaving a stadium, or of traffic on a road network: everyone chooses a route to minimise their own travel time, but the best route depends on what everybody else does. Mean field games describe the equilibria of such systems when the number of agents is very large.

Many of these equilibria can be rewritten as optimal transport or entropy-minimisation problems, which makes them easier to study and to compute. I use this point of view for games with several interacting populations and for economic equilibria (Cournot–Nash), and for other random dynamics: the Schrödinger problem (the most likely evolution of a cloud of diffusing particles observed at two different times) or particles that “stick” to a boundary (sticky diffusions).

t = 0t = T
Try it: drag the grey obstacles and change the congestion. A crowd must go from the left region to the right one in a fixed time; every agent pays for its kinetic energy and for crowded places, and moves with a little noise. The equilibrium of this mean field game is recomputed live in your browser by a generalised Sinkhorn algorithm, the entropic method of M3AS 2019.
t = 0t = T
Try it: three populations must cross the same region: blue goes left to right, orange right to left, green top to bottom (dashed circles are the starting areas, the coloured dots are the targets — drag them). Agents of different populations repel each other, so instead of colliding the populations negotiate lanes around each other. Turn the repulsion to zero and they simply pass through one another. Computed live with the multi-population extension of the same entropic algorithm (NoDEA 2026).
startstart
 
 
 
endend
A mean field planning problem with obstacles: the density of a crowd evolves from an initial to a final configuration while avoiding the obstacles.

Computing the solutions

Multi-marginal problems suffer from the curse of dimensionality. Discretise each marginal with 100 points: two marginals give a 100×100 transport plan, but ten marginals give 10010 = 1020 unknowns, far more than any computer can store.

My numerical work is about getting around this: Sinkhorn-type algorithms, which work with N potentials instead of the full plan; ODEs that follow the solution as the blur parameter changes; particle methods, which describe the solution by a moving cloud of points; reduced-order models, which solve a whole family of related problems at once; and column generation (project PiQuantO), which builds a sparse solution one configuration at a time.

t = 0t = 0
t = 0.25t = 0.25
t = 0.5t = 0.5
t = 0.75t = 0.75
t = 1t = 1
ODE method for semi-discrete entropic transport: evolution of the Laguerre cells along the ODE (10 points, uniform source on the unit square).

All publications → · Talks →