Criss-cross algorithm: Difference between revisions

Revision as of 23:35, 31 May 2011

Revision as of 19:24, 4 June 2011

Line 1:

{{about|an [[algorithm]] for [[optimization (mathematics)|mathematical optimization]]|the naming of [[analytical chemistry|chemicals]]|crisscross method}}

<!-- {{context}} -->

[[Image :Unitcube.svg|thumb|right|alt=A three-dimensional cube|The criss-cross algorithm visits all&nbsp;8 corners of the [[Klee–Minty cube]] in the worst case. It visits&nbsp;3 additional corners on&nbsp;average. The Klee–Minty cube is a perturbation of the cube shown here.]]

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 functions]]; there are criss-cross algorithms for [[linear-fractional programming]] problems,<ref name="LF99Hyperbolic">{{harvtxt|Illés|Szirmai|Terlaky|1999}}</ref><ref name="Bibl" >{{cite journal|first=I.&nbsp;M.|last=Stancu-Minasian|title=A sixth bibliography of fractional programming|journal=Optimization|volume=55|number=4|month=August|url=http://www.informaworld.com/10.1080/02331930600819613| year=2006|pages=405–428|doi=10.1080/02331930600819613|mr=2258634}}</ref> [[quadratic programming|quadratic-programming]] problems, and [[linear complementarity problem]]s.<ref name="FukudaTerlaky" >{{harvtxt|Fukuda|Terlaky|1997}}</ref>

|url=http://www.informaworld.com/10.1080/02331930600819613| year=2006|pages=405–428|doi=10.1080/02331930600819613|MR=2258634}}</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) [[unit cube|cube]] in dimension&nbsp;''D'', the [[Klee–Minty cube]] (after [[Victor Klee]] and [[George J. Minty]]), in the [[worst-case complexity|worst case]].<ref name="Roos" >{{harvtxt|Roos|1990}}</ref><ref name="KleeMinty"/> However, when it is started at a random corner, the criss-cross algorithm [[Average-case complexity|on&nbsp;average]] visits only&nbsp;''D'' additional corners.<ref name="FTNamiki"/><ref name="FukudaNamiki"/><ref name="Borgwardt">The simplex algorithm takes on average&nbsp;''D'' steps for a cube. {{harvtxt|Borgwardt|1987}}: {{cite book|last=Borgwardt|first=Karl-Heinz|title=The simplex method: A probabilistic analysis|series=Algorithms and Combinatorics (Study and Research Texts)|volume=1|publisher=Springer-Verlag|___location=Berlin|year=1987|pages=xii+268|isbn=3-540-17096-0|MRmr=868467|ref=harv}}</ref> Thus, for the three-dimensional cube, the algorithm visits all&nbsp;8 corners in the worst case and exactly&nbsp;3 additional corners on&nbsp;average.

==History==

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.<ref name="FukudaTerlaky"/>

==Comparison with the simplex algorithm for linear optimization==

Line 31 ⟶ 30:

Several algorithms for linear programming—[[Khachiyan]]'s [[ellipsoidal algorithm]], [[Karmarkar]]'s [[Karmarkar's algorithm|projective algorithm]], and [[interior-point method|central-path algorithm]]s—have polynomial time-complexity (in the [[worst case complexity|worst case]] and thus [[average case complexity|on&nbsp;average]]). The ellipsoidal and projective algorithms were published before the criss-cross algorithm.

However, like the simplex algorithm of Dantzig, the criss-cross algorithm is ''not'' a polynomial-time algorithm for linear programming. Terlaky's criss-cross algorithm 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 name="Roos"/><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|MRmr=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> Like the simplex algorithm, the criss-cross algorithm visits all&nbsp;8 corners of the three-dimensional cube in the worst case.

When it is initialized at a random corner of the cube, the criss-cross algorithm visits only&nbsp;''D'' additional corners, however, according to a&nbsp;1994 paper by Fukuda and Namiki.<ref name="FukudaNamikiFTNamiki" >{{harvtxt|Fukuda|NamikiTerlaky|19941997|p=367385}}</ref><ref name="FTNamikiFukudaNamiki" >{{harvtxt|Fukuda|TerlakyNamiki|19971994|p=385367}}</ref> Trivially, the simplex algorithm takes on average&nbsp;''D'' steps for a cube.<ref name="Borgwardt"/><ref>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&nbsp;sphere]], as proved by Borgwardt and by [[Stephen Smale|Smale]].</ref><ref name="Borgwardt"/> Like the simplex algorithm, the criss-cross algorithm visits exactly&nbsp;3 additional corners of the three-dimensional cube on&nbsp;average.

==Variants==

Line 39 ⟶ 38:

===Other optimization problems with linear constraints===

There are variants of the criss-cross algorithm for linear programming, for [[quadratic programming]], and for the [[linear complementarity problem|linear-complementarity problem]].<ref name="FukudaNamikiLCPFukudaTerlaky" />{{harvtxt|Fukuda|Namiki|1994|}}<ref name="FTNamiki"/ref><ref name="FTNamikiFukudaNamikiLCP" >{{harvtxt|Fukuda|TerlakyNamiki|19971994|p=385}}</ref><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|pages=417–479|doi=10.1017/CBO9780511586507|MR=1744046}}</ref> The criss-cross algorithm has been adapted also for [[linear-fractional programming]].<ref name="LF99Hyperbolic"/><ref name="Bibl"/>

