Programowanie półokreślone

Programowanie półokreślone ( SDP ) to poddziedzina optymalizacji wypukłej zajmująca się optymalizacją liniowej funkcji celu (funkcji określonej przez użytkownika, którą użytkownik chce zminimalizować lub zmaksymalizować) na przecięciu stożka dodatnich półokreślonych macierzy z przestrzenią afiniczną , tj. widmowy .

Programowanie półokreślone to stosunkowo nowa dziedzina optymalizacji, która cieszy się rosnącym zainteresowaniem z kilku powodów. Wiele praktycznych problemów w badaniach operacyjnych i optymalizacji kombinatorycznej można modelować lub przybliżać jako półokreślone problemy programowania. W teorii sterowania automatycznego SDP są używane w kontekście liniowych nierówności macierzowych . SDP są w rzeczywistości szczególnym przypadkiem programowania stożkowego i mogą być skutecznie rozwiązane metodami punktów wewnętrznych . Wszystkie programy liniowe i (wypukłe) programy kwadratowe można wyrazić jako SDP, a za pomocą hierarchii SDP można przybliżyć rozwiązania problemów optymalizacji wielomianowej. Programowanie półokreślone zostało wykorzystane w optymalizacji złożonych systemów. W ostatnich latach niektóre problemy złożoności zapytań kwantowych zostały sformułowane w kategoriach programów półokreślonych.

Motywacja i definicja

Wstępna motywacja

programowania liniowego to taki, w którym chcemy zmaksymalizować lub zminimalizować liniową funkcję celu zmiennych rzeczywistych w polytopie . W programowaniu półokreślonym zamiast tego używamy wektorów o wartościach rzeczywistych i możemy wziąć iloczyn skalarny wektorów; ograniczenia nieujemności dla zmiennych rzeczywistych w LP ( programowanie liniowe ) są zastępowane przez ograniczenia półoznaczoności dla zmiennych macierzowych w SDP ( programowanie półokreślone ). W szczególności ogólny problem programowania półokreślonego można zdefiniować jako dowolny problem programowania matematycznego o postaci

${\ Displaystyle {\ rozpocząć {tablica} {rl} {\ Displaystyle \ min _ {x ^ {1}, \ ldots, x ^ {n} \ w \ mathbb {R} ^ {n}} }& {\ Displaystyle \ suma _ {i, j \ w [n]} c_ {i, j} (x ^ {i} \ cdot x ^ {j})} \\ {\ tekst {z zastrzeżeniem}} & {\ Displaystyle \ suma _ {i, j \ w [n]} a_ {i, j, k} (x ^ {i} \ cdot x ^ {j}) \ równoważnik b_ {k}} {\ tekst {dla wszystkie }}k\\\end{tablica}}}$

do ${\ Displaystyle c_ {i, j}, a_ {i, j, k}}$ k $Displaystyle b_ {k}}$ są liczbami rzeczywistymi i ${\ Displaystyle x ^ {i} \ cdot x ^ {j}}$ jest iloczynem skalarnym ${\ Displaystyle x ^ {i}}$ i ${\ Displaystyle x ^ {j}}$ .

Równoważne preparaty

Mówi $że macierz$${\ displaystyle x ^ {1}, \ ldots, x ^ {n}}$ jest dodatnio półokreślona ​​jeśli jest Grama $x$ jeśli istnieją wektory n takie, że ${\ Displaystyle m_ {i, j} = x ^ {i} \ cdot x ^ {j}}$ dla wszystkich $\ Displaystyle i, j}$ ). W takim przypadku oznaczamy to jako ${\ Displaystyle M \ succeq 0}$ . Należy zauważyć, że istnieje kilka innych równoważnych definicji bycia dodatnią półokreśloną, na przykład dodatnie półokreślone macierze to samosprzężone , które mają tylko nieujemne wartości własne .

