Belsőpontos algoritmusok speciális konvex optimalizálási feladatokra

A téma kiírójának neve és tanszéke: 
Eisenberg-Nagy Marianna, Differenciálegyenletek Tanszék
A téma kiírójának e-mail címe: 
enagym@math.bme.hu
Típus: 
PhD téma

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.

A jelentkezővel szemben támasztott elvárások: (alkalmazott) matematikus, jó vagy kiváló minősítésű diploma. Angol nyelvismeret.