POTENTIAL-REDUCTION METHODS IN MATHEMATICAL-PROGRAMMING

We provide a survey of interior-point methods for linear programming a nd its extensions that are based on reducing a suitable potential func tion at each iteration. We give a fairly complete overview of potentia l-reduction methods for linear programming, focusing on the possibilit y of taking long steps and the properties of the barrier function that are necessary for the analysis. We then describe briefly how the meth ods and results can be extended to certain convex programming problems , following the approach of Nesterov and Todd. We conclude with some o pen problems.