تقرير
On the optimal objective value of random linear programs
| العنوان: | On the optimal objective value of random linear programs |
|---|---|
| المؤلفون: | Bakhshi, Marzieh, Ostrowski, James, Tikhomirov, Konstantin |
| سنة النشر: | 2024 |
| المجموعة: | Mathematics |
| مصطلحات موضوعية: | Mathematics - Probability, Mathematics - Optimization and Control |
| الوصف: | We consider the problem of maximizing $\langle c,x \rangle$ subject to the constraints $Ax \leq \mathbf{1}$, where $x\in{\mathbb 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 additional 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}. $$ In the context of high-dimensional convex geometry, our findings imply sharp asymptotic bounds on the spherical mean width of the random convex polyhedron $P=\{x\in{\mathbb R}^n:\; Ax\leq \mathbf{1}\}$. 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^*$. Comment: added proof of asymptotic upper bound on z^* |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2401.17530 |
| رقم الأكسشن: | edsarx.2401.17530 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |