Elipsoidné metódy - lexikón matematiky
Lexikón matematiky: elipsoidné metódy
Elipsoidné metódy sú triedou metód na riešenie problémov s lineárnou (a konvexnou) optimalizáciou. Základná myšlienka je nasledovná: Najskôr sa optimalizačný problém preformuluje ako rozhodovací problém, či polyhedron \ beginP = \\ end nie je prázdny. To sa deje uplatnením vety o dualite lineárnej optimalizácie.
Prvotný problém \ begin ^ \ cdot v \ to \ min \, \, \, E \ cdot v \ ge f, \, \, v \ ge 0 \ end a súvisiaci duálny problém \ begin ^ \ cdot y \ to \ max \, \, \, ^ \ cdot y \ le c, \, \, y \ ge 0 \ koniec systému \ begin-E \ cdot v \ le -f, -v \ le 0, \\ ^ \ cdot y \ le c, -y \ le 0, \\ ^ \ cdot v - ^ \ cdot y \ le 0 \ end dohromady. Takto sa získa systém definujúci P x ≤ b (s x: = (v, y) a zodpovedajúca definícia A a b).
Ekvivalencia úlohy nájsť uskutočniteľný bod pre tento problém s pôvodnou optimalizačnou úlohou vyplýva zo skutočnosti, že rozdiel v dualite c T * x - b T * y mizne iba v krajných bodoch, ale je inak pozitívny.
Samotný postup teraz začína konštrukciou špeciálneho elipsoidu E0 = (z0, B0). Podskupina E (z, B) sa nazýva des ℝ n je (špeciálny) elipsoid so stredom z ∈ ℝ n ak je vo forme \ begin \ >> ^ | ^ \ cdot ^ \ cdot (x-z) \ le 1 \> \ end je zapisovateľný. Tu B je kladne určitá (n, n) matica. Prvý elipsoid E0 je zvolený tak, aby obsahoval bod riešenia P v prípade P ≠ ∅ (pozri nižšie).
Konštrukcia nového elipsoidu
Proces pokračuje, kým nenájdeme stred z ∈ P alebo kým nezaručíte, že P = ∅. Posledne uvedené sa dosiahne porovnaním objemu elipsoidov Ei s odhadom minimálneho objemu P ∩ E0.
Elipsoidová metóda má veľký historický význam, pretože to bola prvá polynomiálna časová metóda pre lineárne programovanie v Turingovom modeli. Pritom sa pozeráme na problémy, ktoré pozostávajú iba z racionálnych vstupných údajov. Bez obmedzenia sa tu predpokladá, že pôvodný systém pozostáva iba z celočíselných údajov (čo sa dá dosiahnuť po vynásobení systému spoločným hlavným menovateľom všetkých racionálnych údajov).
Namiesto A ⋅ x ≤ b zvážte systém prísnych nerovností \ beginA \ cdot x \ lt b + ^ \ cdot e, \ end, kde e = (1, ..., 1) T a L označuje bitovú veľkosť počiatočného problému. Nový systém je možné vyriešiť presne, ak išlo o starý systém. Tento vzťah medzi týmito dvoma systémami je v podstate založený na celočíselnej povahe vstupných údajov a možnom odhade (smerom nahor) bitovej veľkosti určitých riešení pomocou Cramerovho pravidla. Na jednej strane možno z výstupných údajov nájsť vhodný východiskový elipsoid E0 s (P ≠ ∅ ⇒ E0 ∩ P ≠ ∅); na druhej strane je možné nastaviť dolnú hranicu objemu V priesečníka E0 so sadou riešení \ (\ mathop
\ limity ^ \) A ⋅ x - L. ·. Postup je teraz aplikovaný na \ (\ mathop
\ limits ^ \) a opakuje sa do \ begin \ text (_) \ le ^ \ cdot \ text (_) \ lt V \ end (ktorý kvôli λ m × n> udáva počet aritmetických operácií známych elipsoidných metód je obmedzených smerom nahor. Elipsoidné metódy preto nie sú v algebraických výpočtových modeloch polynomické (výsledok Traub a Wozniakowski (1982)).