Zobrazeno 1 - 4
of 4
pro vyhledávání: '"90C51, 14T05"'
The entropic barrier, studied by Bubeck and Eldan (Proc. Mach. Learn. Research, 2015), is a self-concordant barrier with asymptotically optimal self-concordance parameter. In this paper, we study the tropicalization of the central path associated wit
Externí odkaz:
http://arxiv.org/abs/2010.10205
Publikováno v:
SIAM J. Appl. Algebra Geom. 2/1 (2018), 140-178
We prove that primal-dual log-barrier interior point methods are not strongly polynomial, by constructing a family of linear programs with $3r+1$ inequalities in dimension $2r$ for which the number of iterations performed is in $\Omega(2^r)$. The tot
Externí odkaz:
http://arxiv.org/abs/1708.01544
We disprove a continuous analogue of the Hirsch conjecture proposed by Deza, Terlaky and Zinchenko, by constructing a family of linear programs with $3r+4$ inequalities in dimension $2r+2$ where the central path has a total curvature in $\Omega(2^r)$
Externí odkaz:
http://arxiv.org/abs/1405.4161
Publikováno v:
SIAM Journal on Applied Algebra and Geometry
SIAM Journal on Applied Algebra and Geometry, 2018, 2 (1), pp.140-178. ⟨10.1137/17M1142132⟩
SIAM Journal on Applied Algebra and Geometry, Society for Industrial and Applied Mathematics 2018, 2 (1), pp.140-178. ⟨10.1137/17M1142132⟩
SIAM Journal on Applied Algebra and Geometry, 2018, 2 (1), pp.140-178. ⟨10.1137/17M1142132⟩
SIAM Journal on Applied Algebra and Geometry, Society for Industrial and Applied Mathematics 2018, 2 (1), pp.140-178. ⟨10.1137/17M1142132⟩
We prove that primal-dual log-barrier interior point methods are not strongly polynomial, by constructing a family of linear programs with $3r+1$ inequalities in dimension $2r$ for which the number of iterations performed is in $\Omega(2^r)$. The tot
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::a86d1fb46838790052c7399a1154baa2
https://doi.org/10.1137/17m1142132
https://doi.org/10.1137/17m1142132
