Potential-reduction methods in mathematical programming |
| |
Authors: | Michael J Todd |
| |
Institution: | (1) School of Operations Research and Industrial Engineering, Cornell University, 14853 Ithaca, NY, USA |
| |
Abstract: | 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. We conclude with some open problems.
Research supported in part by NSF, AFOSR and ONR through NSF Grant DMS-8920550. Some of this work was done while the author
was on a sabbatical leave from Cornell University visiting the Department of Mathematics at the University of Washington. |
| |
Keywords: | Linear programming Potential functions Interior-point methods Self-concordant barriers Self-scaled barriers |
本文献已被 SpringerLink 等数据库收录! |
|