A lineáris komplementaritási feladatoknak számos alkalmazásai ismertek különböző tudományterületeken. Gazdasági, mérnöki, társadalomtudományi feladatok sokasága fogalmazható meg lineáris komplementaritási feladatként. Ebben a témakörében számos nyitott elméleti kérdéssel találkozunk, és több nagyon fontos gyakorlati alkalmazásra nem létezik véges megoldó módszer sem. A belsőpontos algoritmusok fontosságát az is jelzi, hogy olyan általánosabb feladatok megoldására is alkalmazhatóak, amelyekre nem létezik a szimplex algoritmushoz hasonló megoldási módszer. A lineáris komplementaritási feladat az NP-teljes feladat osztályba tartozik. Ha viszont feltételezzük, hogy a feladat mátrixa speciális tulajdonsággal rendelkezik, akkor bevezethetők olyan belsőpontos algoritmusok, amelyek polinom időben adnak közelítő megoldást a feladat méretében és a mátrix speciális paraméterében.
A belsőpontos algoritmusokat többféleképpen osztályozhatjuk. A lépéshossz alapján megkülönböztetünk rövid, illetve hosszú lépéses algoritmusokat. A rövid lépéses belsőpontos algoritmusok elméleti bonyolultsága jobbnak bizonyult a hosszú lépéses módszerekénél. Gyakorlatban viszont általában a hosszú lépéses módszerek hatékonyabbak. Ma már léteznek olyan belsőpontos algoritmusok is, amelyek a centrális útnak egy széles környezetében hosszú lépéseket tesznek meg, az algoritmusok bonyolultsága viszont megegyezik a legjobb rövid lépéses belsőpontos algoritmusokéval. Emellett a keresési irányok megválasztása is fontos szerepet játszik a belsőpontos algoritmusok elméletében. Egy fontos megválaszolandó kérdés, hogy milyen irány osztályt kellene használni a belsőpontos algoritmusok esetében, amellyel hatékonyabb módszereket lehetne bevezetni.
A doktori kutatási projekt keretében a jelölt feladata új, hatékony belsőpontos algoritmusok bevezetése és elemzése lineáris komplementaritási feladatok megoldására. A szakirodalomban a lineáris komplementaritási feladatokra vonatkozó belsőpontos algoritmusok esetében a megadott numerikus eredmények általában lineáris optimalizálásra vonatkoznak, amely csak egy sajátos esetet jelent. Ezért fontos lenne általánosabb esetekre is hatékony megoldó algoritmusokat készíteni. Komoly előrelépés lenne a bevezetett módszerek kiterjesztése általános lineáris komplementaritási feladatokra is.
felvehető hallgatók száma: 1
Jelentkezési határidő: 2021-10-14
2024. IV. 17. ODT ülés Az ODT következő ülésére 2024. június 14-én, pénteken 10.00 órakor kerül sor a Semmelweis Egyetem Szenátusi termében (Bp. Üllői út 26. I. emelet).
Bejelentkezés
