Monotonicity in Quadratically Regularized Linear Programs

Alberto González-Sanz, Marcel Nutz, Andrés Riveros Valdevenito

Published 2024-08-15Version 1

In optimal transport, quadratic regularization is a sparse alternative to entropic regularization: the solution measure tends to have small support. Computational experience suggests that the support decreases monotonically to the unregularized counterpart as the regularization parameter is relaxed. We find it useful to investigate this monotonicity more abstractly for linear programs over polytopes, regularized with the squared norm. Here, monotonicity can be stated as an invariance property of the curve mapping the regularization parameter to the solution: once the curve enters a face of the polytope, does it remain in that face forever? We show that this invariance is equivalent to a geometric property of the polytope, namely that each face contains the minimum norm point of its affine hull. Returning to the optimal transport problem and its associated Birkhoff polytope, we verify this property for low dimensions, but show that it fails for dimension $d\geq25$. As a consequence, the conjectured monotonicity of the support fails in general, even if experiments suggest that monotonicity holds for many cost matrices.