$przestrzeń$ przez wszystkich $_$ _ Przestrzeń jest wyposażona ${\ Displaystyle \ langle A, B \ rangle _ {\ mathbb {S} ^ {n}} = {\ rm {tr}} (A ^ {T} B) = \ suma _ {i = 1, j = 1 }^{n}A_{ij}B_{ij}.}$ wewnętrzny gdzie oznacza $ślad$ ) b

Możemy przepisać program matematyczny podany w poprzedniej sekcji równoważnie jako

${\ Displaystyle {\ rozpocząć {tablica} {rl} {\ Displaystyle \ min _ {X \ w \ mathbb {S} ^ {n}}} & \ langle C, X \ rangle _ {\ mathbb {S} ^ { n}}\\{\text{podlega}}&\langle A_{k},X\rangle _{\mathbb {S} ^{n}}\leq b_{k},\quad k=1,\ ldots ,m\\&X\succeq 0.\end{array}}}$

gdzie wpis ${\ Displaystyle i, j}$ w do ${\ displaystyle C}$ podany przez do $}$$\ Displaystyle {\ Frac {c_ {i, j} + c_ {j, ja}} {2}$$\ displaystyle$ z poprzedniej sekcji i $j}$$symetryczną$ mającą , th wpis ${\ Displaystyle {\ Frac {a_ {i, j, k} + a_ {j, i, k}} {2}}}$ z poprzedniej sekcji. $macierze są symetryczne$ macierze i $,$ a powyższe iloczyny wewnętrzne są dobrze

Zauważ, że jeśli odpowiednio dodamy zmienne typu slack , to SDP można przekonwertować na jedną z postaci

${\ Displaystyle {\ rozpocząć {tablica} {rl} {\ Displaystyle \ min _ {X \ w \ mathbb {S} ^ {n}}} & \ langle C, X \ rangle _ {\ mathbb {S} ^ { n}}\\{\text{podlega}}&\langle A_{k},X\rangle _{\mathbb {S} ^{n}}=b_{k},\quad k=1,\ldots ,m\\&X\succeq 0.\end{array}}}$

