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

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

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

Propriétés immédiates

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

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

𝐂 𝐏_{𝐬} \subset 𝐂 𝐏_{+} \subset 𝐂 𝐏_{*} \subset 𝐂 𝐏 .

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

$0 \in 𝐂 𝐏_{+} ∖ 𝐂 𝐏_{𝐬}, (\begin{matrix} 0 & - 1 \\ 2 & 1 \end{matrix}) \in 𝐂 𝐏_{*} ∖ 𝐂 𝐏_{+} et (\begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix}) \in 𝐂 𝐏 ∖ 𝐂 𝐏_{*} .$

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

adh 𝐂 𝐏_{𝐬} = adh 𝐂 𝐏_{+} = adh 𝐂 𝐏_{*} = 𝐂 𝐏 .

On montre aussi facilement les inclusions suivantes :

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

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

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.

Propriétés des éléments — Si $M \in 𝐂 𝐏$ , alors

$M_{i i} ⩾ 0$ , pour tout $i \in [[1, n]]$ ,
$4 M_{i i} M_{j j} ⩾ [(M_{i j} + M_{j i})^{-}]^{2}$ , pour tout $i \neq j$ dans $[[1, n]]$ ; en particulier, $M_{i i} = 0$ implique que $M_{i j} + M_{j i} ⩾ 0$ pour tout $j \in [[1, n]]$ .

Si $M \in 𝐂 𝐏_{𝐬}$ , alors

$M_{i i} > 0$ , pour tout $i \in [[1, n]]$ ,
$4 M_{i i} M_{j j} > [(M_{i j} + M_{j i})^{-}]^{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 ℚ^{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 ℝ^{n \times n}$ symétrique. Alors

$M \in 𝐂 𝐏$ si, et seulement si, tous les vecteurs propres $v > 0$ des sous-matrices principales de $M$ ont leur valeur propre $⩾ 0$ ,
$M \in 𝐂 𝐏_{𝐬}$ 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 ℝ^{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$ , $M x + q ⩾ 0$ et $x^{⊤} (M x + q) = 0$ , ce que l'on écrit de manière abrégée comme suit :

$CL (M, q) : 0 ⩽ x ⊥ (M x + q) ⩾ 0.$

Existence de solution

En général, la copositivité de $M$ ne suffit pas pour que $CL (M, q)$ ait une solution, quel que soit $q$ . Par exemple, $0 \in 𝐂 𝐏$ , mais $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 $CL (M, q)$ ait une solution.

Existence de solution avec matrice copositive — Si $M \in 𝐂 𝐏$ et $q \in {x \in ℝ_{+}^{n} : x^{⊤} M x = 0, M x ⩾ 0}^{+}$ (cône dual positif), alors $CL (M, q)$ a une solution.

En corollaire, on a

𝐂 𝐏_{𝐬} \subset 𝐂 𝐏 \cap 𝐑_{𝟎} \subset 𝐂 𝐏_{*} \cap 𝐐,

où

$𝐑_{𝟎}$ désigne l'ensemble des R₀-matrices, c'est-à-dire des matrices $M$ telles que $Sol (M, 0) = {0}$ ou encore telles que $0 ⩽ x ⊥ M x ⩾ 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 $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

$φ : ℝ^{n} \to ℝ : x \mapsto x^{⊤} (M x + q),$

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

Caractérisations de la copositivité — Soit $M \in ℝ^{n \times n}$ . On a

$M \in 𝐂 𝐏$ si, et seulement si, pour tout $q ⩾ 0$ , $φ$ est bornée inférieurement sur $ℝ_{+}^{n}$ ,
$M \in 𝐂 𝐏_{𝐬}$ si, et seulement si, pour tout $q \in ℝ^{n}$ , $φ$ est bornée inférieurement sur $ℝ_{+}^{n}$ .

Annexes

Articles connexes

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