Optymalizacja sumy kwadratów

Ten artykuł dotyczy ograniczeń sumy kwadratów. Aby zapoznać się z problemami z funkcjami kosztów sumy kwadratów, zobacz Najmniejsze kwadraty .

Program optymalizacji sumy kwadratów to problem optymalizacyjny z liniową funkcją kosztu i szczególnym rodzajem ograniczeń na zmienne decyzyjne. Więzy te mają taką postać, że gdy zmienne decyzyjne są używane jako współczynniki w pewnych wielomianach , wielomiany te powinny mieć właściwość wielomianu SOS . Podczas ustalania maksymalnego stopnia zaangażowanych wielomianów optymalizacja sumy kwadratów jest również znana jako hierarchia relaksacji Lasserre'a w programowaniu półokreślonym .

Techniki optymalizacji sumy kwadratów zostały zastosowane w różnych dziedzinach, w tym w teorii sterowania (w szczególności do poszukiwania wielomianowych funkcji Lapunowa dla układów dynamicznych opisanych wielomianowymi polami wektorowymi), statystyce, finansach i uczeniu maszynowym.

Kwestia optymalizacji

Problem można wyrazić jako

$${\ Displaystyle \ max _ {u \ w \ mathbb {R} ^ {n}} c ^ {T} u}$$

z zastrzeżeniem

$${\ Displaystyle a_ {k, 0} (x) + a_ {k, 1} (x) u_ {1} + \ cdots + a_ {k, n} (x) u_ {n} \ w {\ tekst {SOS }}\quad (k=1,\ldots ,N_{s}).}$$

Tutaj „SOS” reprezentuje klasę wielomianów sumy kwadratów (SOS). Wektor $} {\ Displaystyle \ {a_$ wielomiany $k, j} \}$ część dane do problemu optymalizacyjnego. Ilości są zmiennymi decyzyjnymi ${\ displaystyle u \ in \ mathbb {R} ^ {n}} .$ Programy SOS można konwertować na programy półokreślone (SDP) przy użyciu dualności programu wielomianu SOS i relaksacji dla optymalizacji wielomianu z ograniczeniami przy użyciu dodatnich i półskończonych macierzy , patrz następna sekcja.

Podwójny problem: ograniczona optymalizacja wielomianowa

Załóżmy, że mamy -zmienny wielomian $Displaystyle p (x): \ mathbb {R} ^ {n} \ do \ mathbb {R}}$$\$ i załóżmy, że n {\ displaystyle n że chcielibyśmy zminimalizować ten wielomian w podzbiorze ${\textstyle A\subseteq \mathbb {R} ^{n}}$ . Załóżmy ponadto, że ograniczenia na podzbiorze $\$ zakodować za pomocą $textstyle m}$ wielomianowe równości stopnia co najwyżej ${\ Displaystyle 2d}$ , każda z postaci ${\ textstyle a_ {i} (x) = 0}$ gdzie ${\ Displaystyle a_ { i}:\mathbb {R} ^{n}\to \mathbb {R}}$ jest wielomianem stopnia co najwyżej ${\ displaystyle 2d}$ . Naturalny, choć ogólnie niewypukły program dla tego problemu optymalizacji jest następujący:

$${\ Displaystyle \ min _ {x \ in \ mathbb {R} ^ {n}} \ langle C, x ^ {\ równoważnik d} ( x ^ {\ równoważnik d}) ^ {\ wierzchołek } \ rangle }$$

podlega:

$${\ Displaystyle \ langle A_ {i}, x ^ {\ równoważnik d} (x ^ {\ równoważnik d}) ^ { \top }\rangle =0\qquad \forall \ i\in [m],}$$

 

 

 

 

()

$${\ Displaystyle x _ {\ pusty zbiór} = 1,}$$

