Potential Reduction Method for a Class of Smooth Convex Programming Problems

摘要

The paper proposed a potential reduction method for smooth convex programming. It is assumed that the objective and constraint functions fulfill the so-called Relative Lipschitz Condition, with Lipschitz constant M > O. A great advantage of the method, above the existing path-following methods, is that the steps can be made long by performing linesearches. This method performs linesearches along the Newton direction with respect to a strictly convex potential function if they are far away from the central path. If they are sufficiently close to this path, it updates a lower bound for the optimal value. The authors prove that the number of iterations required by the algorithm to converge to an epsilon-optimal solution is O((1 + M sup 2) sq rt(n)/ln epsilon) or O((1 + M sup 2)n/ln epsilon/), dependent on the updating scheme for the lower bound.