Křížový algoritmus - Criss-cross algorithm

Křížový algoritmus v nejhorším případě navštíví všech 8 rohů krychle Klee – Minty . V průměru navštíví 3 další rohy. Klee-Mintyova kostka je narušení zde zobrazené krychle.

V matematické optimalizaci je křížovým algoritmem některý z rodiny algoritmů pro lineární programování . Varianty křížového algoritmu také řeší obecnější problémy s omezeními lineární nerovnosti a nelineárními objektivními funkcemi ; existují křížové algoritmy pro problémy lineárního zlomkového programování, problémy kvadratického programování a problémy lineární komplementarity .

Jako simplex algoritmu z George B. Dantzig , se křižovat algoritmus není polynomiální algoritmus pro lineární programování. Oba algoritmy navštívit všechna 2 ^D rohy (narušena) krychle v rozměr D se Klee-Minty cube (po Victor Klee a George J. Minty ), v nejhorším případě . Když je však spuštěn v náhodném rohu, křížový algoritmus v průměru navštíví pouze D dalších rohů. U trojrozměrné krychle tedy algoritmus v nejhorším případě navštíví všech 8 rohů a v průměru přesně 3 další rohy.

Dějiny

Algoritmus křížení publikovali nezávisle Tamas Terlaky a Zhe-Min Wang; související algoritmy se objevily v nepublikovaných zprávách jiných autorů.

Srovnání s simplexním algoritmem pro lineární optimalizaci

Ve své druhé fázi se simplexní algoritmus plazí po okrajích mnohostěnu, až nakonec dosáhne optimálního vrcholu . Criss-cross algoritmus má za bází, které nejsou spojeny s vrcholy, takže některé iterace může být v interiéru proveditelné oblasti, jako je vnitřní čárkou algoritmy; křížový algoritmus může mít také neproveditelné iterace mimo proveditelnou oblast.

Lineárního programování, se křižovat algoritmus otáčí mezi sekvencí bází, ale liší se od simplex algoritmu z George Dantzig . Algoritmus simplexu nejprve najde (prvotní) proveditelný základ vyřešením „problému první fáze “; ve „fázi dva“ se simplexní algoritmus otáčí mezi řadou základních proveditelných řešení, takže objektivní funkce neklesá s každým otočením a končí optimálním řešením (také konečně najde „duální proveditelné“ řešení).

Křížový algoritmus je jednodušší než simplexní algoritmus, protože křížový algoritmus má pouze jednu fázi. Jeho pravidla otáčení jsou podobná pravidlu otáčení s nejnižším indexem Blanda . Blandovo pravidlo používá při rozhodování o vhodných otočných bodech pouze známky koeficientů, nikoli jejich pořadí (v reálném počtu) . Blandovo pravidlo vybírá vstupující proměnné porovnáním hodnot snížených nákladů pomocí uspořádání způsobilých otočných bodů v reálném čísle. Na rozdíl od Blandova pravidla je křížový algoritmus „čistě kombinatorický“, přičemž se vybírá vstupní proměnná a opouštějící proměnná tím, že se berou v úvahu pouze znaky koeficientů, nikoli jejich pořadí v reálném čísle. Křížový algoritmus byl použit k poskytnutí konstruktivních důkazů základních výsledků v lineární algebře , jako je Lemma Farkase .

Zatímco většina simplexních variant je v objektivu monotónních (striktně v nedegenerovaném případě), většině variant křížového algoritmu chybí monotónní záslužná funkce, což může být v praxi nevýhodou.

Popis

Křížový algoritmus funguje na standardním otočném tablo (nebo za běhu vypočítané části tabla, pokud jsou implementovány jako revidovaná simplexní metoda). V obecném kroku, je-li tablo primitivní nebo dvojí nerealizovatelné, vybere jeden z neproveditelných řádků / sloupců jako otočný řádek / sloupec pomocí pravidla výběru indexu. Důležitou vlastností je, že výběr je prováděn na sjednocení neproveditelných indexů a standardní verze algoritmu nerozlišuje indexy sloupců a řádků (tj. Indexy sloupců základní v řádcích). Pokud je vybrán řádek, pak algoritmus použije pravidlo pro výběr indexu k identifikaci polohy na pivot dvojitého typu, zatímco pokud je vybrán sloupec, použije pravidlo pro výběr indexu k vyhledání polohy řádku a provede pivot primárního typu.

