Optimisation SDP

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.