On the finite convergence of interior-point algorithms for linear programming |
| |
Authors: | Yinyu Ye |
| |
Institution: | (1) Department of Management Sciences, The University of Iowa, 52242 Iowa City, IA, USA |
| |
Abstract: | It has been shown 8] that numerous interior-point algorithms for linear programming (LP) generate solution sequences that converge to strict complementarity solutions, or interior solutions on the optimal face. In this note we further establish a theoretical base for Gay's test (Gay, 1989) to identify the optimal face, and develop a new termination procedure to obtain an exact solution on the optimal face. We also report some numerical results for solving a set of LP test problems, each of which has a highly degenerate and unbounded optimal face.Research supported in part by NSF Grant DDM-8922636, The Iowa Business School Summer Grant, and the Interdisciplinary Research Grant of the University of Iowa Center for Advanced Studies. |
| |
Keywords: | Strict complementarity interior point algorithms linear programming optimal face |
本文献已被 SpringerLink 等数据库收录! |
|