On the optimal objective value of random linear programs

We consider the problem of maximizing langle c,x rangle subject to the constraints Ax ≤ 1, where x∈ Rn, A is an m× 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→∞, fracmn→∞, and under some mild assumptions on c, we prove that the optimal objective value z^* of the linear program satisfies limlimitsn→∞√2log(m/n),z^*= 1quad mboxalmost 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^*.