Křížový algoritmus - Criss-cross algorithm
v matematická optimalizace, křížový algoritmus je někdo z rodiny algoritmy pro lineární programování. Varianty křížového algoritmu také řeší obecnější problémy s omezení lineární nerovnosti a nelineární objektivní funkce; existují křížové algoritmy pro lineární-zlomkové programování problémy,[1][2] kvadratické programování problémy a problémy lineární komplementarity.[3]
Jako simplexní algoritmus z George B. Dantzig, křížový algoritmus není a algoritmus polynomiálního času pro lineární programování. Oba algoritmy navštíví všechny 2D rohy (rozrušený) krychle v rozměruD, Klee – Minty kostka (po Victor Klee a George J. Minty ), v nejhorší případ.[4][5] Když je však spuštěn v náhodném rohu, křížový algoritmus v průměru pouze návštěvyD další rohy.[6][7][8] 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í byl publikován nezávisle uživatelem Tamas Terlaky[9] a Zhe-Min Wang;[10] související algoritmy se objevily v nepublikovaných zprávách jiných autorů.[3]
Srovnání s simplexním algoritmem pro lineární optimalizaci
V lineárním programování se křížový algoritmus otáčí mezi řadou bází, ale liší se od simplexní algoritmus z George Dantzig. Algoritmus simplexu nejprve najde (prvotní) proveditelný základ řešením „fáze jedna problém "; ve" fázi dvě "se simplexní algoritmus otáčí mezi posloupností základních proveditelný řešení tak, aby objektivní funkce neklesala s každým otočným čepem, končící optimálním řešením (také konečně nalezení „duálního“ řešení).[3][11]
Křížový algoritmus je jednodušší než simplexní algoritmus, protože křížový algoritmus má pouze jednu fázi. Jeho pravidla otáčení jsou podobná pravidlům Blandovo pravidlo otočení s nejmenším indexem.[12] Blandovo pravidlo používá pouze znamení spíše než jejich koeficientů (reálné číslo) objednávka při rozhodování o vhodných otočných čepech. 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.[12][13] 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.[3][11] Křížový křížový algoritmus byl použit k poskytnutí konstruktivních důkazů základních výsledků v nemovitý lineární algebra, tak jako Farkasovo lema.[14]
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
Tato sekce potřebuje expanzi. Můžete pomoci přidávat k tomu. (Dubna 2011) |
Algoritmus křížení funguje na standardním pivotním tablo (nebo za běhu vypočítané části tabla, pokud jsou implementovány jako revidovaná simplexní metoda). V obecném kroku, pokud je tablo primitivní nebo dvojité, je možné vybrat jeden z neproveditelných řádků / sloupců jako kontingenční řádek / sloupec pomocí pravidla výběru indexu. Důležitou vlastností je, že výběr se provádí 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í pozice řádku a provede pivot primárního typu.
Výpočetní složitost: Nejhorší a průměrné případy
The časová složitost z algoritmus počítá počet aritmetické operace dostačující pro algoritmus k vyřešení problému. Například, Gaussova eliminace vyžaduje na řád D3 operace, a tak se říká, že má polynomiální časovou složitost, protože její složitost je ohraničena a kubický polynom. Existují příklady algoritmů, které nemají polynomiálně-časovou složitost. Například se nazývá generalizace Gaussovské eliminace 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é polynomy ). 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ěkolik algoritmů pro lineární programování—Khachiyan je elipsoidní algoritmus, Karmarkar je projektivní algoritmus, a algoritmy centrální cesty —Mají polynomiální časovou složitost (v nejhorší případ a tudíž v průměru ). Elipsoidní a projektivní algoritmy byly publikovány před křížovým algoritmem.
Stejně jako Dantzigův simplexní algoritmus je však křížový algoritmus ne algoritmus polynomiálního času pro lineární programování. Terlakyho křížový algoritmus navštěvuje všechny 2D rohy (narušené) krychle v rozměruD, podle článku Roos; Roosův článek upravuje Klee –Minty konstrukce a krychle na kterém simplexní algoritmus trvá 2D kroky.[3][4][5] 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í pouzeD další rohy, nicméně, podle 1994 papíru Fukuda a Namiki.[6][7] Triviálně jednostranný algoritmus trvá v průměruD kroky pro krychli.[8][15] 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ým počtem matic“;[3][6][16][17][18][19] naopak, u problémů lineární komplementarity se algoritmus křížového přechodu definitivně ukončí, pouze pokud je matice dostatečnou maticí.[18][19] A dostatečná matice je zobecnění a pozitivně definitivní matice a P-matice, jehož hlavní nezletilí jsou každý pozitivní.[18][19][20] Křížový algoritmus byl upraven také pro lineární-zlomkové programování.[1][2]
Výčet vrcholů
Algoritmus křížení byl použit v algoritmu pro výčet všech vrcholů mnohostěnu, kterou vydalo David Avis a Komei Fukuda v roce 1992.[21] Avis a Fukuda představili algoritmus, který najdeproti vrcholy a mnohostěn definované nedegenerovaným systémemn lineární nerovnosti vD rozměry (nebo, duálně,proti fazety z konvexní obal zn body vD rozměry, kde každá fazeta obsahuje přesněD dané body) v časeÓ (nDv) a O (nD) prostor.[22]
Orientované matroidy
Křížový algoritmus je často studován pomocí teorie orientované matroidy (OMs), což je a kombinační abstrakce teorie lineární optimalizace.[17][23] 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.[17] První čistě kombinatorický algoritmus pro lineární programování byl vytvořen pomocí Michael J. Todd.[17][24] Toddův algoritmus byl vyvinut nejen pro lineární programování v nastavení orientovaných matroidů, ale také pro problémy s kvadratickým programováním a problémy lineární komplementarity.[17][24] Toddův algoritmus je bohužel dokonce komplikovaný, a jeho důkazy o konečné konvergenci jsou poněkud komplikované.[17]
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 lineární problémy proveditelnosti, to je pro lineární systémy s nezáporné proměnné; tyto problémy lze formulovat pro orientované matroidy.[14] 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.[3][16][17]
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. Křížový algoritmus 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. PAN 2258634.
- ^ 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 (Proceedings of the Third Symposium on Nerovnosti konané na University of California, Los Angeles, Kalifornie, 1. - 9. září 1969, věnovaná památce Theodora S. Motzkina). New York-Londýn: Academic Press. str. 159–175. PAN 0332165.CS1 maint: ref = harv (odkaz)
- ^ A b C Fukuda & Terlaky (1997, str. 385)
- ^ A b Fukuda a Namiki (1994, str. 367)
- ^ A b Simplexový algoritmus trvá 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. PAN 0868467.CS1 maint: ref = harv (odkaz)
- ^ 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. PAN 0459599.CS1 maint: ref = harv (odkaz)
- ^ Blandovo pravidlo souvisí také s dřívějším pravidlem nejnižšího indexu, které navrhla Katta G. Murtyová pro problém lineární komplementarity, podle Fukuda a 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 Euklidovský jednotková koule, 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. PAN 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é křížové algoritmy 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. PAN 2195759.
- ^ Cottle, R. W.; 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. PAN 0986877.
- ^ Avis & Fukuda (1992, str. 297)
- ^ Theproti vrcholy v jednoduchém uspořádánín hyperplanes vD rozměry najdete v O (n2Dv) čas a O (nD) složitost prostoru.
- ^ Teorie orientované matroidy byl zahájen uživatelem R. Tyrrell Rockafellar. (Rockafellar 1969 ):
Rockafellar, R. T. (1969). "Elementární vektory podprostoru o (1967)" (PDF). v R. C. Bose a T. A. 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. PAN 0278972. Dotisk PDF.
Rockafellar byl ovlivněn dřívějšími studiemi o Albert W. Tucker a George J. Minty. 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. Řada B. 39 (2): 105–133. doi:10.1016/0095-8956(85)90042-5. PAN 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. PAN 1174359.
- Csizmadia, Zsolt; Illés, Tibor (2006). „Nové křížové algoritmy 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. PAN 2195759.
- 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. PAN 1286455.
- Fukuda, Komei; Terlaky, Tamás (1997). Liebling, Thomas M .; de Werra, Dominique (eds.). "Křížové metody: nový pohled na pivotní algoritmy". Matematické programování, řada 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. PAN 1464775. 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. PAN 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 vět lineární algebry“. Lineární algebra a její aplikace. 151: 97–118. doi:10.1016/0024-3795(91)90356-2. PAN 1102142. Archivovány od originál (postscript) dne 27. září 2011. Citováno 4. srpna 2011.
- Roos, C. (1990). "Exponenciální příklad Terlakyho otočného pravidla pro metodu criss-cross simplex". Matematické programování. Řada A. 46 (1): 79–84. doi:10.1007 / BF01585729. PAN 1045573.
- 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. PAN 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. PAN 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. PAN 1260019.
- Wang, Zhe Min (1987). "Bezplatný algoritmus konečné konformní eliminace nad orientovaným programováním matroidů". Chinese Annals of Mathematics (Shuxue Niankan B Ji). Řada B. 8 (1): 120–125. ISSN 0252-9599. PAN 0886756.