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