Új hosszúlépéses belsőpontos algoritmus a lineáris programozási feladatra
Varga Anita előadása (Optimization Seminar, negyedik alkalom)
2020. november 5.
13:40
1093 Budapest Fővám tér
Faculty Club, konferenciaterem
Online Microsoft Teams-en keresztül
2020. november 5-én minden egyetemi Polgárt várunk a Corvinus Institute for Advanced Studies keretei között működő Corvinus Centre for Operations Research (CIAS-CCOR) következő előadására, melyen Varga Anita (BME, doktorandusz) magyar nyelvű előadása lesz hallható. Az előadás társszerzője Dr. Eisenberg-Nagy Marianna.
Az előadást online is lehet követni Microsoft Teams-en keresztül.Az online eléréshez előzetes regisztráció szükséges! Regisztrálni a pmiklos@uni-corvinus.hu e-mail címre küldött levéllel tudnak.
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.
Információ: tibor.illes@uni-corvinus.hu
