Criss-cross algorithm: Difference between revisions

Revision as of 14:33, 5 December 2013

Revision as of 11:47, 4 February 2014

Line 16:

The criss-cross algorithm is simpler than the simplex algorithm, because the criss-cross algorithm only has one-phase. Its pivoting rules are similar to the [[Bland's rule|least-index pivoting rule of Bland]].<ref name="Bland">

{{cite journal|title=New finite pivoting rules for the simplex method|first=Robert G.|last=Bland|journal=Mathematics of Operations Research|volume=2|number=2|monthdate=May|year= 1977|pages=103–107|doi=10.1287/moor.2.2.103|jstor=3689647|mr=459599|ref=harv}}</ref> Bland's rule uses only [[sign function|sign]]s of coefficients rather than their [[real number#Axiomatic_approach|(real-number) order]] when deciding eligible pivots. Bland's rule selects an entering variables by comparing values of reduced costs, using the real-number ordering of the eligible pivots.<ref name="Bland"/><ref>Bland's rule is also related to an earlier least-index rule, which was proposed by Katta&nbsp;G. Murty for the [[linear complementarity problem]], according to {{harvtxt|Fukuda|Namiki|1994}}.</ref> Unlike Bland's rule, the criss-cross algorithm is "purely combinatorial", selecting an entering variable and a leaving variable by considering only the signs of coefficients rather than their real-number ordering.<ref name="FukudaTerlaky"/><ref name="TerlakyZhang"/> The criss-cross algorithm has been applied to furnish constructive proofs of basic results in [[real number|real]] [[linear algebra]], such as <!-- [[Steinitz's theorem|Steinitz's lemma]], --> the [[Farkas lemma|lemma of Farkas]]<!-- , [[Weyl's theorem]] on the finite generation of [[convex polytope]]s by linear inequalities ([[halfspace]]s), and the [[Krein–Milman theorem|Minkowski's theorem]] on [[extreme point]]s -->.<ref name="KT91" >{{harvtxt|Klafszky|Terlaky|1991}}</ref>

==Description==

Line 39:

===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]] with "sufficient matrices";<ref name="FukudaTerlaky"/><ref name="FTNamiki"/><ref name="FukudaNamikiLCP" >{{harvtxt|Fukuda|Namiki|1994|}}</ref><ref name="OMBook" >{{cite book|last=Björner|first=Anders|last2=Las&nbsp;Vergnas|first2=Michel|author2-link=Michel Las Vergnas|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=978-0-521-77750-6|url=http://ebooks.cambridge.org/ebook.jsf?bid=CBO9780511586507|pages=417–479|doi=10.1017/CBO9780511586507|MR=1744046}}</ref><ref name="HRT">{{cite journal|first1=D. |last1=den&nbsp;Hertog|first2=C.|last2=Roos|first3=T.|last3=Terlaky|title=The linear complementarity problem, sufficient matrices, and the criss-cross method|journal=Linear Algebra and its Applications|volume=187|monthdate=1 July|year= 1993|pages=1–14|doi=10.1016/0024-3795(93)90124-7|url=http://www.sciencedirect.com/science/article/pii/0024379593901247|<!-- ref=harv -->|url=http://arno.uvt.nl/show.cgi?fid=72943|format=pdf}}</ref><ref name="CIsufficient">{{cite journal|first1=Zsolt|last1=Csizmadia|first2=Tibor|last2=Illés|title=New criss-cross type algorithms for linear complementarity problems with sufficient matrices|journal=Optimization Methods and Software|volume=21|year=2006|number=2|pages=247–266|doi=10.1080/10556780500095009|

url=http://www.cs.elte.hu/opres/orr/download/ORR03_1.pdf|format=pdf|url=http://www.tandfonline.com/doi/abs/10.1080/10556780500095009<!--|eprint=http://www.tandfonline.com/doi/pdf/10.1080/10556780500095009-->|mr=2195759|<!-- ref=harv -->}}</ref> conversely, for linear complementarity problems, the criss-cross algorithm terminates finitely only if the matrix is a sufficient matrix.<ref name="HRT"/><ref name="CIsufficient"/> A [[sufficient&nbsp;matrix]] is a generalization both of a [[positive-definite matrix]] and of a [[P-matrix]], whose [[principal&nbsp;minor]]s are each positive.<ref name="HRT"/><ref name="CIsufficient"/><ref>{{cite journal|last1=Cottle|first1=R.&nbsp;W.|authorlink1=Richard W. Cottle|last2=Pang|first2=J.-S.|last3=Venkateswaran|first3=V.|title=Sufficient matrices and the linear&nbsp;complementarity problem|journal=Linear Algebra and its Applications|volume=114–115|year=1989|pages=231–249|doi=10.1016/0024-3795(89)90463-1|url=http://www.sciencedirect.com/science/article/pii/0024379589904631|month=March–April|mr=986877|ref=harv}}</ref> The criss-cross algorithm has been adapted also for [[linear-fractional programming]].<ref name="LF99Hyperbolic"/><ref name="Bibl"/>

Line 78:

==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 |monthdate=December |year=1992 |pages=295–313 |doi=10.1007/BF02293050 |issue=ACM Symposium on Computational Geometry (North Conway, NH, 1991) number 1 |mr=1174359|ref=harv}}

* {{cite journal|first1=Zsolt|last1=Csizmadia|first2=Tibor|last2=Illés|title=New criss-cross type algorithms for linear complementarity problems with sufficient matrices|journal=Optimization Methods and Software|volume=21|year=2006|number=2|pages=247–266|doi=10.1080/10556780500095009|

url=http://www.cs.elte.hu/opres/orr/download/ORR03_1.pdf|format=pdf|url=http://www.tandfonline.com/doi/abs/10.1080/10556780500095009<!--|eprint=http://www.tandfonline.com/doi/pdf/10.1080/10556780500095009--> |mr=2195759|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|yeardate=March 1994|month=March|pages=365–370|volume=64|number=1|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 |doi=10.1007/BF02614325|journal=Mathematical Programming: Series&nbsp;B|volume=79|pages=369–395|issue=Papers from the&nbsp;16th International Symposium on Mathematical Programming held in Lausanne,&nbsp;1997, number 1–3 |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|mr=1464775|ref=harv|id=[http://www.cas.mcmaster.ca/~terlaky/files/crisscross.ps Postscript preprint]}}

* {{cite journal|first1=D.|last1=den&nbsp;Hertog|first2=C.|last2=Roos|first3=T.|last3=Terlaky|title=The linear complementarity problem, sufficient matrices, and the criss-cross method|journal=Linear Algebra and its Applications|volume=187|monthdate=1 July|year= 1993|pages=1–14|doi=10.1016/0024-3795(93)90124-7|url=http://www.sciencedirect.com/science/article/pii/0024379593901247|ref=harv|url=http://arno.uvt.nl/show.cgi?fid=72943|format=pdf|mr=1221693}}

* {{<!-- 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|first1=Emil|last1=Klafszky|first2=Tamás|last2=Terlaky|title=The role of pivoting in proving some fundamental theorems of linear algebra|journal=Linear Algebra and its Applications|volume=151|monthdate=June|year= 1991|pages=97–118|doi=10.1016/0024-3795(91)90356-2|url=http://www.sciencedirect.com/science/article/pii/0024379591903562|url=http://www.cas.mcmaster.ca/~terlaky/files/pivot-la.ps|format=postscript|ref=harv|mr=1102142}}

* {{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|pages=79–84|doi=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–690|issn=0233-1934|doi=10.1080/02331938508843067|ref=harv|mr=798939|<!-- Google scholar reported no free versions -->}}