# On the optimal objective value of random linear programs

arXiv: https://arxiv.org/abs/2401.17530 · HTML: https://mlsanity.com/paper/2401.17530/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Jan 2024.

## Built on by (most cited first, 1 of 1)

- [Exact objectives of random linear programs and mean widths of random polyhedrons](https://mlsanity.com/paper/2403.03637/) (2024)

## Abstract (arXiv)

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^*.