Criss-cross algorithm: Difference between revisions

Revision as of 01:23, 24 May 2021

Revision as of 13:20, 6 July 2021

Line 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]] with "sufficient matrices";<ref name="FukudaTerlaky"/><ref name="FTNamiki"/><ref name="FukudaNamikiLCP" >{{harvtxt|Fukuda|Namiki|1994|}}</ref><ref name="OMBook" >{{cite book|last1=Björner|first1=Anders|last2=Las Vergnas|first2=Michel|author2-link=Michel Las Vergnas|last3=Sturmfels|first3=Bernd|author-link3=Bernd Sturmfels|last4=White|first4=Neil|last5=Ziegler|first5=Günter|author-link5=Günter M. Ziegler|title=Oriented Matroids|chapter=10 Linear programming|publisher=Cambridge University Press|year=1999|isbn=978-0-521-77750-6|pages=417–479|doi=10.1017/CBO9780511586507|mr=1744046}}</ref><ref name="HRT">{{cite journal|first1=D. |last1=den 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|date=1 July 1993|pages=1–14|url=http://core.ac.uk/download/pdf/6714737.pdf|doi=10.1016/0024-3795(93)90124-7|doi-access=free}}</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<!--|eprint=http://www.tandfonline.com/doi/pdf/10.1080/10556780500095009-->|mr=2195759|s2cid=24418835}}</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. W.|author-link1=Richard W. Cottle|last2=Pang|first2=J.-S.|last3=Venkateswaran|first3=V.|title=Sufficient matrices and the linear complementarity problem|journal=Linear Algebra and Its Applications|volume=114–115|date=March–April 1989|pages=231–249|doi=10.1016/0024-3795(89)90463-1|mr=986877|doi-access=free}}</ref> The criss-cross algorithm has been adapted also for [[linear-fractional programming]].<ref name="LF99Hyperbolic"/><ref name="Bibl"/>

===Vertex enumeration===

Line 60:

|mr=278972

|chapter-url=http://www.math.washington.edu/~rtr/papers/rtr-ElemVectors.pdf |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="OMBook"/><ref name="Todd"/> 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 J.|author-link=Michael J. Todd (mathematician)|title=Linear and quadratic programming in oriented matroids|journal=Journal of Combinatorial Theory|series=Series B|volume=39|year=1985|number=2|pages=105–133|mr=811116|doi=10.1016/0095-8956(85)90042-5|doi-access=free}}</ref> Todd's algorithm is complicated even to state, unfortunately, and its finite-convergence proofs are somewhat complicated.<ref name="OMBook"/>

The criss-cross algorithm and its proof of finite termination can be simply stated and readily extend the setting of oriented matroids. The algorithm can be further simplified for ''linear feasibility problems'', that is for [[linear system]]s with [[linear inequality|nonnegative variable]]s; these problems can be formulated for oriented matroids.<ref name="KT91"/> The criss-cross algorithm has been adapted for problems that are more complicated than linear programming: There are oriented-matroid variants also for the quadratic-programming problem and for the linear-complementarity problem.<ref name="FukudaTerlaky"/><ref name="FukudaNamikiLCP"/><ref name="OMBook"/>

Line 88:

* {{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 A|pages=79–84|doi=10.1007/BF01585729|mr=1045573|s2cid=33463483}}<!-- 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|mr=798939}}<!-- Google scholar reported no free versions -->

* {{cite journal|last=Terlaky|first=Tamás|author-link=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 B|issn=0095-8956|doi=10.1016/0095-8956(87)90049-9|mr=888684|doi-access=free}}<!-- Google scholar reported no free versions -->

* {{cite journal|last1=Terlaky|first1=Tamás| author-link1=Tamás Terlaky |last2=Zhang|first2=Shu Zhong|title=Pivot rules for linear programming: A Survey on recent theoretical developments|issue=Degeneracy in optimization problems, number 1 |journal=Annals of Operations Research|volume=46–47|year=1993|pages=203–233 |doi=10.1007/BF02096264|mr=1260019 |citeseerx = 10.1.1.36.7658 |s2cid=6058077| orig-year = 1991 |issn=0254-5330}}

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