Kors-kors-algoritm

Den här artikeln handlar om en algoritm för matematisk optimering. För annan användning, se Cross-cross .

A three-dimensional cube
Algoritmen på kors och tvärs besöker alla 8 hörn av Klee–Minty-kuben i värsta fall. Den besöker 3 ytterligare hörn i genomsnitt. Klee–Minty-kuben är en störning av kuben som visas här.

I matematisk optimering är kors och tvärs-algoritmen vilken som helst av en familj av algoritmer för linjär programmering . Varianter av kors-kors-algoritmen löser också mer allmänna problem med linjära olikhetsbegränsningar och icke-linjära objektiva funktioner ; det finns kors och tvärs algoritmer för linjär-fraktionella programmeringsproblem , kvadratiska programmeringsproblem och linjära komplementaritetsproblem .

Liksom simplexalgoritmen av George B. Dantzig , är kors-korsalgoritmen inte en polynom-tidsalgoritm för linjär programmering. Båda algoritmerna besöker alla 2 D- hörnen av en (störd) kub i dimension D , Klee –Minty-kuben (efter Victor Klee och George J. Minty ), i värsta fall . Men när den startas i ett slumpmässigt hörn besöker kors-kors-algoritmen i genomsnitt endast D ytterligare hörn. Således, för den tredimensionella kuben, besöker algoritmen alla 8 hörn i värsta fall och exakt 3 ytterligare hörn i genomsnitt.

Historia

Kors-kors-algoritmen publicerades oberoende av Tamas Terlaky och av Zhe-Min Wang; relaterade algoritmer förekom i opublicerade rapporter från andra författare.

Jämförelse med simplexalgoritmen för linjär optimering

Se även: Linjär programmering , Simplex algoritm , och Blands regel
I sin andra fas kryper simplexalgoritmen längs kanterna på polytopen tills den slutligen når en optimal vertex . Kors -kors-algoritmen tar hänsyn till baser som inte är associerade med hörn, så att vissa iterationer kan vara i det inre av den genomförbara regionen, som inre punktalgoritmer; kors-kors-algoritmen kan också ha omöjliga iterater utanför den genomförbara regionen.

I linjär programmering svänger kors och tvärs algoritmen mellan en sekvens av baser men skiljer sig från simplexalgoritmen . Simplexalgoritmen hittar först en (primal-) genomförbar bas genom att lösa ett " fas-ett- problem"; i "fas två" svänger simplexalgoritmen mellan en sekvens av grundläggande genomförbara lösningar så att den objektiva funktionen inte minskar med varje pivot, och avslutas med en optimal lösning (även att hitta en "dubbel genomförbar" lösning).

Kors-algoritmen är enklare än simplex-algoritmen, eftersom kors-kors-algoritmen bara har en fas. Dess pivoteringsregler liknar den minsta index pivoteringsregeln för Bland . Blands regel använder endast tecken på koefficienter snarare än deras ordning (reella tal) när de bestämmer valbara pivoter. Blands regel väljer en ingående variabel genom att jämföra värden för reducerade kostnader, med hjälp av den verkliga ordningen för de kvalificerade pivoterna. Till skillnad från Blands regel är kors och tvärs-algoritmen "rent kombinatorisk", och väljer en ingående variabel och en utgående variabel genom att endast beakta tecknen på koefficienter snarare än deras ordning på reella tal. Kors och tvärs-algoritmen har använts för att tillhandahålla konstruktiva bevis på grundläggande resultat i linjär algebra , såsom Lemma av Farkas .

Medan de flesta simplexvarianter är monotona i objektivet (enbart i det icke-degenererade fallet), saknar de flesta varianter av kors och tvärs-algoritmen en monoton meritfunktion, vilket kan vara en nackdel i praktiken.

Beskrivning

