OPTIMAL TRANSPORT: NUMERICAL OPTIMIZATION AND APPLICATIONS

Abstract

In this thesis, we focus on studying and designing efficient algorithms for solving optimal transport and its related problems. We focus on solving a class of linear programming problems with certain type of constraints and design an implementable inexact entropic proximal point algorithm (iEPPA), where it employs a more practically checkable stopping condition for solving the associated subproblems while achieving provable convergence and does not require the proximal parameter to be very small. Besides, we provide a unified algorithmic framework (corrected inexact proximal augmented Lagrangian method) for solving a class of optimal transport problems with generalized regularizers and structured constraints. In particular, we consider the transportation problems with some widely used constraints (martingale, partial) and regularizers (quadratic, group). Finally, we derive a unified proof of the equivalent interpretation between a certain class of square-root regularized models and distributionally robust optimization (DRO) formulations and design a proximal point dual semismooth Newton algorithm and demonstrate its efficiency in certain circumstances. Extensive experiments demonstrate that our algorithms are highly efficient for solving various large-scale problems.