|pages=417–479|doi=10.1017/CBO9780511586507|MR=1744046}}</ref> The criss-cross algorithm has been adapted also for [[linear-fractional programming]].<ref name="LF99Hyperbolic"/><ref name="Bibl"/>

===Vertex enumeration===

Line 60 ⟶ 58:

|publisher=University of North Carolina Press.

|issue=4

|MRmr=278972

|url=http://www.math.washington.edu/~rtr/papers/rtr-ElemVectors.pdf|ref=harv|id=[http://www.math.washington.edu/~rtr/papers/rtr-ElemVectors.pdf PDF reprint]|}}</p><p>Rockafellar was influenced by the earlier studies of [[Albert W. Tucker]] and [[George J. Minty]]. Tucker and Minty had studied the sign patterns of the matrices arising through the pivoting operations of Dantzig's simplex algorithm.</p>

</ref> Indeed, Bland's pivoting rule was based on his previous papers on oriented-matroid theory. However, Bland's rule exhibits cycling on some oriented-matroid linear-programming problems.<ref name="OMBook"/> The first purely combinatorial algorithm for linear programming was devised by [[Michael J. Todd (mathematician)|Michael&nbsp;J. Todd]].<ref name="ToddOMBook"/><ref name="OMBookTodd"/> Todd's algorithm was developed not only for linear-programming in the setting of oriented matroids, but also for [[quadratic programming|quadratic-programming problems]] and [[linear complementarity problem|linear-complementarity problem]]s.<ref name="OMBook"/><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|MRmr=811116|doi=10.1016/0095-8956(85)90042-5|url=http://dx.doi.org/10.1016/0095-8956(85)90042-5|ref=harv}} </ref><ref name="OMBook"/> Todd's algorithm is complicated even to state, unfortunately, and its finite-convergence proofs are somewhat complicated.<ref name="OMBook"/>

}}</p><p>Rockafellar was influenced by the earlier studies of [[Albert W. Tucker]] and [[George J. Minty]]. Tucker and Minty had studied the sign patterns of the matrices arising through the pivoting operations of Dantzig's simplex algorithm.</p>

</ref> Indeed, Bland's pivoting rule was based on his previous papers on oriented-matroid theory. However, Bland's rule exhibits cycling on some oriented-matroid linear-programming problems.<ref name="OMBook"/> The first purely combinatorial algorithm for linear programming was devised by [[Michael J. Todd (mathematician)|Michael&nbsp;J. Todd]].<ref name="Todd"/><ref name="OMBook"/> Todd's algorithm was developed not only for linear-programming in the setting of oriented matroids, but also for [[quadratic programming|quadratic-programming problems]] and [[linear complementarity problem|linear-complementarity problem]]s.<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=harv}} </ref><ref name="OMBook"/> Todd's algorithm is complicated even to state, unfortunately, and its finite-convergence proofs are somewhat complicated.<ref name="OMBook"/>

When the criss-cross algorithm was published, the simplicity of its statement was remarkable, as was the simplicity of its finite-termination proof. Another remarkable feature of the criss-cross algorithm was that it was readily adapted to more complicated problems.<ref name="OMBook"/> There are oriented-matroid variants of the criss-cross algorithm for the linear programming problem, for the quadratic programming problem, and for the linear-complementarity problem.<ref name="FukudaNamikiLCPFukudaTerlaky"/><ref name="FukudaTerlakyFukudaNamikiLCP"/><ref name="OMBook"/>

==Summary==

Line 77 ⟶ 74:

==Notes==

<references/>

==References==

* {{cite journal|url=http://www.springerlink.com/content/m7440v7p3440757u/|first1=David|last1=Avis|first2=Komei|last2=Fukuda|authorlink2=Komei Fukuda|authorlink1=David Avis|title=A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra|journal=[[Discrete and Computational Geometry]]|volume=8|number=1|month=December|year=1992|pages=295-313295–313

|doi=10.1007/BF02293050|issue=ACM Symposium on Computational Geometry (North Conway, NH, 1991)|MRmr=1174359|ref=harv}}

