Optimalizálási feladatok egy családjára létezik hatékony megoldó
algoritmus, ha valamilyen jól használható struktúrával rendelkeznek. Azt szoktuk mondani, hogy a konvex feladatok bizonyos értelemben a kezelhető, megoldható feladatok. Ez annyiban helytálló, hogy ebben az esetben jól kidolgozott dualitáselmélet áll rendelkezésünkre, ami az optimalitás szükséges és elégséges feltételeit szolgáltatja. Ám ez hatékony megoldó algoritmus létrehozásához nem elegendő.
Nemirovski és Nesterov igazolták, hogy ha egy optimalizálási feladat rendelkezik úgynevezett self-concordant büntető függvénnyel, akkor belsőpontos algoritmussal polinom időben epszilon optimális megoldás állítható elő. Ám nem minden konvex feladat rendelkezik ilyen tulajdonsággal.
A hallgatónak különböző gyakorlati feladatokból származó konvex
optimalizáslási feladatok -- például speciális egyensúlyi feladatok,
Young programozási feladat -- esetén kellene megvizsgálnia, hogy
létezik-e az adott feladatosztály esetén megfelelő büntető függvény, vagy a létezés milyen további feltételek mellett szavatolható.
Másrészről ha ismeretes, hogy létezik az adott feladatosztályra
általános belsőpontos algoritmus, akkor lehet-e ennek hatékonyságát javítani az adott feladat speciális tulajdonságait kihasználva az eljárás lépései során.
előírt nyelvtudás: angol további elvárások: (alkalmazott) matematikus, jó vagy kiváló minősítésű Msc diploma. Angol nyelvismeret.
felvehető hallgatók száma: 1
Jelentkezési határidő: 2018-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).
Bejelentkezés
