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

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.