![]() |
![]() |
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
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 listsComputer Science Distinguished Seminars Centre for Computational Biology Seminar Series SoCS PhD Research Training SessionsOther talksModelling uncertainty in image analysis. Seminar: TBA The science of the large scale heliosphere and the missions that made it possible Well Founded Coalgebras Seminar: TBA Colloquium: TBA |