Výpočetní složitost: Nejhorší a průměrné případy

Nejhorší výpočetní složitost Khachiyanova elipsoidního algoritmu je polynom. Criss-cross algoritmus má exponenciální složitost.

Časová složitost z algoritmu počítá počet aritmetických operací dostačující pro algoritmus pro vyřešení problému. Například Gaussova eliminace vyžaduje v pořadí operací D ³ , a tak se říká, že má polynomiální časovou složitost, protože její složitost je omezena kubickým polynomem . Existují příklady algoritmů, které nemají polynomiálně-časovou složitost. Například zobecnění Gaussovy eliminace zvané Buchbergerův algoritmus má pro svou složitost exponenciální funkci problémových dat ( stupeň polynomů a počet proměnných vícerozměrných polynomů ). Protože exponenciální funkce nakonec rostou mnohem rychleji než polynomiální funkce, exponenciální složitost znamená, že algoritmus má při velkých problémech pomalý výkon.

Některé algoritmy pro lineární programming- Khachiyan ‚s elipsoidní algoritmus , Karmarkar ‘ s projektivní algoritmu a ústřední cesta algoritmy -mít polynomiální časovou složitost (v nejhorším případě , a tak v průměru ). Elipsoidní a projektivní algoritmy byly publikovány před křížovým algoritmem.

Stejně jako Dantzigův simplexní algoritmus však křížový algoritmus není pro lineární programování algoritmem polynomiálního času. Terlaky je křížem krážem algoritmus návštěv 2 ^D rozích (narušena) krychle rozměr D , podle papírem Roos; Roosův článek upravuje Klee –Minty konstrukci krychle, na které simplexní algoritmus trvá 2 ^D kroky. Stejně jako simplexní algoritmus, i křížový algoritmus v nejhorším případě navštíví všech 8 rohů trojrozměrné krychle.

Když je inicializován v náhodném rohu krychle, křížový algoritmus navštíví pouze D dalších rohů, podle článku Fukudy a Namiki z roku 1994 . Triviálně jednostranný algoritmus bere průměrné D kroky pro krychli. Stejně jako simplexní algoritmus, i křížový algoritmus navštěvuje v průměru přesně 3 další rohy trojrozměrné krychle.

Varianty

Křížový algoritmus byl rozšířen tak, aby řešil obecnější problémy než problémy lineárního programování.

Další optimalizační problémy s lineárními omezeními

Existují varianty křížového algoritmu pro lineární programování, pro kvadratické programování a pro problém lineární komplementarity s „dostatečnými maticemi“; naopak, u problémů lineární komplementarity se algoritmus křížového přechodu definitivně ukončí, pouze pokud je matice dostatečnou maticí. Dostatečné matice je zobecněním oba z pozitivně definitní matice a z P-matice , jehož hlavní mladiství jsou každý pozitivní. Křížový algoritmus byl upraven také pro lineární frakční programování .

Výčet vrcholů

Se křižovat algoritmus byl použit v algoritmu pro výčet všech vrcholů mnohostěnu , který byl zveřejněn podle Davida Avis a Komei Fukuda v roce 1992. Avis a Fukuda prezentován algoritmus, který nalezne v vrcholů mnohostěnu definovaného nedegenerovaného systémem z n lineárních nerovností v D rozměrech (nebo, duální, že v aspekty tohoto konvexního obalu z n bodů v D rozměrů, kde každý aspekt obsahuje přesně D uvedené body) v čase o ( NDV ) a o ( nD ) prostoru .

Orientované matroidy

Tyto Fordova-Fulkersonova věta uvádí, že tok maximum prostřednictvím sítě je přesně kapacity svého minimálního řezu. Tuto větu lze prokázat pomocí křížového algoritmu pro orientované matroidy.

