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 polynomial

Add to your list(s) Download to your calendar using vCal

  • UserXavier Allamigeon (INRIA and CMAP Ecole Polytechnique, France)
  • ClockThursday 16 February 2017, 12:00-13:00
  • HouseUniversity 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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


Talks@bham, University of Birmingham. Contact Us | Help and Documentation | Privacy and Publicity.
talks@bham is based on from the University of Cambridge.