Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Optimisation SDP
Résumé
En mathématiques et en informatique théorique, l'optimisation SDP ou semi-définie positive, est un type d'optimisation convexe, qui étend l'optimisation linéaire. Dans un problème d'optimisation SDP, l'inconnue est une matrice symétrique que l'on impose d'être semi-définie positive. Comme en optimisation linéaire, le critère à minimiser est linéaire et l'inconnue doit également satisfaire une contrainte affine.
L'optimisation SDP se généralise par l'optimisation conique, qui s'intéresse aux problèmes de minimisation d'une fonction linéaire sur l'intersection d'un cône et d'un sous-espace affine.
L'optimisation SDP s'est beaucoup développée à partir des années 1990, du fait de plusieurs découvertes. D'une part, beaucoup de problèmes pratiques ont pu être définis au moyen de ce formalisme (en recherche opérationnelle) ou ont trouvé une formalisation SDP approchée, mais précise (en optimisation combinatoire, en optimisation algébrique). Par ailleurs, ces problèmes peuvent être résolus efficacement par divers algorithmes : points intérieurs (algorithmes polynomiaux), lagrangien augmenté, méthode des faisceaux (algorithme d'optimisation non différentiable), etc.
On note
l'espace vectoriel des matrices réelles d'ordre symétriques,
la partie de formée des matrices semi-définies positives (c'est ce que signifie la notation ) et
la partie de formée des matrices définies positives (c'est ce que signifie la notation ).
On munit d'une structure euclidienne en y définissant le produit scalaire standard
où désigne la trace du produit matriciel .
On utilise souvent les propriétés « élémentaires » suivantes.
La propriété du point 1, attribuée à Fejér, exprime lautodualité du cône :
Un problème d'optimisation SDP s'écrit de la manière suivante
où , est une application linéaire et . Il s'agit donc de minimiser un critère linéaire sur l'intersection du cône des matrices semi-définies positives et d'un sous-espace affine. C'est que l'on appelle la formulation primale d'un problème SDP.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Proximité ontologique
Concepts associés (8)
Conjecture des jeux uniques
La conjecture des jeux uniques (en anglais Unique Games Conjecture et souvent abrégée UGC) est une conjecture en théorie de la complexité, proposée par Subhash Khot en 2002. Selon cette conjecture, résoudre de manière approximative un certain problème spécifique est NP-difficile. Elle a d'importantes applications relatives à la complexité des algorithmes d'approximation ; le travail qui a été fourni autour de cette conjecture a également permis de démontrer des résultats relatifs à d'autres sujets, par exemple sur la stabilité des systèmes de vote.
Dualité (optimisation)
En théorie de l'optimisation, la dualité ou principe de dualité désigne le principe selon lequel les problèmes d'optimisation peuvent être vus de deux perspectives, le problème primal ou le problème dual, et la solution du problème dual donne une borne inférieure à la solution du problème (de minimisation) primal. Cependant, en général les valeurs optimales des problèmes primal et dual ne sont pas forcément égales : cette différence est appelée saut de dualité. Pour les problèmes en optimisation convexe, ce saut est nul sous contraintes.
Optimisation convexe
vignette|320x320px|Optimisation convexe dans un espace en deux dimensions dans un espace contraint L'optimisation convexe est une sous-discipline de l'optimisation mathématique, dans laquelle le critère à minimiser est convexe et l'ensemble admissible est convexe. Ces problèmes sont plus simples à analyser et à résoudre que les problèmes d'optimisation non convexes, bien qu'ils puissent être NP-difficile (c'est le cas de l'optimisation copositive). La théorie permettant d'analyser ces problèmes ne requiert pas la différentiabilité des fonctions.