Křížový algoritmus je často studován pomocí teorie orientovaných matroidů (OM), což je kombinatorická abstrakce teorie lineární optimalizace. Ve skutečnosti bylo Blandovo otočné pravidlo založeno na jeho předchozích dokumentech o teorii orientovaných matroidů. Blandovo pravidlo však vykazuje cyklování na některých problémech lineárního programování s orientovaným matroidem. První čistě kombinatorický algoritmus pro lineární programování vytvořil Michael J. Todd . Toddův algoritmus byl vyvinut nejen pro lineární programování v prostředí orientovaných matroidů, ale také pro problémy kvadratického programování a lineární komplementarity . Toddův algoritmus je bohužel komplikovaný i pro vyjádření a jeho důkazy o konečné konvergenci jsou poněkud komplikované.

Křížový algoritmus a jeho důkaz konečného ukončení lze jednoduše určit a snadno rozšířit nastavení orientovaných matroidů. Algoritmus lze dále zjednodušit pro problémy lineární proveditelnosti , tj. Pro lineární systémy s nezápornými proměnnými ; tyto problémy lze formulovat pro orientované matroidy. Algoritmus křížení byl upraven pro problémy, které jsou složitější než lineární programování: Existují varianty orientovaných matroidů také pro problém kvadratického programování a pro problém lineární komplementarity.

souhrn

Křížový algoritmus je jednoduše uvedený algoritmus pro lineární programování. Byl to druhý plně kombinatorický algoritmus pro lineární programování. Částečně kombinatorický simplexní algoritmus Blandových cyklů na některých (nerealizovatelných) orientovaných matroidech. První plně kombinatorický algoritmus publikoval Todd a je také jako simplexní algoritmus v tom, že zachovává proveditelnost po vygenerování prvního proveditelného základu; Toddova vláda je však komplikovaná. Křížový algoritmus není simplexní algoritmus, protože nemusí udržovat proveditelnost. Algoritmus křížového přechodu však nemá polynomiální časovou složitost.

Vědci rozšířili křížový algoritmus o mnoho optimalizačních problémů, včetně lineárního zlomkového programování. Křížový algoritmus může vyřešit problémy s kvadratickým programováním a problémy s lineární komplementaritou, a to i v nastavení orientovaných matroidů. I když je zobecněn, algoritmus křížového přechodu zůstává jednoduše uveden.

Viz také

Jack Edmonds (průkopník kombinatorické optimalizace a teoretik orientovaného matroidu; doktorský poradce Komei Fukuda)

Poznámky

