Budapest University of Technology and Economics, Faculty of Electrical Engineering and Informatics

    Belépés
    címtáras azonosítással

    vissza a tantárgylistához   nyomtatható verzió    

    Alkalmazott optimalizálás és játékelmélet

    A tantárgy angol neve: Applied Optimisation and Game Theory

    Adatlap utolsó módosítása: 2016. május 27.

    Budapesti Műszaki és Gazdaságtudományi Egyetem
    Villamosmérnöki és Informatikai Kar

    Villamosmérnöki tudományok doktori iskola
    Informatikai tudományok doktori iskola
    Doktoranduszi kötelező tárgy a
    Híradástechnika szakmacsoport részére
    és választható tárgy a fenti doktori iskolák hallgatói részére

    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    VITMD097   4/0/0/v 5 1/1
    3. A tantárgyfelelős személy és tanszék Dr. Cinkler Tibor, Távközlési és Médiainformatikai Tanszék
    4. A tantárgy előadója
    Név: Beosztás: Tanszék:
     Dr. Cinkler Tibor egyetemi tanár TMIT
     Dr. Toka László
     adjunktus TMIT
     Dr. Rétvári Gábor tudományos főmunkatárs TMIT
     Dr. Tapolcai János
     egy. docens TMIT
     Dr. Biczók Gergely
     adjunktus
     TMIT
    5. A tantárgy az alábbi témakörök ismeretére épít

    - - - -

    6. Előtanulmányi rend
    Ajánlott:

    A tárgyat csak az veheti fel, aki nem hallgatta a következő választható tárgyakat:
    Optimalizálási módszerek (VITTD090), Játékelmélet és távközlési alkalmazásai (VITTD096)

    7. A tantárgy célkitűzése

    Bármilyen problémával is szembesülünk, célunk a legjobb megoldást/stratégiát találni. Ebben segít az optimalizálás és a játékelmélet. A tárgy keretei közt ismertetjük a jellegzetes matematikai optimalizálási módszereket és a játékelmélet alapjait, valamint néhány modellezési-, tervezési példán keresztül bemutatjuk azok alkalmazását is.
    Egy-egy mérnöki feladathoz a megfelelő modell megalkotása, egy áramkör/rendszer megtervezése, egy megoldó szoftver kialakítása és a megfelelő matematikai optimalizálási módszer, vagy a játékelméleti eszköz nem triviális alkalmazása új műszaki tudományos eredmények alapjául szolgál. E tárgy segíti doktoranduszainkat az alkalmazott matematikai módszerek megismerésében és ilymódon a kutatási feladataik színvonalas megoldásában, választott szakterületüktől függetlenül.

    8. A tantárgy részletes tematikája

    Bevezetés
    Optimalizálás, folytonos, diszkrét és dinamikus feladatok
    Játékelmélet, nem-kooperatív, kooperatív és dinamikus játékok

    OPTIMALIZÁLÁS
    Bevezetés az optimalizálásba
    Célfüggvény, feltételes és kötetlen optimalizálás, megengedett megoldások
    Az optimalizálási problémák (nemlineáris, kvadratikus, lineáris; valós értékű, diszkrétváltozós és egész értékű; kötött, kötetlen; statikus, dinamikus) és algoritmusok osztályozása (egy- és sokváltozós, kereső- és gradiensalapú eljárások, általános heurisztikák)
    Lokális és globális optimum, a konvexitás szerepe, konvex programozás
    Modellezési technikák, a modellezés lépései, hibafüggvények. Konkrét műszaki problémák megfogalmazása optimalizálási feladatként. Megoldószoftverek.

    A lineáris programozás
    A lineáris programozás alapjai, a lineáris programok általános alakja, a modellezhető problémák általános jellemzői, példák és alkalmazások
    Lineáris programok megoldása, grafikus megoldás, bázismegoldások, a szimplex algoritmus, optimalitás, nemkorlátos megoldások, a degeneráció fogalma és kezelése, komplexitás, a szimplex tábla, példák megoldása a szimplex tábla segítségével
    Lineáris programok duáljai és a duál szimplex, Farkas lemmája, a dualitás fogalma, a duális előállítása, a dualitás gyenge és erős tétele, a duál szimplex algoritmus
    A lineáris programozás klasszikus alkalmazásai, a szállítási probléma, az ütemezési probléma, hálózati folyamproblémák, folyamok egészértékűsége, többtermékes folyamok, duálisok
    Lineáris programok megoldása számítógépes programcsomaggal

    Nemlineáris programozás
    Feltételmentes nemlineáris optimalizálás: kötetlen szélsőérték-keresés, a gradiens módszer, másodrendű gradiens módszerek, a Newton módszer
    Feltételek szerinti nemlineáris programozás: a nemlineáris programok általános alakja, az optimalitás szükséges és elégséges feltételei
    Nemlineáris programok megoldásának visszavezetése kötetlen optimalizálásra: az iránykeresés módszere. Visszavezetés lineáris programok megoldására: szukcesszív lineáris programozás

    Diszkrét (kombinatorikus) optimalizálás
    Lokális és globális optimum.
    Statikus és Dinamikus optimalizálás (dinamikus programozás)
    Többcélú optimalizálás
    Helyi (lokális) keresés
    Mohó, iteratív és „véletlen” módszerek
    Állapottér, szomszédosság, célfüggvény
    Állapottér szűkítése, korlátok kezelése
    Heurisztikák
    Egészértékű és bináris lineáris programozás
    Bonyolultság. Kapcsolat a folytonos és diszkrét optimalizálás között. Kapcsolat a bináris és egészértékű optimalizálás között
    Kevert egészértékű LP (MILP)
    ILP megoldó módszerek: Branch and bound, Cutting plain, Branch and cut, Lagrangian relaxation, Column Generation
    Példák: útvonalválasztás, töbtermékes hálózati folyamok, osztatlan folyamok, diszjunkt osztatlan folyamok

    Általánosan alkalmazható optimalizáló heurisztikák
    Simulated Annealing: energia függvény, szomszédosság, kezdő hőmérséklet, hűtési szabályok, kiinduló pont
    Threshold Accepting: a küszöbérték megválasztása
    Tabu Search: Tabu lista típusai
    Genetic (Evolutionary) Algorithms: különböző reprezentációk, GA operátorok, kereszteződések, mutációk
    Go With the Winner: fa mélysége és optimalizálás kapcsolata
    STAGE: becslésekkel gyorsított optimalizálás
    Példák: TSP (utazóügynök feladat), Hátizsák probléma és ládapakolás, Simulated Allocation (szimulált foglalás)

    JÁTÉKELMÉLET

    Bevezetés
    Mi a játékelmélet
    Racionális választás elmélete

    Nash egyensúly: Elmélet és illusztráció
    Stratégiai játékok
    Nash-egyensúly fogalom
    A legjobb válasz fogalma és domináns stratégiák
    Szimmetrikus játékok és szimmetrikus egyensúlyok
    Algoritmusok a tiszta stratégiai Nash-egyensúlyok keresésére

    Kevert stratégiai játékok 
    Stratégiai játékok kevert bővítése
    Von Neumann - Morgenstein kifizetési függvények
    Kevert stratégiai Nash-egyensúly
    Nash tétele a kevert stratégiai Nash egyensúly létezéséről
    Algoritmusok a kevert stratégiai egyensúlyok keresésére

    Dinamikus játékok: elmélet és illusztráció
    Alapfogalmak
    Aljáték-tökéletes egyensúly
    Hátráló indukció algoritmus
    Ismételt játékok
    Nash tétele (Nash folk theorem)
    Stackelberg-féle játékok és Stackelberg-egyensúly kiszámítása
    Végtelen dinamikus játékok

    Kooperatív játékok
    Általános fogalmak
    Shapley-értékek vizsgálata
    A mag (The Core) fogalma
    Sztochasztikus játékok

    Műszaki alkalmazások, esettanulmányok
    Hálózatmenedzsment (erőforrás-foglalás, torlódásvezérlés, „peering”-megállapodások, ütemezés)
    Útvonalválasztás (QoS routing, optimális útvonalválasztás-vezérlés)
    Torlódásvezérlés (TCP paraméter-beállítások)

    KITEKINTÉS
    Az optimalizálás és játékelmélet alkalmazási területeinek áttekintése és rendszerezése
    Nyilvánosan elérhető optimalizálási programok, valamint optimalizálással foglalkozó toolbox-ok áttekintése.

    9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium)

    Előadás

    10. Követelmények
    • A szorgalmi időszakban: 2 zárthelyi
    • A vizsgaidőszakban: írásbeli és szóbeli vizsga
    • Elővizsga: nincs

    A 2 zárthelyinek külön-külön min. elégségesnek kell lennie.

    11. Pótlási lehetőségek

    a szorgalmi időszak utolsó két hetének valamelyikében különeljárási díj fejében a zárthelyi pótolható abból a részből (részekből), amely nem sikerült. A zárthelyit (zárthelyiket) csak a szorgalmi időszakban lehet pótolni.

    A vizsga pótlására a Kar szabálya érvényes

    12. Konzultációs lehetőségek

    Az órákon egyeztetett illetve kihirdetett időpontokban.

    13. Jegyzet, tankönyv, felhasználható irodalom

    (Az alkalmazások esetére folyóirat és konferencia cikkek)

    1. D. G. Luenberger, Yinyu Ye: Linear and Nonlinear Programming. Third Edition, Springer kiadó. 1-546 old (részletek!). 2008.
    2. W. H. Press at al. Numerical Recipes. Cambridge University Press. Third Edition, 2002. (http://www.nr.com)
    3. M. Dell'Amico, F. Maoli, S. Martello, Annotated Bibliographies in Combinatorial Optimization, Wiley (1997).
    4. T. A. Trinh and S. Molnár, A Game-Theoretic Analysis of TCP Vegas, Lecture Notes in  Computer Science, Springer-Verlag, Chapter: pp. 338-347, Volume 3266 / 2004.
    5. G. Ausiello et. al. Complexity and Approximation, Springer (1999)
      Nemo Semret, Market Mechanisms for Network Resource Sharing, Ph.D. Dissertation, Columbia University, 1999.
    6. T. Basar and G. J. Olsder. Dynamic Noncooperative Game Theory. SIAM Series in Classics   in Applied Mathematics, Philadelphia, January 1999,.
    7. Drew Fudenberg and Jean Tirol, Game Theory, The MIT Press, Massachusetts Institute of Technology, 1991.
    8. Szidarovszky Ferenc, Molnár Sándor, Játékelmélet műszaki alkalmazásokkal, Műszaki Könyv Kiadó, Budapest, 1986.
    9. R. La, V. Anantharam, Optimal Routing Control : Repeated Game Approach, IEEE Transactions on Automatic Control, Vol. 47, No. 3, pp. 437 -450, March 2002.
    10. A. Akella, R. Karp, C. Papadimitriou, S. Seshan, S. Shenker, Selfish Behavior and Stability of the Internet: A Game-Theoretic Analysis of TCP, ACM SIGCOMM'02, Pittsburgh PA, 2002.
    14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka

    Kontaktóra

    60

    Félévközi készülés órákra

    20

    Felkészülés zárthelyire

    20

    Házi feladat elkészítése

    -

    Kijelölt írásos tananyag elsajátítása

           -

    ..

           -

    Vizsgafelkészülés könyv, anyag

    50

    Összesen

    150

    15. A tantárgy tematikáját kidolgozta

     Név: Beosztás: Tanszék, Intézet:
     Dr. Halász Edit egyetemi docens TMIT
     Dr. Cinkler Tibor egyetemi docens TMIT
     Dr. Vidács Attila egyetemi docens TMIT
     Dr. Trinh Anh Tuan tudományos munkatárs TMIT
     Dr. Rétvári Gábor tudományos főmunkatárs TMIT