Quand l'écart de dualité de la programmation semi-définie (SDP) est-il nul?

10

Je n'ai pas pu trouver dans la littérature une caractérisation précise de la disparition de l'écart de dualité SDP. Ou, quand la "forte dualité" tient-elle?

Par exemple, quand on va et vient entre le Lasserre et le SOS SDP, on a en principe un écart de dualité. Cependant, d'une manière ou d'une autre, il semble y avoir une raison «triviale» pour laquelle cet écart n'existe pas.

La condition de Slater semble être suffisante mais pas nécessaire et elle s'applique à tous les programmes convexes. J'espère que pour les PDS en particulier, quelque chose de plus fort pourrait être vrai. Je serais également heureux de voir un exemple explicite d'utilisation de la condition de Slater pour prouver la disparition de l'écart de dualité.

approximation-hardness convex-optimization semidefinite-programming sum-of-squares primal-dual étudiant diplômé
la source

10

Il existe une théorie de la dualité plus compliquée pour les SDP qui est exacte: il n'y a pas de «condition supplémentaire» comme celle de Slater. Cela est dû à Ramana . (Pour une autre version de SOS, voir [KS12] .) Pour être honnête, je n'ai jamais essayé de comprendre ces papiers et serais heureux si quelqu'un les rédigeait pour moi.

Une conséquence notable de ce travail est que le problème de tester si un SDP donné est faisable est dans NP si et seulement s'il est dans coNP. (Cependant, je pense que les experts s'attendent à ce que le problème ne soit dans aucun des deux. La meilleure limite supérieure connue est PSPACE.)

Ryan O'Donnell
la source

Merci beaucoup pour la réponse très utile! Laisse-moi chercher ça! (Quelle coïncidence si au cours des dernières semaines, j'ai également essayé de travailler avec Daniel Kane sur les limites inférieures du circuit du réseau profond! C'est un document tellement éducatif! activations réalistes comme ReLU.)

étudiant diplômé

9

Pour le SDP sous forme standard la condition de Slater se réduit à l'existence d'un défini positif qui satisfait les contraintes affines . Je suppose que cela est satisfait pour tout SDP que vous pouvez trouver dans la littérature sur les algorithmes d'optimisation / approximation combinatoire. Par exemple, pour le SDP Goemans-Williamson Max-Cut, les contraintes de faisabilité sont et le La matrice d'identité est une solution faisable définie positive.

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 ce qui concerne la hiérarchie Lasserre / Somme des carrés, Lasserre a montré que si l'ensemble réalisable déterminé par les contraintes polynomiales a un point intérieur, il n'y a pas d'écart de dualité. Vous pouvez trouver une condition plus faible dans cet article .

Sasho Nikolov
la source

Merci beaucoup pour les références! La condition du Slater transformé est-elle également une condition nécessaire pour le SDP? Ou existe-t-il d'autres conditions nécessaires? (Je vais bientôt parcourir les documents auxquels vous avez fait référence, mais je me demandais si vous pouviez dire quelque chose sur ce que vous entendiez par "condition plus faible". Vous voulez dire que la condition dans le deuxième document est toujours une condition suffisante et non condition mais est plus simple que la condition suffisante dans le premier article?)

gradstudent

C'est la condition Slater standard, je viens de me spécialiser sur les SDP, ce qui simplifie les choses car toutes les contraintes sont affines, à l'exception de la contrainte PSD. Cette condition n'est pas nécessaire. Je ne pense pas non plus que l'une des conditions SoS soit nécessaire, mais la condition "plus faible" ne nécessite pas l'existence d'un point intérieur, il peut donc être plus facile à vérifier.

Sasho Nikolov

Merci! Donc, une condition nécessaire n'est pas connue?

gradstudent

1

Il y a une belle (je pense ...) caractérisation du moment où une forte dualité tient ou échoue pour {\ em all} les fonctions objectives.

Nous disons que le {\ em système} semi-fini

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

se comporte mal si voici une fonction objective pour laquelle le SDP $c$

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

a une valeur optimale finie, mais le double SDP n'a pas de solution avec la même valeur: c'est-à-dire qu'une forte dualité échoue pour certains $c.$

$(P_{SD})$ se comporte bien s'il ne se comporte pas mal. C'est-à-dire que pour chaque fonction objective, une forte dualité existe. (C'est-à-dire que pour chaque pour lequel le SDP primal a une valeur optimale finie, le dual a une solution avec la même valeur). $c$

Bien sûr, si la condition de Slater est vraie , alors se comporte bien, mais l'inverse n'est pas vrai. $(P_{SD})$

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

Le document sort bientôt dans SIAM Review. J'espère que les gens vont l'aimer :)

district 9
la source

Quand l'écart de dualité de la programmation semi-définie (SDP) est-il nul?

Réponses: