Matrice complètement positive

En mathématiques et, plus particulièrement en algèbre linéaire, une matrice réelle carrée $A$ est dite complètement positive si elle admet une factorisation de la forme $A=BB^{\mathsf {T}}$ , avec $B$ positive. Il revient au même de dire qu'une matrice est complètement positive lorsqu'elle est une combinaison convexe de matrices de la forme $xx^{\mathsf {T}}$ , formées à partir de vecteurs positifs $x$ .

L'ensemble ${\mathcal {C}}^{n+}$ des matrices d'ordre $n$ complètement positives est un cône convexe fermé non vide de ${\mathcal {S}}^{n}$ , l'ensemble des matrices symétriques d'ordre $n$ . C'est le cône dual (positif) du cône ${\mathcal {C}}^{n}$ des matrices d'ordre $n$ symétriques copositives, pour le produit scalaire standard de ${\mathcal {S}}^{n}$ , ce qui justifie la notation ${\mathcal {C}}^{n+}$ .

Soit ${\mathcal {S}}^{n}$ l'espace vectoriel des matrices réelles symétriques d'ordre $n$ , que l'on suppose muni de son produit scalaire standard

{\displaystyle (A,B)\in {\mathcal {S}}^{n}\times {\mathcal {S}}^{n}\mapsto \langle A,B\rangle

où $\operatorname {tr} AB$ désigne la trace du produit des matrices $A$ et $B$ . On note

{\mathcal {S}}_{+}^{n}:=\{A\in {\mathcal {S}}^{n}:x^{\mathsf {T}}Ax\geqslant 0~{\mbox{pour tout}}~x\in \mathbb {R} ^{n}\}

le cône des matrices de ${\mathcal {S}}^{n}$ qui sont semi-définies positives,

{\mathcal {C}}^{n}:=\{A\in {\mathcal {S}}^{n}:x^{\mathsf {T}}Ax\geqslant 0~{\mbox{pour tout}}~x\geqslant 0\}

le cône des matrices de ${\mathcal {S}}^{n}$ qui sont copositives et enfin

{\mathcal {P}}^{n}:=\{A\in {\mathcal {S}}^{n}:A_{ij}\geqslant 0~{\mbox{pour tout}}~(i,j)\in [\![1,n]\!]^{2}\}

le cône des matrices de ${\mathcal {S}}^{n}$ qui sont positives (élément par élément).

Définition

Matrice complètement positive — Une matrice réelle carrée d'ordre $n$ (un entier $\geqslant 0$ ) $A$ est dite complètement positive si elle admet la factorisation suivante

A=BB^{\mathsf {T}},

dans laquelle $B$ est une matrice positive (c'est-à-dire que tous les éléments de $B$ sont positifs).

On note ${\mathcal {C}}^{n+}$ l'ensemble des matrices complètement positives.

Une matrice complètement positive $A$ est donc nécessairement symétrique et la forme quadratique $x\mapsto x^{\mathsf {T}}Ax$ associée s'écrit comme une somme de carrés de fonctions linéaires à coefficients positifs.

Propriétés

Premières propriétés

On voit facilement que ${\mathcal {C}}^{n+}$ s'écrit comme une enveloppe convexe :

{\mathcal {C}}^{n+}:=\operatorname {co} \,\{xx^{\mathsf {T}}:x\in \mathbb {R} _{+}^{n}\}.

Le résultat suivant justifie la notation ${\mathcal {C}}^{n+}$ adoptée pour le cône des matrices complètement positives.

Cônes ${\mathcal {C}}^{n}$ et ${\mathcal {C}}^{n+}$ — Les ensembles ${\mathcal {C}}^{n}$ et ${\mathcal {C}}^{n+}$ sont deux cônes convexes fermés de ${\mathcal {S}}^{n}$ , duaux l'un de l'autre, et l'on a

{\mathcal {C}}^{n+}\subset \left\{{\begin{array}{c}{\mathcal {S}}_{+}^{n}\\{\mathcal {P}}^{n}\end{array}}\right\}\subset {\mathcal {C}}^{n}.

Dans les inclusions ci-dessus, les cônes ${\mathcal {S}}_{+}^{n}$ et ${\mathcal {P}}^{n}$ jouent une espèce de rôle de pivot, car ils sont autoduaux et que l'on a $({\mathcal {C}}^{n+})^{+}={\mathcal {C}}^{n}$ et $({\mathcal {C}}^{n})^{+}={\mathcal {C}}^{n+}$ .

Reconnaissance

Vérifier l'appartenance aux cônes ${\mathcal {C}}^{n}$ et ${\mathcal {C}}^{n+}$ (c'est-à-dire, étant donnés $A\in \mathbb {Q} _{s}^{n\times n}$ et $K={\mathcal {C}}^{n}$ ou $K={\mathcal {C}}^{n+}$ , décider si $A\in K$ ou si $A\notin K$ ) est NP-ardu^[1]^,^[2], sans que l'on sache si le problème est dans NP.
Vérifier l'appartenance faible aux cônes ${\mathcal {C}}^{n}$ et ${\mathcal {C}}^{n+}$ (c'est-à-dire, étant donnés $\varepsilon \in \mathbb {Q} _{++}$ , $A\in \mathbb {Q} _{s}^{n\times n}$ , $K={\mathcal {C}}^{n}$ ou $K={\mathcal {C}}^{n+}$ et $B$ la boule unité fermée de $\mathbb {R} ^{n\times n}$ , décider si $A\in K+\varepsilon B$ ou si $A+\varepsilon B\nsubseteq K$ ) est NP-ardu^[2], sans que l'on sache si le problème est dans NP.