Kors och tvärs-algoritmen fungerar på en vanlig pivottabell (eller on-the-fly beräknade delar av en tablå, om den implementeras som den reviderade simplexmetoden). I ett allmänt steg, om tablån är primal eller dubbel omöjlig, väljer den en av de omöjliga raderna/kolumnerna som pivotraden/kolumnen med hjälp av en indexvalsregel. En viktig egenskap är att valet görs på union av de omöjliga indexen och standardversionen av algoritmen särskiljer inte kolumn- och radindex (det vill säga kolumnindexen grundläggande i raderna). Om en rad väljs så använder algoritmen indexvalsregeln för att identifiera en position till en pivot av dubbel typ, medan om en kolumn väljs så använder den indexvalsregeln för att hitta en radposition och utför en pivot av primärtyp.

Beräkningskomplexitet: Värsta och genomsnittliga fall

Den värsta beräkningskomplexiteten hos Khachiyans ellipsoidala algoritm är ett polynom. Kors och tvärs-algoritmen har exponentiell komplexitet.

Tidskomplexiteten för en algoritm räknar antalet aritmetiska operationer som är tillräckligt för att algoritmen ska lösa problemet. Till exempel Gaussisk eliminering i storleksordningen D 3 operationer , och så sägs den ha polynomisk tidskomplexitet, eftersom dess komplexitet begränsas av ett kubiskt polynom . Det finns exempel på algoritmer som inte har polynom-tidskomplexitet. Till exempel har en generalisering av Gauss eliminering som kallas Buchbergers algoritm för sin komplexitet en exponentiell funktion av problemdata ( graden av polynomen och antalet variabler för de multivariata polynomen ). Eftersom exponentialfunktioner så småningom växer mycket snabbare än polynomfunktioner, innebär en exponentiell komplexitet att en algoritm har långsam prestanda på stora problem.

Flera algoritmer för linjär programmering - Khachiyans ellipsoidala algoritm , Karmarkars projektiva algoritm och central-path-algoritmer - har polynomisk tidskomplexitet (i värsta fall och därmed i genomsnitt ). De ellipsoidala och projektiva algoritmerna publicerades före kors-kors-algoritmen.

Men liksom simplexalgoritmen i Dantzig är kors-korsalgoritmen inte en polynom-tidsalgoritm för linjär programmering. Terlakys kors och tvärs-algoritm besöker alla 2 D- hörnen i en (störd) kub i dimension D , enligt en tidning från Roos; Roos papper modifierar Klee -Minty-konstruktionen av en kub där simplexalgoritmen tar 2D- steg . Precis som simplexalgoritmen besöker kors och tvärs algoritmen alla 8 hörn av den tredimensionella kuben i värsta fall.

När den initieras i ett slumpmässigt hörn av kuben besöker kors och tvärs-algoritmen endast D ytterligare hörn, dock enligt en artikel från 1994 av Fukuda och Namiki. Trivialt tar simplexalgoritmen i genomsnitt D- steg för en kub. Liksom simplexalgoritmen besöker kors-korsalgoritmen exakt 3 ytterligare hörn av den tredimensionella kuben i genomsnitt.

Varianter

Kryss-algoritmen har utökats för att lösa mer allmänna problem än linjära programmeringsproblem.

Andra optimeringsproblem med linjära begränsningar

Det finns varianter av kors-kors-algoritmen för linjär programmering, för kvadratisk programmering och för linjär-komplementaritetsproblemet med "tillräckliga matriser"; omvänt, för linjära komplementaritetsproblem, avslutas kors-kors-algoritmen ändligt endast om matrisen är en tillräcklig matris. En tillräcklig matris är en generalisering av både en positiv-definitiv matris och av en P-matris , vars huvudsakliga minderåriga är positiva. Kryss-algoritmen har också anpassats för linjär-fraktionell programmering .

Vertex uppräkning

Kors-kors-algoritmen användes i en algoritm för att räkna upp alla hörn i en polytop, som publicerades av David Avis och Komei Fukuda 1992. Avis och Fukuda presenterade en algoritm som hittar v -hörnen för en polyeder definierad av ett icke degenererat system av n linjära olikheter i D -dimensioner (eller, dubbelt, de v -fasetter av det konvexa skrovet av n punkter i D -dimensioner, där varje fasett innehåller exakt D givna punkter) i tiden O ( nDv ) och O( nD ) rymden .

