Optimisation semi-définie positive

Optimisation semi-définie positive

L’optimisation semi-définie positive (optimisation SDP ou OSDP) a connu un essor important dans les années 1990 pour au moins quatre raisons. D’abord, bien qu’ils soient non linéaires, les problèmes d’optimisation SDP peuvent être résolus en un nombre d’itérations polynomial. Ensuite, un grand nombre de problèmes convexes ont pu être exprimés dans ce formalisme, ce qui montre par conséquent qu’ils sont polynomialement résolubles. Puis, certains problèmes non convexes (en particulier des problèmes combinatoires) ont une relaxation SDP précise, qui permet de leur trouver rapidement une solution approchée de qualité. Enfin, certains problèmes non convexes peuvent être approché par une hiérarchie de problèmes SDP dont les valeurs optimales convergent vers celle du problèmes original (mais se pose dans des espaces vectoriels de dimension de plus en plus grande). Les problèmes d’optimisation SDP ont une structure assez semblable à celle de l’optimisation linéaire (OL), ce qui les rend très vite familiers. Les résultats que l’on connaît en OL ne s’étendent cependant pas tous tels quels à l’optimisation SDP ; on ne peut guère en être étonné, vu la généralité du formalisme. Notre compte-rendu s’attachera à relever quelques subtilités qui ne peuvent être ignorées. Connaissances supposées. La dualité par perturbation (section 14.2) pour établir l’existence de solutions primale et duale ; la notion de fonction asymptotique (section 3.3.4) pour l’existence du chemin central. 20.1 Définition du problème d’optimisation SDP

Les problèmes primal et dual

 Les cônes S n + et S n ++ On note S n l’espace vectoriel des matrices d’ordre n symétriques, qui est de dimension n(n+ 1)/2, S n + le cône de S n formé des matrices semi-définies positives et S n ++ le cône de S n formé des matrices définies positives. On note aussi A < B [resp. A ≻ B] au lieu de A−B ∈ Sn + [resp. A−B ∈ Sn ++]. La relation < introduit un ordre partiel sur S n, dit de Löwner. Les relations 4 et ≺ s’introduisent naturellement : A 4 B équivaut à B − A < 0 et A ≺ B équivaut à B − A ≻ 0. On munit S n du produit scalaire hA, Bi = tr AB = Pn i,j=1 AijBij (tr A désigne la trace de la matrice A). La norme associée à ce produit scalaire est le norme de Frobenius kAkF = (Pn i,j=1 A2 ij ) 1/2 . Voici quelques propriétés des cônes S n + et S n ++ qui nous seront utiles. Lemme 20.1 (cônes S n + et S n ++) 1) A < 0 ⇐⇒ ∀ B < 0, on a hA, Bi > 0. 2) A ≻ 0 ⇐⇒ ∀ B < 0 non nulle, on a hA, Bi > 0. 3) Si A et B ∈ Sn +, on a hA, Bi = 0 ⇐⇒ AB = 0. Démonstration. 1) C’est l’exercice 2.35. P 2) Soit A ≻ 0. Si B < 0 est non nulle, elle a une factorisation spectrale B = n i=1 λiviv T i avec au moins un λi > 0 (les autres valeurs propres sont > 0). Alors hA, Bi = Pn i=1 λi tr(Aviv T i ) = Pn i=1 λiv T i Avi > 0, puisque tous les v T i Avi > 0 et au moins un des λi > 0. Inversement, supposons que hA, Bi > 0 pour toute matrice B < 0 non nulle. En prenant B = vvT < 0, avec v quelconque non nul, on doit avoir 0 < hA, Bi = v TAv, ce qui montre que A ≻ 0. 3) Il est clair que AB = 0 implique que hA, Bi = 0. Réciproquement, avec la factorisation spectrale de A = Pn i=1 λiviv T i P (les λi sont > 0) et hA, Bi = 0, on a i λiviBvT i = 0. Comme B ∈ Sn +, on en déduit que Bvi = 0 lorsque λi > 0. Alors AB = Pn i=1 λiviv T i B = 0. ✷ La propriété du point 1, attribuée à Fejér, exprime l’autodualité du cône S n + : (S n +) + = S n +. Si v est un vecteur, on notera Diag(v) la matrice diagonale dont les éléments diagonaux sont les composantes vi de v. 

Le problème primal 

