On the optimal objective value of random linear programs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910054239698944 |
|---|---|
| author | Bakhshi, Marzieh Ostrowski, James Tikhomirov, Konstantin |
| author_facet | Bakhshi, Marzieh Ostrowski, James Tikhomirov, Konstantin |
| contents | We consider the problem of maximizing $\langle c,x \rangle$ subject to the constraints $Ax \leq \mathbf{1}$, where $x\in R^n$, $A$ is an $m\times n$ matrix with mutually independent centered subgaussian entries of unit variance, and $c$ is a cost vector of unit Euclidean length. In the asymptotic regime $n\to\infty$, $\frac{m}{n}\to\infty$, and under some mild assumptions on $c$, we prove that the optimal objective value $z^*$ of the linear program satisfies $$ \lim\limits_{n\to\infty}\sqrt{2\log(m/n)}\,z^*= 1\quad \mbox{almost surely}. $$ We provide numerical experiments as supporting data for the theoretical predictions. Further, we carry out numerical studies of the limiting distribution and the standard deviation of $z^*$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_17530 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the optimal objective value of random linear programs Bakhshi, Marzieh Ostrowski, James Tikhomirov, Konstantin Probability Optimization and Control We consider the problem of maximizing $\langle c,x \rangle$ subject to the constraints $Ax \leq \mathbf{1}$, where $x\in R^n$, $A$ is an $m\times n$ matrix with mutually independent centered subgaussian entries of unit variance, and $c$ is a cost vector of unit Euclidean length. In the asymptotic regime $n\to\infty$, $\frac{m}{n}\to\infty$, and under some mild assumptions on $c$, we prove that the optimal objective value $z^*$ of the linear program satisfies $$ \lim\limits_{n\to\infty}\sqrt{2\log(m/n)}\,z^*= 1\quad \mbox{almost surely}. $$ We provide numerical experiments as supporting data for the theoretical predictions. Further, we carry out numerical studies of the limiting distribution and the standard deviation of $z^*$. |
| title | On the optimal objective value of random linear programs |
| topic | Probability Optimization and Control |
| url | https://arxiv.org/abs/2401.17530 |