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

Tematika/vizsgakérdések, 2025 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).
  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?
  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).
  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.
  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.
  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.
  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.
  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?
  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.
  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.
  11. Egy konvex halmaz határpontja, támaszféltere, támaszhipersíkja és ezek kapcsola. Poliéderek lapjai. Csúcsok fogalma. Csúcsok jellemzése. Rendes poliéderek. A Minkowski-Weyl-tétel finomított alakja.
  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.
  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.
  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 tulajdonságát. Írja le egy példa-mátrixsereget, amely TU tulajdonságú. 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.
  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.
  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.
  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 tehetjük fel, hogy a tesztelendő vektor a csúcs-feltételeket egyenlőséggel teljesíti?
  18. Írja le egy gráf párosítási politópját. Mit értünk ennek tesztelési feladatán? Ha a tesztelendő vektor a csúcs-feltételeket egyenlőséggel teljesíti, akkor milyen vágási problémát kell megoldani? Definiálja a Gomori-Hu-fát. Hogyan lehet ebből kiolvasni vágási problémákra adott válaszokat? Igazolja a szubmoduláris lemmát. [A handout pdf file "Cuts" kivetítéstől a "Further Information in a Gomory–Hu Tree" kivetítésig és a "Introductory Lemma"+"Proof kivetítés." ]
  19. Í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. [A handout pdf file eleje a "Another Example" kivetítésig]
  20. 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. 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. [A handout pdf file a "Colorings, Cliques" kivetítéstől a "Two Sides of the Fulkerson—Chvatal Theorem" kivetítésig]
  21. 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.
  22. 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.
  23. 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.
  24. 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.
  25. 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!)