Constant potential primal—dual algorithms: A framework |
| |
Authors: | Tunçel Levent |
| |
Institution: | (1) Department of Combinatorics and Optimization, Faculty of Mathematics, University of Waterloo, N2L 3G1 Waterloo, Ontario, Canada |
| |
Abstract: | We start with a study of the primal—dual affine-scaling algorithms for linear programs. Using ideas from Kojima et al., Mizuno and Nagasawa, and new potential functions we establish a framework for primal—dual algorithms that keep a potential function value fixed. We show that if the potential function used in the algorithm is compatible with a corresponding neighborhood of the central path then the convergence proofs simplify greatly. Our algorithms have the property that all the iterates can be kept in a neighborhood of the central path without using any centering in the search directions.Research performed while the author was Ph.D. student at Cornell University and was supported in part by the United States Army Research Office through the Army Center of Excellence for Symbolic Methods in Algorithmic Mathematics (ACSyAM), Mathematical Sciences Institute of Cornell University, Contract DAAL03-91-C-0027, and also by NSF, AFOSR and ONR through NSF Grant DMS-8920550. |
| |
Keywords: | Linear programming Interior point methods Primal— dual algorithms Potential function |
本文献已被 SpringerLink 等数据库收录! |
|