A nonconvex weighted potential function for polynomial target following methods

E. de Klerk, C. Roos, T. Terlaky

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 non-convex potential function and adapting the analysis framework of Jansen et al. \cite{int:Jansen8,int:Jansen9,int:Jansen0}. The main advantage is that the new potential function has an obvious extension to semi-definite programming, whereas the potential used in abovementioned papers does not.

Report 95--127, Faculty of Technical Mathematics and Computer Science, Delft University of Technology, Delft, 1995.