¿Cuándo es cero la brecha de dualidad de la programación semidefinida (SDP)?

10

No he podido encontrar en la literatura una caracterización precisa de la desaparición de la brecha de dualidad SDP. O, ¿cuándo se mantiene la "dualidad fuerte"?

Por ejemplo, cuando uno va y viene entre Lasserre y SOS SDP, en principio uno tiene una brecha de dualidad. Sin embargo, de alguna manera parece haber alguna razón "trivial" por la cual esta brecha no existe.

La condición de Slater parece ser suficiente pero no necesaria y se aplica a todos los programas convexos. Espero que para los SDP en particular, algo más fuerte sea cierto. Me encantaría ver cualquier ejemplo explícito del uso de la condición de Slater para demostrar la desaparición de la brecha de la dualidad.

approximation-hardness convex-optimization semidefinite-programming sum-of-squares primal-dual graduado
fuente

10

Existe una teoría de la dualidad más complicada para los SDP que es exacta: no existe una 'condición adicional' como la condición de Slater. Esto se debe a Ramana . (Para otra versión de esto que involucra SOS, vea [KS12] .) Para ser honesto, nunca he tratado de entender estos documentos y sería feliz si alguien los hubiera engañado por mí.

Una consecuencia notable de este trabajo es que el problema de probar si un determinado SDP es factible está en NP si y solo si está en coNP. (Sin embargo, creo que los expertos esperan que el problema no esté en ninguno de los dos. El mejor límite superior conocido es PSPACE).

Ryan O'Donnell
fuente

Muchas gracias por una respuesta muy útil! Déjame ver esto! (¡Qué coincidencia que durante las últimas semanas también haya estado tratando de trabajar en tu trabajo con Daniel Kane en los límites inferiores del circuito de red profunda! ¡Es un trabajo tan educativo! Me he estado preguntando si lo que haces para LTF también sucede para activaciones realistas como 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\}$

En cuanto a la jerarquía de Lasserre / Suma de cuadrados, Lasserre mostró que si el conjunto factible determinado por las restricciones polinómicas tiene un punto interior, entonces no hay una brecha de dualidad. Puede encontrar una condición más débil en este documento .

Sasho Nikolov
fuente

Muchas gracias por las referencias! Entonces, ¿la condición del Slater transformado también es una condición necesaria para el SDP? ¿O hay otras condiciones necesarias? (Pronto veré los documentos a los que se refirió, pero me preguntaba si podría decir algo sobre lo que quería decir con "condición más débil". ¿Quiere decir que la condición en el segundo documento sigue siendo una condición suficiente y no necesaria? condición pero es más simple que la condición suficiente en el primer artículo?)

gradstudent

Esta es la condición estándar de Slater, acabo de especializarme en SDP, lo que simplifica las cosas porque todas las restricciones son afines, excepto la restricción PSD. Esta condición no es necesaria. Tampoco creo que ninguna de las condiciones de SoS sea necesaria, pero la "más débil" no requiere la existencia de un punto interior, por lo que puede ser más fácil de verificar.

Sasho Nikolov

¡Gracias! Entonces, ¿una condición necesaria no se conoce?

gradstudent

1

Hay una buena caracterización (creo ...) de cuándo una fuerte dualidad se mantiene o falla para {\ em all} funciones objetivas.

Decimos que el semidefinito {\ em system}

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

se comporta mal si aquí hay una función objetivo para la cual el SDP $c$

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

tiene un valor óptimo finito, pero el SDP dual no tiene una solución con el mismo valor: es decir, la fuerte dualidad falla para algunos $c.$

$(P_{SD})$ se porta bien si no se porta mal. Es decir, para cada función objetivo tiene una fuerte dualidad. (Es decir, para cada para el que el SDP primario tiene un valor óptimo finito, el dual tiene una solución con el mismo valor). $c$

Por supuesto, si la condición de Slater se mantiene, entonces se comporta bien, pero lo contrario no es cierto. $(P_{SD})$

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

El documento saldrá pronto en SIAM Review. Espero que a la gente le guste :)

Distrito 9
fuente

¿Cuándo es cero la brecha de dualidad de la programación semidefinida (SDP)?

Respuestas: