On the Equivalence of the Simplex Methods and a Multiplier-Alike Method for Linear Programming |
| |
| Authors: | Chang T. S. Adachi J. Wang X. Chen T.R. |
| |
| Affiliation: | (1) Department of Electrical and Computer Engineering, University of California, Davis, California;(2) Applied Mathematics Group, University of California, Davis, California;(3) Department of Electrical and Computer Engineering, University of California, Davis, California |
| |
| Abstract: | In linear programming, the simplex method has been viewed for a long time as an efficient tool. Interior methods have attracted a lot of attention since they were proposed recently. It seems plausible intuitively that there is no reason why a good linear programming algorithm should not be allowed to cross the boundary of the feasible region when necessary. However, such an algorithm is seldom studied. In this paper, we will develop first a framework of a multiplier-alike algorithm for linear programming which allows its trajectory to move across the boundary of the feasible region. Second, we illustrate that such a framework has the potential to perform as well as the simplex method by showing that these methods are equivalent in a well-defined sense, even though they look so different. |
| |
| Keywords: | Linear programming simplex method multiplier method augmented Lagrangian method |
| 本文献已被 SpringerLink 等数据库收录！ |
|
