Solving Mass Transportation Problems Using Liouville Equations

Transporting objects and moving from one place to another occurs in everyday life. We can observe it at all scales: molecules are transported inside cells; rockets transport satellites into Earth’s orbit. This is an age-old activity that has developed its rules and techniques for effectiveness and convenience. Thus, by looking carefully at any transport phenomena, we recognize a methodology. This is true for movement of human beings through different places to perform different tasks, transfer of data, which is the core concept of internet, televisions, radios and radar systems, migration of birds and fishes, the flow of blood in tissues, etc.; all these represent some form of transportation. One could argue that transportation is an expression of life.

Transportation is a complex and precise job and thus it becomes essential to study various methods and strategies of time-effective transportation with minimal effort. This need leads to the concept of optimal transportation that is the focus of the mathematical theory of transport. The main components in optimal transportation include the objects to be transported, which are represented by sets, the dynamics of the process, which is usually given by a time-evolution differential equation and includes a control function whose job is to drive the process to its optimal configuration and a cost functional, which is to be optimized. Such problems were first studied mathematically by A. N. Tolstoi in 1920.

Subsequently, major advances in this field were made by Leonid Kantorovich. One early special class of transport problems is the transport of mass that represents the displacement of a collection of similar objects from an original location to a desired one: the famous Monge-Kantorovich problem. For this purpose, the dynamics of a single particle is extended to the dynamics of multi-particle systems and this is usually done through Liouville equations, which are a set of hyperbolic partial differential equations (PDE). However, although the Liouville equation in space coordinates and its counterpart in phase-space are central in classical continuous mechanics, we notice that optimal transport problems governed by these equations have not been a research focus. Investigation of robust control mechanisms using the Liouville framework appears natural for mass transportation problems.

In a recent work, Nikolay Pogodaev proposed a challenging Liouville optimal control problem where the controller has the purpose to transport an initial probability measure to maximize the measure of a target set at a given final time. This setting accommodates multi-agent control problems as well as the problem of the control of a beam of charged particles, and it can be considered an approximation to the classical mass transportation problem.

Pursuing this challenging work, Alfio Borzì and Souvik Roy from the University of Würzburg developed a new computational framework for solving the Liouville control problems proposed by Pogodaev. Two major breakthroughs of this new research effort are the analysis of high-order conservative and positive preserving approximation schemes for continuity-type equations and the development of a new methodology for the fast solution of Liouville transport problems that are formulated in the framework of the Pontryagin’s maximum principle (PMP).

The major focus of this work was to build a novel iterative scheme for implementing the PMP for an optimal mass transportation problem governed by Liouville PDE. A major advantage of the maximum principle framework for optimal control problems is the non-differentiability with respect to the control function, which helps incorporate a wide class of controllers to be used for real-life mass transportation. Moreover, the concept of maximum principle for PDE control problems is not well-studied in literature. Thus, the scope of this research involves optimization strategies with PMP for various PDE control problems.

With this generic idea at the back of mind, a time-split nonlinear collective update scheme is proposed. This is an iterative scheme which solves the PMP optimality condition pointwise in time which includes a third order conservative numerical scheme for solving the Liouville equation. In fact, the iterative scheme does not change with the choice of discretization schemes for PDE’s, thus enabling it to solve any PDE optimal control problem. Various numerical experiments presented in the paper demonstrated the efficiency and robustness of the proposed optimization framework for mass transportation problems.

These findings are described in the article entitled Numerical Investigation of a Class of Liouville Control Problems, published in the Journal of Scientific Computing. This work was led by Souvik Roy from Universität Würzburg.