University of Birmingham > Talks@bham > Optimisation and Numerical Analysis Seminars > Log-barrier interior-point methods are not strongly polynomial

## Log-barrier interior-point methods are not strongly polynomialAdd to your list(s) Download to your calendar using vCal - Xavier Allamigeon (INRIA and CMAP Ecole Polytechnique, France)
- Thursday 16 February 2017, 12:00-13:00
- University House, 110.
If you have a question about this talk, please contact Sergey Sergeev. We identify a class of path-following interior-point methods which are not strongly polynomial. This class corresponds to primal-dual interior-point methods which iterates in the so-called ``wide’’ neighborhood of the central path arising from the logarithmic barrier. It includes short step, long step as well as predictor-corrector types of interior-point methods. We establish a lower bound on the number of iterations of these methods when applied to some parametric families of linear programs. The lower bound is expressed in terms of the number of tropical segments in a piecewise linear curve arising from the tropicalization of the central path. In this way, we derive that the aforementioned interior point methods require $\Omega(2^d)$ iterations to solve a linear program in dimension $O(d)$ which we studied in a previous work. This talk is part of the Optimisation and Numerical Analysis Seminars series. ## This talk is included in these lists:Note that ex-directory lists are not shown. |
## Other listsPIPS - Postgraduate Informal Physics Seminars Bham Talks Computer Science Distinguished Seminar## Other talksGravitational wave progenitors near and far The statistical era of strong gravitational lensing cosmology Privileged side-channel attacks for enclave adversaries Stellar population models Plundervolt: Pillaging and plundering SGX with Software-based Fault Injection Attacks Role of Mechanics and Geometry in Cellular Information Processing |