Criss-cross algorithm: Difference between revisions

Revision as of 20:18, 22 March 2011

Revision as of 20:19, 22 March 2011

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; Roos's paper modifies the [[Victor Klee|Klee]]–Minty construction of a [[unit cube|cube]] on which the simplex algorithm takes&nbsp;2^''D''&nbsp;steps).<ref name="FukudaTerlaky"/><ref>{{harvtxt| name="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> On average, the criss-cross algorithm visits only&nbsp;''D'' corners, however.<ref name="FukudaTerlaky"/> Trivially, the simplex algorithm takes on average&nbsp;''D'' steps for a cube. More generally, for the simplex algorithm, the expected number of steps is proportional to&nbsp;''D'' for linear-programming problems that are randomly drawn from the [[Euclidean metric|Euclidean]] [[unit sphere]], as proved by Borgwardt and by [[Stephen Smale|Smale]].

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|