Orienterade matroider

Max -flöde min-cut-satsen säger att det maximala flödet genom ett nätverk är exakt kapaciteten för dess minsta cut. Detta teorem kan bevisas med hjälp av kors och tvärs-algoritmen för orienterade matroider.

Kors-kors-algoritmen studeras ofta med hjälp av teorin om orienterade matroider (OMs), som är en kombinatorisk abstraktion av linjär-optimeringsteori. Faktum är att Blands svängningsregel baserades på hans tidigare artiklar om orienterad matroideori. Blands regel uppvisar dock att cykla på vissa linjärprogrammeringsproblem med orienterad matroid. Den första rent kombinatoriska algoritmen för linjär programmering utarbetades av Michael J. Todd. Todds algoritm utvecklades inte bara för linjär programmering i inställningen av orienterade matroider, utan också för kvadratiska programmeringsproblem och linjär-komplementaritetsproblem . Todds algoritm är komplicerad till och med att ange, tyvärr, och dess ändliga konvergensbevis är något komplicerade.

Den kors och tvärs-algoritmen och dess bevis på ändlig avslutning kan enkelt anges och utökar lätt inställningen för orienterade matroider. Algoritmen kan ytterligare förenklas för linjära genomförbarhetsproblem , det vill säga för linjära system med icke-negativa variabler ; dessa problem kan formuleras för orienterade matroider. Kors och tvärs-algoritmen har anpassats för problem som är mer komplicerade än linjär programmering: Det finns varianter av orienterade matroider även för kvadratisk programmeringsproblem och för linjär-komplementaritetsproblemet.

Sammanfattning

Kors och tvärs-algoritmen är en enkelt angiven algoritm för linjär programmering. Det var den andra helt kombinatoriska algoritmen för linjär programmering. Den delvis kombinatoriska simplexalgoritmen för Bland cykler på vissa (icke realiserbara) orienterade matroider. Den första helt kombinatoriska algoritmen publicerades av Todd, och den är också som simplexalgoritmen genom att den bevarar genomförbarheten efter att den första genomförbara basen har genererats; dock är Todds regel komplicerad. Kors-kors-algoritmen är inte en simplexliknande algoritm, eftersom den inte behöver upprätthålla genomförbarheten. Kors-kors-algoritmen har dock inte polynomisk tidskomplexitet.

Forskare har utökat kors och tvärs-algoritmen för många optimeringsproblem, inklusive linjär-fraktionell programmering. Algoritmen på kors och tvärs kan lösa kvadratiska programmeringsproblem och linjära komplementaritetsproblem, även i inställningen av orienterade matroider. Även när den är generaliserad förblir kors och tvärs-algoritmen enkelt uttryckt.

Se även

  • Jack Edmonds (pionjär inom kombinatorisk optimering och orienterad matroideoretiker; doktorandrådgivare för Komei Fukuda)