gdzie ${\ textstyle x ^ {\ równoważnik d}}$ jest $re {\$ -wymiarowym z jednym wpisem dla każdego jednomianu w $równoważnik d}}$ stopnia co najwyżej $tak$ że dla każdego multiset ${\ Displaystyle S \ podzbiór [n], | S | \ równoważnik d,}$${\ textstyle x_ {S} = \ prod _ {i \ in S} x_ {i}}$ , ${\ textstyle C}$ jest macierzą współczynników wielomianu $} ,$${\ textstyle p (x$${\ textstyle a_ {i}$$który$ chcemy zminimalizować, a jest macierzą współczynników wielomianu kodującego za $}$$displaystyle i}$ -te ograniczenie na podzbiorze ${\ Displaystyle A \ podzbiór \ mathbb {R} ^ {n}}$ . Dodatkowy, stały indeks w naszej przestrzeni poszukiwań ${\ textstyle p$ jest dodawany dla wygody zapisywania wielomianów $x$ i ${\ textstyle a_ {i} (x)}$ w reprezentacji macierzowej.

Ten program jest generalnie niewypukły, ponieważ ograniczenia ( 1 ) nie są wypukłe. Jedna z możliwych relaksacji wypukłych dla tego problemu minimalizacji wykorzystuje programowanie półokreślone w celu zastąpienia macierzy zmiennych pierwszego rzędu ${\ Displaystyle x ^ {\ równoważnik d} (x ^ {\ równoważnik d}) ^ { \ top }}$$macierzą$$:$ półskończoną indeksujemy każdy jednomian rozmiaru co najwyżej multiset ${\ Displaystyle S}$ co najwyżej indeksów $2d}$${\ Displaystyle S \ podzbiór [n], | S | \ równoważnik 2d}$ , . Dla każdego takiego jednomianu tworzymy w programie zmienną $i$ układamy zmienne tak, aby tworzyły macierz $displaystyle X_ {S}$${\ textstyle X \ in \ mathbb {R} ^ {[n] ^ {\ równoważnik d} \ razy [n] ^ {\ równoważnik d}}} ,$ gdzie ${\ Displaystyle \ mathbb {R} ^ {[n] ^ {\ równoważnik d} \ razy [n] ^ {\ równoważnik d}}} to zbiór rzeczywistych macierzy, których wiersze$ i kolumny są identyfikowane z multisetami elementów o rozmiarze co najwyżej $displaystyle$$d}$ . Następnie piszemy następujący półokreślony program w zmiennych: ${\ displaystyle X_ {S}}$ :

$${\ Displaystyle \ min _ {X \ in \ mathbb {R} ^ {[n] ^ {\ równoważnik d} \ razy [n ]^{\równik d}}}\langle C,X\rangle }$$

podlega:

$${\ Displaystyle \ langle A_ {i}, X \ rangle = 0 \ qquad \ forall \ i \ w [m], Q}$$

$${\ Displaystyle X _ {\ pusty zbiór} = 1,}$$

$${\ Displaystyle X _ {U \ kubek V} = X_ {S \ kubek T} \ qquad \ forall \ U, V, S, T \ subseteq [n], | U |, | V |, | S |, | T |\leq d,{\text{ and}}\ U\cup V=S\cup T,}$$

$${\ Displaystyle X \ succeq 0,}$$

gdzie ponownie $}$ macierzą współczynników wielomianu , który chcemy zminimalizować, a $)$ współczynników do $( x$ wielomianu za ${\ textstyle a_ {i} (x)}$ kodujący $-te$ ograniczenie podzbioru $\ displaystyle A \ podzbiór \ mathbb {R} ^ { n}}$ .

