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^[1]).

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^[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$ 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^[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\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₀-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

${\displaystyle \varphi$

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}$ .

Matrice copositive

Critères de copositivité

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

Critères simplexiques

Copositivité et complémentarité linéaire

Problème de complémentarité linéaire

Existence de solution

Propriétés variationnelles

Annexes

Notes

Articles connexes

Bibliographie

Related Articles