On the optimal objective value of random linear programs

Abstract

We consider the problem of maximizing $⟨c,x⟩$ subject to the constraints $Ax\le 1$, where $x\in R^n$, $A$ is an $m\times n$ matrix with mutually independent centered subgaussian entries of unit variance, and $c$ is a cost vector of unit Euclidean length. In the asymptotic regime $n\to \infty$, $\frac{m}{n}\to \infty$, and under some mild assumptions on $c$, we prove that the optimal objective value $z^{\ast }$ of the linear program satisfies $$ \lim\limits_{n\to\infty}\sqrt{2\log(m/n)}\,z^*= 1\quad \mbox{almost surely}. $$ We provide numerical experiments as supporting data for the theoretical predictions. Further, we carry out numerical studies of the limiting distribution and the standard deviation of $z^{\ast }$.

added proof of asymptotic upper bound on z^*