On the Equivalence of the Simplex Methods and a Multiplier-Alike Method for Linear Programming

T. S. Chang, J. Adachi, X. Wang and T.R. Chen
Additional contact information
T. S. Chang: University of California
J. Adachi: University of California
X. Wang: University of California
T.R. Chen: University of California

Journal of Optimization Theory and Applications, 2002, vol. 113, issue 3, No 4, 487-512

Abstract: 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 (search for similar items in EconPapers)
Date: 2002
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1023/A:1015356704142 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:113:y:2002:i:3:d:10.1023_a:1015356704142

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1023/A:1015356704142

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().