Félig határozott programozás

A félig meghatározott programozás (vagy az angolból SDP . Semidefinite programming ) a konvex programozás egy alszaka, amely egy lineáris célfüggvény optimalizálásával foglalkozik (a célfüggvény egy felhasználó által megadott függvény, amelynek értékét a felhasználó minimalizálni vagy maximalizálni szeretné) pozitív félig határozott mátrixok kúpjainak metszéspontja affin térrel .

A félig határozott programozás az optimalizálás viszonylag új területe, amely több okból is egyre nagyobb érdeklődést mutat. Az operációkutatás és a kombinatorikus optimalizálás területén számos gyakorlati probléma modellezhető vagy közelíthető félig meghatározott programozási problémaként. Az automatikus vezérlés elméletében az SDP-problémákat lineáris mátrixegyenlőtlenségekkel összefüggésben használják . Az SDP problémák valójában a kúpos programozás speciális esetei , és hatékonyan megoldhatók a belső pont módszerrel . Minden lineáris programozási problémaSDP-problémákként fejezhetők ki, és SDP-problémahierarchiák segítségével közelíthetők a polinomiális optimalizálási problémák megoldásai. A félig határozott programozást komplex rendszerek optimalizálására használják . Az elmúlt években néhány kvantumlekérdezés-bonyolultsági probléma megfogalmazódott a félig meghatározott programozás szempontjából.

Motiváció és meghatározás

Kezdeti motivációk

A lineáris programozási probléma olyan probléma, amelyben maximalizálni vagy minimalizálni kell a valós változók lineáris célfüggvényét egy poliéderen . A félig határozott programozásban helyette valós vektorokat használunk, és megengedett a vektorok pontszorzatának használata. Az LP-probléma valós változóinak nem-negativitásának feltételét az SDP-probléma változóinak mátrixára vonatkozó félig meghatározottsági megszorítások váltják fel. Közelebbről, egy általános félig meghatározott programozási probléma az űrlap bármely matematikai programozási problémájaként definiálható

{\min _{x^{1},\ldots ,x^{n}\in \mathbb {R} ^{n))}{\sum _{i,j\in [n]}c_ {i,j}(x^{i}\cdot x^{j})}

feltételek mellett

{\sum _{i,j\in [n]}a_{i,j,k}(x^{i}\cdot x^{j})\leq b_{k}\qquad \forall k }.

Egyenértékű megfogalmazások

Egy mátrixot akkor mondunk pozitív félig meghatározottnak, ha egyes vektorok Gram-mátrixa (vagyis ha vannak olyan vektorok , amelyek mindegyikére ). Ha ez igaz, akkor jelöljük . Vegye figyelembe, hogy a pozitív félig meghatározottságnak van néhány más ekvivalens definíciója is, például a pozitív félig meghatározott mátrixok csak nem negatív sajátértékekkel rendelkeznek, és pozitív félig határozott négyzetgyökük van. $n\szer n$ $M$ ${\displaystyle x^{1},\ldots ,x^{n))$ ${\displaystyle m_{i,j}=x^{i}\cdot x^{j))$ $i,j$ $M \siker 0$

Jelölje az összes valós szimmetrikus mátrix terével. Ebben a térben van egy belső termék (ahol nyomot jelent ) ${\mathbb {S}}^{n}$ $n\szer n$ $\langle A,B\rangle _{\mathbb {S} ^{n}}={\rm {tr}}(A^{T}B)=\sum _{i=1,j=1 }^{n}A_{ij}B_{ij}.$ ${\rm {tr))$

A matematikai programozási feladatot átírhatjuk az előző részből ekvivalens formában

{\min _{X\in \mathbb {S} ^{n))}\langle C,X\rangle _{\mathbb {S} ^{n))

feltételek mellett

{\begin{array}{ll}{\displaystyle \langle A_{k},X\rangle _{\mathbb {S} ^{n))\leq b_{k},\quad k=1, \ldots ,m}\\X\succeq 0\end{array}}

ahol a mátrix elem egyenlő az előző szakaszból származó elemmel, és egy olyan mátrix, amely az előző szakaszból származó értéket tartalmazza mátrixelemként. $i,j$ $C$ $c_{i,j}$ $A_k$ $n\szer n$ $i,j$ ${\displaystyle a_{i,j,k))$

Vegye figyelembe, hogy ha megfelelően hozzáadunk további változókat , akkor ez az SDP feladat konvertálható