Dla wygody SDP można określić w nieco innej, ale równoważnej formie. Na przykład do specyfikacji programu można dodać wyrażenia liniowe obejmujące nieujemne zmienne skalarne . $)$$każdą$ zmienną można włączyć do macierzy $jako$ wpis ukośny ( dla Aby zapewnić, że ograniczenia $Displaystyle X_ {ii} \ geq 0}$${\ Displaystyle X_ {ij} = 0}$ można dodać dla wszystkich ${\ Displaystyle j \ neq i}$ . Jako inny przykład zauważ, że dla dowolnej dodatniej półokreślonej macierzy istnieje $wektorów$ takich , $że$$displaystyle$${\ displaystyle j}$ wpis ${\ displaystyle X}$ to ${\ Displaystyle X_ {ij} = (v_ {i}, v_ {j})}$ iloczyn skalarny v ${\ Displaystyle v_ {i}}$ i $}}$${\ Displaystyle v_ {$ . Dlatego SDP są często formułowane w kategoriach wyrażeń liniowych na iloczynach skalarnych wektorów. Biorąc pod uwagę rozwiązanie SDP w standardowej postaci, wektory można odzyskać w ${\ displaystyle \ {v_ {i} \}}$${\ Displaystyle O (n ^ {3})}$ czas (np. przy użyciu niepełnego rozkładu X Cholesky'ego).

Teoria dualizmu

Definicje

Analogicznie do programowania liniowego, mając ogólny SDP postaci

${\ Displaystyle {\ rozpocząć {tablica} {rl} {\ Displaystyle \min _{X\in \mathbb {S} ^{n}}}&\langle C,X\rangle _{\mathbb {S} ^{n}}\\{\text{z zastrzeżeniem}}&\ langle A_{i},X\rangle _{\mathbb {S} ^{n}}=b_{i},\quad i=1,\ldots ,m\\&X\succeq 0\end{array}}}$

(problem pierwotny lub P-SDP), definiujemy podwójny program półokreślony (D-SDP) jako

${\ Displaystyle {\ rozpocząć {tablica} {rl} {\ Displaystyle \ max _ {y \ w \ mathbb$

gdzie dla dowolnych dwóch macierzy i ${$$\ Displaystyle Q}$ , ${\ Displaystyle P \ succeq Q}$ P $\ Displaystyle PQ \ succeq 0}$ .

Słaby dualizm

Słabe twierdzenie o dualności stwierdza, że ​​​​wartość pierwotnego SDP jest co najmniej wartością podwójnego SDP. Dlatego każde wykonalne rozwiązanie dla podwójnego SDP ogranicza dolną granicę pierwotnej wartości SDP i odwrotnie, każde wykonalne rozwiązanie dla pierwotnego SDP ogranicza górną granicę podwójnej wartości SDP. To dlatego, że

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

gdzie ostatnia nierówność wynika z tego, że obie macierze są dodatnio półokreślone, a wynik tej funkcji jest czasami określany jako luka dualności.

Silna dwoistość

Gdy wartości pierwotnego i dualnego SDP są równe, mówi się, że SDP spełnia silną właściwość dualizmu . W przeciwieństwie do programów liniowych , gdzie każdy dualny program liniowy ma optymalny cel równy celowi pierwotnemu, nie każdy SDP spełnia silną dualność; ogólnie wartość dualnego SDP może leżeć ściśle poniżej wartości pierwotnej, a P-SDP i D-SPD spełniają następujące właściwości:

(i) Załóżmy, że pierwotny problem (P-SDP) jest ograniczony poniżej i ściśle wykonalny (tj. istnieje ${\ Displaystyle X_ {0} \ in \ mathbb {S} ^ {n}, X_ {0} \ succ 0}$ takie, że ${\ Displaystyle \ langle A_ {i}, X_ {0} \ rangle _ {\ mathbb {S} ^ {n}} = b_ {i}}$ , ${\ Displaystyle i = 1, \ ldots, m}$ ). Wtedy istnieje optymalne rozwiązanie do (D-SDP) i ${\ Displaystyle y ^ {*}}$

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

(ii) Załóżmy, że podwójny problem (D-SDP) jest ograniczony powyżej i ściśle wykonalny (tj. ${\ Displaystyle \ suma _ {i = 1} ^ {m} ( y_ {0}) _ {i} A_ {i} \ prec C}$ dla pewnego ${\ Displaystyle y_ {0} \ in \ mathbb {R} ^ {m}})$ . $)$ istnieje optymalne rozwiązanie dla i zachodzi równość z (i).

Warunkiem wystarczającym, aby silna dualność była spełniona dla problemu SDP (i ogólnie dla każdego problemu optymalizacji wypukłej) jest warunek Slatera . Możliwe jest również osiągnięcie silnej dualności dla SDP bez dodatkowych warunków regularności, stosując rozszerzony problem dualny zaproponowany przez Ramanę.

Przykłady

Przykład 1

Rozważ trzy zmienne losowe , $displaystyle$$B}$ i do {\ $}$ . $_$ definicji korelacji _

$} 1 i \ rho _ {AB} & \ rho _ {AC} \\ \rho _{AB}&1&\rho _{BC}\\\rho _{AC}&\rho _{BC}&1\end{pmatrix}}\succeq 0,}$

w takim przypadku macierz ta nazywana jest macierzą korelacji . Załóżmy, że wiemy z wcześniejszej wiedzy (na przykład empiryczne wyniki eksperymentu), że ${\ Displaystyle -0,2 \ równoważnik \ rho _ {AB} \ równoważnik -0,1}$ i ${\ Displaystyle 0,4 \ równoważnik \ rho _ {BC} \ równoważnik 0,5}$ . Problem określenia najmniejszych i największych wartości, które $\ Displaystyle \ rho _ {AC} \}$ może wziąć jest dana przez:

