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

{\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.

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

Annexes

Notes

(en) K.G. Murty, S.N. Kabadi (1987). Some NP-complete problems in quadratic and nonlinear programming. Mathematical Programming, 39, 117–129.
(en) P.J.C. Dickinson, L. Gijben (2011). On the computational complexity of membership problems for the completely positive cone and its dual. Optimization Online
Théorème 3.2 chez Hall et Newman (1963).
P.H. Diananda (1962). On nonnegative forms in real variables some or all of which are nonnegative. Proceedings Cambridge Philos. Soc., 58, 17–25.
M. Hall, M. Newman (1963). Copositive and completely positive quadratic forms. Proceedings Cambridge Philos. Soc., 59, 329–339.
P.A. Parrilo (2000, May). Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. Thèse de doctorat, California Institute of Technology.
I.M. Bomze, E. de Klerk (2002). Solving standard quadratic optimization problems via linear, semidefinite and copositive programming. Journal of Global Optimization, 24, 163–185.

Articles connexes

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.

Portail des mathématiques

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[kabadi-murty-1987-1] (en) K.G. Murty, S.N. Kabadi (1987). Some NP-complete problems in quadratic and nonlinear programming. Mathematical Programming, 39, 117–129.

[dickinson-gijben-2011-2] (en) P.J.C. Dickinson, L. Gijben (2011). On the computational complexity of membership problems for the completely positive cone and its dual. Optimization Online

[3] Théorème 3.2 chez Hall et Newman (1963).

[4] P.H. Diananda (1962). On nonnegative forms in real variables some or all of which are nonnegative. Proceedings Cambridge Philos. Soc., 58, 17–25.

[5] M. Hall, M. Newman (1963). Copositive and completely positive quadratic forms. Proceedings Cambridge Philos. Soc., 59, 329–339.

[6] P.A. Parrilo (2000, May). Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. Thèse de doctorat, California Institute of Technology.

[7] I.M. Bomze, E. de Klerk (2002). Solving standard quadratic optimization problems via linear, semidefinite and copositive programming. Journal of Global Optimization, 24, 163–185.