{\displaystyle \min _{X\in \mathbb {S} ^{n))}\langle C,X\rangle _{\mathbb {S} ^{n))

feltételek mellett

{\begin{array}{ll}\langle A_{k},X\rangle _{\mathbb {S} ^{n))=b_{k},\quad k=1,\ldots ,m \\X\succeq 0\end{array}}

A kényelem kedvéért az SDP-probléma kissé eltérő, de egyenértékű formában definiálható. Például nemnegatív skalárváltozókat használó lineáris kifejezések hozzáadhatók a feladatspecifikációhoz. A feladat továbbra is SDP marad, mivel minden változó átlós elemként szerepelhet a mátrixban ( egyeseknél ). Ennek biztosítása érdekében korlátozásokat adhat meg mindenre . Egy másik példaként jegyezzük meg, hogy bármely pozitív félig meghatározott mátrixhoz létezik egy olyan vektorhalmaz , amelyre a mátrix eleme egyenlő , a vektorok skaláris szorzata és . Így az SDP-problémákat gyakran a vektorok skaláris szorzatainak lineáris kifejezései alapján fogalmazzák meg. Ha az SDP-probléma szabványos formában megoldódik, a vektorok időben rekonstruálhatók (például a Cholesky X mátrix nem teljes dekompozíciójával). $x$ ${\displaystyle X_{ii))$ $én$ $X_{ii}\geq 0$ $X_{ij}=0$ $j\neq i$ $x$ $\{v_{i}\}$ $én$ $j$ $x$ $X_{ij}=(v_{i},v_{j})$ $v_{i}$ $v_{j}$ $\{v_{i}\}$ $O(n^{3})$

Dualitáselmélet

Definíciók

Hasonlóan a lineáris programozáshoz, ha az SDP általános problémát a formában adjuk meg

\min _{X\in \mathbb {S} ^{n}}\langle C,X\rangle _{\mathbb {S} ^{n}}

feltételek mellett

{\begin{array}{ll}\langle A_{i},X\rangle _{\mathbb {S} ^{n))=b_{i},\quad i=1,\ldots ,m \\X\succeq 0\end{array}}

(közvetlen probléma vagy P-SDP), a kettős félig meghatározott problémát (D-SDP) a következőképpen definiáljuk

\max _{y\in \mathbb {R} ^{m}}\langle b,y\rangle _{\mathbb {R} ^{m}}

feltételek mellett

{\begin{array}{ll}{\displaystyle \sum _{i=1}^{m}}y_{i}A_{i}\preceq C\end{array}}

Ahol bármely két mátrix és , azt jelenti . $P$ $K$ $P\succeq Q$ $PQ\succeq 0$

Gyenge kettősség

A gyenge dualitás tétele kimondja, hogy az elsődleges SDP értéke nem kisebb, mint a duális SDP értéke. Így a kettős SDP probléma bármely megengedhető megoldása alulról korlátozza a közvetlen SDP értékét, és fordítva, a közvetlen SDP probléma bármely megengedhető értéke felülről korlátozza a kettős SDP értékét. Ez azért történik, mert

\langle C,X\rangle -\langle b,y\rangle =\langle C,X\rangle -\sum _{i=1}^{m}y_{i}b_{i}=\langle C,X\rangle -\sum _{i=1}^{m}y_{i}\langle A_{i},X\rangle =\langle C-\sum _{i=1}^{m}y_ {i}A_{i},X\rangle \geq 0,

ahol az utolsó egyenlőtlenség azt a tényt tükrözi, hogy mindkét mátrix pozitív félig határozott. Ennek a függvénynek az értékét néha dual gap-nek is nevezik.

Erős kettősség

A Slater - feltételként ismert feltétel mellett az elsődleges és a kettős SDP-probléma értéke egyenlő. Ezt erős kettősségnek hívják . A lineáris programozási problémákkal ellentétben nem minden SDP-probléma szigorú kettősséggel rendelkezik. Általános esetben a kettős probléma SDP értéke szigorúan kisebb lehet, mint a közvetlen probléma értéke.

(i) Tételezzük fel, hogy a közvetlen probléma (P-SDP) alulról korlátos és szigorúan megengedhető (vagyis létezik olyan, hogy , ). Akkor van egy optimális megoldás a kettős problémára (D-SDP) és $X_{0}\in \mathbb {S} ^{n},X_{0}\succ 0$ ${\displaystyle \langle A_{i},X_{0}\rangle _{\mathbb {S} ^{n))=b_{i))$ $i=1,\ldots ,m$ $y^{*}$

