An iterative scheme for optimal transport: strong MTW costs

Effective computational methods for the optimal transport (Monge-Kantorovich) problem have been elusive due to the highly nonlinear nature of the problem. One approach, first raised by Oliker and Prussner (for the case of cost function given by the Euclidean inner product) is to discretize only the target measure and find an approximative solution within some error tolerance, using a method similar in some sense to the auction algorithm. Their method was later adapted by Caffarelli, Kochengin, and Oliker to the far-field reflector problem (shown to be equivalent to an optimal transport problem by X-J. Wang). On the other hand, Ma, Trudinger, and Wang exhibited a condition that is necessary to obtain regularity results for the optimal transport problem, and it is known that the reflector case satisfies a strong version of this condition. In this talk, we present an extension of Caffarelli, Kochengin, and Oliker's iterative scheme to other cost functions that satisfy this strong version Ma, Trudinger, and Wang's condition, and also show that the scheme satisfies a similar upper bound on the number of steps necessary to terminate.