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