Matrice copositive

En mathématiques et plus particulièrement en algèbre linéaire, en optimisation et en complémentarité linéaire, une matrice réelle carrée M {\displaystyle M} est dite :

  • copositive si pour tout x ⩾ 0 {\displaystyle x\geqslant 0} , x ⊤ M x ⩾ 0 {\displaystyle x^{\top }Mx\geqslant 0}  ;
  • strictement copositive si pour tout x ⩾ 0 {\displaystyle x\geqslant 0} non nul, x ⊤ M x > 0 {\displaystyle x^{\top }Mx>0}  ;
  • copositive-plus si M {\displaystyle M} est copositive et si x ⊤ M x = 0 {\displaystyle x^{\top }Mx=0} et x ⩾ 0 {\displaystyle x\geqslant 0} impliquent ( M + M ⊤ ) x = 0 {\displaystyle (M+M^{\top })x=0}  ;
  • copositive-étoile si M {\displaystyle M} est copositive et si x ⊤ M x = 0 {\displaystyle x^{\top }Mx=0} , M x ⩾ 0 {\displaystyle Mx\geqslant 0} et x ⩾ 0 {\displaystyle x\geqslant 0} impliquent M ⊤ x ⩽ 0 {\displaystyle M^{\top }x\leqslant 0} .

L'ensemble des matrices copositives est noté C P {\displaystyle \mathbf {CP} } , celui des matrices strictement copositives est noté C P s {\displaystyle \mathbf {CP_{s}} } , celui des matrices copositives-plus est noté C P + {\displaystyle \mathbf {CP_{+}} } et celui des matrices copositives-étoile est noté C P ∗ {\displaystyle \mathbf {CP_{*}} } .

La notion de matrice copositive symétrique a été introduite et étudiée par Motzkin (1952[1]).

Propriétés immédiates

Les ensembles C P s {\displaystyle \mathbf {CP_{s}} } , C P + {\displaystyle \mathbf {CP_{+}} } , C P ∗ {\displaystyle \mathbf {CP_{*}} } , C P {\displaystyle \mathbf {CP} } sont des cônes non vides. Les cônes C P s {\displaystyle \mathbf {CP_{s}} } et C P {\displaystyle \mathbf {CP} } sont convexes (intersections de demi-espaces).

Les ensembles C P s {\displaystyle \mathbf {CP_{s}} } , C P + {\displaystyle \mathbf {CP_{+}} } , C P ∗ {\displaystyle \mathbf {CP_{*}} } , C P {\displaystyle \mathbf {CP} } sont reliés entre eux par la chaîne d'inclusions suivante :

C P s ⊂ C P + ⊂ C P ∗ ⊂ C P . {\displaystyle \mathbf {CP_{s}} \subset \mathbf {CP_{+}} \subset \mathbf {CP_{*}} \subset \mathbf {CP} .}

Aucun de ces ensembles n'est vide, car la matrice identité est strictement copositive (donc C P s ≠ ∅ {\displaystyle \mathbf {CP_{s}} \neq \varnothing } ). Par ailleurs, aucune de ces inclusions n'est une égalité car

0 ∈ C P + ∖ C P s , ( 0 − 1 2 1 ) ∈ C P ∗ ∖ C P + et ( 0 1 1 1 ) ∈ C P ∖ C P ∗ . {\displaystyle 0\in \mathbf {CP_{+}} \setminus \mathbf {CP_{s}} ,\qquad {\begin{pmatrix}0&-1\\2&1\end{pmatrix}}\in \mathbf {CP_{*}} \setminus \mathbf {CP_{+}} \qquad {\mbox{et}}\qquad {\begin{pmatrix}0&1\\1&1\end{pmatrix}}\in \mathbf {CP} \setminus \mathbf {CP_{*}} .}

