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

Annexes

Articles connexes

• Matrice complètement positive : cet article aborde aussi le cas des matrices copositives symétriques
• Optimisation copositive

Bibliographie

• (en) A. Berman et N. Shaked-Monderer, Completely Positive Matrices, River Edge, NJ, USA, World Scientific, 2003.
• (en) S. Bundfuss, Copositive Matrices, Copositive Programming, and Applications, Universität Darmstadt, Dissertation, Technischen, 2009.
• (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, 2009.
• (en) P.J.C. Dickinson et L. Gijben, On the computational complexity of membership problems for the completely positive cone and its dual, 2011 (lire en ligne)
• (en) M. Hall et M. Newman, « Copositive and completely positive quadratic forms », Proceedings Cambridge Philos. Soc., vol. 59,‎ 1963, p. 329–339.
• (en) K. G. Murty et S. N. Kabadi, « Some NP-complete problems in quadratic and nonlinear programming », Mathematical Programming, vol. 39,‎ 1987, p. 117–129.