Optimalizálási eljárások, előadás
Tematika/vizsgakérdések, 2025 Tavasz
-
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).
-
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?
-
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).
-
Í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.
-
Í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.
-
Í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.
-
Í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.
-
Í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?
-
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.
-
Í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.
-
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.
-
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.
-
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.
-
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 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.
-
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.
-
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.
-
Í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.
-
Í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.
-
Í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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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!)