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.

Notations

On note

${\mathcal {S}}^{n}:=\{M\in \mathbb {R} ^{n\times n}:M^{\top }=M\}$

l'espace vectoriel des matrices réelles d'ordre $n$ symétriques,

${\mathcal {S}}_{+}^{n}:=\{M\in {\mathcal {S}}^{n}:M\succcurlyeq 0\}$

la partie de ${\mathcal {S}}^{n}$ formée des matrices semi-définies positives (c'est ce que signifie la notation $M\succcurlyeq 0$) et

${\mathcal {S}}_{++}^{n}:=\{M\in {\mathcal {S}}^{n}:M\succ 0\}$

la partie de ${\mathcal {S}}^{n}$ formée des matrices définies positives (c'est ce que signifie la notation $M\succ 0$).

On munit ${\mathcal {S}}^{n}$ d'une structure euclidienne en y définissant le produit scalaire standard

$\langle \cdot ,\cdot \rangle :(M,N)\in {\mathcal {S}}^{n}\times {\mathcal {S}}^{n}\mapsto \langle M,N\rangle =\operatorname {tr} (M^{\top }N)=\sum _{ij}M_{ij}N_{ij},$

où $\operatorname {tr} (MN)$ désigne la trace du produit matriciel $MN$.

On utilise souvent les propriétés « élémentaires » suivantes.

Cônes ${\mathcal {S}}_{+}^{n}$ et ${\mathcal {S}}_{++}^{n}$ — 

1. $M\succcurlyeq 0$ $~\Longleftrightarrow ~$ $\forall N\succcurlyeq 0$, on a $\langle M,N\rangle \geqslant 0$.
2. $M\succ 0$ $~\Longleftrightarrow ~$ $\forall N\succcurlyeq 0$ non nulle, on a $\langle M,N\rangle >0$.
3. Si $M$ et $N\in {\mathcal {S}}_{+}^{n}$, on a $\langle M,N\rangle =0$ $~\Longleftrightarrow ~$ $MN=0$.

La propriété du point 1, attribuée à Fejér, exprime l'autodualité du cône ${\mathcal {S}}_{+}^{n}$ :

$({\mathcal {S}}_{+}^{n})^{+}={\mathcal {S}}_{+}^{n}.$

Définitions primale et duale du problème

Le problème primal

Un problème d'optimisation SDP s'écrit de la manière suivante

($P_{SDP})\quad \left\{{\begin{array}{l}{\inf }_{X\in {\mathcal {S}}^{n}}\;\langle C,X\rangle \\A(X)=b\\X\succcurlyeq 0,\end{array}}\right.$

où $C\in {\mathcal {S}}^{n}$, $A:{\mathcal {S}}^{n}\to \mathbb {R} ^{m}$ est une application linéaire et $b\in \mathbb {R} ^{m}$. 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.

Le critère et la contrainte d'égalité sont linéaires (ou affines), mais la contrainte d'appartenance au cône ${\mathcal {S}}_{+}^{n}$ est « très » non linéaire, éventuellement non différentiable. Elle exprime en effet que $v^{\top }Xv\geqslant 0$ pour tout $v\in \mathbb {R} ^{n}$ ; de ce point de vue, $(P_{SDP})$ est un problème d'optimisation semi-infinie (il a un nombre infini de contraintes). Elle exprime aussi que toutes les valeurs propres de $X$ (des fonctions non linéaires et non différentiables de $X$) doivent être positives ; de ce point de vue, le problème est non convexe et non différentiable. Elle exprime enfin que tous les mineurs principaux de $X$ (des polynômes des éléments de $X$) doivent être positifs ; de ce point de vue, le problème est non linéaire, non convexe, à données polynomiales. Cependant, le critère du problème étant linéaire et son ensemble admissible étant convexe, le problème SDP est en général considéré comme un problème d'optimisation convexe.

Si les problèmes d'optimisation SDP ont une structure assez semblable à celle de l'optimisation linéaire, qui les rend très vite familiers, les résultats que l'on connaît en optimisation linéaire ne s'étendent pas tous tels quels à l'optimisation SDP ; on ne peut guère en être étonné, vu la généralité du formalisme. Il faudra y prendre garde.

On note

$\operatorname {val} (P_{SDP})\quad {\mbox{et}}\quad \operatorname {sol} (P_{SDP})$

la valeur optimale du problème $(P_{SDP})$ et son ensemble de solution. On note

${\begin{array}{rcl}{\mathcal {A}}_{P}&:=&\{X\in {\mathcal {S}}^{n}:A(X)=b,~X\succcurlyeq 0\}\\{\mathcal {A}}_{P}^{s}&:=&\{X\in {\mathcal {S}}^{n}:A(X)=b,~X\succ 0\},\end{array}}$

les ensembles des matrices admissibles et strictement admissibles de $(P_{SDP})$.

On peut représenter l'application linéaire $A$ au moyen de $m$ matrices $A_{i}\in {\mathcal {S}}^{n}$ (théorème de Riesz-Fréchet). On a

$A(X)={\begin{pmatrix}\langle A_{1},X\rangle \\\vdots \\\langle A_{m},X\rangle \end{pmatrix}}.$

Dans cette représentation, l'application $A$ est surjective si, et seulement si, les matrices $A_{i}$ sont linéairement indépendantes dans ${\mathcal {S}}^{n}$.

Le problème dual

On se donne un produit scalaire sur $\mathbb {R} ^{m}$, également noté $\langle \cdot ,\cdot \rangle$, et l'on introduit l'opérateur $A^{*}:\mathbb {R} ^{m}\to {\mathcal {S}}^{n}$ adjoint de $A$, qui est défini par

$\forall X\in {\mathcal {S}}^{n},~\forall y\in \mathbb {R} ^{m}\,:\quad \langle A(X),y\rangle =\langle X,A^{*}(y)\rangle .$

La méthode la plus simple pour obtenir un dual de $(P_{SDP})$ est d'utiliser la dualisation lagrangienne de sa contrainte d'égalité. On utilise donc le lagrangien $\ell :{\mathcal {S}}_{+}^{n}\times \mathbb {R} ^{m}\to \mathbb {R}$ défini par

$\ell (X,y)=\langle C,X\rangle -\langle y,A(X)-b\rangle$

et on écrit $(P_{SDP})$ comme un inf-sup :

$\inf _{X\in {\mathcal {S}}_{+}^{n}}\,\sup _{y\in \mathbb {R} ^{m}}\;\ell (X,y).$

Le dual s'obtient alors en inversant l'infimum et le supremum

$\sup _{y\in \mathbb {R} ^{m}}\,\inf _{X\in {\mathcal {S}}_{+}^{n}}\;\ell (X,y).$

Après calculs, le problème dual de $(P_{SDP})$ obtenu par ce procédé consiste donc à trouver $(y,S)\in \mathbb {R} ^{m}\times {\mathcal {S}}^{n}$ solution de

$(D_{SDP})\quad {\begin{cases}\textstyle \sup _{(y,S)\in \mathbb {R} ^{m}\times {\mathcal {S}}^{n}}\;\langle b,y\rangle \\A^{*}(y)+S=C\\S\succcurlyeq 0.\end{cases}}$

On note

$\operatorname {val} (D_{SDP})\quad {\mbox{et}}\quad \operatorname {sol} (D_{SDP})$

la valeur optimale du problème $(D_{SDP})$ et son ensemble de solution. On note

${\begin{array}{rcl}{\mathcal {A}}_{D}&:=&\{(y,S)\in \mathbb {R} ^{m}\times {\mathcal {S}}^{n}:A^{*}(y)+S=C,~S\succcurlyeq 0\}\\{\mathcal {A}}_{D}^{s}&:=&\{(y,S)\in \mathbb {R} ^{m}\times {\mathcal {S}}^{n}:A^{*}(y)+S=C,~S\succ 0\},\end{array}}$

les ensembles des couples admissibles et strictement admissibles de $(D_{SDP})$. On note enfin

${\mathcal {A}}:={\mathcal {A}}_{P}\times {\mathcal {A}}_{D}\quad {\mbox{et}}\quad {\mathcal {A}}^{s}:={\mathcal {A}}_{P}^{s}\times {\mathcal {A}}_{D}^{s}.$

L'écart entre les valeurs optimales primale et duale est ce que l'on appelle le saut de dualité :

${\mbox{saut de dualité}}=\operatorname {val} (P_{SDP})-\operatorname {val} (D_{SDP}).$

On dit qu'il n'y a pas de saut de dualité si le saut de dualité est nul.

Si l'on utilise le produit scalaire euclidien dans $\mathbb {R} ^{m}$ et si l'on prend la représentation ci-dessus de $A$, son adjoint $A^{*}$ s'écrit

$A^{*}(y)=\sum _{i=1}^{m}A_{i}y_{i}.$

Dans ce cas, le problème dual peut se voir comme celui cherchant à maximiser une forme linéaire en $y$ sur ${\mathcal {S}}^{n}$, tout en imposant qu'une combinaison affine de matrices (avec coefficients $y_{i}$) soit semi-définie positive :

$C-\sum _{i=1}^{m}A_{i}y_{i}\succcurlyeq 0.$

Cette dernière relation est ce que l'on appelle une inégalité matricielle linéaire (on devrait dire affine) ; IML en abrégé.

La proposition suivante donne quelques conséquences simples de la dualisation lagrangienne de $(P_{SDP})$. Le point 1 est connu sous le nom de dualité faible. L'écart $\operatorname {val} (P_{SDP})-\operatorname {val} (D_{SDP})$ entre valeurs optimales primale et duale est appelé le saut de dualité. Le point 2 montre que $\langle X,S\rangle$ est l'écart entre valeurs primale et duale pour un triplet admissible $(X,y,S)\in {\mathcal {A}}$. Le point 3 donne une condition suffisante d'optimalité élémentaire, mais bien utile.

Conséquences de la dualisation lagrangienne — 

1. $\operatorname {val} (D_{SDP})\leqslant \operatorname {val} (P_{SDP})$.
2. $(X,y,S)\in {\mathcal {A}}$ $~\Longrightarrow ~$ $\langle C,X\rangle -\langle b,y\rangle =\langle X,S\rangle \geqslant 0$.
3. $(X,y,S)\in {\mathcal {A}}$ et $\langle X,S\rangle =0$ $~\Longrightarrow ~$ $X\in \operatorname {sol} (P_{SDP})$ et $(y,S)\in \operatorname {sol} (D_{SDP})$.

La réciproque du point 3 est fausse en général, mais on verra qu'elle a lieu si ${\mathcal {A}}^{s}\neq \varnothing$. Lorsqu'elle a lieu, $(X,y)$ est un point-selle du lagrangien $\ell$ défini ci-dessus sur ${\mathcal {S}}_{+}^{n}\times \mathbb {R} ^{m}$.

Réalisabilités primale et duale

Nous nous intéressons ici à la question de la réalisabilité des problèmes primal et dual. Quand peut-on trouver une matrice $X\succcurlyeq 0$ telle que $A(X)=b$ ? Quand peut-on trouver un vecteur $y\in \mathbb {R} ^{m}$ tel que $A^{*}(y)\preccurlyeq C$ ?

Dans $(\mathbb {R} ^{n},\geqslant )$, ces questions trouvent une réponse dans les théorèmes de l'alternative, qui sont eux-mêmes des conséquences du lemme de Farkas. Une première application de la forme généralisée de ce lemme à l'optimisation SDP s'obtient en prenant $\mathbb {E} :={\mathcal {S}}^{n}$, $\mathbb {F} :=\mathbb {R} ^{m}$, $L:=\mathbb {R} ^{m}$, $K:={\mathcal {S}}_{+}^{n}$ et l'application $A:{\mathcal {S}}^{n}\to \mathbb {R} ^{m}$ comme application linéaire ; cela donne

$\{y\in \mathbb {R} ^{m}:A^{*}(y)\succcurlyeq 0\}^{+}={\overline {A({\mathcal {S}}_{+}^{n})}}.$

On ne peut pas se passer de l'adhérence à droite, car $A({\mathcal {S}}_{+}^{n})$ n'est pas nécessairement un fermé, alors que le cône dual à gauche est toujours fermé. La situation est donc différente de celle rencontrée en optimisation linéaire où $A(\mathbb {R} _{+}^{n})$ est un polyèdre convexe, donc un fermé. On dit alors que les contraintes primales en $X\in {\mathcal {S}}^{n}$,

$A(X)=b\quad {\mbox{et}}\quad X\succcurlyeq 0,$

sont quasi-réalisables si $b\in {\overline {A({\mathcal {S}}_{+}^{n})}}$, c'est-à-dire si, pour tout $\varepsilon >0$, il existe $b_{\varepsilon }\in \mathbb {R} ^{m}$ et $X_{\varepsilon }\in {\mathcal {S}}_{+}^{n}$ tels que $\|b_{\varepsilon }-b\|\leq \varepsilon$ et $A(X_{\varepsilon })=b_{\varepsilon }$.

De même, des conditions duales d'admissibilité du problème dual $(D_{SDP})$ peuvent être obtenues par le lemme de Farkas généralisé avec $\mathbb {E} :=\mathbb {R} ^{m}\times \mathbb {R} ^{m}\times {\mathcal {S}}^{n}$, $\mathbb {F} :={\mathcal {S}}^{n}$, $L:={\mathcal {S}}^{n}$, $K:=\mathbb {R} _{+}^{m}\times \mathbb {R} _{+}^{m}\times {\mathcal {S}}_{+}^{n}$ et l'application linéaire $(u,v,X)\in \mathbb {E} \to \mathbb {F} \to A^{*}(u-v)+S$. Cela donne

$\{X\in {\mathcal {S}}_{+}^{n}:A(X)=0\}^{+}={\overline {A^{*}(\mathbb {R} ^{m})+{\mathcal {S}}_{+}^{n}}}.$

On dit alors que les contraintes duales en $(y,S)\in \mathbb {R} ^{m}\times {\mathcal {S}}^{n}$,

$A^{*}(y)+S=C\quad {\mbox{et}}\quad S\succcurlyeq 0,$

sont quasi-réalisables si $C\in {\overline {A^{*}(\mathbb {R} ^{m})+{\mathcal {S}}_{+}^{n}}}$, c'est-à-dire si, pour tout $\varepsilon >0$, il existe $C_{\varepsilon }\in {\mathcal {S}}^{n}$, $y_{\varepsilon }\in \mathbb {R} ^{m}$ et $S_{\varepsilon }\in {\mathcal {S}}_{+}^{n}$ tels que $\|C_{\varepsilon }-C\|\leq \varepsilon$ et $A^{*}(y_{\varepsilon })+S_{\varepsilon }=C_{\varepsilon }$.

Le résultat suivant résume cette discussion.

Quasi-réalisabilités primale et duale — 

1. Les contraintes primales sont quasi-réalisables si, et seulement si, $\langle b,y\rangle \geqslant 0$ pour tout $y\in \mathbb {R} ^{m}$ tel que $A^{*}(y)\succcurlyeq 0$.
2. Les contraintes duales sont quasi-réalisables si, et seulement si, $\langle C,X\rangle \geqslant 0$ pour tout $X\in {\mathcal {S}}_{+}^{n}$ tel que $A(X)=0$.

La quasi-réalisabilité des contraintes primales et duales n'est pas une propriété très forte (elle n'assure même pas leur réalisabilité !). Numériquement, il est certainement préférable d'avoir une réalisabilité plus robuste, insensible à de petites perturbations du second membre. On définit donc les concepts suivants. On dit que les contraintes primales sont fortement réalisables si

$b\in \operatorname {int} A({\mathcal {S}}_{+}^{n}),$

où l'opérateur «int» désigne la prise de l'intérieur. De même, on dit que les contraintes duales sont fortement réalisables si

$C\in \operatorname {int} {(A^{*}(\mathbb {R} ^{m})+{\mathcal {S}}_{+}^{n})}.$

Réalisabilités primale et duale fortes — 

1. Les contraintes primales sont fortement réalisables si, et seulement si, $A$ est surjective et ${\mathcal {A}}_{P}^{s}\neq \varnothing$.
2. Les contraintes duales sont fortement réalisables si, et seulement si, ${\mathcal {A}}_{D}^{s}\neq \varnothing$.

On peut obtenir des caractérisations de réalisabilité en termes de géométrie algébrique.

Existence de solution et condition d'optimalité

Existence de solution

Notons $(P_{L})$ le problème d'optimisation linéaire primal et $(D_{L})$ son dual lagrangien. En optimisation linéaire, les résultats d'existence de solution et de dualité forte assurent que les propriétés suivantes sont équivalentes :

• $(P_{L})$ et $(D_{L})$ sont réalisables,
• $(P_{L})$ est réalisable et borné,
• $(D_{L})$ est réalisable et borné,
• $(P_{L})$ a une solution,
• $(D_{L})$ a une solution.

De plus, dans chacun de ces cas, il n'y a pas de saut de dualité.

Bien que l'optimisation linéaire et l'optimisation SDP aient une structure très semblable, les équivalences ci-dessus ne tiennent plus en optimisation SDP. Voici quelques contre-exemples qui pourront servir de garde-fous.

1. $(P_{SDP})$ est réalisable et borné, mais n'a pas de solution ; $(D_{SDP})$ a une solution ; il n'y a pas de saut de dualité. Voici un exemple avec $n=2$ et $m=1$ :
   $C={\begin{pmatrix}2&-1\\-1&0\end{pmatrix}},\quad A_{1}={\begin{pmatrix}0&-1\\-1&2\end{pmatrix}},\quad b=2.$
2. $(P_{SDP})$ a une solution ; $(D_{SDP})$ est réalisable et borné, mais n'a pas de solution ; il n'y a pas de saut de dualité ; c'est le cas symétrique du précédent. Voici un exemple avec $n=2$ et $m=2$ :
   $C={\begin{pmatrix}0&1\\1&0\end{pmatrix}},\quad A_{1}={\begin{pmatrix}-1&0\\0&0\end{pmatrix}},\quad A_{2}={\begin{pmatrix}0&0\\0&-1\end{pmatrix}},\quad b={\begin{pmatrix}-1\\0\end{pmatrix}}.$
3. $(P_{SDP})$ n'est pas réalisable ; $(D_{SDP})$ a une solution. Voici un exemple avec $n=2$ et $m=2$ :
   $C={\begin{pmatrix}0&0\\0&0\end{pmatrix}},\quad A_{1}={\begin{pmatrix}1&0\\0&0\end{pmatrix}},\quad A_{2}={\begin{pmatrix}0&1\\1&0\end{pmatrix}},\quad b={\begin{pmatrix}0\\2\end{pmatrix}}.$
4. $(P_{SDP})$ et $(D_{SDP})$ ont une solution ; il y a un saut de dualité. Voici un exemple avec $n=3$ et $m=2$ :
   $C={\begin{pmatrix}0&0&0\\0&0&0\\0&0&1\end{pmatrix}},\quad A_{1}={\begin{pmatrix}1&0&0\\0&0&0\\0&0&0\end{pmatrix}},\quad A_{2}={\begin{pmatrix}0&1&0\\1&0&0\\0&0&2\end{pmatrix}},\quad b={\begin{pmatrix}0\\2\end{pmatrix}}.$

Le résultat d'existence de solution classique est le suivant. Il prend comme hypothèse des conditions ressemblant à la qualification de Slater.

Existence de solution — 

1. Si ${\mathcal {A}}_{P}\times {\mathcal {A}}_{D}^{s}\neq \varnothing$, alors $\operatorname {sol} (P_{SDP})$ est non vide et borné et il n'y a pas de saut de dualité.
2. Si ${\mathcal {A}}_{P}^{s}\times {\mathcal {A}}_{D}\neq \varnothing$ et si $A$ est surjective, alors $\operatorname {sol} (D_{SDP})$ est non vide et borné et il n'y a pas de saut de dualité.
3. Si ${\mathcal {A}}^{s}\neq \varnothing$ et si $A$ est surjective, alors $\operatorname {sol} (P_{SDP})$ et $\operatorname {sol} (D_{SDP})$ sont non vides et bornés et il n'y a pas de saut de dualité.

Méthodes de résolution

Il existe plusieurs méthodes de résolution : les méthodes de points intérieurs, la méthode du lagrangien augmenté (on connait par exemple une adaptation de l'algorithme des directions alternées aux problèmes SDP, voir Wen, Goldfarb et Yin (2010), et les méthodes non-différentiables.

Complexité

On peut résoudre le problème avec une erreur additive $\epsilon$ en un temps polynomial en la taille du problème et en $\log(1/\epsilon )$.

Exemples de modélisation SDP

Beaucoup de problèmes convexes ont une formulation SDP. L'intérêt d'exhiber une telle formulation est de montrer que l'on peut les résoudre par des algorithmes polynomiaux, souvent efficaces. Certains problèmes non convexes ont une relaxation SDP précise, c'est-à-dire qu'il existe un problème d'optimisation SDP dont la valeur optimale est proche de celle du problème original.

Pour plusieurs problèmes algorithmiques le meilleur algorithme d'approximation connu utilise ce type d'optimisation, qui autorise une modélisation plus générale du problème, mais en conservant la résolution en temps polynomial. L'exemple le plus connu est celui du problème de la coupe maximum avec l'algorithme de Goemans et Williamson.

Logiciels

Voir le site de Christoph Helmberg.

• PENSDP (en Matlab), par TOMLAB Optimization Inc., interface pour PENNON.
• SDLS (en Matlab), par D. Henrion, J. Malick, résout des problèmes de moindres-carrés coniques.
• SeDuMi (en Matlab), initié par Jos F. Sturm, utilise une méthode de points intérieurs (résout plus généralement des problèmes d'optimisation conique pour des cônes homogènes auto-duaux).

Annexes

Articles connexes

• Optimisation conique
• Optimisation linéaire
• Conditions d'optimalité (dimension finie)

Lien externe

• J. Ch. Gilbert, Éléments d'Optimisation Différentiable — Théorie et Algorithmes, syllabus de cours à l'ENSTA ParisTech, Paris.

Bibliographie

• (en) F. Alizadeh (1995). Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM Journal on Optimization, 5, 13–51.
• (en) M. F. Anjos, J.-B. Lasserre (2012). Handbook on Semidefinite, Conic and Polynomial Optimization. Springer.
• (en) E. de Klerk (2002). Aspects of Semidefinite Programming - Interior Point Algorithms and Selected Applications. Kluwer Academic Publishers, Dordrecht.
• (en) R. D. C. Monteiro (2003). First- and second-order methods for semidefinite programming. Mathematical Programming, 97, 209–244.
• (en) L. Vandenberghe, S. Boyd (1996). Semidefinite programming. SIAM Review, 38, 49–95.
• (en) H. Wolkowicz, R. Saigal, L. Vandenberghe, éditeurs (2000). Handbook of Semidefinite Programming – Theory, Algorithms, and Applications. Kluwer Academic Publishers.