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 =₍mn (0, ), any unit vector c Rⁿ, any fixed a Rⁿ, and A R^m n with iid standard normal entries, we have eqnarray* ₍ P₀ ( (1-) ₎₏ₓ (;a) ₀ₗ ₀cTx (1+) ₎₏ₓ (;a) ) 1, eqnarray* where equation* ₎₏ₓ (;a) ₗ>₀ x²- x² ₍ _₈=₁^{₌ (1{2 ( (aᵢx) ² + 1) erfc (aᵢx2) - aᵢx e^-{{aᵢ²2x²}}2) }n }. equation* For example, for a=1, one uncovers equation* ₎₏ₓ () = ₗ>₀ x²- x² (1{2 (1x² + 1) erfc (1x2) - 1x e^-{1{2x²}}2) }. equation* Moreover, 2 ₎₏ₓ () is precisely the concentrating point of the mean width of the polyhedron \x|Ax 1\.