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) {StojnicRegRndDlt10}, we obtain, in a large dimensional context, the exact characterizations of the program's objectives. In particular, for any α=limn→∞m/n∈(0,∞), any unit vector c∈ Rⁿ, any fixed a∈ Rⁿ, and A∈ Rm× n with iid standard normal entries, we have {eqnarray*} limn→∞{ P}A ( (1-ε) ξₒₚₜ(α;a) ≤ minAx≤ ac^Tx ≤ (1+ε) ξₒₚₜ(α;a) ) 1, {eqnarray*} where {equation*} ξₒₚₜ(α;a) minx>0 √{x^2- x^2 limn→∞ {∑ᵢ₌₁ᵐ ( 1/2 ( ( a_i/x )^2 + 1 ) erfc( {a_i}{x√2} ) - a_i/x {e-a_i^2/2x^2}{√2π} ) }{n} }. {equation*} For example, for a=1, one uncovers {equation*} ξₒₚₜ(α) = minx>0 √{x^2- x^2 α ( 1/2 ( 1/x^2 + 1 ) erfc ( {1}{x√2} ) - 1/x {e-1/2x^2}{√2π} ) }. {equation*} Moreover, 2 ξₒₚₜ(α) is precisely the concentrating point of the mean width of the polyhedron |Ax ≤ 1\.