Optimalizálási eljárások, előadás

2022 Tavasz

Előadások/gyakorlatok

1.-2. hét, Február 8-17.: Az optimalizálás alapfeladata, speciális osztályok, konkrét példák
- A videó kivetítése: pdf file nyomtatható pdf file
- Az előadáson túlmutató segédanyagok:
  - Tichaschke cikke az optimalizálás nagy alakjairól
3.-4. hét, Február 24.-Március 3.: Dualizálás, gyenge dualitás, példák.
- A videó kivetítése: pdf file nyomtatható pdf file
- Az előadáson túlmutató segédanyagok:
  - A wikipedia oldala a dualitásról
  - A wikipedia oldala a duális normáról
  - A wikipedia oldala a konvex konjugáltról
5. hét, Március 10.: Erős dualitás tételek, Karush-Kuhn-Tucker-tétel
- A videó kivetítése: pdf file nyomtatható pdf file
- Segédanyagok:
  - Kuhn és Tucker eredeti cikke
  - Cottle cikke Karush és a KKT tétel történetéről
  - Kjeldsen cikke a Kuhn-Tucker-tételről és a II. világháború kapcsolatáról
6. hét, Március 17.: LP geometriája
- A videó kivetítése: pdf file nyomtatható pdf file [Utolsó javítás: március 10.]
- Segédanyagok:
  - Shu-Cherng Fang egy előadása egy LP-ről szóló kurzuson (North Carolina State University, Fall 2011)
  - Geir Dahl egy jegyzete Convexity cimmel
  - John Nachbar egy jegyzete kúpokról
  - Geir Dahl egy jegyzete Convexity és combinatorial optimization témában
7. hét, Március 24.: Feltételek egy politóp egész mivoltára
- A videó kivetítése: pdf file nyomtatható pdf file
- Segédanyagok:
  - Egy University of Illinois-ról származó jegyzet (Chandra Chekuri)
  - Egy Stanford University-ről származó jegyzet (Jan Vondrák)
  - Pulleyblank egy cikke Edmonds tételének történeti előzményeiről
  - Az Edmonds poliéder tétel eredeti cikke
8. hét, Március 31.: Az Edmonds politóp tesztelése, Gomory-Hu-fák
- A videó kivetítése: pdf file handout file
- Segédanyagok:
  - Koutris Paraschos és Vasileios Syrgkanis Gomory-Hu-fáról szóló előadásának jegyzete
9. hét, Április 7.: Pontpakolási politóp, perfekt gráfok
- A videó kivetítése: pdf file handout file
- Segédanyagok:
  - A Wikipedia oldala a perfekt gráfokról
  - Stefan Hougardy cikke speciális gráfosztályokról, amelyekről tudjuk, hogy perfektek
  - Lovász László eredeti cikke a gyenge perfekt gráf sejtés megoldásával
  - A gyenge perfekt gráf/Lovász tétel a wikipédián
  - Chvatal honlapja a perfekt gráfokról
  - A Wikipedia oldala az erős perfekt gráf tételről
  - Az Annals of Mathematics-ban megjelent cikk az erős perfekt gráf tétel bizonyításával (Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas)
  - Perfekt gráfokkal kapcsolatos problémák honlapja

[Április 14.]: Húsvéti szünet

10. hét, Április 21.: Szemidefinit programozás: Alapok
- A videó kivetítése: pdf file handout file
- Segédanyagok:
  - Szemidefinit programozás honlapja
  - Lovász László szemidefinit programozásról írt összefoglalója
  - Vandenberghe és Boyd cikke
  - Freund cikke: Introduction to Semidefinite Programming (SDP)
11. hét, Április 28.: Szemidefinit programozás: Sajátértékek
- A videó kivetítése: pdf file handout file
- Segédanyagok:
  - Lovász László egy jegyzete gráfok sajátértékeiről
  - Spielman egy jegyzete gráfokról, sajátértékekről, algebrai módszerekről
  - Hwang egy egyszerű bizonyítása Cauchy interlace tételére az American Mathematical Monthlyból
12. hét, Május 5.: Szemidefinit programozás: Vektor relaxációk
- A videó kivetítése: pdf file handout file
- Segédanyagok:
  - Wikipedia oldal Shannon capacity of a graphcímmel
  - Lovász László eredeti cikke a Shannon-kapacitásról
  - Wikipedia oldal Lovász number címmel
  - Femke Bekius BSc szakdolgozata The Shannon Capacity of a Graph címmel
  - Donald Knuth összefoglaló cikke a szendvics tételről az arXiv, tudományos cikkeket rendszerező adatbázisból
  - Goemans, Williamson eredeti cikke
  - Uri Feige előadása The Use of Semidefinite Programming in Approximation Algorithms címmel (ppt file)
13. hét, Május 5.: Heurisztikák kezelhetetlen problémák kezelésére
- A videó kivetítése: pdf file handout file
- Segédanyagok:
  - Branch and bound methods wikipedia
  - Egy cikk (Jens Clausen: Branch and Bound Algorithms - Principles and Examples (1999)) a branch and bound módszerről pdf file
  - Egy M.I.T. kurzus előadása IP-ről és Gomory vágásokról előadás pdf file-ok
Nem volt rá idő: Numerikus módszerek optimalizálásra
- A videó kivetítése: pdf file handout file
- Segédanyagok:
  - A Soviet Discovery Rocks World of Mathematics The NY Times címlapja, 1979. november 7. [A cikkben szerepel Szeged! Keressük meg.]
  - Karmakar algoritmus wikipedia
  - Karmakar eredeti cikke (1984) pdf file
  - Egy öszefogalaló cikk (Anders Forsgren, Philip E. Gill, Margaret H. Wright - Interior Methods for Nonlinear Optimization) a belső pontos módszerekről pdf file