Criss-cross algorithm: Difference between revisions

Revision as of 09:08, 13 December 2011

Revision as of 07:09, 4 May 2012

Line 1:

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

<!-- {{contextContext|date=May 2012}} -->

[[ImageFile: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>

Line 11:

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

{{See also|Linear programming|Simplex algorithm|Bland's rule}}

[[ImageFile:Simplex description.png|thumb|240px|In its second phase, the ''simplex algorithm'' crawls along the edges of the polytope until it finally reaches an optimum [[vertex (geometry)|vertex]]. The ''criss-cross algorithm'' considers bases that are not associated with vertices, so that some iterates can be in the ''interior ''of the feasible region, like interior-point algorithms; the criss-cross algorithm can also have ''infeasible'' iterates ''outside'' the feasible region.]]

In linear programming, the criss-cross algorithm pivots between a sequence of bases but differs from the [[simplex algorithm]] of [[George Dantzig]]. The simplex algorithm first finds a (primal-) feasible basis by solving a "''phase-one'' problem"; in "phase two", the simplex algorithm pivots between a sequence of basic ''feasible ''solutions so that the objective function is non-decreasing with each pivot, terminating when with an optimal solution (also finally finding a "dual feasible" solution).<ref name="FukudaTerlaky"/><ref name="TerlakyZhang">{{harvtxt|Terlaky|Zhang|1993}}</ref>

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|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=9780521777506978-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|month=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|url2=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"/>