Klee – Minty kostka - Klee–Minty cube - Wikipedia

Klee Minty kostka pro jednoduchou metodu stínového vrcholu.

The Klee – Minty kostka nebo Klee – mátový polytop (pojmenoval podle Victor Klee a George J. Minty [de ]) je jednotka hyperkrychle proměnné dimenze jejichž rohy byly narušeny. Klee a Minty to prokázali George Dantzig je simplexní algoritmus má špatný výkon v nejhorším případě, když je inicializován v jednom rohu jejich „rozmačkané kostky“. Na trojrozměrné verzi je simplexní algoritmus a křížový algoritmus v nejhorším případě navštivte všech 8 rohů.

Zejména mnoho optimalizací algoritmy pro lineární optimalizace vykazují špatný výkon při aplikaci na kostku Klee – Minty. V roce 1973 Klee a Minty ukázali, že Dantzig simplexní algoritmus nebyl algoritmus polynomiálního času při aplikaci na jejich krychli.^[1] Později úpravy kostky Klee – Minty ukázaly špatné chování ostatních základ -výměna otočné algoritmy a také pro algoritmy vnitřních bodů.^[2]

Popis krychle

Klee-Mintyova kostka byla původně specifikována parametrizovaným systémem lineárních nerovností s dimenzí jako parametrem. Když je dimenze dvě, je „krychlí“ zmáčknutý čtverec. Když je dimenze tři, je „kostka“ rozmačkaná kostka. Kromě algebraických popisů se objevily ilustrace „krychle“.^[3][4]

Polytop Klee – Minty je dán vztahem^[5]

${ displaystyle { begin {aligned} x_ {1} leq 5 4x_ {1} + x_ {2} leq 25 8x_ {1} + 4x_ {2} + x_ {3} leq 125 vdots 2 ^ {D} x_ {1} + 2 ^ {D-1} x_ {2} + dots + 4x_ {D-1} + x_ {D} leq 5 ^ {D} x_ {1} geq 0, , , tečky, , , x_ {D} geq 0. end {zarovnáno}}}$

To má D proměnné, D jiná omezení než D omezení negativity a 2^D vrcholy, stejně jako D-dimenzionální hyperkrychle dělá. Pokud je objektivní funkce, která má být maximalizována, je

${ displaystyle 2 ^ {D-1} x_ {1} + 2 ^ {D-2} x_ {2} + tečky + 2x_ {D-1} + x_ {D},}$

a pokud je počátečním vrcholem pro simplexní algoritmus počátek, pak algoritmus formulovaný Dantzigem navštíví všechny 2^D vrcholy, nakonec dosáhne optimálního vrcholu ${ displaystyle (0,0, tečky, 5 ^ {D}).}$

Výpočetní složitost

Klee – Mintyova kostka byla použita k analýze výkonu mnoha algoritmů, a to jak v nejhorším případě, tak v průměru. 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 D³ 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.

Nejhorší případ

Ilustrace trojrozměrného polytop což je proveditelná oblast pro problém lineárního programování. Simplex algoritmus prochází hranami mezi vrcholy dokud nedosáhne optimálního vrcholu. V uvedeném případě má simplexní algoritmus pět kroků. Algoritmus simplexu však navštěvuje každý vrchol v nejhorším případě problému, jehož proveditelnou oblastí je Klee-Mintyova kostka, takže počet kroků exponenciálně stoupá s dimenzí problému.

V matematické optimalizaci je Klee-Mintyova kostka příkladem, který ukazuje nejhorší případ výpočetní složitost z mnoha algoritmy z lineární optimalizace. Je to zdeformované krychle s přesně 2^D rohy dovnitř dimenze  D. Klee a Minty to ukázali Dantzig simplexní algoritmus navštíví všechny rohy (rozrušený) krychle v rozměruD v nejhorší případ.^[1][6][7]

Modifikace konstrukce Klee-Minty vykazovaly podobnou exponenciálnost časová složitost pro další otočná pravidla simplexního typu, která udržují prvotní proveditelnost, například Blandovo pravidlo.^[8][9][10] Další modifikace ukázala, že křížový algoritmus, který nezachovává prvotní proveditelnost, navštíví také všechny rohy upravené kostky Klee – Minty.^[7][11][12] Stejně jako simplexní algoritmus, i křížový algoritmus v nejhorším případě navštíví všech 8 rohů trojrozměrné krychle.