^ ^a ^b Illés, Szirmai a Terlaky (1999)
^ ^a ^b Stancu-Minasian, I. M. (srpen 2006). "Šestá bibliografie částečného programování". Optimalizace . 55 (4): 405–428. doi : 10.1080 / 02331930600819613 . MR 2258634 . S2CID 62199788 .
^ ^a ^b ^c ^d ^e ^f ^g Fukuda & Terlaky (1997)
^ ^a ^b Roos (1990)
^ ^a ^b Klee, Victor ; Minty, George J. (1972). "Jak dobrý je simplexní algoritmus?". V Shisha, Oved (ed.). Nerovnosti III (Sborník ze třetího sympozia o nerovnostech konaného na Kalifornské univerzitě v Los Angeles v Kalifornii od 1. do 9. září 1969 věnovaný památce Theodora S. Motzkina) . New York-Londýn: Academic Press. str. 159–175. MR 0332165 .
^ ^a ^b ^c Fukuda & Terlaky (1997 , s. 385)
^ ^a ^b Fukuda & Namiki (1994 , s. 367)
^ ^a ^b simplexní algoritmus bere průměrné D kroky pro krychli. Borgwardt (1987) : Borgwardt, Karl-Heinz (1987). Metoda simplex: Pravděpodobnostní analýza . Algoritmy a kombinatorika (studijní a výzkumné texty). 1 . Berlín: Springer-Verlag. str. xii + 268. ISBN 978-3-540-17096-9. MR 0868467 .
^ Terlaky (1985) a Terlaky (1987)
^ Wang (1987)
^ ^a ^b Terlaky & Zhang (1993)
^ ^a ^b Bland, Robert G. (květen 1977). Msgstr "Nová pravidla konečného otočení pro simplexní metodu". Matematika operačního výzkumu . 2 (2): 103–107. doi : 10,1287 / bř . 2.2.23 . JSTOR 3689647 . MR 0459599 .
^ Blandovo pravidlo souvisí také s dřívějším pravidlem nejnižšího indexu, které navrhla Katta G. Murty pro problém lineární komplementarity , podle Fukuda & Namiki (1994) .
^ ^a ^b Klafszky & Terlaky (1991)
^ Obecněji řečeno, pro simplexní algoritmus je očekávaný počet kroků úměrný D pro problémy lineárního programování, které jsou náhodně čerpány z sféry euklidovských jednotek , jak dokazují Borgwardt a Smale .
^ ^a ^b Fukuda a Namiki (1994)
^ ^a ^b ^c ^d ^e ^f ^g Björner, Anders; Las Vergnas, Michel ; Sturmfels, Bernd ; White, Neil; Ziegler, Günter (1999). "10 Lineární programování". Orientované matroidy . Cambridge University Press. 417–479. doi : 10.1017 / CBO9780511586507 . ISBN 978-0-521-77750-6. MR 1744046 .
^ ^a ^b ^c den Hertog, D .; Roos, C .; Terlaky, T. (1. července 1993). „Problém lineární komplementarity, dostatek matic a křížová metoda“ (PDF) . Lineární algebra a její aplikace . 187 : 1–14. doi : 10.1016 / 0024-3795 (93) 90124-7 .
^ ^a ^b ^c Csizmadia, Zsolt; Illés, Tibor (2006). „Nové algoritmy křížového typu pro problémy lineární komplementarity s dostatečnými maticemi“ (pdf) . Optimalizační metody a software . 21 (2): 247–266. doi : 10.1080 / 10556780500095009 . MR 2195759 . S2CID 24418835 .
^ Cottle, RW ; Pang, J.-S .; Venkateswaran, V. (březen – duben 1989). "Dostatečné matice a problém lineární komplementarity" . Lineární algebra a její aplikace . 114–115: 231–249. doi : 10.1016 / 0024-3795 (89) 90463-1 . MR 0986877 .
^ Avis a Fukuda (1992 , s. 297)
^ V V vrcholy v jednoduché uspořádání n nadrovinami v D rozměrech lze nalézt v O ( n ²Dv ) čas a O ( nD ) složitost prostor .
^ Teorii orientovaných matroidů inicioval R. Tyrrell Rockafellar . ( Rockafellar 1969 ):
Rockafellar, RT (1969). "Elementární vektory podprostoru (1967)" ${\ displaystyle R ^ {N}}$ (PDF) . V RC Bose a TA Dowling (ed.). Kombinatorická matematika a její aplikace . The University of North Carolina Monograph Series in Probability and Statistics. Chapel Hill, Severní Karolína: University of North Carolina Press. str. 104–127. MR 0278972 . Dotisk PDF .

Rockafellar byl ovlivněn dřívějšími studiemi Alberta W. Tuckera a George J. Mintyho . Tucker a Minty studovali znaménkové vzorce matic vznikající otočnými operacemi Dantzigova simplexního algoritmu.
^ ^a ^b Todd, Michael J. (1985). "Lineární a kvadratické programování v orientovaných matroidech" . Journal of Combinatorial Theory . Série B. 39 (2): 105–133. doi : 10.1016 / 0095-8956 (85) 90042-5 . MR 0811116 .

Reference

