Log-barrier interior-point methods are not strongly polynomial

Add 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:

• Optimisation and Numerical Analysis Seminars
• School of Mathematics Events
• University House, 110

Note that ex-directory lists are not shown.