Algoritmy sledující cestu

Další úpravy krychle Klee – Minty prokázaly špatný výkon centrální cesta–Poslední algoritmy pro lineární optimalizaci v tom, že centrální dráha je libovolně blízko ke každému z rohů krychle. Tento výkon „sledování vrcholů“ je překvapivý, protože takové algoritmy sledování dráhy mají pro lineární optimalizaci polynomiálně-časovou složitost.^[3][13]

Průměrný případ

Kostka Klee – Minty také inspirovala výzkum průměrná složitost. Pokud jsou způsobilé otočné čepy vytvořeny náhodně (a nikoli pravidlem nejstrmějšího klesání), potřebuje Dantzigův simplexní algoritmus v průměru kvadraticky mnoho kroků (na objednávku Ó(D²).^[4]Standardní varianty simplexního algoritmu jsou v průměruD kroky pro krychli.^[14] Když je inicializován v náhodném rohu krychle, křížový algoritmus navštíví pouzeD další rohy, nicméně, podle papíru 1994 Fukuda a Namiki.^[15][16] Jak simplexní algoritmus, tak i křížový algoritmus navštěvují v průměru přesně 3 další rohy trojrozměrné krychle.

Viz také

• Projektivní algoritmus Karmarkaru
• Elipsoidní algoritmus Khachiyan

Poznámky

Reference

• Deza, Antoine; Nematollahi, Eissa; Terlaky, Tamás (květen 2008). „Jak dobré jsou metody vnitřních bodů? Klee-Minty kostky zpřísňují hranice složitosti iterace“. Matematické programování. 113 (1): 1–14. CiteSeerX  10.1.1.214.111. doi:10.1007 / s10107-006-0044-x. PAN  2367063.
• 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). Thomas M. Liebling; Dominique de Werra (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í v Lausanne, 1997): 369–395. CiteSeerX  10.1.1.36.9373. doi:10.1007 / BF02614325. PAN  1464775. Postprintový předtisk.
• Gartner, B .; Ziegler, G. M. (1994). Randomizované simplexní algoritmy na kostkách Klee-Minty. Základy informatiky, výroční sympozium IEEE dne. IEEE. 502–510. CiteSeerX  10.1.1.24.1405. doi:10.1109 / SFCS.1994.365741. ISBN  978-0-8186-6580-6.
• 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.
• Megiddo, Nimrod; Shub, Michael (Únor 1989). "Hraniční chování vnitřních bodových algoritmů v lineárním programování". Matematika operačního výzkumu. 14 (1): 97–146. CiteSeerX  10.1.1.80.184. doi:10,1287 / bř. 14.1.97. JSTOR  3689840. PAN  0984561.
• Murty, Katta G. (1983). Lineární programování. New York: John Wiley & Sons. str. xix + 482. ISBN  978-0-471-09725-9. PAN  0720547.
• 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, Tamás; Zhang, Shu Zhong (1993). "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.

externí odkazy

Algebraický popis s ilustrací

První dva odkazy mají jak algebraickou konstrukci, tak obrázek trojrozměrné Klee-Mintyho kostky:

• Deza, Antoine; Nematollahi, Eissa; Terlaky, Tamás (květen 2008). „Jak dobré jsou metody vnitřních bodů? Klee-Minty kostky zpřísňují hranice složitosti iterace“. Matematické programování. 113 (1): 1–14. CiteSeerX  10.1.1.214.111. doi:10.1007 / s10107-006-0044-x. PAN  2367063. (vyžadováno předplatné). pdf verze na domovské stránce profesora Dezy.
• Gartner, B .; Ziegler, G. M. (1994). Randomizované simplexní algoritmy na kostkách Klee-Minty. Základy informatiky, výroční sympozium IEEE dne. IEEE. 502–510. CiteSeerX  10.1.1.24.1405. doi:10.1109 / SFCS.1994.365741. ISBN  978-0-8186-6580-6. IEEE překlepne jméno „Gärnter“ jako „Gartner“ (sic.).

Obrázky bez lineárního systému

• Články E. Nematollahi, které pojednávají o kostce Klee-Minty s ilustracemi.
• Obrázek kostky Klee-Minty ukazující cestu simplexního algoritmu (automatický překlad Němec ) od Günter Ziegler. Obrázek ve druhé polovině stránky.