BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.bham.ac.uk//v3//EN
BEGIN:VEVENT
CATEGORIES:Optimisation and Numerical Analysis Seminars
SUMMARY:Log-barrier interior-point methods are not strongl
y polynomial - Xavier Allamigeon (INRIA and CMAP E
cole Polytechnique\, France)
DTSTART:20170216T120000Z
DTEND:20170216T130000Z
UID:TALK2349AT
URL:/talk/index/2349
DESCRIPTION:We identify a class of path-following interior-poi
nt methods which are not strongly polynomial. This
class corresponds to primal-dual interior-point m
ethods which iterates in the so-called ``wide'' ne
ighborhood of the central path arising from the lo
garithmic barrier. It includes short step\, long s
tep as well as predictor-corrector types of interi
or-point methods.\n\nWe establish a lower bound on
the number of iterations of these methods when ap
plied to some parametric families of linear progra
ms. The lower bound is expressed in terms of the n
umber of tropical segments in a piecewise linear c
urve arising from the tropicalization of the centr
al path. In this way\, we derive that the aforemen
tioned interior point methods require $\\Omega(2^d
)$ iterations to solve a linear program in dimensi
on $O(d)$ which we studied in a previous work.\n
LOCATION:University House\, 110
CONTACT:Sergey Sergeev
END:VEVENT
END:VCALENDAR