Avis, David ; Fukuda, Komei (prosinec 1992). "Otočný algoritmus pro konvexní trupy a výčet vrcholů uspořádání a mnohostěnů" . Diskrétní a výpočetní geometrie . 8 (ACM Symposium on Computational Geometry (North Conway, NH, 1991) číslo 1): 295–313. doi : 10,1007 / BF02293050 . MR 1174359 .
Csizmadia, Zsolt; Illés, Tibor (2006). „Nové algoritmy křížového typu pro problémy lineární komplementarity s dostatečnými maticemi“ (pdf) . Optimalizační metody a software . 21 (2): 247–266. doi : 10.1080 / 10556780500095009 . MR 2195759 . S2CID 24418835 .
Fukuda, Komei ; Namiki, Makoto (březen 1994). "O extremálním chování Murtyho metody nejmenšího indexu". Matematické programování . 64 (1): 365–370. doi : 10,1007 / BF01582581 . MR 1286455 . S2CID 21476636 .
Fukuda, Komei ; Terlaky, Tamás (1997). Liebling, Thomas M .; de Werra, Dominique (eds.). "Křížové metody: nový pohled na pivotní algoritmy". Matematické programování, Series B . 79 (Příspěvky ze 16. mezinárodního symposia o matematickém programování, které se konalo v Lausanne, 1997, číslo 1–3): 369–395. CiteSeerX 10.1.1.36.9373 . doi : 10,1007 / BF02614325 . MR 1464775 . S2CID 2794181 . Postprintový předtisk .
den Hertog, D .; Roos, C .; Terlaky, T. (1. července 1993). „Problém lineární komplementarity, dostatek matic a křížová metoda“ (PDF) . Lineární algebra a její aplikace . 187 : 1–14. doi : 10.1016 / 0024-3795 (93) 90124-7 . MR 1221693 .
Illés, Tibor; Szirmai, Ákos; Terlaky, Tamás (1999). "Metoda konečného křížení pro hyperbolické programování" . Evropský žurnál operačního výzkumu . 114 (1): 198–214. doi : 10,1016 / S0377-2217 (98) 00049-6 . Zbl 0953,90055 . Postprintový předtisk .
Klafszky, Emil; Terlaky, Tamás (červen 1991). "Role otáčení při dokazování některých základních teorémů lineární algebry" . Lineární algebra a její aplikace . 151 : 97–118. doi : 10.1016 / 0024-3795 (91) 90356-2 . MR 1102142 .
Roos, C. (1990). "Exponenciální příklad Terlakyho otočného pravidla pro metodu criss-cross simplex". Matematické programování . Série A. 46 (1): 79–84. doi : 10,1007 / BF01585729 . MR 1045573 . S2CID 33463483 .
Terlaky, T. (1985). "Konvergentní křížová metoda". Optimalizace: Žurnál matematického programování a operačního výzkumu . 16 (5): 683–690. doi : 10.1080 / 02331938508843067 . ISSN 0233-1934 . MR 0798939 .
Terlaky, Tamás (1987). "Metoda konečného křížení pro orientované matroidy" . Journal of Combinatorial Theory . Řada B. 42 (3): 319–327. doi : 10.1016 / 0095-8956 (87) 90049-9 . ISSN 0095-8956 . MR 0888684 .
Terlaky, Tamás ; Zhang, Shu Zhong (1993) [1991]. "Pivot pravidla pro lineární programování: Průzkum o nedávném teoretickém vývoji". Annals of Operations Research . 46–47 (Degenerace v optimalizačních problémech, číslo 1): 203–233. CiteSeerX 10.1.1.36.7658 . doi : 10,1007 / BF02096264 . ISSN 0254-5330 . MR 1260019 . S2CID 6058077 .
Wang, Zhe Min (1987). "Bezplatný algoritmus konečné konformní eliminace nad orientovaným programováním matroidů". Čínské Annals of Mathematics (Shuxue Niankan B Ji) . Série B. 8 (1): 120–125. ISSN 0252-9599 . MR 0886756 .

externí odkazy

[LF99Hyperbolic-1] Illés, Szirmai a Terlaky (1999)

[Bibl-2] Stancu-Minasian, I. M. (srpen 2006). "Šestá bibliografie částečného programování". Optimalizace . 55 (4): 405–428. doi : 10.1080 / 02331930600819613 . MR 2258634 . S2CID 62199788 .

[FukudaTerlaky-3] ^ ^a ^b ^c ^d ^e ^f ^g Fukuda & Terlaky (1997)

[Roos-4] Roos (1990)

[KleeMinty-5] Klee, Victor ; Minty, George J. (1972). "Jak dobrý je simplexní algoritmus?". V Shisha, Oved (ed.). Nerovnosti III (Sborník ze třetího sympozia o nerovnostech konaného na Kalifornské univerzitě v Los Angeles v Kalifornii od 1. do 9. září 1969 věnovaný památce Theodora S. Motzkina) . New York-Londýn: Academic Press. str. 159–175. MR 0332165 .

[FTNamiki-6] Fukuda & Terlaky (1997 , s. 385)

[FukudaNamiki-7] Fukuda & Namiki (1994 , s. 367)

