Ívkeresési technikák a belső-pont módszerekhez

Eredeti címe:

Arc-Search Techniques for Interior-Point Methods

Könyv tartalma:

Ez a könyv a numerikus optimalizálás egy fontos területét, az úgynevezett belsőpontos módszert tárgyalja. Ez a téma az 1980-as évek óta népszerű, amikor az emberek fokozatosan rájöttek, hogy nem minden szimplex algoritmus konvergál polinomiális időben, és számos belső-pontos algoritmusról bebizonyítható, hogy polinomiális időben konvergál.

Azonban sokáig érezhető szakadék tátongott a belső-pontos algoritmusok elméleti polinomiális határai és ezen algoritmusok hatékonysága között. A számítási hatékonyság szempontjából fontos stratégiák akadályokká váltak a jó polinomiális korlátok bizonyításában. Minél több stratégiát használtak az algoritmusokban, annál rosszabbak lettek a polinomiális korlátok.

A problémát tovább súlyosbítja, hogy Mehrotra prediktor-korrektor (MPC) algoritmusa (a legnépszerűbb és leghatékonyabb belsőpontos algoritmus a közelmúltig) minden jó stratégiát használ, és nem tudja bizonyítani a konvergenciát.

Ezért az MPC nem rendelkezik polinomialitással, ami kritikus probléma a szimplex módszerrel. Ez a könyv a legújabb fejleményeket tárgyalja, amelyek feloldják a dilemmát.

Három fő részből áll. Az első, amely az 1., 2., 3. és 4.

fejezetet tartalmazza, a belsőpontos módszer 1990-es évek körüli fejlődése során a legfontosabb algoritmusokat mutatja be, amelyek többsége széles körben ismert. E rész fő célja a fent leírt dilemma magyarázata ezen algoritmusok polinomiális határainak elemzésével és a hozzájuk kapcsolódó számítási tapasztalatok összefoglalásával. A második rész, amely az 5., 6., 7.

és 8. fejezetet tartalmazza, leírja, hogyan lehet a dilemmát lépésről lépésre megoldani az ívkeresési technikák segítségével.

E rész végén egy nagyon hatékony, a legalacsonyabb polinomiális korlátot tartalmazó algoritmust mutatunk be. Az utolsó rész, amely a 9., 10., 11. és 12.

fejezetet tartalmazza, kiterjeszti az ívkeresési technikákat néhány általánosabb problémára, például a konvex kvadratikus programozásra, a lineáris komplementaritási problémára és a félig definiált programozásra.