\langle C,X^{*}\rangle _{\mathbb {S} ^{n))=\langle b,y^{*}\rangle _{\mathbb {R} ^{m)) .

(ii) Tételezzük fel, hogy a kettős probléma (D-SDP) felülről korlátos és szigorúan megengedhető (azaz egyeseknél ). Ekkor van egy optimális megoldás a közvetlen problémára (P-SDP), és az (i) egyenlőség teljesül. $\sum _{i=1}^{m}(y_{0})_{i}A_{i}\prec C$ ${\displaystyle y_{0}\in \mathbb {R} ^{m))$ $X^{*}$

Példák

1. példa

Tekintsünk három valószínűségi változót , és . Definíció szerint korrelációs együtthatóik akkor és csak akkor érvényesek $A$ $B$ $C$ $\rho _{AB},\ \rho _{AC},\rho _{BC}$

{\begin{pmatrix}1&\rho _{AB}&\rho _{AC}\\\rho _{AB}&1&\rho _{BC}\\\rho _{AC}&\rho _ {BC}&1\end{pmatrix}}\succeq 0

Tegyük fel, hogy bizonyos forrásokból (például empirikus vagy kísérleti adatokból) tudjuk, hogy és . A legkisebb és legnagyobb érték meghatározásának problémája a következőképpen írható fel: $-0.2\leq \rho _{AB}\leq -0.1$ $0.4\leq \rho _{BC}\leq 0.5$ $\rho _{AC}\$

minimalizálni/maximálni

x_{13}

feltételek mellett

-0,2\leq x_{12}\leq -0,1

0.4\leq x_{23}\leq 0.5

x_{11}=x_{22}=x_{33}=1\

{\begin{pmatrix}1&x_{12}&x_{13}\\x_{12}&1&x_{23}\\x_{13}&x_{23}&1\end{pmatrix}}\succeq 0

Itt elfogadjuk . A probléma SDP problémaként is megfogalmazható. Az egyenlőtlenségeket a változók mátrixának kibővítésével és további változók bevezetésével egészítjük ki, pl. ${\displaystyle \rho _{AB}=x_{12},\ \rho _{AC}=x_{13},\ \rho _{BC}=x_{23))$

