Details

Autor(en) / Beteiligte

• Klatt, Marcel
• Munk, Axel
• Zemel, Yoav

Titel

Limit laws for empirical optimal solutions in random linear programs

Ist Teil von

• Annals of operations research, 2022-08, Vol.315 (1), p.251-278

Ort / Verlag

New York: Springer US

Erscheinungsjahr

2022

Link zum Volltext

Quelle

EBSCOhost Business Source Ultimate

Beschreibungen/Notizen

• We 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.