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

Notations

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

$(A,B)\in {\mathcal {S}}^{n}\times {\mathcal {S}}^{n}\mapsto \langle A,B\rangle :=\operatorname {tr} AB=\sum _{i\in [\![1,n]\!] \atop j\in [\![1,n]\!]}\,A_{ij}B_{ij},$

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, 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, 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).

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]\!]$. Mais ${\mathcal {C}}_{0}^{n}\neq {\mathcal {C}}^{n}$, si $n\geqslant 5$, comme le montre la matrice de Horn

$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 :

${\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+}.$

Annexes

Articles connexes

• Matrice copositive
• Optimisation complètement positive

Bibliographie

• (en) A. Berman, N. Shaked-Monderer (2003). Completely Positive Matrices. World Scientific, River Edge, NJ, USA.
• (en) M. Hall, M. Newman (1963). Copositive and completely positive quadratic forms. Proceedings Cambridge Philos. Soc., 59, 329–339.