Potential-Reduction Methods in Mathematical Programming
Michael Todd
We provide a survey of interior-point methods for linear programming
and its extensions that are based on reducing a suitable potential
function at each iteration. We give a fairly complete overview of
potential-reduction methods for linear programming, focusing on the
possibility of taking long steps and the properties of the barrier
function that are necessary for the analysis. We then describe
briefly how the methods and results can be extended to certain
convex programming problems, following the approach of Nesterov
and Todd.
Technical Report No. 1112, School of Operations Research and
Industrial Engineering,
Cornell University, Ithaca, NY 14853-3801