[Borgwardt-8] simplexní algoritmus bere průměrné D kroky pro krychli. Borgwardt (1987) : Borgwardt, Karl-Heinz (1987). Metoda simplex: Pravděpodobnostní analýza . Algoritmy a kombinatorika (studijní a výzkumné texty). 1 . Berlín: Springer-Verlag. str. xii + 268. ISBN 978-3-540-17096-9. MR 0868467 .

[9] Terlaky (1985) a Terlaky (1987)

[Wang-10] Wang (1987)

[TerlakyZhang-11] Terlaky & Zhang (1993)

[Bland-12] Bland, Robert G. (květen 1977). Msgstr "Nová pravidla konečného otočení pro simplexní metodu". Matematika operačního výzkumu . 2 (2): 103–107. doi : 10,1287 / bř . 2.2.23 . JSTOR 3689647 . MR 0459599 .

[13] Blandovo pravidlo souvisí také s dřívějším pravidlem nejnižšího indexu, které navrhla Katta G. Murty pro problém lineární komplementarity , podle Fukuda & Namiki (1994) .

[KT91-14] Klafszky & Terlaky (1991)

[15] Obecněji řečeno, pro simplexní algoritmus je očekávaný počet kroků úměrný D pro problémy lineárního programování, které jsou náhodně čerpány z sféry euklidovských jednotek , jak dokazují Borgwardt a Smale .

[FukudaNamikiLCP-16] Fukuda a Namiki (1994)

[OMBook-17] ^ ^a ^b ^c ^d ^e ^f ^g Björner, Anders; Las Vergnas, Michel ; Sturmfels, Bernd ; White, Neil; Ziegler, Günter (1999). "10 Lineární programování". Orientované matroidy . Cambridge University Press. 417–479. doi : 10.1017 / CBO9780511586507 . ISBN 978-0-521-77750-6. MR 1744046 .

[HRT-18] Hertog, D .; Roos, C .; Terlaky, T. (1. července 1993). „Problém lineární komplementarity, dostatek matic a křížová metoda“ (PDF) . Lineární algebra a její aplikace . 187 : 1–14. doi : 10.1016 / 0024-3795 (93) 90124-7 .

[CIsufficient-19] Csizmadia, Zsolt; Illés, Tibor (2006). „Nové algoritmy křížového typu pro problémy lineární komplementarity s dostatečnými maticemi“ (pdf) . Optimalizační metody a software . 21 (2): 247–266. doi : 10.1080 / 10556780500095009 . MR 2195759 . S2CID 24418835 .

[20] Cottle, RW ; Pang, J.-S .; Venkateswaran, V. (březen – duben 1989). "Dostatečné matice a problém lineární komplementarity" . Lineární algebra a její aplikace . 114–115: 231–249. doi : 10.1016 / 0024-3795 (89) 90463-1 . MR 0986877 .

[21] Avis a Fukuda (1992 , s. 297)

[22] V V vrcholy v jednoduché uspořádání n nadrovinami v D rozměrech lze nalézt v O ( n ²Dv ) čas a O ( nD ) složitost prostor .

[23] Teorii orientovaných matroidů inicioval R. Tyrrell Rockafellar . ( Rockafellar 1969 ):
Rockafellar, RT (1969). "Elementární vektory podprostoru (1967)" ${\ displaystyle R ^ {N}}$ (PDF) . V RC Bose a TA Dowling (ed.). Kombinatorická matematika a její aplikace . The University of North Carolina Monograph Series in Probability and Statistics. Chapel Hill, Severní Karolína: University of North Carolina Press. str. 104–127. MR 0278972 . Dotisk PDF .

Rockafellar byl ovlivněn dřívějšími studiemi Alberta W. Tuckera a George J. Mintyho . Tucker a Minty studovali znaménkové vzorce matic vznikající otočnými operacemi Dantzigova simplexního algoritmu.

[Todd-24] Todd, Michael J. (1985). "Lineární a kvadratické programování v orientovaných matroidech" . Journal of Combinatorial Theory . Série B. 39 (2): 105–133. doi : 10.1016 / 0095-8956 (85) 90042-5 . MR 0811116 .

Languages

In other projects