Exact objectives of random linear programs and mean widths of random polyhedrons
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917605929910272 |
|---|---|
| author | Stojnic, Mihailo |
| author_facet | Stojnic, Mihailo |
| contents | 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 $α=\lim_{n\rightarrow\infty}\frac{m}{n}\in(0,\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 ξ_{opt}(α)$ is precisely the concentrating point of the mean width of the polyhedron $\{\mathbf{x}|A\mathbf{x} \leq \mathbf{1}\}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_03637 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Exact objectives of random linear programs and mean widths of random polyhedrons Stojnic, Mihailo Optimization and Control Information Theory Probability Machine Learning 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 $α=\lim_{n\rightarrow\infty}\frac{m}{n}\in(0,\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 ξ_{opt}(α)$ is precisely the concentrating point of the mean width of the polyhedron $\{\mathbf{x}|A\mathbf{x} \leq \mathbf{1}\}$. |
| title | Exact objectives of random linear programs and mean widths of random polyhedrons |
| topic | Optimization and Control Information Theory Probability Machine Learning |
| url | https://arxiv.org/abs/2403.03637 |