Repository logo
 

Limit laws for empirical optimal solutions in random linear programs

Published version
Peer-reviewed

Change log

Authors

Klatt, M 
Munk, A 

Abstract

jats:titleAbstract</jats:title>jats:pWe consider a general linear program in standard form whose right-hand side constraint vector is subject to random perturbations. For the corresponding random linear program, we characterize under general assumptions the random fluctuations of the empirical optimal solutions around their population quantities after standardization by a distributional limit theorem. Our approach is geometric in nature and further relies on duality and the collection of dual feasible basic solutions. The limiting random variables are driven by the amount of degeneracy inherent in linear programming. In particular, if the corresponding dual linear program is degenerate the asymptotic limit law might not be unique and is determined from the way the empirical optimal solution is chosen. Furthermore, we include consistency and convergence rates of the Hausdorff distance between the empirical and the true optimality sets as well as a limit law for the empirical optimal value involving the set of all dual optimal basic solutions. Our analysis is motivated from statistical optimal transport that is of particular interest here and distributional limit laws for empirical optimal transport plans follow by a simple application of our general theory. The corresponding limit distribution is usually non-Gaussian which stands in strong contrast to recent finding for empirical entropy regularized optimal transport solutions. </jats:p>

Description

Keywords

Limit law, Linear programming, Optimal transport, Sensitivity analysis

Journal Title

Annals of Operations Research

Conference Name

Journal ISSN

0254-5330
1572-9338

Volume Title

315

Publisher

Springer Science and Business Media LLC
Sponsorship
Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung (CH) (178220)
Deutsche Forschungsgemeinschaft (DE) (Research Training Group 2088)