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 listsFeatured talks Computer Security Seminars Condensed Matter Physics Seminars## Other talksLovĂˇsz' Theorem and Comonads in Finite Model Theory Generalised hydrodynamics and universalities of transport in integrable (and non-integrable) spin chains Best Response Dynamics on Random Graphs Quantum simulation of strongly correlated fermions: A theory perspective |