On the optimal objective value of random linear programs

We consider the problem of maximizing $⟨c,x⟩$ subject to the constraints $Ax\le \mathbf{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 \mathrm{\infty }$, $\frac{m}{n}\to \mathrm{\infty }$, and under some mild assumptions on $c$, we prove that the optimal objective value $z^{\ast }$ of the linear program satisfies $$\underset{n\to \mathrm{\infty }}{\lim }\sqrt{2\log (m\mathrm{/}n)}{z}^{\ast }=1almostsurely\mathrm{.}$$ 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 }$.