Seul le cône C P {\displaystyle \mathbf {CP} } est fermé (intersection de demi-espaces fermés). Par ailleurs, si l'on note «  adh ⁡ A {\displaystyle \operatorname {adh} A}  » l'adhérence d'un ensemble A {\displaystyle A} , on a (on approche M ∈ C P {\displaystyle M\in \mathbf {CP} } par M + t I ∈ C P s {\displaystyle M+tI\in \mathbf {CP_{s}} } avec t ↓ 0 {\displaystyle t\downarrow 0} )

adh ⁡ C P s = adh ⁡ C P + = adh ⁡ C P ∗ = C P . {\displaystyle \operatorname {adh} \mathbf {CP_{s}} =\operatorname {adh} \mathbf {CP_{+}} =\operatorname {adh} \mathbf {CP_{*}} =\mathbf {CP} .}

On montre aussi facilement les inclusions suivantes :

   D P ⊂ C P s , {\displaystyle \mathbf {DP} \subset \mathbf {CP_{s}} ,}   

      

   S D P ⊂ C P + {\displaystyle \mathbf {SDP} \subset \mathbf {CP_{+}} }   

      et       

   P O S ⊂ C P , {\displaystyle \mathbf {POS} \subset \mathbf {CP} ,}   

où D P {\displaystyle \mathbf {DP} } désigne l'ensemble des matrices définies positives, S D P {\displaystyle \mathbf {SDP} } désigne l'ensemble des matrices semi-définies positives (à forme quadratique associée positive) et P O S {\displaystyle \mathbf {POS} } désigne l'ensemble des matrices positives.

Propriétés des éléments — Si M ∈ C P {\displaystyle M\in \mathbf {CP} } , alors

  • M i i ⩾ 0 {\displaystyle M_{ii}\geqslant 0} , pour tout i ∈ [ [ 1 , n ] ] {\displaystyle i\in [\![1,n]\!]} ,
  • 4 M i i M j j ⩾ [ ( M i j + M j i ) − ] 2 {\displaystyle 4M_{ii}M_{jj}\geqslant [(M_{ij}+M_{ji})^{-}]^{2}} , pour tout i ≠ j {\displaystyle i\neq j} dans [ [ 1 , n ] ] {\displaystyle [\![1,n]\!]}  ; en particulier, M i i = 0 {\displaystyle M_{ii}=0} implique que M i j + M j i ⩾ 0 {\displaystyle M_{ij}+M_{ji}\geqslant 0} pour tout j ∈ [ [ 1 , n ] ] {\displaystyle j\in [\![1,n]\!]} .

Si M ∈ C P s {\displaystyle M\in \mathbf {CP_{s}} } , alors

  • M i i > 0 {\displaystyle M_{ii}>0} , pour tout i ∈ [ [ 1 , n ] ] {\displaystyle i\in [\![1,n]\!]} ,
  • 4 M i i M j j > [ ( M i j + M j i ) − ] 2 {\displaystyle 4M_{ii}M_{jj}>[(M_{ij}+M_{ji})^{-}]^{2}} , pour tout i ≠ j {\displaystyle i\neq j} dans [ [ 1 , n ] ] {\displaystyle [\![1,n]\!]} .

Critères de copositivité

Le problème de décision consistant à déterminer si une matrice M ∈ Q n × n {\displaystyle M\in \mathbb {Q} ^{n\times n}} est copositive est co-NP-complet[2].

Critères fondés sur les sous-matrices principales

Pour les matrices symétriques, on dispose de critères utilisant la décomposition spectrale des sous-matrices principales. Le résultat suivant est dû à Kaplan (2000[3]). La notation v > 0 {\displaystyle v>0} signifie que toutes les composantes de v {\displaystyle v} sont/doivent être strictement positives.

Critères spectraux — Soit M ∈ R n × n {\displaystyle M\in \mathbb {R} ^{n\times n}} symétrique. Alors

  • M ∈ C P {\displaystyle M\in \mathbf {CP} } si, et seulement si, tous les vecteurs propres v > 0 {\displaystyle v>0} des sous-matrices principales de M {\displaystyle M} ont leur valeur propre ⩾ 0 {\displaystyle \geqslant 0} ,
  • M ∈ C P s {\displaystyle M\in \mathbf {CP_{s}} } si, et seulement si, tous les vecteurs propres v > 0 {\displaystyle v>0} des sous-matrices principales de M {\displaystyle M} ont leur valeur propre > 0 {\displaystyle >0} .

