Qu'est-ce qui peut être résolu avec une programmation semi-définie qui ne peut pas être résolu avec une programmation linéaire?

9

Je connais les programmes linéaires dans la mesure où ils peuvent résoudre des problèmes avec des fonctions objectives linéaires et des contraintes linéaires. Mais qu'est-ce que la programmation semi-définie peut résoudre que la programmation linéaire ne peut pas? Je sais déjà que les programmes semi-définis sont une généralisation des programmes linéaires.

Aussi, comment reconnaît-on un problème qui peut être résolu en utilisant une programmation semi-définie? Quel est un problème typique pour lequel une programmation semi-définie est utilisée et qui ne peut pas être résolu via une programmation linéaire?

Merci beaucoup pour toute réponse.

linear-programming convex-optimization semidefinite-programming user11094
la source
2
Peut-être pouvez-vous rendre votre question plus précise? Après tout, la programmation linéaire est . P
Kristoffer Arnsfelt Hansen
5
@KristofferArnsfeltHansen Je n'arrête pas de me demander pourquoi les gens continuent à évoquer ce fait dans des discussions similaires. La complétude de P n'est pas pertinente à moins que nous ne parlions de séparer P de L ou NC - si nous parlons de poly-temps, tout dans P est "P-complet". Pour suggérer une réponse à OP: une fois que vous avez corrigé l'encodage linéaire d'un problème (c'est-à-dire écrit en optimisant une fonction linéaire sur un polytope), il est parfaitement logique de demander si un LP / SDP polysize peut résoudre le problème.
Sasho Nikolov

Réponses:

18

Un problème typique est MaxCut: produire une coupe dans un graphique qui maximise (approximativement) le nombre de bords coupés. Goemans et Williamson ont montré qu'un SDP se rapproche de la valeur de MaxCut à un facteur d'au moins 0,878. Récemment, Chan, Lee, Raghavendra et Steurer ont montré que pour un codage linéaire naturel du problème MaxCut, tous les LP de taille polynomiale atteignent une approximation non supérieure à 0,5.

Il est difficile de dire de manière concise quels types de problèmes bénéficient généralement d'un PDS. Une approche systématique de la construction des relaxations SDP passe par des hiérarchies, dont la plus puissante est la hiérarchie de Lasserre: voir l'enquête de Rothvoß pour une belle introduction. À ce jour, il y a trop d'exemples de succès des SDP en optimisation pour les énumérer. En outre, Raghavendra a montré qu'un SDP particulier donne la meilleure approximation à tous les problèmes MaxCSP, si la conjecture Unique Games est vraie.

Consultez les livres de Gaertner et Matousek , chapitres 6 et 13 du livre de Willimson et Shmoys , l'enquête de Lovasz .

Sasho Nikolov
la source
12

Pour de nombreux problèmes d'optimisation combinatoire (par exemple Max-Cut), la programmation semi-définie donne des relaxations beaucoup plus fortes que la relaxation LP des formulations IP. Cela permet la conception d'algorithmes d'approximation et d'algorithmes exacts qui sont plus efficaces que leurs homologues linéaires en raison de la meilleure qualité des bornes. Des exemples peuvent être trouvés dans la thèse Habilitation de Christoph Helmberg , cette enquête et cette page de cours .

Une autre séquence récente de résultats spectaculaires utilisant la programmation semi-définie est l'application des algèbres de drapeau de Razborov pour prouver les résultats sur des problèmes de type Turan (voir cette étude et le projet flagmatique ).

Thomas Kalinowski
la source