Trzecie ograniczenie zapewnia, że ​​​​wartość jednomianu, który pojawia się kilka razy w macierzy, jest równa w całej macierzy i jest dodawane, aby respektować symetrie występujące w postaci kwadratowej ${\ Displaystyle x ^ {\ równoważnik d} (x ^ {\ równoważnik d}) ^ {\ top}}$${\ displaystyle X$ .

Dwoistość

Można wziąć podwójność powyższego półokreślonego programu i otrzymać następujący program:

$${\ Displaystyle \ max _ {y \ in \ mathbb {R} ^ {m'}} y_ {0},}$$

podlega:

$${\ Displaystyle C-y_ {0} e _ {\ pusty zestaw} - \ suma _ {i \ w [m]} y_ {i} A_ {i} - \ suma _ {S \ kubek T = U \ kubek V} y_ {S,T,U,V}(e_{S,T}-e_{U,V})\succeq 0.}$$

Mamy zmienną $mi$ ograniczeniu ${\ Displaystyle \ langle e_ {\ pusty zbiór}, X \ rangle = 1}$ gdzie ${\ displaystyle e_ {\ pusty zbiór}}$ to macierz ze wszystkimi wpisami zerowymi z wyjątkiem wpisu indeksowanego przez ${\ Displaystyle (\ varnothing, \ varnothing)}$ ), zmienną rzeczywistą ${\ displaystyle y_ {i}}$ dla każdego ograniczenia wielomianowego ${\ Displaystyle \ langle X, A_ {i} \ rangle = 0 \ quad sti \ in [m]}$ i dla każdej grupy multisetów ${\ Displaystyle S, T, U, V \ podzbiór [n], | S |, | T |, | U |, | V | \ równoważnik d, S \ kubek T = U \ kubek V}$ , mamy podwójną zmienną $}}$ ograniczenia symetrii ${\ Displaystyle \ langle X, e_ {S, T} -e_ {U, V} \ rangle = 0}$ . Ograniczenie dodatniej półskończoności zapewnia, że $^{n}}$ sumą kwadratów wielomianów nad $ZA$$A \ podzbiór \$$macierzy$ przez charakterystykę dodatnio-półokreślonych macierzy dla półokreślonej napisz ${\ textstyle Q = \ suma _ {i \ w [m]} f_ {i} f_ {i} ^ {\ wierzchołek}}$ dla wektorów ${\ styl tekstu f_{i}\in \mathbb {R} ^{m}}$ . Zatem dla dowolnego ${\textstyle x\in A\subset \mathbb {R} ^{n}$ }

$${\ Displaystyle {\ rozpocząć {wyrównane} p (x) -y_ {0} i = p (x) -y_ {0} - \ suma _ {i \ w [m ']} y_ {i} a_ {i} (x)\qquad {\text{od}}x\in A\\&=(x^{\równoważnik d})^{\top }\left(C-y_{0}e_{\pusty zbiór }-\ suma _{i\in [m']}y_{i}A_{i}-\sum _{S\cup T=U\cup V}y_{S,T,U,V}(e_{S,T }-e_{U,V})\right)x^{\leq d}\qquad {\text{przez symetrię}}\\&=(x^{\leq d})^{\top }\left( \sum _{i}f_{i}f_{i}^{\top }\right)x^{\równoważnik d}\\&=\sum _{i}\langle x^{\równik d},f_ {i}\rangle ^{2}\\&=\sum _{i}f_{i}(x)^{2},\end{wyrównane}}}$$

gdzie zidentyfikowaliśmy wektory $wielomianu$ stopnia najwyżej . $displaystyle d}$ . Daje to dowód sumy kwadratów, że wartość ${\ textstyle p (x) \ geq y_ {0}}$ nad ${\ Displaystyle A \ podzbiór \ mathbb {R} ^ { n}}$ .

Powyższe można również rozszerzyć na $regiony$ .

Hierarchia sumy kwadratów

Hierarchia sumy kwadratów (hierarchia SOS), znana również jako hierarchia Lasserre'a, jest hierarchią wypukłych relaksacji o rosnącej mocy i rosnących kosztach obliczeniowych. Dla każdej liczby naturalnej $jako$ odpowiednia $lub$ jest znana SOS $poziom$ runda Runda ${\ textstyle 1}$ , kiedy ${\ textstyle d = 1}$ odpowiada podstawowemu $programowi$ półokreślonemu lub optymalizacji sumy kwadratów na wielomianach stopnia co . Aby rozszerzyć podstawowy program wypukły na $poziomu , do programu dodaje się dodatkowe zmienne i ograniczenia$ poziomie hierarchii do $,$ aby program uwzględniał wielomiany stopnia co najwyżej ${\ Displaystyle 2d}$ .