On se donne C ∈ Sn, A : S n → R m une application linéaire, et b ∈ R m. Le problème primal consiste à trouver X ∈ Sn solution de (P)    inf hC, Xi A(X) = b X < 0. (20.1) Ce problème a une structure très semblable à la forme standard (17.1) d’un problème d’optimisation linéaire. À première vue, les seules différences sont que l’on travaille sur l’espace des matrices S n plutôt que R n (mais cela reste un espace vectoriel) et que la contrainte de positivité est remplacée par la contrainte de semi-définie positivité de la matrice X (d’où le nom du problème). Il n’y en a pas d’autres en effet, mais cela implique que certaines propriétés de l’optimisation linéaire ne seront pas conservées en optimisation SDP. Examinons le problème plus en détail. Le critère et la contrainte d’égalité sont linéaires (ou affines), mais la contrainte d’appartenance au cône S n + est « très » non linéaire, éventuellement non différentiable. Elle exprime en effet que v TXv > 0 pour tout v ∈ R n ; de ce point de vue, (20.1) 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 primal 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 primal est non linéaire, non convexe, à données polynomiales. On note val(P) la valeur optimale de (P) et Fp := {X ∈ Sn : A(X) = b, X < 0} (20.2a) F s p := {X ∈ Sn : A(X) = b, X ≻ 0}, (20.2b) les ensembles des matrices admissibles et strictement admissibles de (P). On peut représenter A au moyen de m matrices Ai ∈ Sn (théorème A.3 de RieszFréchet). On a A(X) =   hA1, Xi . . . hAm, Xi   . (20.3) Dans cette représentation, l’application A est surjective si, et seulement si, les matrices Ai sont linéairement indépendantes dans S n.

Le problème dual 

On se donne un produit scalaire sur R m, également noté h·, ·i, et l’on introduit l’opérateur A∗ : R m → Sn adjoint de A, qui est défini par ∀ X ∈ Sn , ∀ y ∈ R m : hA(X), yi = hX, A ∗ (y)i. La méthode la plus simple pour obtenir un dual de (P) est d’utiliser la dualisation lagrangienne de sa contrainte d’égalité. On utilise le lagrangien ℓ : S n + × R m → R défini par ℓ(X, y) = hC, Xi − hy, A(X) − bi (20.4) et l’on écrit (P) comme un inf-sup : inf X∈Sn + sup y∈Rm ℓ(X, y). Le problème dual s’obtient alors en inversant l’infimum et le supremum (c’est la dualité min-max de la section 14.1). En utilisant le lemme 20.1, on obtient sup y∈Rm inf X∈Sn + ℓ(X, y) = sup y∈Rm inf X∈Sn + hC − A∗ (y), Xi + hb, yi = sup y∈Rm  hb, yi si C − A∗ (y) < 0 −∞ sinon. Le problème dual de (P) obtenu par ce procédé consiste donc à trouver (y, S) ∈ R m × Sn solution de (D)    sup hb, yi A∗ (y) + S = C S < 0.

Réalisabilités primale et duale

Intéressons-nous à présent à la question de la réalisabilité des problèmes primal et dual.Quand peut-on trouver une matrice X < 0 telle que A(X) = b ? Quand peut-on trouver un vecteur y ∈ R m tel que A∗ (y) 4 C ? Les contraintes sont-elles qualifiées et dans quel sens ? Dans (R n , >), une partie de ces questions trouve une réponse dans le lemme de Farkas (proposition 2.45). Une application de ce lemme à l’optimisation SDP s’obtient en prenant E := S n, F := R m, l’application linéaire A : S n → R m et K := S n + ; cela donne {y ∈ R m : A ∗ (y) < 0} + = adhA(S n +). (20.10) On ne peut pas se passer de l’adhérence à droite, car A(S n +) n’est pas nécessairement un fermé, alors que le cône dual à gauche est toujours fermé (point 1 de la proposition 2.43) ; voir l’exercice 2.23 pour un exemple de cône A(S n +) non fermé. L’identité (20.10) nous donnera de l’information sur l’admissibilité du problème primal (20.1). Pour avoir de l’information sur l’admissibilité du problème dual (20.5), on utilise le lemme de Farkas sous la forme du point 1 de l’exercice 2.38, avec E := R m, F := S n, l’application linéaire A∗ , K = R m et L = S n + ; cela donne {X ∈ Sn + : A(X) = 0} + = adh