Description
Optimalizálási szeminárium
Absztrakt:
Az előadásban bemutatunk egy új hosszúlépéses belsőpontos algoritmust a lineáris programozási feladat megoldására.
A Darvay Zsolt által 2002-ben bevezetett algebrailag ekvivalens átalakítások módszere új keresési irányok meghatározását teszi lehetővé belsőpontos algoritmusok esetén. Különböző függvények alkalmazásával számos új algoritmust definiáltak lineáris programozási feladatok, lineáris komplementaritási feladatok és számos más feladatosztály esetében is.
A lépéshossz alapján a belsőpontos algoritmusok két csoportra oszthatók, rövid- és hosszúlépéses módszerekre. A gyakorlatban hatékonyabb hosszúlépéses algoritmusok elméleti komplexitása azonban sokáig elmaradt a rövidlépéses változatokétól. Ai és Zhang 2005-ben egy új széles környezet alkalmazásával bevezetett egy új hosszúlépéses belsőpontos algoritmust, amelyre tudták igazolni a rövidlépéses módszerekre jellemző jobb komplexitást.
2018-ban Darvay Zsolt és Rigó Petra Renáta adta meg az első, Ai-Zhang típusú széles környezetre és a négyzetgyök-függvénnyel alkalmazott algebrailag ekvivalens átalakítások módszerére épülő hosszúlépéses algoritmust.
Az előadásban ismertetett algoritmus szintén Ai-Zhang típusú környezetet használ és az algebrailag ekvivalens átalakítások módszerére épül, a φ(t) = t − √t függvény alkalmazásával. Az elemzés ismertetésén túl bemutatjuk a NETLIB LP-feladatokra kapott numerikus eredményeket és összehasonlítjuk őket az identitás- és négyzetgyökfüggvényre épülő algoritmusok működésével.
Társszerző: Eisenberg-Nagy Marianna
Az előadást Teams-en is közvetítjük, aki online szeretne csatlakozni, kérem, hogy e-mailben jelezze Pintér Miklósnak (miklos.pinter@gmail.com)