Optimalizálási eljárások/Methods of optimization, előadás

2025 Tavasz/Fall

Előadások/Lectures

1.-2. hét, Február 14-21.: Az optimalizálás alapfeladata, speciális osztályok, konkrét példák/The Basic problem of optimization, examples
- Egy covid korszakos videó kivetítése / beamer files from covid years: pdf file nyomtatható pdf file English pdf file handout pdf file
- Az előadáson túlmutató segédanyagok/Additional materials:
  - Tichaschke's paper on the major researchers in optimization
2.-3. hét, Február 28.-Március 7.: Dualizálás, gyenge dualitás, példák/Dualization, weak duality, examples.
- Beamer files: pdf file nyomtatható pdf file English pdf file handout pdf file
- Az előadáson túlmutató segédanyagok/Additional materials:
  - The wikipedia page on duality
  - The wikipedia page on dual norm
  - The wikipedia page on convex conjugate
4.-5. hét, Március 7.-10.: Erős dualitás tételek, Karush-Kuhn-Tucker-tétel/Strong duality theorems, KKT theorem
- Beamer files: pdf file nyomtatható pdf file English pdf file handout pdf file
- Segédanyagok/Additional materials:
  - Kuhn and Tucker's original paper
  - Cottle's paper on the history of Karush and the KKT theorem
  - Kjeldsen's paper on Kuhn-Tucker theorem and its relation to the second world war
6. hét, Március 17.: LP geometriája/Geometry of LP
- Beamer files: pdf file nyomtatható pdf file English pdf file handout pdf file
- Segédanyagok/Additional materials:
  - Shu-Cherng Fang's lecture in a course on LP (North Carolina State University, Fall 2011)
  - Geir Dahl's lecture notes on Convexity
  - John Nachbar's lecture notes on cones
  - Geir Dahl's lecture notes on Convexity és combinatorial optimization
7. hét, Március 24.: Feltételek egy politóp egész mivoltára/Integer polyhedra
- Beamer files: pdf file nyomtatható pdf file English pdf file handout pdf file
- Segédanyagok/additional materials:
  - A lecture note from University of Illinois (Chandra Chekuri)
  - A lecture note Stanford University (Jan Vondrák)
  - Pulleyblank's paper on the background of Edmonds' theorem
  - Edmonds' original paper
8. hét, Március 31.: Az Edmonds politóp tesztelése, Gomory-Hu-fák / Testing the Edmonds' polytope, Gomory-Hu trees
- Beamer files: pdf file handout file English pdf file handout pdf file
- Segédanyagok/additional materials:
  - 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
- Beamer files: pdf file handout file English pdf file handout pdf file
- Segédanyagok/additional materials:
  - 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.: Tavaszi szünet / Spring break, Április 21.: Húsvét / Easter

11. hét, Április 27.: Szemidefinit programozás: Alapok/Semidefinite programming: The basics
- Beamer files: pdf file handout file English pdf file English handout file
- Segédanyagok/additional materials:
  - 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)
12. hét, Május 5.: Szemidefinit programozás: Sajátértékek/Semidefinite programming: Eigenvalues
- Beamer files: pdf file handout file English pdf file English handout file
- Segédanyagok/additional materials:
  - Lovász László egy jegyzete gráfok sajátértékeiről
  - Frank de Zeuw 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
13. hét, Május 12.: Szemidefinit programozás: Vektor relaxációk/Semidefinite programming: vector relaxations
- Beamer files: pdf file handout file English pdf file English handout file
- Segédanyagok/additional materials:
  - 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)
14. hét, Május 19.: Heurisztikák/Heuristics
- Beamer files: pdf file English pdf file handout pdf file
- Segédanyagok/additional materials:
  - 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

Ha az előadással, gyakorlattal kapcsolatban bármilyen kérdés, megjegyzés, vélemény stb. felmerül, akkor azokat az hajnal@math.u-szeged.hu email címen érdeklődve várom.