Criss-cross algorithm: Difference between revisions

Revision as of 21:53, 30 August 2011

Revision as of 22:13, 30 August 2011

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 matrix|sufficient matrices]]" (which generalize both [[positive definite matrix|positive-definite matrices]] and [[P-matrix|''P''-matrices]], which have all [[principal minor]]s positive).;<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=9780521777506|url=http://ebooks.cambridge.org/ebook.jsf?bid=CBO9780511586507|pages=417–479|doi=10.1017/CBO9780511586507|MR=1744046}}</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> the class of sufficient matrices generalize both [[positive definite matrix|positive-definite matrices]] and [[P-matrix|''P''-matrices]], whose [[principal minor]]s are each positive.<ref>{{cite journal|last1=Cottle|first1=R. W.|authorlink1=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 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"/>

===Vertex enumeration===