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

We consider \emph{random linear programs} (rlps) as a subclass of \emph{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 \emph{random duality theory} (RDT) \cite{StojnicRegRndDlt10}, we obtain, in a large dimensional context, the exact characterizations of the program’s objectives. In particular, for any $\alpha ={\lim }_{n\to \mathrm{\infty }}\frac{m}{n}\in (0,\mathrm{\infty })$, any unit vector $\mathbf{c}\in {\mathbb{R}}^n$, any fixed $\mathbf{a}\in {\mathbb{R}}^n$, and $A\in {\mathbb{R}}^{m\times n}$ with iid standard normal entries, we have \begin{eqnarray*} \lim_{n\rightarrow\infty}{\mathbb P}{A} \left ( (1-ε) ξ{opt}(α;$\mathbf{a}$) \leq \min_{A$\mathbf{x}$\leq $\mathbf{a}$}$\mathbf{c}$^T$\mathbf{x}$ \leq (1+ε) ξ_{opt}(α;$\mathbf{a}$) \right ) \longrightarrow 1, \end{eqnarray*} where \begin{equation*} ξ_{opt}(α;$\mathbf{a}$) \triangleq \min_{x>0} \sqrt{x^2- x^2 \lim_{n\rightarrow\infty} \frac{\sum_{i=1}^{m} \left ( \frac{1}{2} \left (\left ( \frac{$\mathbf{a}$_i}{x}\right )^2 + 1\right ) \mbox{erfc}\left( \frac{$\mathbf{a}$_i}{x\sqrt{2}}\right ) - \frac{$\mathbf{a}$i}{x} \frac{e^{-\frac{$\mathbf{a}$i^2}{2x^2}}}{\sqrt{2π}} \right ) }{n} }. \end{equation*} For example, for $\mathbf{a}=\mathbf{1}$, one uncovers \begin{equation*} ξ{opt}(α) = \min{x>0} \sqrt{x^2- x^2 α\left ( \frac{1}{2} \left ( \frac{1}{x^2} + 1\right ) \mbox{erfc} \left ( \frac{1}{x\sqrt{2}}\right ) - \frac{1}{x} \frac{e^{-\frac{1}{2x^2}}}{\sqrt{2π}} \right ) }. \end{equation*} Moreover, $2{\xi }_{opt}(\alpha )$ is precisely the concentrating point of the mean width of the polyhedron $\{\mathbf{x}\mathrm{\mid }A\mathbf{x}\le \mathbf{1}\}$.