Hierarchia SOS wywodzi swoją nazwę od faktu, że wartość funkcji celu na $poziomie$ jest ograniczona dowodem sumy kwadratów przy użyciu wielomianów stopnia co najwyżej ${\ textstyle d}$ przez podwójne (patrz „Dwoistość” powyżej). W konsekwencji każdy dowód sumy kwadratów, który wykorzystuje wielomiany stopnia co najwyżej, $użyty$ do ograniczenia wartości obiektywnej, pozwalając udowodnić gwarancje ścisłości relaksacji.

W połączeniu z twierdzeniem Berga oznacza to dalej, że przy wystarczającej liczbie rund relaksacja staje się dowolnie ciasna w dowolnym ustalonym przedziale. Wynik Berga stwierdza, że ​​​​każdy nieujemny wielomian rzeczywisty w ograniczonym przedziale można przybliżyć z dokładnością $w$ przedziale za pomocą sumy kwadratów rzeczywistych wielomianów o wystarczająco wysokim stopniu, a zatem jeśli ${\ textstyle OBJ (x)}$ jest wielomianową wartością celu jako funkcją punktu ${\ textstyle x}$ , jeśli nierówność ${\ textstyle c + \ varepsilon -OBJ (x) \ geq 0}$$zachodzi$ dla wszystkich obszarze zainteresowania, to musi istnieć dowód sumy kwadratów tego faktu. Wybierając $.$ funkcji celu w możliwym obszarze, mamy wynik

Koszt obliczeniowy

Podczas optymalizowania funkcji w $,$ poziom $\$ można zapisać jako półokreślony program na $}$$textstyle n ^ {O (d)$$}$ zmiennych i można je metodą

Tło sumy kwadratów

Główny artykuł: Wielomian SOS

wielomian jest sumą kwadratów ( SOS $)$ , jeśli istnieją wielomiany ${m}}$ takie, że $\ textstyle p = \ suma _ {i = 1} ^ {m} f_ {i} ^ {2}}$ . Na przykład,

$${\ Displaystyle p = x ^ {2} -4xy + 7y ^ {2}}$$

jest sumą kwadratów od

$${\ Displaystyle p = f_ {1} ^ {2} + f_ {2} ^ {2}}$$

Gdzie

$${\ Displaystyle f_ {1} = (x-2y) {\ tekst {i}} f_ {2} = {\ sqrt {3}} r.}$$

Zauważ, że jeśli jest sumą kwadratów, to $\$$Displaystyle p (x) \ geq 0}$ wszystkich ${\ Displaystyle x \ in \ mathbb {R} ^ { n}}$ . Dostępne są szczegółowe opisy wielomianu SOS .

Formy $_$ można _ $_$ _ Podobnie wielomiany stopnia ≤ 2 d można wyrazić jako

$${\ Displaystyle p (x) = z (x) ^ {\ mathsf {T}} Qz (x),}$$

$}$ wektor zawiera wszystkie jednomiany stopnia ${\ displaystyle \ leq d$ . Jest to znane jako macierzy Grama . Ważnym faktem jest to, że $SOS wtedy i tylko wtedy$ istnieje macierz symetryczna i $Q$ -półokreślona taka, że ${\ Displaystyle p (x) = z (x) ^ {\ mathsf {T}} Qz (x)}$ . Zapewnia to połączenie między wielomianami SOS a dodatnimi i półskończonymi macierzami.

Narzędzia programowe

• SOSTOOLS , na licencji GNU GPL . Przewodnik referencyjny jest dostępny pod adresem arXiv:1310.4716 [math.OC] , a prezentacja dotycząca jego elementów wewnętrznych jest dostępna tutaj .
• CDCS-sos , pakiet z CDCS , rozszerzony solwer metody Lagrange'a , do obsługi programów SOS na dużą skalę.
• Rozszerzenie SumOfSquares JuMP dla Julii .
• TSSOS dla Julii, narzędzie do optymalizacji wielomianów oparte na hierarchiach momentu-SOS dostosowanych do rzadkości.
• Dla podwójnego problemu optymalizacji wielomianowej z ograniczeniami, GloptiPoly dla MATLAB/Octave, Ncpol2sdpa dla Pythona i MomentOpt dla Julii.