A vizsganapjaim az ETR-en elérhetők.

Amennyiben egyéb teendőim megengedik (például nincs záróvizsga) a vizsga előtti szerda 11-től a szobámban elérhető leszek konzultációra.

Optimalizálás alapfeladat és speciális típusok: lineáris programozás, szemidefiniti programozás, konvex programozás. Ekvivalens átalakítások. Példák: Folyam feladat, alfa(G), gráfok optimális szétvágása. Lagrange-duális. Gyenge duálitás tétel. Erős dualitás: Slater-feltétel, Slater-tétel, Karush-Kuhn-Tucker-feltétel, Karush-Kuhn-Tucker-tétel. LP dualitás (kimondás BSc-ből), példa: folyam feladat. Totálisan unimoduláris mátrixok. Totálisan duális egész értékű problémák. Edmonds-féle politóptétel (párosítási politóp leírása lineáris egyenlőtlenségekkel). Cunningham-Marsh-tétel. Gomory-Hu-fák, Gomory-Hu-algoritmus. Minimális kapacitású paratlan vágások problémája. Szeparációs orákulum az Edmonds-politópra. Ellipszoidok Rⁿ-ben: definíció, félgömb minimális térfogatú forgás szimmetrikus ellipszoidba foglalása. Ellipszoid módszer (Khachian-algoritmus). Az ellipszoid módszer elméleti követkeményei. Gradiens módszer és analízise. Newton-módszer. Newton-módszer lineáris egyenlőség feltételek melletti optimalizálásra. Gátfüggvény (barrier) módszer: logaritmikus gátfüggvény. Szemidefinit gyenge dualitás tétel. Szemidefinit erős dualitás tétel (kimondás). alfa(G) és khi (G) sajátértékes becslése (Hoffman-tétel). Ezen becslések szemidefinit programozási megfogalmazása. Lovász-féle téta függvény. Gráfok ortogonális reprezentációja. Shannon-féle téta függvény. Approximációs algoritmusok: optimalis szétvágás. 3-kromatikus gráfok színezése.

A vizsgán az alábbi típusú kérdésekből szerepel három.

1. • Milyen függvények esetén (ÉT, ÉK?) beszélhetünk szubmoduláris, szemimoduláris tualjdonságról?
   • Definiálja is ezeket a tulajdonságokat.
   • Van-e köztük kapcsolat? Ha igen, bizonyítsa be.
   • Igazolja, hogy ha egy élsúlyozott gráfban egy x és y csúcsot elválasztó minimális súlyú vágás egyik oldaláról veszünk két csúcsot, akkor hozzájuk van olyan minimalis súlyú szeparáló vágás, amely nem keresztezi a kiindulót.
2. • Definiálja az optimalizálás alapfeladatát.
   • Definiálja a Lagrange-duálist.
   • Mondja ki és bizonyítsa be a gyenge dualitást.
   • Írja le a Karush-Kuhn-Tucker-feltételeket. igazolja, hogy primál és duál optimális megoldáspár teljesíti ezeket (differenciálható függvényekkel dolgozva).
3. • Definiálja gráfok alfa(G) és khi (G) paramétereit.
   • Mondja ki a rájuk vonatkozó sajátértékes becsléseket.
   • Az egyiket bizonyítsa be.
   • A másikat fogalmazza meg szemidefinit programozási feladatként.
4. • Definiálja a párosítási politópot.
   • Írja le ezt a politópot mint lineáris feltételrendszerrel definiált halmaz.
   • Mondja ki a Cunnigham-Marsh-tételt.
   • Miért következik ebből az Edmond-féle politóptétel? A következtetést mozgató állítást/tételt igazolja.
5. • Definiálja az ellipszoid fogalmát. Hogyan számítható ki a térfogata?
   • Számolja ki a félgömböt magába fogalaló legkisebb térfogatú ellipszoidot leíró képletet.
   • Milyen feladat megoldására alkalmazhatuk az ellipszoid módszer?
   • Vázolja hogyan működik az ellipszoid módszer.