Techniky obloukového vyhledávání pro metody vnitřních bodů

Původní název:

Arc-Search Techniques for Interior-Point Methods

Obsah knihy:

Tato kniha se zabývá důležitou oblastí numerické optimalizace, tzv. metodou vnitřních bodů.

Toto téma je populární od 80. let 20. století, kdy si lidé postupně uvědomili, že všechny simplexové algoritmy nekonvergují v polynomiálním čase a u mnoha algoritmů vnitřních bodů lze dokázat, že konvergují v polynomiálním čase.

Dlouhou dobu však existovala znatelná mezera mezi teoretickými polynomiálními hranicemi algoritmů vnitřního bodu a efektivitou těchto algoritmů.

Strategie, které byly důležité pro výpočetní efektivitu, se staly překážkami v důkazu dobrých polynomiálních mezí. Čím více se tyto strategie v algoritmech používaly, tím horší byly polynomiální meze.

Aby se problém ještě více prohloubil, Mehrotrův algoritmus prediktor-korektor (MPC) (donedávna nejoblíbenější a nejefektivnější algoritmus vnitřního bodu) používá všechny dobré strategie a nedokáže dokázat konvergenci. MPC tedy nemá polynomialitu, což je u simplexové metody kritický problém. Tato kniha se zabývá nedávným vývojem, který toto dilema řeší.

Má tři hlavní části. První, zahrnující kapitoly 1, 2, 3 a 4, představuje některé z nejdůležitějších algoritmů během vývoje metody vnitřních bodů kolem roku 1990, z nichž většina je všeobecně známá. Hlavním cílem této části je vysvětlit výše popsané dilema analýzou polynomiálních hranic těchto algoritmů a shrnutím výpočetních zkušeností s nimi spojených.

Druhá část, zahrnující kapitoly 5, 6, 7 a 8, popisuje postupné řešení dilematu pomocí technik obloukového hledání. Na konci této části je představen velmi efektivní algoritmus s nejnižší polynomiální mezí.

Poslední část, zahrnující kapitoly 9, 10, 11 a 12, rozšiřuje techniky hledání oblouků na některé obecnější problémy, jako je konvexní kvadratické programování, problém lineární komplementarity a semidefinitní programování.