A quadratic regularization of optimal transport problems and its application to bilevel optimization

Abstract

This thesis consists of two parts, in each of which a quadratic regularization is applied to an optimal transport problem and its effect on a prototypical bilevel optimization problem is investigated. In the first part, we use the mentioned quadratic regularization in combination with a smoothing of the marginals to improve certain properties of the well-known Kantorovich problem, which is a linear optimization problem defined on infinite-dimensional spaces. In this way we obtain, for example, the uniqueness of the optimal solution and an associated optimality system containing (non-unique) dual variables. We then use these improved properties of the problem to regularize a bilevel optimization problem whose constraints require to solve the Kantorovich problem. We then show that the regularized bilevel problem has a solution and that we can, under certain conditions, approximate solutions of the non-regularized bilevel problem by solutions of the regularized one. We conclude the first part with a brief overview of possible applications of this regularization approach. In the second part, we apply the same regularization approach to the also well-known Hitchcock problem, which we introduce as a finite-dimensional special case of the Kantorovich problem. Due to the structure of this problem, however, we can dispense with the additional smoothing of the boundary conditions. Similar to the first part, we regularize a bilevel problem whose constraints require the solution of the Hitchcock problem. We again show the existence of solutions to the regularized bilevel problem and that we can use this to approximate solutions to the non-regularized bilevel problem, in certain cases. By introducing a further regularization of the Lagrangian dual problem, we enforce the uniqueness of the dual variables from the optimality system. This enables us to calculate derivatives of the marginal-to-transportplan mapping and, in turn, to establish an implicit programming approach for the solution of the regularized bilevel problem. To conclude the second part, we test our findings numerically by means of an transportation identification problem.