Propriétés géométriques

Rayon extrême

Le résultat suivant est démontré par Hall et Newman (1963^[3]).

Rayon extrême — Un rayon extrême de ${\mathcal {C}}^{n+}$ est de la forme $\mathbb {R} _{+}vv^{\mathsf {T}}$ , avec $v\in \mathbb {R} _{+}^{n}\setminus \{0\}$ .

Approximation

On peut resserrer l'encadrement de ${\mathcal {S}}_{+}^{n}$ en utilisant les deux cônes suivants :

{\mathcal {C}}_{0}^{n}:={\mathcal {S}}_{+}^{n}+{\mathcal {P}}^{n}\qquad {\mbox{et}}\qquad {\mathcal {C}}_{0}^{n+}:={\mathcal {S}}_{+}^{n}\cap {\mathcal {P}}^{n}.

Le « $+$ » en exposant dans ${\mathcal {C}}^{n+}$ , qui indique la prise du dual, est justifié par la proposition ci-dessous. On peut aussi voir ${\mathcal {C}}_{0}^{n}$ et ${\mathcal {C}}_{0}^{n+}$ comme des approximations de ${\mathcal {C}}^{n}$ et ${\mathcal {C}}^{n+}$ , respectivement.

Cônes ${\mathcal {C}}_{0}^{n}$ et ${\mathcal {C}}_{0}^{n+}$ — Les ensembles ${\mathcal {C}}_{0}^{n}$ et ${\mathcal {C}}_{0}^{n+}$ sont deux cônes convexes fermés, duaux l'un de l'autre, et l'on a

{\mathcal {C}}^{n+}\subset {\mathcal {C}}_{0}^{n+}\subset \left\{{\begin{array}{c}{\mathcal {S}}_{+}^{n}\\{\mathcal {P}}^{n}\end{array}}\right\}\subset {\mathcal {C}}_{0}^{n}\subset {\mathcal {C}}^{n}.

On peut montrer que ${\mathcal {C}}_{0}^{n}={\mathcal {C}}^{n}$ si $n\in [\![1,4]\!]$ ^[4]. Mais ${\mathcal {C}}_{0}^{n}\neq {\mathcal {C}}^{n}$ , si $n\geqslant 5$ , comme le montre la matrice de Horn^[5]

H=\left(\!\!{\begin{array}{rrrrr}1&-1&1&1&-1\\-1&1&-1&1&1\\1&-1&1&-1&1\\1&1&-1&1&-1\\-1&1&1&-1&1\end{array}}\!\!\right)\in {\mathcal {C}}^{5}\setminus {\mathcal {C}}_{0}^{5}.

On montre en effet que $H$ engendre un rayon extrême de ${\mathcal {C}}^{5}$ qui n'est pas dans ${\mathcal {C}}_{0}^{5}$ .

Le cône ${\mathcal {C}}_{0}^{n}$ est aussi le premier cône d'une suite croissante de cônes approchant ${\mathcal {C}}^{n}$ par l'intérieur^[6]^,^[7] :

{\mathcal {C}}_{0}^{n}\subset {\mathcal {C}}_{1}^{n}\subset {\mathcal {C}}_{2}^{n}\subset \cdots \subset {\mathcal {C}}^{n}\qquad {\mbox{et}}\qquad \bigcup _{k\in \mathbb {N} }{\mathcal {C}}_{k}^{n}={\mathcal {C}}^{n},

tandis que les cônes duaux approchent ${\mathcal {C}}^{n+}$ par l'extérieur :

{\mathcal {C}}^{n+}\subset \cdots \subset ({\mathcal {C}}_{2}^{n})^{+}\subset ({\mathcal {C}}_{1}^{n})^{+}\subset ({\mathcal {C}}_{0}^{n})^{+}={\mathcal {C}}_{0}^{n+}\qquad {\mbox{et}}\qquad \bigcap _{k\in \mathbb {N} }({\mathcal {C}}_{k}^{n})^{+}={\mathcal {C}}^{n+}.

Matrice complètement positive

Définition

Propriétés

Premières propriétés

Reconnaissance

Propriétés géométriques

Rayon extrême

Approximation

Annexes

Notes

Articles connexes

Bibliographie

Related Articles