Two and a half centuries of optimal transport

Do you recognize the people shown in this figure? Probably not, because these people… do not exist! The portraits were generated automatically by a computer program—a neural network trained to create as many portraits as desired. One of the tools used to train this neural network is optimal transport. Although this mathematical theory is more than two centuries old, it has proved very useful in the rapidly expanding field of data science. Physics, economics and image processing also draw on optimal transport to solve their problems.

Monge, a pioneer -------------------------

The history of optimal transport begins with the French mathematician Gaspard Monge. Born in Beaune (Côte-d’Or), he attracted attention at the age of 17 by drawing a detailed map of his hometown, revealing a genuine gift for geometry. He was then hired as an assistant at the École royale du génie de Mézières (Ardennes), his modest background preventing him from being admitted as a student. He soon became a professor of mathematics and physics. He taught there for almost twenty years while pursuing a wealth of varied scientific activities in which teaching, research and applications were closely intertwined.

Monge’s scientific activities were driven by applications, often inspired by military problems. In 1781, he presented his Mémoire sur la théorie des déblais et des remblais to the Académie des sciences. The question he sought to answer was this: how can a pile of sand of a particular shape (the excavation) be moved elsewhere and transformed into another pile (the embankment) of the same volume and a prescribed shape, while minimizing the total distance traveled by the grains of sand?

Gaspard Monge, Count of Péluse (1746–1818), engraving by Naigeon Jeune.

Consider an instance of the problem. Suppose that N people in the same city (represented here by the capital letters A, B… G) all want to read the same book, and that N city libraries (represented by numbers) each hold one copy. How should these N people be assigned so that each collects a copy from a library without creating a conflict—each library can receive only one of them, since it has only one copy—and so that the total distance traveled is minimized? This is known as the optimal assignment problem.

To solve it, we can construct a table containing the distances between the people and the libraries. The columns correspond to the people and the rows to the libraries. Solving the problem amounts to coloring N cells so that exactly one cell in each column and one cell in each row is colored, thus avoiding conflicts, while making the sum of the distances in the colored cells as small as possible.

The solution to the assignment problem is shown in blue.

Rather than use the distances between the points, we could have used cycling times or any other cost function between the people and the libraries. This would have produced a different table and therefore a different result (see box).

There is one special case in which a solution to the assignment problem is easy to find: when all the libraries and people lie on the same line. The problem is then one-dimensional. If the cost function for travel is the distance or the square of the distance, a solution is given by the monotone rearrangement: order the libraries and the people from left to right along the line, then send the first person to the first library, and so on. The resulting solution is not necessarily unique: several distinct solutions may attain the minimum of the cost function.

The point-assignment problem has a delightful application in image processing: it can transfer colors from one image to another. An image is a rectangular array in which every cell, or pixel, contains three values encoding a color (see Mathématiques et Imagerie, special issue 77, 2021). These three values are the red, green and blue coordinates in a three-dimensional color space. By matching the colors of two images using optimal transport, each color in the first image can be transformed into its corresponding color in the second. This process is called color transfer and is particularly useful in video post-production.

####

The routes taken by the sand -----------------------

Return to Monge. The problem that interested him is more general than the library problem. A pile of sand of a given shape must be moved to form another pile whose shape is also prescribed. The total distance traveled by the grains of sand must still be minimized, subject to the constraint that the grains are initially distributed according to the excavation and finally according to the embankment. Monge did not solve his problem, but he assumed that a solution existed and investigated which geometric properties it might satisfy.

He studied the problem first in two dimensions, then in three. In particular, he showed that the routes do not cross: if two grains of sand must be sent from points A and B to points a and b, the routes that minimize the total distance traveled cannot cross (see box).

Monge’s problem is in fact a special—and difficult—case. Simple examples can be constructed in which it has several solutions rather than a unique one, as can others in which it has no solution at all. A century later—at the end of the 19^th century—the question still remained unresolved, and the Académie des sciences set it as the subject of the Bordin Prize.

It was not until the 20^th century that the question of whether the optimal transport problem has solutions was finally settled. Beginning in the 1930s and continuing through the Second World War, several mathematicians made major advances, particularly in response to questions concerning resource allocation and the optimization of economic production. These ideas emerged concurrently and independently among several scientists, both "in the West" and "in the East."

Kantorovich enters the scene --------------------------------

The most important contributions to the subject came from the Russian mathematician Leonid Vitalyevich Kantorovich (1912–1986). He developed the tools of linear programming, one of the most significant contributions to 20^th-century economic theory. He received the 1975 Nobel Prize in Economics with Tjalling Charles Koopmans (1910–1985) for this work.

The problem studied by Kantorovich differs slightly from Monge’s. Return to our people and libraries. In Monge’s problem, there are as many people as libraries, and the aim is to match them. In Kantorovich’s version, each library may hold several copies of the book, while each person is replaced by a household of several people living in the same place and eager to read the much-coveted book.

The total number of people wishing to read the book across all the households equals the total number of copies held by all the libraries. We still want to determine how to allocate the people among the different libraries so that there are no conflicts, everyone receives a copy and the total distance traveled is minimized. This time, however, people from the same household may be allocated to different libraries—and, conversely, a single library may receive people from different households.

To solve Kantorovich’s problem, we again construct a matrix of distances between the households (A, B, C and D) and the libraries (a, b and c). We write *c_a*_A for the distance between household A and library a, and similarly for the other distances. We then create another table of the same size showing how the different households are allocated among the libraries. For example, the value *p_a*_A denotes how many people from household A will go to library a.

The values in this table must satisfy certain constraints: the number of people from the different households who go to library a must be exactly equal to the number of copies of the book held there—namely, three. Likewise, the number of people from household A who visit the libraries must be exactly equal to the number of people in that household—namely, two. Together, these constraints yield seven equations fixing the sums of the values in each row and each column of the table.

We then seek to fill in the table so as to minimize the sum of the products of the *p_i*_,*_j and the costs c_i*_,*_j, subject to the quantities p* being positive and satisfying the seven equations; that is:

The resulting problem is a special case of a more general class of problems known as linear programming problems. One very well-known method for solving them is the simplex algorithm, developed by George Dantzig in 1947 (see la Recherche opérationnelle, special issue 75, 2020).

Solution to Kantorovich’s optimal transport problem.

A key tool -----------------

It was not until the 1990s, notably through the work of the French mathematician Yann Brenier, that the conditions under which solutions to Kantorovich’s problem also provide solutions to Monge’s problem were established explicitly. Since then, the Franco-Italian school of optimal transport has grown considerably and achieved many successes in both theoretical and applied mathematics. Optimal transport has also become a key tool in many fields, including economics, computer graphics and physics. For example, optimal transport has strong links with fluid mechanics. In imaging, it is used to alter the contrast or color of images, to compare shapes or create interpolations between them, and to manipulate textures… In machine learning, it has become an indispensable tool for comparing data and is used, in particular, to train certain neural networks. Today, optimal transport works wonders!