Anteckningar

  1. ^ a b Illés, Szirmai & Terlaky (1999)
  2. ^ a b    Stancu-Minasian, I. M. (augusti 2006). "En sjätte bibliografi över fraktionerad programmering". Optimering . 55 (4): 405–428. doi : 10.1080/02331930600819613 . MR 2258634 . S2CID 62199788 .
  3. ^ a b c d e f g Fukuda & Terlaky (1997)
  4. ^ a b Roos (1990)
  5. ^ a b   Klee, Victor ; Minty, George J. (1972). "Hur bra är simplexalgoritmen?". I Shisha, Oved (red.). Inequalities III (Proceedings of the Third Symposium on Inequalities som hölls vid University of California, Los Angeles, Kalifornien, 1–9 september 1969, tillägnad minnet av Theodore S. Motzkin) . New York-London: Academic Press. s. 159–175. MR 0332165 .
  6. ^ a b c Fukuda & Terlaky (1997 , s. 385)
  7. ^ a b Fukuda & Namiki (1994 , s. 367)
  8. ^ a b Simplexalgoritmen tar i genomsnitt D- steg för en kub. Borgwardt (1987) :    Borgwardt, Karl-Heinz (1987). Simplexmetoden: En probabilistisk analys . Algoritmer och kombinatorik (Studie- och forskningstexter). Vol. 1. Berlin: Springer-Verlag. s. xii+268. ISBN 978-3-540-17096-9 . MR 0868467 .
  9. ^ Terlaky (1985) och Terlaky (1987)
  10. ^ Wang (1987)
  11. ^ a b Terlaky & Zhang (1993)
  12. ^ a b    Bland, Robert G. (maj 1977). "Nya finita pivoteringsregler för simplexmetoden". Operationsforskningens matematik . 2 (2): 103–107. doi : 10.1287/moor.2.2.103 . JSTOR 3689647 . MR 0459599 .
  13. ^ Blands regel är också relaterad till en tidigare minsta index-regel, som föreslogs av Katta G. Murty för det linjära komplementaritetsproblemet, enligt Fukuda & Namiki (1994) .
  14. ^ a b Klafszky & Terlaky (1991)
  15. ^ Mer allmänt, för simplexalgoritmen, är det förväntade antalet steg proportionellt mot D för linjärprogrammeringsproblem som dras slumpmässigt från den euklidiska enhetssfären , vilket bevisats av Borgwardt och av Smale .
  16. ^ a b Fukuda & Namiki (1994)
  17. ^ a b c d e f g    Björner, Anders; Las Vergnas, Michel ; Sturmfels, Bernd ; White, Neil; Ziegler, Günter (1999). "10 Linjär programmering". Oriented Matroids . Cambridge University Press. s. 417–479. doi : 10.1017/CBO9780511586507 . ISBN 978-0-521-77750-6 . MR 1744046 .
  18. ^ a b c den Hertog, D.; Roos, C.; Terlaky, T. (1 juli 1993). "Det linjära komplementaritetsproblemet, tillräckliga matriser och kors och tvärs-metoden" ( PDF) . Linjär algebra och dess tillämpningar . 187 : 1–14. doi : 10.1016/0024-3795(93)90124-7 .
  19. ^ a b c    Csizmadia, Zsolt; Illés, Tibor (2006). "Nya algoritmer av kors och tvärs för linjära komplementaritetsproblem med tillräckliga matriser" ( pdf) . Optimeringsmetoder och programvara . 21 (2): 247–266. doi : 10.1080/10556780500095009 . MR 2195759 . S2CID 24418835 .
  20. ^   Cottle, RW ; Pang, J.-S.; Venkateswaran, V. (mars–april 1989). "Tillräckliga matriser och det linjära komplementaritetsproblemet" . Linjär algebra och dess tillämpningar . 114–115: 231–249. doi : 10.1016/0024-3795(89)90463-1 . MR 0986877 .
  21. ^ Avis & Fukuda (1992 , s. 297)
  22. ^ V - punkten i ett enkelt arrangemang av n hyperplan i D- dimensioner kan hittas i O( n 2 Dv ) tid och O( nD ) rymdkomplexitet .
  23. ^ Teorin om orienterade matroider initierades av R. Tyrrell Rockafellar . ( Rockafellar 1969 ):

      Rockafellar, RT (1969). "De elementära vektorerna för ett delrum av (1967)" (PDF) . I RC Bose och TA Dowling (red.). Kombinatorisk matematik och dess tillämpningar . University of North Carolina Monograph Series in Probability and Statistics. Chapel Hill, North Carolina: University of North Carolina Press. s. 104–127. MR 0278972 . PDF omtryck .

    Rockafellar var influerad av de tidigare studierna av Albert W. Tucker och George J. Minty . Tucker och Minty hade studerat teckenmönster för matriserna som uppstår genom svängningsoperationerna i Dantzigs simplexalgoritm.

  24. ^ a b   Todd, Michael J. (1985). "Linjär och kvadratisk programmering i orienterade matroider" . Journal of Combinatorial Theory . Serie B. 39 (2): 105–133. doi : 10.1016/0095-8956(85)90042-5 . MR 0811116 .

externa länkar

Hämtad från " https://en.wikipedia.org/w/index.php?title=Criss-cross_algorithm&oldid=1094666421 "