Critères simplexiques

Pour les matrices symétriques, voir Andersson, Chang et Elfving (1995[4]), Bundfuss et Dür (2008[5]).

Copositivité et complémentarité linéaire

Problème de complémentarité linéaire

Étant donnés une matrice réelle carrée M ∈ R n × n {\displaystyle M\in \mathbb {R} ^{n\times n}} et un vecteur q ∈ R n {\displaystyle q\in \mathbb {R} ^{n}} , un problème de complémentarité linéaire consiste à trouver un vecteur x ∈ R n {\displaystyle x\in \mathbb {R} ^{n}} tel que x ⩾ 0 {\displaystyle x\geqslant 0} , M x + q ⩾ 0 {\displaystyle Mx+q\geqslant 0} et x ⊤ ( M x + q ) = 0 {\displaystyle x^{\!\top }(Mx+q)=0} , ce que l'on écrit de manière abrégée comme suit :

CL ( M , q ) : 0 ⩽ x ⊥ ( M x + q ) ⩾ 0. {\displaystyle {\mbox{CL}}(M,q):\qquad 0\leqslant x\perp (Mx+q)\geqslant 0.}

Existence de solution

En général, la copositivité de M {\displaystyle M} ne suffit pas pour que CL ⁡ ( M , q ) {\displaystyle \operatorname {CL} (M,q)} ait une solution, quel que soit q {\displaystyle q} . Par exemple, 0 ∈ C P {\displaystyle 0\in \mathbf {CP} } , mais CL ⁡ ( 0 , q ) {\displaystyle \operatorname {CL} (0,q)} a une solution si, et seulement si, q ⩾ 0 {\displaystyle q\geqslant 0} . Le résultat suivant donne des conditions sur ( M , q ) {\displaystyle (M,q)} avec M ∈ C P {\displaystyle M\in \mathbf {CP} } pour que CL ⁡ ( M , q ) {\displaystyle \operatorname {CL} (M,q)} ait une solution.

Existence de solution avec matrice copositive — Si M ∈ C P {\displaystyle M\in \mathbf {CP} } et q ∈ { x ∈ R + n : x ⊤ M x = 0 ,   M x ⩾ 0 } + {\displaystyle q\in \{x\in \mathbb {R} _{+}^{n}:x^{\top }Mx=0,~Mx\geqslant 0\}^{+}} (cône dual positif), alors CL ⁡ ( M , q ) {\displaystyle \operatorname {CL} (M,q)} a une solution.

En corollaire, on a

C P s ⊂ C P ∩ R 0 ⊂ C P ∗ ∩ Q , {\displaystyle \mathbf {CP_{s}} \subset \mathbf {CP} \cap \mathbf {R_{0}} \subset \mathbf {CP_{*}} \cap \mathbf {Q} ,}

où

  • R 0 {\displaystyle \mathbf {R_{0}} } désigne l'ensemble des R0-matrices, c'est-à-dire des matrices M {\displaystyle M} telles que Sol ⁡ ( M , 0 ) = { 0 } {\displaystyle \operatorname {Sol} (M,0)=\{0\}} ou encore telles que 0 ⩽ x ⊥ M x ⩾ 0 {\displaystyle 0\leqslant x\perp Mx\geqslant 0} implique que x = 0 {\displaystyle x=0} ,
  • Q {\displaystyle \mathbf {Q} } désigne l'ensemble des Q-matrices, c'est-à-dire des matrices M ∈ R n × n {\displaystyle M\in \mathbb {R} ^{n\times n}} pour lesquelles le problème de complémentarité linéaire CL ⁡ ( M , q ) {\displaystyle \operatorname {CL} (M,q)} a une solution quel que soit q ∈ R n {\displaystyle q\in \mathbb {R} ^{n}} .

