Kiedy różnica w dualności programowania semidefinite (SDP) wynosi zero?

10

Nie udało mi się znaleźć w literaturze dokładnej charakterystyki zaniku luki dualności SDP. Lub kiedy ma miejsce „silna dualność”?

Na przykład, kiedy ktoś porusza się między Lasserre a SOS SDP, w zasadzie ma się lukę w dualności. Jednak wydaje się, że istnieje jakiś „trywialny” powód, dla którego nie ma tej luki.

Stan Slatera wydaje się wystarczający, ale nie konieczny i dotyczy wszystkich programów wypukłych. Mam nadzieję, że w szczególności dla SDP może być coś silniejszego. Byłbym równie szczęśliwy, widząc jakikolwiek wyraźny przykład wykorzystania stanu Slatera do wykazania zaniku luki w dualności.

approximation-hardness convex-optimization semidefinite-programming sum-of-squares primal-dual absolwent
źródło

10

Dokładniejsza jest bardziej skomplikowana teoria dualności dla SDP: nie ma „dodatkowego warunku” takiego jak warunek Slatera. Wynika to z Ramana . (Kolejne spojrzenie na ten problem z SOS, patrz [KS12] .) Szczerze mówiąc, nigdy nie próbowałem zrozumieć tych dokumentów i byłbym szczęśliwy, gdyby ktoś ich oszukał.

Jedną z godnych uwagi konsekwencji tej pracy jest to, że problem testowania, czy dany SDP jest wykonalny, dotyczy NP, tylko wtedy, gdy jest w CoNP. (Myślę jednak, że eksperci oczekują, że problem nie występuje. Najlepszą znaną górną granicą jest PSPACE.)

Ryan O'Donnell
źródło

Bardzo dziękuję za bardzo pomocną odpowiedź! Pozwól mi to sprawdzić! (Co za zbieg okoliczności, że w ciągu ostatnich tygodni próbowałem również omówić twój artykuł z Danielem Kane'em na temat dolnych granic obwodu sieci głębokiej! To taki edukacyjny artykuł! Zastanawiam się, czy to, co robisz dla LTF, dzieje się również po więcej realistyczne aktywacje, takie jak ReLU.)

gradstudent

9

min {t r (C^{T} X) : t r (A_{1}^{T} X) = b_{1}, \dots, t r (A_{m}^{T} X) = b_{m}, X ⪰ 0},

$\min\{ \mathrm{tr}(C^T X): \mathrm{tr}(A_1^T X) = b_1, \ldots, \mathrm{tr}(A_m^T X) = b_m, X \succeq 0\},$

X ≻ 0

$X\succ 0$

t r (A_{i}^{T} X) = b_{i}

$\mathrm{tr}(A_i^T X) = b_i$

{X : X_{1, 1} = 1, \dots, X_{n, n} = 1, X ⪰ 0}

$\{X: X_{1,1} = 1, \ldots, X_{n,n} = 1, X\succeq 0\}$

Jeśli chodzi o hierarchię Lasserre / Suma kwadratów, Lasserre wykazał, że jeśli wykonalny zbiór określony przez ograniczenia wielomianowe ma punkt wewnętrzny, to nie ma luki w dualności. W tym dokumencie można znaleźć słabszy stan .

Sasho Nikolov
źródło

Wielkie dzięki za referencje! Czy więc stan przekształconego Slatera jest również warunkiem koniecznym dla SDP? Czy są też inne niezbędne warunki? (Wkrótce przejrzę dokumenty, o których pan wspomniał, ale zastanawiałem się, czy możecie powiedzieć coś o tym, co rozumiecie przez „słabszą kondycję”? Masz na myśli, że warunek w drugiej pracy jest nadal warunkiem wystarczającym, a nie koniecznym warunek, ale jest prostszy niż warunek wystarczający w pierwszym artykule?)

gradstudent

Jest to standardowy warunek Slatera, właśnie specjalizowałem się w SDP, co upraszcza sprawy, ponieważ wszystkie ograniczenia są afiniczne, z wyjątkiem ograniczenia PSD. Ten warunek nie jest konieczny. Nie uważam też, aby którykolwiek z warunków SoS był konieczny, ale „słabszy” nie wymaga istnienia punktu wewnętrznego, więc może być łatwiej zweryfikować.

Sasho Nikolov

Dzięki! Więc konieczny warunek nie jest znany?

gradstudent

1

Istnieje ładna (myślę ...) charakterystyka, kiedy silna dwoistość utrzymuje się lub kończy się niepowodzeniem dla funkcji obiektywnych.

Mówimy, że semidefinite {\ em system}

$(P_{SD}) \,\, \sum_{i=1}^m x_i A_i \preceq B$

jest źle zachowywała , jeśli o to funkcja celu , dla których SDP $c$

$\sup c^T x \,\, s.t. \,\, \sum_{i=1}^m x_i A_i \preceq B$

ma skończoną wartość optymalną, ale podwójny SDP nie ma rozwiązania o tej samej wartości: tzn. silna dualność zawodzi dla niektórych $c.$

$(P_{SD})$ jest dobrze wychowany, jeśli nie jest źle wychowany. Oznacza to, że dla każdej funkcji celu zachowuje się silna dualność. (Tj. Dla każdego dla którego pierwotny SDP ma skończoną optymalną wartość, dual ma rozwiązanie o tej samej wartości). $c$

Oczywiście, jeśli warunek Slatera się utrzyma, wówczas jest dobrze wychowany, ale odwrotność nie jest prawdą. $(P_{SD})$

https://arxiv.org/pdf/1709.02423.pdf

Artykuł ukaże się wkrótce w SIAM Review. Mam nadzieję, że ludziom się spodoba :)

Dystrykt 9
źródło

Kiedy różnica w dualności programowania semidefinite (SDP) wynosi zero?

Odpowiedzi: