# Exact objectives of random linear programs and mean widths of random polyhedrons

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 73 references that are in the map.
- First posted on arXiv 6 Mar 2024.

## Builds on (most cited first, 15 of 15)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Regularly random duality](https://mlsanity.com/paper/1303.7295/) (2013)
- [Another look at the Gardner problem](https://mlsanity.com/paper/1306.3979/) (2013)
- [Properties of the geometry of solutions and capacity of multi-layer neural networks with Rectified Linear Units activations](https://mlsanity.com/paper/1907.07578/) (2019)
- [Discrete perceptrons](https://mlsanity.com/paper/1306.4375/) (2013)
- [Binary perceptrons capacity via fully lifted random duality theory](https://mlsanity.com/paper/2312.00073/) (2023)
- [Fl RDT based ultimate lowering of the negative spherical perceptron capacity](https://mlsanity.com/paper/2312.16531/) (2023)
- [Activation function dependence of the storage capacity of treelike neural networks](https://mlsanity.com/paper/2007.11136/) (2020)
- [Meshes that trap random subspaces](https://mlsanity.com/paper/1304.0003/) (2013)
- [Sampling Kaczmarz Motzkin Method for Linear Feasibility Problems: Generalization & Acceleration](https://mlsanity.com/paper/2002.07321/) (2020)
- [Exact capacity of the wide hidden layer treelike neural networks with generic activations](https://mlsanity.com/paper/2402.05719/) (2024)
- [Asymptotic confidence sets for random linear programs](https://mlsanity.com/paper/2302.12364/) (2023)
- [A Friendly Smoothed Analysis of the Simplex Method](https://mlsanity.com/paper/1711.05667/) (2017)
- [Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method](https://mlsanity.com/paper/2211.11860/) (2022)
- [On the optimal objective value of random linear programs](https://mlsanity.com/paper/2401.17530/) (2024)

## Abstract (arXiv)

We consider random linear programs (rlps) as a subclass of random optimization problems (rops) and study their typical behavior. Our particular focus is on appropriate linear objectives which connect the rlps to the mean widths of random polyhedrons/polytopes. Utilizing the powerful machinery of random duality theory (RDT) citeStojnicRegRndDlt10, we obtain, in a large dimensional context, the exact characterizations of the program's objectives. In particular, for any α=limnrightarrow∞fracmn∈(0,∞), any unit vector c∈mathbb Rn, any fixed a∈mathbb Rn, and A∈ mathbb Rm× n with iid standard normal entries, we have begineqnarray* limnrightarrow∞mathbb PA left ( (1-ε) xiopt(α;a) ≤ minAx≤ acTx ≤ (1+ε) xiopt(α;a) right ) longrightarrow 1, endeqnarray* where beginequation* xiopt(α;a) triangleq minx>0 √x2- x2 limnrightarrow∞ fracsumi=1m left ( frac12 left (left ( fracaixright )2 + 1right ) mboxerfcleft( fracaix√2right ) - fracaix frace^-fracai22x2√2π right ) n . endequation* For example, for a=1, one uncovers beginequation* xiopt(α) = minx>0 √x2- x2 α left ( frac12 left ( frac1x2 + 1right ) mboxerfc left ( frac1x√2right ) - frac1x frace^-frac12x2√2π right ) . endequation* Moreover, 2 xiopt(α) is precisely the concentrating point of the mean width of the polyhedron x|Ax ≤ 1.