Criss-cross algorithm: Difference between revisions

Revision as of 03:44, 22 March 2011

Revision as of 11:38, 22 March 2011

Line 1:

In [[optimization (mathematics)|mathematical optimization]], the '''criss-cross algorithm''' denotes a family of [[algorithm]]s for [[linear programming]]. Variants of the criss-cross algorithm also solve more general problems with [[linear programming|linear inequality constraints]] and [[nonlinear programming|nonlinear]] [[optimization (mathematics)|objective functionfunctions]]s; there are criss-cross algorithms for [[linear-fractional programming]] problems,<ref name="LF99Hyperbolic">{{harvtxt|Illés|Szirmai|Terlaky|1999}}</ref> [[quadratic programming|quadratic-programming]] problems, and [[linear complementarity problem]]s.<ref name="FukudaTerlaky" > {{harvtxt|Fukuda|Terlaky|1997}} </ref>

Like the [[simplex algorithm]] of [[George Dantzig|George B. Dantzig]], the criss-cross algorithm is not a [[time complexity|polynomial-time algorithm]] for linear programming. Both algorithms visit all&nbsp;2^''D''&nbsp;corners of a (perturbed) cube in dimension&nbsp;''D'', the [[Victor Klee|Klee]]-Minty cube.<ref name="FukudaTerlaky"/><ref name="KleeMinty"/>

==Comparison with the simplex algorithm of Dantzig==

Line 10:

==Properties==

Like the simplex algorithm of Dantzig, the criss-cross algorithm is not a [[time complexity|polynomial-time algorithm]] for linear programming. The original criss-cross algorithm of Terlaky visits all the&nbsp;2^''D''&nbsp;corners of a (perturbed) cube in dimension&nbsp;''D'', according to a paper of Roos (which modifies the Klee-Minty construction of a cube on which the simplex algorithm takes&nbsp;2^''D''&nbsp;steps.<ref name="FukudaTerlaky"/><ref>{{harvtxt|Roos|1990}}</ref><ref name="KleeMinty">{{cite book|title=Inequalities&nbsp;III (Proceedings of the Third Symposium on Inequalities held at the University of California, Los Angeles, Calif., September&nbsp;1–9,&nbsp;1969, dedicated to the memory of Theodore&nbsp;S. Motzkin)|editor-first=Oved|editor-last=Shisha|publisher=Academic Press|___location=New York-London|year=1972|MR=332165|last1=Klee|first1=Victor|authorlink1=Victor Klee|last2=Minty|first2= George&nbsp;J.|authorlink2=George J. Minty|chapter=How good is the simplex algorithm?|pages=159–175|ref=harv}}</ref>

The criss-cross algorithm was published independently by [[Tamás Terlaky]]<ref> {{harvtxt|Terlaky|1985}} and {{harvtxt|Terlaky|1987}} </ref> and by Zhe-Min Wang;<ref name="Wang" >{{harvtxt|Wang|1987}} </ref> related algorithms appeared in unpublished reports by other authors. The criss-cross algorithm is often studied using the theory of [[oriented matroid]]s (OMs), which is a [[combinatorics|combinatorial]] abstraction of linear-optimization theory.<ref>The theory of [[oriented matroid]]s was initiated by [[R.&nbsp;Tyrrell Rockafellar]] to describe the sign patterns of the matrices arising through the pivoting operations of Dantzig's simplex algorithm; Rockafellar was inspired by [[Albert W. Tucker]] studies of such sign patterns in "Tucker tableaux". {{harv|Rockafellar|1969}}</ref> Indeed, Bland's pivoting rule was based on his previous papers on oriented matroid theory. Much literature on the criss-cross algorithm concerns oriented matroids. Historically, OM&nbsp;algorithms for [[quadratic programming|quadratic-programming problems]] and [[linear complementarity problem|linear-complementarity problem]]s had been published by [[Michael J. Todd (mathematician)|Michael J. Todd]] before Terlaky and Wang published their criss-cross algorithms.<ref name="Todd" > {{cite journal|last=Todd|first=Michael&nbsp;J.|authorlink=Michael J. Todd (mathematician)|title=Linear and quadratic programming in oriented matroids|journal=Journal of Combinatorial Theory|series=Series&nbsp;B|volume=39|year=1985|number=2|pages=105–133|MR=811116|doi=10.1016/0095-8956(85)90042-5|url=http://dx.doi.org/10.1016/0095-8956(85)90042-5}} </ref> However, Todd's pivoting-rule cycles on nonrealizable oriented matroids (and only on nonrealizable oriented matroids). Such cycling does not stump the OM criss-cross algorithms of Terlaky and Wang, however. There are oriented-matroid variants of the criss-cross algorithm for linear programming, for quadratic programming, and for the linear-complementarity problem.<ref name="FukudaTerlaky"/><ref name="OMBook" >{{cite book|last=Björner|first=Anders|last2=Las&nbsp;Vergnas|first2=Michel|last3=Sturmfels|first3=Bernd|authorlink3=Bernd Sturmfels|last4=White|first4=Neil|last5=Ziegler|first5=Günter|authorlink5=Günter M. Ziegler|title=Oriented Matroids|chapter=10 Linear programming|publisher=Cambridge University Press|year=1999|isbn=9780521777506|url=http://ebooks.cambridge.org/ebook.jsf?bid=CBO9780511586507|