A nonconvex weighted potential function for polynomial target following methods

Long step interior-point methods in linear programming are some of the most efficient algorithms from a computational point of view. We prove polynomial complexity of a class of long step target-following methods in a novel way, by introducing a new nonconvex potential function and adapting the analysis framework of Jansen et al. The main advantage is that the new potential function has an obvious extension to semi-definite programming, whereas the potential used in the above-mentioned papers does not.