M.Sc Thesis

M.Sc StudentMeisler Dmitry
SubjectPoint Allocations and Transport Algorithms
DepartmentDepartment of Applied Mathematics
Supervisor PROFESSOR EMERITUS Gershon Wolansky


This work is concerned with the Monge problem of optimal mass transportation between two probability measures mu0 and mu on a state space Omega, where mu0=rho0(x)dx is a continuous measure (with respect to Lebesgue measure) and mu=m1delta_y1?Ndelta_yN in B1(Gamma), where B1(Gamma) is the set of all probability measures supported on the finite set {y1,?,yN} in Omega. It can be shown that the solution of the Monge-Kantorovich problem is equivalent to an optimal partition of the state space.

Let C(mu0,mu) be the cost of transportation of the measure mu0 to the measure mu. In our work we study two optimization problems:

 min_{mu in B1(Gamma)}[C(mu0,mu)(mu)], min_{mu in B1(Gamma)}[alphaC(mu0,mu)(1-alpha)C(mu,mu1)]. Here H is a convex function in B1(Gamma) and mu1 is, like mu0, a continuous probability measure with respect to Lebesgue. We perform minimization with respect to the discrete measure mu in B1(Gamma), i.e. mu=m1delta_y1?Ndelta_yN.

In order to find the optimal partition we use the Monge-Kantorovich duality. We show that the dual problem is concave and is strictly concave near the solution, is differentiable, and we find its gradient and Hessian. We prove that it has a unique global maximum where the gradient vanishes. This allows us to use optimization methods in order to find the optimal partition.

The contribution of our work is in the solution of the second optimization problem since it has an additional interpretation: it approximates the solution of the Monge problem for the continuous measures mu0, mu1.