Propriétés variationnelles

Les caractérisations suivantes de la copositivité (stricte) d'une matrice M ∈ R n × n {\displaystyle M\in \mathbb {R} ^{n\times n}} se font au moyen de la fonction quadratique

φ : R n → R : x ↦ x ⊤ ( M x + q ) , {\displaystyle \varphi :\mathbb {R} ^{n}\to \mathbb {R} :x\mapsto x^{\top }(Mx+q),}

où q ∈ R n {\displaystyle q\in \mathbb {R} ^{n}} . On y a noté R + n := { x ∈ R n : x ⩾ 0 } {\displaystyle \mathbb {R} _{+}^{n}:=\{x\in \mathbb {R} ^{n}:x\geqslant 0\}} l'ensemble des vecteurs dont les composantes sont positives.

Caractérisations de la copositivité — Soit M ∈ R n × n {\displaystyle M\in \mathbb {R} ^{n\times n}} . On a

  • M ∈ C P {\displaystyle M\in \mathbf {CP} } si, et seulement si, pour tout q ⩾ 0 {\displaystyle q\geqslant 0} , φ {\displaystyle \varphi } est bornée inférieurement sur R + n {\displaystyle \mathbb {R} _{+}^{n}} ,
  • M ∈ C P s {\displaystyle M\in \mathbf {CP_{s}} } si, et seulement si, pour tout q ∈ R n {\displaystyle q\in \mathbb {R} ^{n}} , φ {\displaystyle \varphi } est bornée inférieurement sur R + n {\displaystyle \mathbb {R} _{+}^{n}} .

Annexes

Notes

  1. ↑ Selon Cottle, Pang et Stone (2009), la notion de matrice copositive symétrique a été introduite et étudiée par Motzkin en 1952 dans un rapport sans titre du National Bureau of Standards, le rapport 1818, pages 11-12.
  2. ↑ Ce résultat a été obtenu par Murty et Kabadi (1987). Ils montrent que le problème de la somme de sous-ensembles (subset sum) peut se réduire à un test de copositivité. Voir aussi Dickinson et Gijben (2011).
  3. ↑ (en) W. Kaplan, « A test for copositive matrices », Linear Algebra and its Applications, vol. 313,‎ , p. 203–206.
  4. ↑ (en) L.-E. Andersson, G. Chang et T. Elfving, « Criteria for copositive matrices using simplices and barycentric coordinates », Linear Algebra and its Applications, vol. 313 220,‎ , p. 9–30.
  5. ↑ (en) S. Bundfuss et M. Dür, « Algorithmic copositivity detection by simplicial partition », Linear Algebra and its Applications, vol. 428,‎ , p. 1511–1523.

Articles connexes

Bibliographie

  • (en) A. Berman et N. Shaked-Monderer, Completely Positive Matrices, River Edge, NJ, USA, World Scientific, .
  • (en) S. Bundfuss, Copositive Matrices, Copositive Programming, and Applications, Universität Darmstadt, Dissertation, Technischen, .
  • (en) R. W. Cottle, J.-S. Pang et R. E. Stone, The linear complementarity problem. Classics in Applied Mathematics, vol. 60, Philadelphia, PA, USA, SIAM, .
  • (en) P.J.C. Dickinson et L. Gijben, On the computational complexity of membership problems for the completely positive cone and its dual, (lire en ligne)
  • (en) M. Hall et M. Newman, « Copositive and completely positive quadratic forms », Proceedings Cambridge Philos. Soc., vol. 59,‎ , p. 329–339.
  • (en) K. G. Murty et S. N. Kabadi, « Some NP-complete problems in quadratic and nonlinear programming », Mathematical Programming, vol. 39,‎ , p. 117–129.
v · m
Matrices
Forme
Transformée
Relation
Propriété
Famille
Associée
Résultats
Décompositions
Articles liés
  • icône décorative Portail des mathématiques