* {{cite journal|last1=Fukuda|first1=Komei|authorlink1=Komei Fukuda|last2=Namiki|first2=Makoto|title=On extremal behaviors of Murty's least index method|journal=Mathematical Programming|year=1994|month=March|pages=365–370|volume=64|number=1|url=http://dx.doi.org/10.1007/BF01582581|doi=10.1007/BF01582581|ref=harv|MR=1286455|}}

* {{cite journal|first1=Komei|last1=Fukuda|<!-- authorlink1=Komei Fukuda -->|first2=Tamás|last2=Terlaky|<!-- authorlink2=Tamás Terlaky -->|title=Criss-cross methods: A fresh view on pivot algorithms |url=http://dx.doi.org/10.1007/BF02614325|journal=Mathematical Programming: Series&nbsp;B|volume=79|number=1–3|pages=369–395|issue=Papers from the&nbsp;16th International Symposium on Mathematical Programming held in Lausanne,&nbsp;1997|editor1-first=Thomas&nbsp;M.|editor1-last=Liebling|editor2-first=Dominique|editor2-last=de&nbsp;Werra|publisher=North-Holland Publishing&nbsp;Co.|___location=Amsterdam|year=1997|doi=10.1016/S0025-5610(97)00062-2|MRmr=1464775|ref=harv|id=[http://www.cas.mcmaster.ca/~terlaky/files/crisscross.ps Postscript preprint]|}}

* {{<!-- citation -->cite journal|title=The finite criss-cross method for hyperbolic programming|journal=European Journal of Operational Research|volume=114|number=1|

pages=198–214|year=1999|<!-- issn=0377-2217 -->|doi=10.1016/S0377-2217(98)00049-6|url=http://www.sciencedirect.com/science/article/B6VCT-3W3DFHB-M/2/4b0e2fcfc2a71e8c14c61640b32e805a

|first1=Tibor|last1=Illés|first2=Ákos|last2=Szirmai|first3=Tamás|last3=Terlaky|zbl=0953.90055|id=[http://www.cas.mcmaster.ca/~terlaky/files/dut-twi-96-103.ps.gz Postscript preprint]|ref=harv}}

* {{cite journal|last=Roos|first=C.|title=An exponential example for Terlaky's pivoting rule for the criss-cross simplex method|journal=Mathematical Programming|volume=46|year=1990|number=1|series=Series&nbsp;A|79–84|doi=10.1007/BF01585729|url=http://dx.doi.org/10.1007/BF01585729|MR=1045573|ref=harv|<!-- Google scholar reported no free versions -->}}

* {{cite journal|last=Terlaky|first=T.|title=A convergent criss-cross method|journal=Optimization: A Journal of Mathematical Programming and Operations Research|volume=16|year=1985|number=5|pages=683--690683–690|issn=0233-1934|doi=10.1080/02331938508843067|url=http://dx.doi.org/10.1080/02331938508843067|ref=harv|MR=798939|<!-- Google scholar reported no free versions -->}}

* {{cite journal|last=Terlaky|first=Tamás|authorlink=Tamás Terlaky|title=A finite crisscross method for oriented matroids|volume=42|year=1987|number=3|pages=319–327|journal=Journal of Combinatorial Theory|series=Series&nbsp;B|ref=harv|issn=0095-8956|doi=10.1016/0095-8956(87)90049-9|url=http://dx.doi.org/10.1016/0095-8956(87)90049-9|MR=888684|ref=harv|<!-- Google scholar reported no free versions -->}}

* {{cite journal|last1=Terlaky|first1=Tamás|<!-- authorlink1=Tamás Terlaky -->|last2=Zhang|first2=Shu&nbsp;Zhong|title=Pivot rules for linear programming: A Survey on recent theoretical developments|issue=Degeneracy in optimization problems|journal=Annals of Operations Research|volume=46–47|year=1993|number=1|pages=203–233|doi=10.1007/BF02096264|url=http://dx.doi.org/10.1007/BF02096264|MR=1260019|id=[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.36.7658&rep=rep1&type=pdf PDF file of (1991) preprint]|publisher=Springer Netherlands|issn=0254-5330|ref=harv}}

* {{cite journal|last=Wang|first=Zhe&nbsp;Min|title=A finite conformal-elimination free algorithm over oriented&nbsp;matroid programming|journal=Chinese Annals of Mathematics (Shuxue Niankan&nbsp;B&nbsp;Ji)|series=Series&nbsp;B|volume=8|year1987year=1987|number=1|pages=120–125|issn=0252-9599|MRmr=886756|ref=harv|<!-- Google scholar reported no free versions -->}}

==External links==

* [http://www.ifor.math.ethz.ch/~fukuda/ Komei Fukuda (ETH Zentrum, Zurich)] with [http://www.ifor.math.ethz.ch/~fukuda/publ/publ.html publications]

* [http://coral.ie.lehigh.edu/~terlaky/ Tamás Terlaky (Lehigh University)] with [http://coral.ie.lehigh.edu/~terlaky/publications publications]