A generic path-following algorithm with a sliding constraint and its application to linear programming and the computation of analytic centers

Jean-Philippe Vial

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(\sqrt 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.

Technical Report 1996.8, Logilab, HEC Geneva, Section of Management Studies, University of Geneva, 102 Bd Carl-Vogt, CH-1211, Switzerland.

The report can be retrieved from this Web page.

Contact: jpvial@uni2a.unige.ch