Ê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.