Overview
This proposal aims to develop the theory, models and numerical methods, based on
optimal mass transportation (OMT), towards application problems such as evolutionary
dynamics and image processing. Three research topics will be the focus of this proposal:
- 1. Study OMT on discrete states, such as finite graphs or networks, including their
dualities, geometry, and computational properties;
- 2. Propose discrete OMT related dynamical systems, such as Fokker-Planck equations
and Schrodinger equations on discrete states, and investigate their applications in evolutionary
games, which aim to learn, understand, predict and optimize population behaviors
over discrete strategy sets. The noise and uncertainties play critical roles in models. Their
connections with physical functionals, such as entropy and Fisher information, will be
emphasized;
- 3. Design fast, parallel numerical schemes and software towards OMT related minimizations,
and apply those into applications, such as image segmentation and robotics
path planning.
L1 minimization
In 1781, Monge proposed a distance function among histograms. We develop fast methods for it using techniques borrowed in L1 compressive sensing. Our method is very simple, easy to parallelize and can be combined with other regularizations. We use it in applications including partial optimal transport, image segmentation, image alignment and others. It is flexible enough to easily deal with histograms and other features of the data.
- Optimal flux among two images I
- Optimal flux among two images II
- Partial optimal transport
- Image segmentation I
- Image segmentation II
Schrodinger equation and bridge problems
In 1966, Nelson derived Schrödinger equation by the diffusion process. Nowadays this approach connects with the theory of optimal transport. We consider similar matters on finite graphs. We propose a discrete Schrödinger related equations from Nelson’s idea and optimal transport. The proposed equation enjoys several dynamical features.
- Transportation from digits 4 to digits 1.
Mean field games
We compute numerical solutions of some infinitely dimensional Hamilton-Jacobi equations (HJ-PDE) in probability space that are coming from the theory of mean field games. Numerics towards such HJ-PDE was previously almost impossible owing to the incredibly high dimension of the PDE after discretization of a function space. We propose to utilize the Hopf formula, which comes from an optimal control approach. The resulting formula is an optimization problem involving only a finite dimensional PDE constraint which can be computed using a standard finite difference scheme. In particular, our method will provide us a possible way to compute proximal maps of Wasserstein metrics. They are of special importance in computing optimization problems involving Wasserstein metrics. Our techniques have applications in optimal transport, mean field games and optimal control in the space of probability densities.
- Evolution of Population density.
Evolutionary game theory
We propose a new dynamic framework for the finite or infinite player (population) discrete strategy games. By utilizing tools from optimal transportation theory, we derive Fokker-Planck equations of games. Furthermore, we introduce an associated Best-Reply Markov process that models players’ myopic, greedy and uncertainty when making decisions. The model gives rise to a method to rank/select equilibria for both potential and non-potential games.
- Poluation dynamics in Rock paper Scissors' game via optimal transport.
Robotics
We design a new fast algorithm for a class of optimal control problems with constraints on both state and control variables. Instead of searching global minimizer(s) from all feasible paths, we consider the subset of paths with the structure of optimal paths. By leveraging these paths, we transfer optimal control problems to a set of finite and different dimensional optimization problems with constraints. Moreover, for each of these finite dimensional subproblems, we apply methods from stochastic differential equations in order to find numerically all possible global minimizers of our original optimal control problem.
- Frogger game/Finite drone's game.