title: Matrice copositive
text: # 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$ est dite :
  
  * copositive si pour tout $x\geqslant 0$, $x^{\top }Mx\geqslant 0$ ;
  * strictement copositive si pour tout $x\geqslant 0$ non nul, $x^{\top }Mx>0$ ;
  * copositive-plus si $M$ est copositive et si $x^{\top }Mx=0$ et $x\geqslant 0$ impliquent $(M+M^{\top })x=0$ ;
  * copositive-étoile si $M$ est copositive et si $x^{\top }Mx=0$, $Mx\geqslant 0$ et $x\geqslant 0$ impliquent $M^{\top }x\leqslant 0$.
  
  L'ensemble des matrices copositives est noté $\mathbf {CP}$, celui des matrices strictement copositives est noté $\mathbf {CP_{s}}$, celui des matrices copositives-plus est noté $\mathbf {CP_{+}}$ et celui des matrices copositives-étoile est noté $\mathbf {CP_{*}}$.
  
  La notion de matrice copositive symétrique a été introduite et étudiée par Motzkin (1952).
  
  ## Propriétés immédiates
  
  Les ensembles $\mathbf {CP_{s}}$, $\mathbf {CP_{+}}$, $\mathbf {CP_{*}}$, $\mathbf {CP}$ sont des cônes non vides. Les cônes $\mathbf {CP_{s}}$ et $\mathbf {CP}$ sont convexes (intersections de demi-espaces).
  
  Les ensembles $\mathbf {CP_{s}}$, $\mathbf {CP_{+}}$, $\mathbf {CP_{*}}$, $\mathbf {CP}$ sont reliés entre eux par la chaîne d'inclusions suivante :
  
  $\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 $\mathbf {CP_{s}} \neq \varnothing$). Par ailleurs, aucune de ces inclusions n'est une égalité car
  
  $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 $\mathbf {CP}$ est fermé (intersection de demi-espaces fermés). Par ailleurs, si l'on note « $\operatorname {adh} A$ » l'adhérence d'un ensemble $A$, on a (on approche $M\in \mathbf {CP}$ par $M+tI\in \mathbf {CP_{s}}$ avec $t\downarrow 0$)
  
  $\operatorname {adh} \mathbf {CP_{s}} =\operatorname {adh} \mathbf {CP_{+}} =\operatorname {adh} \mathbf {CP_{*}} =\mathbf {CP} .$
  
  On montre aussi facilement les inclusions suivantes :
  
  | $\mathbf {DP} \subset \mathbf {CP_{s}} ,$ | $\mathbf {SDP} \subset \mathbf {CP_{+}}$ | et | $\mathbf {POS} \subset \mathbf {CP} ,$ |
  | - | - | - | - |
  
  où $\mathbf {DP}$ désigne l'ensemble des matrices définies positives, $\mathbf {SDP}$ désigne l'ensemble des matrices semi-définies positives (à forme quadratique associée positive) et $\mathbf {POS}$ désigne l'ensemble des matrices positives.
  
  Propriétés des éléments — Si $M\in \mathbf {CP}$, alors
  
  * $M_{ii}\geqslant 0$, pour tout $i\in [\![1,n]\!]$,
  * $4M_{ii}M_{jj}\geqslant [(M_{ij}+M_{ji})^{-}]^{2}$, pour tout $i\neq j$ dans $[\![1,n]\!]$ ; en particulier, $M_{ii}=0$ implique que $M_{ij}+M_{ji}\geqslant 0$ pour tout $j\in [\![1,n]\!]$.
  
  Si $M\in \mathbf {CP_{s}}$, alors
  
  * $M_{ii}>0$, pour tout $i\in [\![1,n]\!]$,
  * $4M_{ii}M_{jj}>[(M_{ij}+M_{ji})^{-}]^{2}$, pour tout $i\neq j$ dans $[\![1,n]\!]$.
  
  ## Critères de copositivité
  
  Le problème de décision consistant à déterminer si une matrice $M\in \mathbb {Q} ^{n\times n}$ est copositive est co-NP-complet.
  
  ### 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). La notation $v>0$ signifie que toutes les composantes de $v$ sont/doivent être strictement positives.
  
  Critères spectraux — Soit $M\in \mathbb {R} ^{n\times n}$ symétrique. Alors
  
  * $M\in \mathbf {CP}$ si, et seulement si, tous les vecteurs propres $v>0$ des sous-matrices principales de $M$ ont leur valeur propre $\geqslant 0$,
  * $M\in \mathbf {CP_{s}}$ si, et seulement si, tous les vecteurs propres $v>0$ des sous-matrices principales de $M$ ont leur valeur propre $>0$.
  
  ### Critères simplexiques
  
  Pour les matrices symétriques, voir Andersson, Chang et Elfving (1995), Bundfuss et Dür (2008).
  
  ## Copositivité et complémentarité linéaire
  
  ### Problème de complémentarité linéaire
  
  Étant donnés une matrice réelle carrée $M\in \mathbb {R} ^{n\times n}$ et un vecteur $q\in \mathbb {R} ^{n}$, un problème de complémentarité linéaire consiste à trouver un vecteur $x\in \mathbb {R} ^{n}$ tel que $x\geqslant 0$, $Mx+q\geqslant 0$ et $x^{\!\top }(Mx+q)=0$, ce que l'on écrit de manière abrégée comme suit :
  
  ${\mbox{CL}}(M,q):\qquad 0\leqslant x\perp (Mx+q)\geqslant 0.$
  
  ### Existence de solution
  
  En général, la copositivité de $M$ ne suffit pas pour que $\operatorname {CL} (M,q)$ ait une solution, quel que soit $q$. Par exemple, $0\in \mathbf {CP}$, mais $\operatorname {CL} (0,q)$ a une solution si, et seulement si, $q\geqslant 0$. Le résultat suivant donne des conditions sur $(M,q)$ avec $M\in \mathbf {CP}$ pour que $\operatorname {CL} (M,q)$ ait une solution.
  
  Existence de solution avec matrice copositive — Si $M\in \mathbf {CP}$ et $q\in \{x\in \mathbb {R} _{+}^{n}:x^{\top }Mx=0,~Mx\geqslant 0\}^{+}$ (cône dual positif), alors $\operatorname {CL} (M,q)$ a une solution.
  
  En corollaire, on a
  
  $\mathbf {CP_{s}} \subset \mathbf {CP} \cap \mathbf {R_{0}} \subset \mathbf {CP_{*}} \cap \mathbf {Q} ,$
  
  où
  
  * $\mathbf {R_{0}}$ désigne l'ensemble des $R_0-matrices,$ c'est-à-dire des matrices $M$ telles que $\operatorname {Sol} (M,0)=\{0\}$ ou encore telles que $0\leqslant x\perp Mx\geqslant 0$ implique que $x=0$,
  * $\mathbf {Q}$ désigne l'ensemble des Q-matrices, c'est-à-dire des matrices $M\in \mathbb {R} ^{n\times n}$ pour lesquelles le problème de complémentarité linéaire $\operatorname {CL} (M,q)$ a une solution quel que soit $q\in \mathbb {R} ^{n}$.
  
  ## Propriétés variationnelles
  
  Les caractérisations suivantes de la copositivité (stricte) d'une matrice $M\in \mathbb {R} ^{n\times n}$ se font au moyen de la fonction quadratique
  
  $\varphi :\mathbb {R} ^{n}\to \mathbb {R} :x\mapsto x^{\top }(Mx+q),$
  
  où $q\in \mathbb {R} ^{n}$. On y a noté $\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\in \mathbb {R} ^{n\times n}$. On a
  
  * $M\in \mathbf {CP}$ si, et seulement si, pour tout $q\geqslant 0$, $\varphi$ est bornée inférieurement sur $\mathbb {R} _{+}^{n}$,
  * $M\in \mathbf {CP_{s}}$ si, et seulement si, pour tout $q\in \mathbb {R} ^{n}$, $\varphi$ est bornée inférieurement sur $\mathbb {R} _{+}^{n}$.
  