A Generic Path-Following Algorithm With a Sliding Constraint and Its Application to Linear Programming and the Computation of Analytic Centers

We propose a generic path-following scheme which is essentially a method of centers that can be implemented with a variety of algorithms. The complexity estimate is computed on the sole assumption that a certain local quadratic convergence property holds, independently of the specific algorithmic procedure in use, primal, dual or primal-dual. We show convergence in O( p n) iterations. We verify that the primal, dual and primal-dual algorithms satisfy the local quadratic convergence property. The method can be applied to solve the linear programming problem (with a feasible start) and to compute the analytic center of a bounded polytope. The generic path-following scheme easily extends to the logarithmic penalty barrier approach. Keywords Interior point method, method of centers, path-following, linear programming. This work has been completed with the support from the Swiss National Foundation for Scientific Research, grant 12-34002.92. 1 Introduction Shortly after Karmarkar's s..