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⩾0$, $x^{\mathrm{\top }}Mx⩾0$ ;
• strictement copositive si pour tout $x⩾0$ non nul, $x^{\mathrm{\top }}Mx>0$ ;
• copositive-plus si $M$ est copositive et si $x^{\mathrm{\top }}Mx=0$ et $x⩾0$ impliquent $(M+M^{\mathrm{\top }})x=0$ ;
• copositive-étoile si $M$ est copositive et si $x^{\mathrm{\top }}Mx=0$, $Mx⩾0$ et $x⩾0$ impliquent $M^{\mathrm{\top }}x⩽0$.

L'ensemble des matrices copositives est noté $𝐂𝐏$, celui des matrices strictement copositives est noté $𝐂{𝐏}_{𝐬}$, celui des matrices copositives-plus est noté $𝐂{𝐏}_{\mathbf{+}}$ et celui des matrices copositives-étoile est noté $𝐂{𝐏}_{\mathbf{*}}$.

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

Propriétés immédiates

Les ensembles $𝐂{𝐏}_{𝐬}$, $𝐂{𝐏}_{\mathbf{+}}$, $𝐂{𝐏}_{\mathbf{*}}$, $𝐂𝐏$ sont des cônes non vides. Les cônes $𝐂{𝐏}_{𝐬}$ et $𝐂𝐏$ sont convexes (intersections de demi-espaces).

Les ensembles $𝐂{𝐏}_{𝐬}$, $𝐂{𝐏}_{\mathbf{+}}$, $𝐂{𝐏}_{\mathbf{*}}$, $𝐂𝐏$ sont reliés entre eux par la chaîne d'inclusions suivante :

Aucun de ces ensembles n'est vide, car la matrice identité est strictement copositive (donc $𝐂{𝐏}_{𝐬}\ne \varnothing$). Par ailleurs, aucune de ces inclusions n'est une égalité car

$0\in 𝐂{𝐏}_{\mathbf{+}}\setminus 𝐂{𝐏}_{𝐬},\left(\begin{array}{cc}0& -1\\ 2& 1\end{array}\right)\in 𝐂{𝐏}_{\mathbf{*}}\setminus 𝐂{𝐏}_{\mathbf{+}}\text{et}\left(\begin{array}{cc}0& 1\\ 1& 1\end{array}\right)\in 𝐂𝐏\setminus 𝐂{𝐏}_{\mathbf{*}}.$

Seul le cône $𝐂𝐏$ est fermé (intersection de demi-espaces fermés). Par ailleurs, si l'on note « $\mathrm{adh}A$ » l'adhérence d'un ensemble $A$, on a (on approche $M\in 𝐂𝐏$ par $M+tI\in 𝐂{𝐏}_{𝐬}$ avec $t\downarrow 0$) Modèle:Bloc emphase

On montre aussi facilement les inclusions suivantes :

$𝐃𝐏\subset 𝐂{𝐏}_{𝐬},$

$𝐒𝐃𝐏\subset 𝐂{𝐏}_{\mathbf{+}}$

et

$𝐏𝐎𝐒\subset 𝐂𝐏,$

où $𝐃𝐏$ désigne l'ensemble des matrices définies positives, $𝐒𝐃𝐏$ désigne l'ensemble des matrices semi-définies positives (à forme quadratique associée positive) et $𝐏𝐎𝐒$ désigne l'ensemble des matrices positives.

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 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 {ℝ}^{n\times n}$ et un vecteur $q\in {ℝ}^n$, un problème de complémentarité linéaire consiste à trouver un vecteur $x\in {ℝ}^n$ tel que $x⩾0$, $Mx+q⩾0$ et $x^{\mathrm{\top }}(Mx+q)=0$, ce que l'on écrit de manière abrégée comme suit :

$\text{CL}(M,q):0⩽x\perp (Mx+q)⩾0.$

Existence de solution

En général, la copositivité de $M$ ne suffit pas pour que $\mathrm{CL}(M,q)$ ait une solution, quel que soit $q$. Par exemple, $0\in 𝐂𝐏$, mais $\mathrm{CL}(0,q)$ a une solution si, et seulement si, $q⩾0$. Le résultat suivant donne des conditions sur $(M,q)$ avec $M\in 𝐂𝐏$ pour que $\mathrm{CL}(M,q)$ ait une solution.

En corollaire, on a

où

• ${𝐑}_{\mathrm{𝟎}}$ désigne l'ensemble des [[R0-matrice|RModèle:Ind-matrices]], c'est-à-dire des matrices $M$ telles que $\mathrm{Sol}(M,0)=\{0\}$ ou encore telles que $0⩽x\perp Mx⩾0$ implique que $x=0$,
• $𝐐$ désigne l'ensemble des Q-matrices, c'est-à-dire des matrices $M\in {ℝ}^{n\times n}$ pour lesquelles le problème de complémentarité linéaire $\mathrm{CL}(M,q)$ a une solution quel que soit $q\in {ℝ}^n$.

Propriétés variationnelles

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

$\phi :{ℝ}^n\to ℝ:x\mapsto x^{\mathrm{\top }}(Mx+q),$

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

Annexes

Articles connexes

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

Bibliographie

• Modèle:Ouvrage.
• Modèle:Ouvrage.
• Modèle:Ouvrage.
• Modèle:Ouvrage
• Modèle:Article.
• Modèle:Article.