- - - -

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.

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.

Előadás

• 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.

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

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

(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.
    

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