Nonconvex Weighted Potential Function for Polynomial Target Following Methods

摘要

Long step interior point methods in linear programming are some of the mostefficient algorithms from a computational point of view. The authors 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. 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.