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

2021 Tavasz

  1. Mi az optimalizálás alapfeladata? Mit értünk lineáris programozáson (LP)? Adjon példát olyan optimalizálási feladatra, amely LP feladatként fogalmazható meg (nem triviális módon). [Videó: 1. témakör 1. rész + 2. rész]
  2. Mi az optimalizálás alapfeladata? Mit értünk kvadratikus programozáson (QP)? Mikor mondjuk, hogy egy QP probléma konvex? Adjon példát olyan optimalizálási feladatra, amely QP feladatként fogalmazható meg (nem triviális módon). Konvex-e példája? [Videó: 1. témakör 1. rész + 3. rész]
  3. Mi az optimalizálás alapfeladata? Mit értünk egész értékű programozáson (IP)? Adjon példát olyan optimalizálási feladatra, amely IP feladatként fogalmazható meg (nem triviális módon). [Videó: 1. témakör 1. rész + 3. rész]
  4. Írja le, hogy kaphatjuk egy primál feladat Lagrange-féle duálisát. Mit jelöltünk p*-gal, d*-gal? Mondja ki a gyenge dualitás tételt. Milyen normálformáit ismeri az LP feladatnak? Lineáris függvény globális minimalizálása Rn-en. Az egyik LP normálformát dualizálja. [Videó: 2. témakör 1. rész + 2. rész]
  5. Írja le, hogy kaphatjuk egy primál feladat Lagrange-féle duálisát. Mit jelöltünk p*-gal, d*-gal? Mondja ki a gyenge dualitás tételt. Homogén kvadratikus függvény globális minimalizálása Rn-en. Egy QP alakra hozható problémát dualizáljon. [Videó: 2. témakör 1. rész + 2. rész]
  6. Írja le, hogy kaphatjuk egy primál feladat Lagrange-féle duálisát. Milyen normákat ismer? Definiálja a duális norma fogalmát. Dualizálja a norma minimalizálás problémáját lineáris feltételek mellett. [Videó: 2. témakör 1. rész + 3. rész]
  7. Írja le, hogy kaphatjuk egy primál feladat Lagrange-féle duálisát. Definiálja egy valós értékű függvény konvex konjugáltjának fogalmát. Dualizálja egy célfüggvény minimalizálás problémáját lineáris feltételek mellett. [Videó: 2. témakör 1. rész + 3. rész]
  8. Írja fel a Slater-tétel feltételeit. E és F halmazokat definiálja és adja meg alapvető tulajdonságaikat. Mondja ki a konvex halmazokra vonatkozó szeparációs tételt. Írja fel ennek következményét a Slater-tétel bizonyításában. Milyen esetben vagyunk "majdnem kész" és miért? [Videó: 3. témakör 1. rész]
  9. Ha van primál és duális optimális hely, akkor egyetlen egyenlőtlenségsorozatként igazolja a gyenge dualitás tételt. Elemezze az egyenlőség esetét (természetesen ha szükséges, akkor bizonyos feltételek mellett). Írja fel a KKT feltételeket és mondja ki a Karush-Kuhn-Tucker-tételt. Igazolja a tételt. [Videó: 3. témakör 2. rész]
  10. Írja le az Ax=0, Ax=b, Ax<=0, Ax<=b feltételrendzserek megoldáshalmazát, definiálja a szükséges alapfogalmakat: lineáris altér, affin altér, poliedrikus kúp, poliéder. AB szakasz, AB egyenes leírása vektorokkal. Lineáris kombináció, affin kombináció, kúp kombináció, konvex kombináció fogalma. Poliedrikus kúp, poliéder alternatív leírása: Minkowski-Weyl-tétel kimondása. [Videó: 4. témakör 1. rész]
  11. Egy konvex halmaz határpontja, támaszféltere, támaszhipersíkja és ezek kapcsola. Poliéderek lapjai. Csúcsok, élek fogalma. Csúcsok jellemzése. Rendes poliéderek. A Minkowski-Weyl-tétel finomított alakja. [Videó: 4. témakör 2. rész]
  12. LP feladat rendes poliédereken: A csúcsok és optimális helyek kapcsolata (tétel és bizonyítás). LP feladat egész együtthatós feltételek mellett: a tétel kimondása és igazolása. [Videó: 4. témakör 3. rész]
  13. Definiálja az IP alapfeladatot. Mit értünk egy IP alapfeladat LP relaxációján? Mi az eredeti és a relaxált feladat optimális értéke közötti kapcsolat? Mikor nevezünk egy rendes poliédert egésznek? Mondja ki az Edmonds-Giles-tételt. Igazolja az Edmonds-Giles-tételt. [Videó: 5. témakör 1. rész]
  14. Definiálja az IP alapfeladatot. Mit értünk egy IP alapfeladat LP relaxációján? Mi az eredeti és a relaxált feladat optimális értéke közötti kapcsolat? Mikor nevezünk egy rendes poliédert egésznek? Definiálja mátrixok TU tualjdonságát. Írja le az előadáson tárgyalt két példa-mátrixsereget, amely TU tulajdonságú. Egyik esetben igazolja is ezt. Ha egy poliédert leíró egyenlőtlenségrendszer mátrixa TU tulajdonságú, konstansai egészek, akkor a poliéder is egész. Igazolja ezt. Adjon egy alkalmazását ennek a tételnek. [Videó: 5. témakör 2. rész]
  15. Definiálja az IP alapfeladatot. Mit értünk egy IP alapfeladat LP relaxációján? Mi az eredeti és a relaxált feladat optimális értéke közötti kapcsolat? Mikor nevezünk egy rendes poliédert egésznek? Definiálja egyenlőtlenségrendszerek TDI tulajdonságát. Mondja ki a korábbi Edmonds-Giles tételt és vezesse le ebből, hogy egy TDI rendszer egész poliédert ír le. [Videó: 5. témakör 3. rész]
  16. Definiálja az IP alapfeladatot. Mit értünk egy IP alapfeladat LP relaxációján? Mi az eredeti és a relaxált feladat optimális értéke közötti kapcsolat? Mikor nevezünk egy rendes poliédert egésznek? Definiálja egyenlőtlenségrendszerek TDI tulajdonságát. Definiálja a párosítási politópot. Mondja ki Edmonds tételét erre a politópra. Ha ezt a tételt mint két tartalmazás tekinti, akkor melyik egyszerű és miért. Mondja ki a Cunningham-Marsh-tételt. [Videó: 5. témakör 3. rész]
  17. Írja le egy gráf párosítási politópját. Mit értünk ennek tesztelési feladatán? Mi a tesztelési algoritmus naív kezdése? Miért nem lehet naívan befejezni a tesztelést? Írja le és indokolja, hogy miért tehető fel, hogy a tesztelendő vektor a csúcs-feltételeket egyenlőséggel teljesíti, továbbá csúcshalmaza páros elemszámú. [Videó: 6. témakör 1. rész]
  18. Írja le egy gráf párosítási politópját. Mit értünk ennek tesztelési feladatán? Mi a tesztelési algoritmus naív kezdése? Tegyük fel, hogy a tesztelendő vektor a csúcs-feltételeket egyenlőséggel teljesíti. Ebben az esetben fogalmazzuk át a tesztelési feladatot mint egy vágás probléma. Milyen vágási problémákra emlékszik? Mi a bolyolultséguk? Definiálja a Gomori-Hu-fát. Hogyan lehet ebből kiolvasni vágási problémákra adott válaszokat. [Videó: 6. témakör 2. rész]
  19. Írja le egy gráf párosítási politópját. Mit értünk ennek tesztelési feladatán? Definiálja egy gráf Gomory-Hu-fáját. Mondja ki a főlemmát és igazolja. Bizonyítása igazolja a szubmoduláris tulajdonságot is (az alkalmas függvényre). Írja le azt a szabdalási eljárást, ami outputja a Gomory-Hu-fa. [Videó: 6. témakör 3. rész]
  20. Írja le egy gráf független ponthalmazainak PP politópját. Adjon "felső becslést" erre a politópra. Definiálja a klikk feltételeket. Adjon példákat, ahol a felső becslései pontosak, illetve olyanokat ahol nem pontosak. [Videó: 7. témakör 1. rész]
  21. Definiálja a szép és perfekt gráfokat. Adjon példákat perfekt gráfokra és nem perfekt gráfokra. Mondja ki az erős és gyenge perfekt gráf sejtést/tételt. Adjon alternatív definíciókat a perfekt gráf tulajdonságra ((*) és (*+) tulajdonságok). Definiálja egy perfekt gráf klikkekkel történő felfújását. Igazolja, hogy így perfekt gráfot kapunk. [Videó: 7. témakör 2.+3. rész]
  22. Mondja ki a gyenge perfekt gráf sejtést/tételt. Mondja ki a Chvatal-Fulkerson-tételt. Írja fel az előadás két állítását, amelyból mindkét fenti tétel adódik. Válassza ki az egyiket és igazolja azt. [Videó: 7. témakör 2.+3. rész]
  23. Pozitív szemidefinit mátrixok leírásai. Belsőszorzat a szimmetrikus mátrixok terén. Definiálja a szemidefinit programozás alapfeladatát. Normálformák. [Videó: 8. témakör 1. rész]
  24. A Lagrange-féle dualizálási eljárás az SDP-re. Poszitív szemindefinit mátrixok jellemzése a belsőszorzat segítségével. [Videó: 8. témakör 2. rész]
  25. Sajátértékek és SDP. alfa(G) és khi (G) paraméterek, alfa(G) sajátértékes becslése (Hoffman-tétel). A becslés kisajtolása. [Videó: 9. témakör 1. + 2. rész]
  26. Gráfok Shannon-kapacitása, elemi becslések. Gráfok ortogonális reprezentációja. C5 és az esernyő konstrukció. Lovász-féle theta függvény. [Videó: 10. témakör 1. rész]
  27. Kombinatorikus feladatok vektor relaxációja, approximációs algoritmusok SDP technikával: Goemans-Williamson-algoritmus !VAGY! 3-kromatikus gráfok színezése. (Saját választás!) [Videó: 10. témakör 3 VAGY 4. rész]
  28. Branch and bound módszer általános leírása. Egy konkrét példán való bemutatása (a példa szabadon választható a videókból). [Videó: 11. témakör 1. VAGY 2. rész]
  29. Ellipszoidok n-dimenzióban, definíció. Lineáris célfüggvény optimalizálása ellipszoidon. Fél gömb befoglalása minimális térfogatú ellipszoidba. Bináris keresés magasabb dimenzióban. [Videó: 12. témakör 1. rész]