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

2022 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, élek 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 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.
  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 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ú.
  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.
  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.