${\ Displaystyle {\ rozpocząć {tablica} {rl }{\ Displaystyle \ min /\ max} & x_ {13} \\ {\ tekst {z zastrzeżeniem}} & -0,2 \ równoważnik x_ {12} \ równoważnik -0,1 \\&0,4 \ równoważnik x_ {23} \ równoważnik 0.5\\&{\begin{pmatrix}1&x_{12}&x_{13}\\x_{12}&1&x_{23}\\x_{13}&x_{23}&1\end{pmatrix}}\succeq 0\end {szyk}}}$

ρ $Displaystyle \ rho _ {AB} = x_ {12}, \ \ rho _ {AC} = x_ {13}, \ \rho _{BC}=x_{23}}$ , aby uzyskać odpowiedź. Może to być sformułowane przez SDP. Poradzimy sobie z ograniczeniami nierówności, rozszerzając macierz zmiennych i wprowadzając na przykład zmienne luźne

$\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&0&1&0&0\\0&0&0&0&0&0\\0&0&0&0&0&0\end{array}}\right)\cdot \left({\begin{tablica}{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&0&0&s_{2}&0\\0&0&0&0&0&s_{3}\end{tablica}}\right)\right)=x_{12}+s_{1}=-0.1$

Rozwiązanie tego SDP daje wartości minimalne i maksymalne odpowiednio i ρ $= x_ {13} \ }$ Displaystyle \ rho _ {AC ${\ Displaystyle -0,978$$}$ .

Przykład 2

Rozważ problem

zminimalizować ${\ Displaystyle {\ Frac {(c ^ {T} x) ^ {2}} {d ^ {T} x}}}$

z zastrzeżeniem ${\ Displaystyle topór+b\geq 0}$

gdzie zakładamy, że ilekroć $0} re$${\ Displaystyle Ax + b \ geq$ }

Wprowadzając zmienną pomocniczą, problem można przeformułować: ${\ displaystyle t}$

zminimalizować ${\ displaystyle t}$

z zastrzeżeniem ${\ Displaystyle Ax + b \ geq 0, \, {\ Frac {(c ^ {T} x) ^{2}}{d^{T}x}}\równoważnik t}$

W tym sformułowaniu cel jest liniową funkcją zmiennych ${\ displaystyle x, t}$ .

Pierwsze ograniczenie można zapisać jako

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

gdzie macierz ${\ Displaystyle {\ textbf {diag}} (Ax + b)}$ jest macierzą kwadratową z wartościami na przekątnej równymi elementom wektora ${\ Displaystyle Ax +b}$ .

Drugie ograniczenie można zapisać jako

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

Definiowanie $następujący$ sposób

${\ Displaystyle D = \ lewo [{\ rozpocząć {tablica} {cc} t & c ^ {T} x \\ c ^ {T} x i d ^ {T} x \end{tablica}}\prawo]}$

Możemy użyć teorii dopełnień Schura, aby to zobaczyć

${\ Displaystyle D \ succeq 0}$

(Boyd i Vandenberghe, 1996)

Półokreślony program związany z tym problemem to

zminimalizować ${\ displaystyle t}$

z zastrzeżeniem ${\ Displaystyle \ lewo [{\ rozpocząć {tablica} {ccc} {\ textbf {diag} }(Ax+b)&0&0\\0&t&c^{T}x\\0&c^{T}x&d^{T}x\end{tablica}}\right]\succeq 0}$

Przykład 3 (algorytm aproksymacji maksymalnego cięcia Goemansa-Williamsona)

Programy półokreślone są ważnymi narzędziami do opracowywania algorytmów aproksymacji dla NP-trudnych problemów maksymalizacji. Pierwszy algorytm aproksymacyjny oparty na SDP jest autorstwa Michela Goemansa i Davida P. Williamsona (JACM, 1995). Zbadali problem maksymalnego cięcia : mając graf G = ( V , E ), wyprowadź podział wierzchołków V tak, aby zmaksymalizować liczbę krawędzi przecinających się z jednej strony na drugą. Ten problem można wyrazić jako całkowitoliczbowy program kwadratowy :

