Wann ist die Dualitätslücke der semidefiniten Programmierung (SDP) Null?

10

Ich konnte in der Literatur keine genaue Charakterisierung des Verschwindens der SDP-Dualitätslücke finden. Oder wann gilt "starke Dualität"?

Wenn man zum Beispiel zwischen dem Lasserre und dem SOS SDP hin und her geht, hat man im Prinzip eine Dualitätslücke. Irgendwie scheint es jedoch einen "trivialen" Grund zu geben, warum diese Lücke nicht vorhanden ist.

Slaters Zustand scheint ausreichend, aber nicht notwendig zu sein und gilt für alle konvexen Programme. Ich hoffe, dass insbesondere für SDPs etwas Stärkeres wahr sein könnte. Ich würde mich ebenso freuen, ein explizites Beispiel für die Verwendung von Slaters Bedingung zu sehen, um das Verschwinden der Dualitätslücke zu beweisen.

approximation-hardness convex-optimization semidefinite-programming sum-of-squares primal-dual gradstudent
quelle

10

Es gibt eine kompliziertere Dualitätstheorie für SDPs, die genau ist: Es gibt keine zusätzliche Bedingung wie die von Slater. Dies ist Ramana zu verdanken . (Eine weitere Sichtweise zu SOS finden Sie unter [KS12] .) Um ehrlich zu sein, habe ich nie versucht, diese Papiere zu verstehen, und würde mich freuen, wenn jemand sie für mich ablegen würde.

Eine bemerkenswerte Konsequenz dieser Arbeit ist, dass das Problem, zu testen, ob ein bestimmtes SDP machbar ist, genau dann in NP liegt, wenn es in coNP ist. (Ich denke jedoch, dass die Experten erwarten, dass das Problem in keinem von beiden liegt. Die beste bekannte Obergrenze ist PSPACE.)

Ryan O'Donnell
quelle

Vielen Dank für die sehr hilfreiche Antwort! Lass mich das nachschlagen! (Was für ein Zufall, dass ich in den letzten Wochen auch versucht habe, Ihre Arbeit mit Daniel Kane an den unteren Grenzen des tiefen Netzkreises durchzuarbeiten! Es ist eine so lehrreiche Arbeit! Ich habe mich gefragt, ob das, was Sie für LTF tun, auch für mehr passiert realistische Aktivierungen wie ReLU.)

gradstudent

9

Für das SDP in Standardform Slaters Bedingung reduziert sich auf die Existenz eines positiven definitiven , das die affinen Bedingungen erfüllt . Ich würde vermuten, dass dies für jedes SDP erfüllt ist, das Sie in der Literatur zu kombinatorischen Optimierungs- / Approximationsalgorithmen finden. Beispielsweise sind für das Goemans-Williamson Max-Cut-SDP die Durchführbarkeitsbeschränkungen und die Identitätsmatrix ist eine positiv definitive realisierbare Lösung.

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\}$

In Bezug auf die Hierarchie von Lasserre / Summe der Quadrate hat Lasserre gezeigt, dass es keine Dualitätslücke gibt, wenn die durch die Polynombedingungen bestimmte realisierbare Menge einen inneren Punkt hat. In diesem Artikel finden Sie einen schwächeren Zustand .

Sasho Nikolov
quelle

Vielen Dank für die Referenzen! Ist der Zustand des transformierten Slaters also auch eine notwendige Bedingung für das SDP? Oder gibt es andere notwendige Bedingungen? (Ich werde bald die Papiere durchsehen, auf die Sie sich bezogen haben, aber ich habe mich gefragt, ob Sie etwas darüber sagen könnten, was Sie unter "schwächerem Zustand" verstanden haben? Sie meinen, der Zustand im zweiten Papier ist immer noch ein ausreichender Zustand und kein notwendiger Bedingung, aber ist einfacher als die ausreichende Bedingung in der ersten Arbeit?)

Gradstudent

Dies ist die Standard-Slater-Bedingung, ich habe mich gerade auf SDPs spezialisiert, was die Sache vereinfacht, da alle Einschränkungen mit Ausnahme der PSD-Einschränkung affin sind. Diese Bedingung ist nicht erforderlich. Ich denke auch nicht, dass eine der SoS-Bedingungen notwendig ist, aber die "schwächere" erfordert nicht die Existenz eines inneren Punktes, so dass es möglicherweise einfacher ist, dies zu überprüfen.

Sasho Nikolov

Vielen Dank! Ein notwendiger Zustand ist also nicht bekannt?

Gradstudent

1

Es gibt eine schöne (ich denke ...) Charakterisierung, wann eine starke Dualität für {\ em alle} Zielfunktionen gilt oder fehlschlägt.

Wir sagen, dass das semidefinite {\ em System}

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

ist schlecht benommen hier , wenn eine objektive Funktion ist die SDP , für die $c$

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

hat einen endlichen optimalen Wert, aber das duale SDP hat keine Lösung mit dem gleichen Wert: dh eine starke Dualität schlägt für einige fehl $c.$

$(P_{SD})$ verhält sich gut, wenn es sich nicht schlecht verhält. Das heißt, für jede Zielfunktion gilt eine starke Dualität. (Dh für jedes für das das ursprüngliche SDP einen endlichen optimalen Wert hat, hat das Dual eine Lösung mit demselben Wert). $c$

Wenn Slaters Bedingung zutrifft , natürlich gut, aber das Gegenteil ist nicht der Fall. $(P_{SD})$

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

Das Papier erscheint bald in SIAM Review. Ich hoffe die Leute werden es mögen :)

Bezirk 9
quelle

Wann ist die Dualitätslücke der semidefiniten Programmierung (SDP) Null?

Antworten: