Thesis supervisor: Tibor Illés
Location of studies (in Hungarian): BME Matematika Intézet, Differenciálegyenletek Tanszék Abbreviation of location of studies: BME
Description of the research topic:
Az optimalizálás körében az utóbbi időszak egyik legintenzívebben kutatott területének a lineáris programozásra vonatkozó belsőpontos algoritmusokat tekinthetjük. Alapvető belsőpontos algoritmus családok kifejlesztésre kerültek a lineáris programozás területén. Számos kiváló implementáció is született nagyméretű lineáris programozási feladatok megoldására.
Egyre elterjedtebb vélemény, hogy lineáris optimalizálás alatt egyre inkább ne csak a lineáris programozást értsük, hanem az olyan feladatokat, amelyek lineáris programozási feladatok megoldására kidolgozott technikák (pivot algoritmusok, belsőpontos algoritmusok) segítségével megoldhatók. Ebben az értelemben a lineáris optimalizálás témakörébe tartoznak a lineáris programozáson túl, a lineáris feltételes kvadratikus programozási feladatok; a lineáris komplementaritási feladatok; a lineáris feltételes kúp optimalizálási feladatok; a lineáris feltételes hiperbolikus optimalizálási feladatok.
A lineáris programozásra vonatkozó algoritmusok esetén nemrég egy olyan nem megengedett belsőpontos módszer került bevezetésre, amely teljes Newton-lépéseket használva közelíti meg az optimumot. Az algoritmus különböző változataiban egy megengedettségi, illetve egy vagy több centralizálási lépéssel dolgoznak.
Emellett, pár évvel ezelőtt, egy elégséges lineáris komplementaritási feladatra vonatkozó módszer látott napvilágot, amely a centrális útnak egy széles környezetében hosszú lépéseket tesz meg. Ennek ellenére, a módszer bonyolultsága megegyezik a legjobb rövid lépéses belsőpontos algoritmusokéval. Az eddigi kutatásokkal szemben ez azért jelent áttörést, mivel hagyományosan a rövid lépéses módszerek elméleti hatékonysága jobb a hosszú lépéses módszerekénél. Gyakorlati megvalósítás szemszögéből nézve viszont általában a hosszú lépéses módszerek bizonyulnak hatékonyabbaknak. A lineáris komplementaritás 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 a lineáris optimalizálási feladatoknál általánosabb feladatok megoldására is alkalmazhatóak, amelyekre nem létezik a szimplex algoritmushoz hasonló megoldási módszer. Az utóbbi időszakban nagy hangsúlyt fektettek a belsőpontos algoritmusok általánosítására szemidefinit optimalizálásra és másodrendű kúpprogramozásra. Az egyik legmodernebb témának a szimmetrikus optimalizálást tekinthetjük, amely magába foglalja az eddig említett feladatköröket.
A doktori kutatási projekt keretében a jelölt feladata olyan új, hatékony belsőpontos algoritmusok kidolgozása, amelyik prototípusát lineáris optimalizálási feladatra fejleszti ki és a szemidefinit optimalizálási- illetve a másodrendű kúpprogramozási feladatok esetén is megőrzi előnyös tulajdonságait. Komoly előrelépés lenne egy-egy speciális feladatosztályára gyakorlatban hatékony megoldó algoritmusokat készíteni.
Recommended language skills (in Hungarian): angol Further requirements: - angol nyelv ismerete,
- lineáris és nemlineáris programozási témakörök alaposabb ismerete
- programozási tapasztalat (MATLAB, XPRESS-MP/MOSEL, C)
Number of students who can be accepted: 1
Deadline for application: 2016-05-31
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).
Login
