Techniky vyhľadávania oblúka pre metódy vnútorného bodu

Pôvodný názov:

Arc-Search Techniques for Interior-Point Methods

Obsah knihy:

Táto kniha sa zaoberá dôležitou oblasťou numerickej optimalizácie, tzv. metódou vnútorného bodu.

Táto téma je populárna od 80. rokov minulého storočia, keď si ľudia postupne uvedomili, že všetky simplexové algoritmy nekonvergujú v polynomiálnom čase a mnohé algoritmy vnútorného bodu sa dajú dokázať ako konvergujúce v polynomiálnom čase. Dlho však existovala výrazná medzera medzi teoretickými polynomiálnymi hranicami algoritmov vnútorného bodu a efektívnosťou týchto algoritmov.

Stratégie, ktoré boli dôležité pre výpočtovú efektívnosť, sa stali prekážkami pri dokazovaní dobrých polynomiálnych hraníc.

Čím viac stratégií sa v algoritmoch používalo, tým horšie boli polynomiálne ohraničenia. Aby sa problém ešte viac prehĺbil, Mehrotrov algoritmus prediktor-korektor (MPC) (donedávna najpopulárnejší a najefektívnejší algoritmus vnútorného bodu) používa všetky dobré stratégie a nedokáže dokázať konvergenciu.

MPC preto nemá polynomialitu, čo je kritický problém simplexovej metódy. Táto kniha sa zaoberá najnovším vývojom, ktorý túto dilemu rieši. Má tri hlavné časti.

V prvej, ktorá obsahuje kapitoly 1, 2, 3 a 4, sa uvádzajú niektoré z najdôležitejších algoritmov počas vývoja metódy vnútorného bodu okolo roku 1990, pričom väčšina z nich je všeobecne známa. Hlavným cieľom tejto časti je vysvetliť opísanú dilemu analýzou polynomických hraníc týchto algoritmov a zhrnutím výpočtových skúseností s nimi spojených. Druhá časť, ktorá obsahuje kapitoly 5, 6, 7 a 8, opisuje postupné riešenie dilemy pomocou techník hľadania oblúkov.

Na konci tejto časti je uvedený veľmi efektívny algoritmus s najnižšou polynomickou hranicou. Posledná časť, ktorá obsahuje kapitoly 9, 10, 11 a 12, rozširuje techniky hľadania oblúkov na niektoré všeobecnejšie problémy, ako je konvexné kvadratické programovanie, problém lineárnej komplementarity a semidefinitné programovanie.