$\mathrm {tr} \left(\left({\begin{array}{cccccc}0&1&0&0&0&0\\0&0&0&0&0&0\\0&0&0&0&0\\0&0&0&1&0&0&0\\0&0&0&0&0&0\0&0&0&0&ray) \left({\begin{array}{cccccc}1&x_{12}&x_{13}&0&0&0\\x_{12}&1&x_{23}&0&0&0\\x_{13}&x_{23}&1&0&0&0\\0&0&0&s_{1} \\0&0&0&0&s_{2}&0\\0&0&0&0&0&s_{3}\end{array}}\right)\right)=x_{12}+s_{1}=-0,1$

Az SDP-probléma megoldása után megkapjuk a minimális és maximális értékeket ( illetve ). $\rho _{AC}=x_{13}\$ $-0,978$ $0,872$

2. példa

Fontolja meg a problémát

minimalizálni

{\frac {(c^{T}x)^{2}}{d^{T}x}}

feltételek mellett

Ax+b\geq 0

ahol azt feltételezik, hogy at . $d^{T}x>0$ $Ax+b\geq 0$

Egy további változó bevezetésével átírjuk a problémát a következő formában: $t$

minimalizálni

t

feltételek mellett

Ax+b\geq 0,\,{\frac {(c^{T}x)^{2}}{d^{T}x}}\leq t

Ebben a megfogalmazásban a célfüggvény két változó lineáris függvénye ( ). $x,t$

Az első megszorítás átírható a következőre:

{\textbf {diag}}(Ax+b)\geq 0

ahol a mátrix egy négyzetmátrix, amelynek az átlóján lévő értékek megegyeznek a vektor elemeivel . ${\textbf {diag}}(Ax+b)$ $A+b$

A második megszorítást így írhatjuk fel

td^{T}x-(c^{T}x)^{2}\geq 0

A mátrixot a következőképpen definiáljuk $D$

D=\left[{\begin{array}{cc}t&c^{T}x\\c^{T}x&d^{T}x\end{array}}\right]

Ennek bemutatására használhatjuk Schur komplementelméletét

D\succeq 0

[egy]

Ennek a feladatnak a félig határozott programozási problémája a következő formában lesz

minimalizálni

t

feltételek mellett

\left[{\begin{array}{ccc}{\textbf {diag}}(Ax+b)&0&0\\0&t&c^{T}x\\0&c^{T}x&d^{T}x\ end{array}}\right]\succeq 0

3. példa (Goemans-Williamson MAX CUT Approximációs algoritmus)

A félig határozott programozás fontos eszköz az NP-kemény maximalizálási problémák közelítő algoritmusainak létrehozásához. Az első SDP-n alapuló közelítő algoritmust Michel Goemans és David Williamson javasolta [2] . Tanulmányozták a MAX CUT problémát : Adott egy G = ( V , E ) gráf, V csúcsait két részre kell osztani úgy, hogy maximalizálja a két részt összekötő élek számát. A probléma egész szám másodfokú programozási problémaként fogható fel :

Maximalizálja bármelyik tárgyat .

\sum _{(i,j)\in E}{\frac {1-v_{i}v_{j}}{2}},

{\displaystyle v_{i}\in \{1,-1\))

én

Ha nem P = NP , ezt a problémát nem tudjuk hatékonyan megoldani. Goemans és Williamson azonban felvázoltak egy három lépésből álló eljárást az ilyen jellegű problémák megtámadására:

Az egész szám másodfokú programozási problémáját az SDP problémává gyengítjük .
Megoldjuk az SDP problémát (bármilyen kis hibával ). $\epsilon$
Lekerekítjük az SDP feladat megoldását, hogy megközelítő megoldást kapjunk az egész másodfokú programozás eredeti problémájára.

A MAX CUT probléma esetén a legtermészetesebb relaxáció az

\max \sum _{(i,j)\in E}{\frac {1-\langle v_{i},v_{j}\rangle }{2)),

for , ahol a maximalizálás vektorokon keresztül történik, nem pedig skaláris egész változókon.

\lVert v_{i}\rVert ^{2}=1

\{v_{i}\}

A probléma SDP probléma, mert mind a célfüggvény, mind a megszorítások a vektorok skaláris szorzatának lineáris függvényei. Az SDP probléma megoldása egységvektorok halmazát adja meg -ben . Mivel a vektorok nem feltétlenül kollineárisak, a relaxált feladat értéke csak nagyobb lehet, mint az eredeti egész szám másodfokú programozási feladat értéke. A felosztáshoz egy végső kerekítési eljárásra van szükség. Goemans és Williamson véletlenszerű hipersíkot választanak (egyenletes eloszlást használva) az origón keresztül, és felosztják a csúcsokat a síkhoz viszonyított elhelyezkedésük alapján. A közvetlen elemzés azt mutatja, hogy ez az eljárás biztosítja a 0,87856 - ε várható közelítési tényezőt . (A vágás várható értéke egyenlő annak a valószínűségnek az összes élére eső összegével, hogy az él bekerül a vágásba, és ez a várakozás arányos az él végcsúcsánál lévő vektorok közötti szöggel. Ha ezt a valószínűséget összehasonlítjuk , az arány elvárása mindig legalább 0,87856 lesz.) Az egyedi játék helyességi hipotézisét feltételezve kimutatható, hogy ennek a közelítésnek a közelítési együtthatója főként optimális. $\mathbf {R^{n}}$ $\cos ^{-1}\langle v_{i},v_{j}\rangle$ ${\displaystyle (1-\langle v_{i},v_{j}\rangle )/{2))$

Goemans és Williamson cikkének megjelenése óta az SDP-problémákat számos közelítő algoritmus kifejlesztésére alkalmazták. A közelmúltban Prasad Raghavendra kidolgozott egy általános sémát a kényszer-elégedettségi problémákra az egyedi játékhipotézis [3] alapján .

Algoritmusok

Az SDP problémák megoldására többféle algoritmus létezik. Ezeknek az algoritmusoknak az eredménye az SDP-probléma -ig terjedő értéke , amelyet egy olyan idő alatt kapunk, amely polinomiálisan függ a feladat méretétől és . $\epsilon$ $\log(1/\epsilon )$

Interior Point Methods

A legtöbb megoldási rendszer a belső pont módszerre épül (CSDP, SeDuMi, SDPT3, DSDP, SDPA), amely robusztus és hatékony az általános lineáris SDP problémák megoldására. A megközelítést korlátozza az a tény, hogy az algoritmusok másodrendű módszerek, és nagy (és gyakran sűrű) mátrixokat igényelnek a memorizáláshoz és a felbontáshoz.

Elsőrendű módszerek

A kúpos optimalizálás elsőrendű módszerei elkerülik a nagy Hess-mátrixok tárolását és felbontását, és sokkal nagyobb problémákra alkalmazhatók, mint a belső pont módszerek, a pontosság elvesztése árán. A módszer az "SCS megoldó" rendszerben valósul meg.

A sugármódszer

Az SDP-probléma nem sima optimalizálási problémaként van megfogalmazva, és spektrális nyalábos módszerrel oldja meg. Ez a megközelítés nagyon hatékony a lineáris SDP problémák bizonyos osztályaiban.

Egyéb

Az általánosított Lagrange-módszeren (PENSDP) alapuló algoritmusok viselkedésükben hasonlóak a belső pont módszerekhez, és néhány nagyon nagy problémára adaptálhatók. Más algoritmusok alacsony szintű információkat használnak, és az SDP -problémát nemlineáris programozási problémaként (SPDLR) fogalmazzák újra.

Alkalmazások

A félig határozott programozást alkalmazták a kombinatorikus optimalizálási problémák közelítő megoldásainak megtalálására, például a maximális vágási feladat megoldására 0,87856 - os közelítési tényezővel . Az SDP-problémákat a geometriában is használják tensegrity gráfok meghatározására, és a vezérléselméletben lineáris mátrixegyenlőtlenségekként jelennek meg .

Irodalom

Lieven Vandenberghe, Stephen Boyd. Semidefinite Programming // SIAM Review 38. - 1996. - március. - S. 49-95 .
Monique Laurent, Franz Rendl. Félig meghatározott programozás és egészszámú programozás/jelentés PNA-R0210, CWI, Amszterdam . - 2002. - április.
E. de Klerk. A félig meghatározott programozás szempontjai: Belső pont algoritmusok és kiválasztott alkalmazások. - Kluwer Academic Publishers, 2002. - ISBN 1-4020-0547-4 .
P. Raghavendra. Optimális algoritmusok és megközelíthetetlenségi eredmények minden CSP-hez? // Proceedings of the 40th Annual ACM Symposium on theory of Computing (Victoria, British Columbia, Kanada, 2008. május 17–20.). STOC'08 . - New York, NY: ACM, 2008. - S. 245-254.
Robert M Freund. Bevezetés a félig meghatározott programozásba (SDP) .
Michel X. Goemans, David P. Williamson. Továbbfejlesztett közelítő algoritmusok maximális vágási és kielégítési problémákhoz félig meghatározott programozással // JACM. - 1995. - november ( 42. évf. , 6. szám ). - S. 1115-1145 . doi : 10.1145 / 227683.227684 .

Linkek

Linkek bemutatkozásokhoz és a szakterület eseményeihez
Lovász László előadási jegyzetei a félig határozott programozásról

Optimalizálási módszerek
Egydimenziós	aranymetszet módszer Kettősség Parabola módszer Rács keresés Egységes blokkkeresési módszer Fibonacci módszer Háromszoros keresés Piyavsky módszer Strongin módszer
Nulla sorrend	Gauss módszer Nelder-Mead módszer Hook-Jeeves módszer Rosenbrock módszer Powell-módszer
Első rendelés	gradiens süllyedés Zeutendijk módszer Koordináta süllyedés Konjugált gradiens módszer Kvázi-Newtoni módszerek Levenberg-Marquardt algoritmus
másodrendű	Newton módszere Newton-Raphson módszer Broyden-Fletcher-Goldfarb-Shanno algoritmus (BFGS)
Sztochasztikus	Monte Carlo módszer Szimulált lágyítás Evolúciós algoritmusok differenciális evolúció Hangya algoritmus Részecskeraj módszer Méhtelep algoritmus Véletlenszerű séta módszer
Lineáris programozási módszerek	Simplex módszer Gomori algoritmusa Ellipszoid módszer Potenciális módszer
Nemlineáris programozási módszerek	Szekvenciális kvadratikus programozás