Maksymalizuj ${\ Displaystyle \ suma _ {(i, j) \ in E} {\ Frac {1-v_ {i} v_ {j}} {2 }},}$ takie, że każdy ${\ Displaystyle v_ {i} \ in \ {1, -1 \}}$ .

Jeśli P = NP , nie możemy skutecznie rozwiązać tego problemu maksymalizacji. Jednak Goemans i Williamson zaobserwowali ogólną trzyetapową procedurę ataku na tego rodzaju problem:

1. Zrelaksuj program całkowitoliczbowy do SDP.
2. Rozwiąż SDP (w granicach dowolnie małego błędu addytywnego ${\ displaystyle \ epsilon}$ ).
3. Zaokrąglij rozwiązanie SDP, aby uzyskać przybliżone rozwiązanie oryginalnego programu całkowitoliczbowego kwadratowego.

Dla maksymalnego cięcia najbardziej naturalny jest relaks

$v_ {j} \ rangle {2}},}$${\ Displaystyle \ max \ suma _ {(i, j) \ w E} {\ Frac {1- \ langle v_ {i}$${\ Displaystyle \ {v_ {i} \}}$ takie, że ${\ Displaystyle \ lVert v_ {i} \ rVert ^ {2} =$ 1 zamiast skalarów całkowitych.

Jest to SDP, ponieważ funkcja celu i ograniczenia są funkcjami liniowymi iloczynów wewnętrznych wektorów. Rozwiązanie SDP daje zestaw wektorów jednostkowych w ${\ displaystyle \ mathbf {R ^ {n}}}$ ; ponieważ wektory nie muszą być współliniowe, wartość tego swobodnego programu może być tylko wyższa niż wartość oryginalnego kwadratowego programu liczb całkowitych. Wreszcie, aby uzyskać podział, potrzebna jest procedura zaokrąglania. Goemans i Williamson po prostu wybierają jednolicie losową hiperpłaszczyznę przechodzącą przez początek układu współrzędnych i dzielą wierzchołki zgodnie z tym, po której stronie hiperpłaszczyzny leżą odpowiednie wektory. Prosta analiza pokazuje, że ta procedura osiąga oczekiwany efekt współczynnik aproksymacji (gwarantowanej wydajności) 0,87856 - ε. (Oczekiwana wartość cięcia to suma po krawędziach prawdopodobieństwa, że ​​krawędź zostanie przecięta, która jest proporcjonalna do kąta sałata $\ Displaystyle \ cos ^ {- 1} \ langle v_ {i}, v_ {j} \ rangle}$$między$ wektorami na końcach krawędzi nad Porównując to prawdopodobieństwo do ${\ Displaystyle (1- \ langle v_ {i}, v_ {j} \ rangle) / {2}}$ , w oczekiwaniu stosunek zawsze wynosi co najmniej 0,87856.) Zakładając przypuszczenie o unikalnych grach , może być wykazało, że ten współczynnik przybliżenia jest zasadniczo optymalny.

Od czasu oryginalnej pracy Goemansa i Williamsona, SDP zostały zastosowane do opracowania wielu algorytmów aproksymacyjnych. Niedawno Prasad Raghavendra opracował ogólne ramy dla problemów spełniania ograniczeń w oparciu o przypuszczenia o unikalnych grach .

Algorytmy

Istnieje kilka rodzajów algorytmów rozwiązywania SDP. Algorytmy te wyprowadzają wartość SDP aż do błędu addytywnego $}$ czasie, który jest wielomianem w rozmiarze opisu programu i ${\ Displaystyle \ log (1/\ epsilon)$ .

Istnieją również algorytmy redukcji twarzy, których można użyć do wstępnego przetwarzania problemów SDP poprzez sprawdzenie ograniczeń problemu. Można ich użyć do wykrycia braku ścisłej wykonalności, usunięcia zbędnych wierszy i kolumn, a także do zmniejszenia rozmiaru macierzy zmiennych.

Metody punktów wewnętrznych

Większość kodów bazuje na metodach punktów wewnętrznych (CSDP, MOSEK , SeDuMi, SDPT3 , DSDP, SDPA). Są one solidne i wydajne w przypadku ogólnych liniowych problemów SDP, ale są ograniczone przez fakt, że algorytmy są metodami drugiego rzędu i muszą przechowywać i rozkładać na czynniki dużą (i często gęstą) macierz. Teoretycznie najnowocześniejsze algorytmy SDP o wysokiej dokładności opierają się na tym podejściu.

Metody pierwszego rzędu

Metody pierwszego rzędu optymalizacji stożkowej unikają obliczania, przechowywania i rozkładania na czynniki dużej macierzy Hessego i skalowania do znacznie większych problemów niż metody punktów wewnętrznych, przy pewnym koszcie dokładności. Metoda pierwszego rzędu jest zaimplementowana w Splitting Cone Solver (SCS). Inną metodą pierwszego rzędu jest metoda mnożników w kierunku przemiennym (ADMM). Metoda ta wymaga w każdym kroku rzutowania na stożek półokreślonych macierzy.

Metoda pakietowa

Kod ConicBundle formułuje problem SDP jako problem optymalizacji niepłynnej i rozwiązuje go metodą optymalizacji niepłynnej Spectral Bundle. Podejście to jest bardzo efektywne w przypadku specjalnej klasy problemów liniowych SDP.

Inne metody rozwiązywania

Algorytmy oparte na metodzie rozszerzonego lagrangianu (PENSDP) zachowują się podobnie do metod punktu wewnętrznego i mogą być wyspecjalizowane w niektórych problemach o bardzo dużej skali. Inne algorytmy wykorzystują informacje niskiego rzędu i przeformułowanie SDP jako programowania nieliniowego (SDPLR).

Przybliżone metody

Zaproponowano również algorytmy rozwiązujące w przybliżeniu SDP. Głównym celem takich metod jest osiągnięcie mniejszej złożoności w aplikacjach, w których rozwiązania przybliżone są wystarczające, a złożoność musi być minimalna. Wybitną metodą stosowaną do wykrywania danych w systemach bezprzewodowych z wieloma wejściami i wieloma wyjściami (MIMO) jest Triangular Approximate SEmidefinite Relaxation (TASER), która działa na współczynnikach rozkładu Cholesky'ego macierzy półokreślonej zamiast macierzy półokreślonej. Ta metoda oblicza przybliżone rozwiązania problemu typu maksymalnego cięcia, które są często porównywalne z rozwiązaniami z dokładnych solwerów, ale tylko w 10-20 iteracjach algorytmu.

Aplikacje

Programowanie półokreślone zostało zastosowane do znalezienia przybliżonych rozwiązań problemów optymalizacji kombinatorycznej, takich jak rozwiązanie problemu maksymalnego cięcia ze współczynnikiem aproksymacji 0,87856. SDP są również używane w geometrii do wyznaczania wykresów tensegrity i pojawiają się w teorii sterowania jako LMI oraz w problemach odwrotnych współczynników eliptycznych jako wypukłe, nieliniowe ograniczenia półokreśloności. Jest również szeroko stosowany w fizyce do ograniczania konforemnych teorii pola za pomocą konforemnego ładowania początkowego .

• Lieven Vandenberghe, Stephen Boyd, „Programowanie półokreślone”, SIAM Review 38, marzec 1996, s. 49–95. pdf
• Monique Laurent, Franz Rendl, „Semidefinite Programming and Integer Programming”, Report PNA-R0210, CWI, Amsterdam, kwiecień 2002. optymalizacja-online
•   E. de Klerk, „Aspekty programowania półokreślonego: algorytmy punktów wewnętrznych i wybrane aplikacje”, Kluwer Academic Publishers, marzec 2002, ISBN 1-4020-0547-4 .
• Robert M. Freund, „Wprowadzenie do programowania półokreślonego (SDP), SDP-Introduction

Linki zewnętrzne

• Linki do prezentacji i wydarzeń w tej dziedzinie
• Notatki z wykładów László Lovásza na temat programowania półokreślonego