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

L'ensemble des matrices copositives est noté $\mathbf {CP}$ , celui des matrices strictement copositives est noté $\mathbf {CP_{s}}$ , celui des matrices copositives-plus est noté $\mathbf {CP_{+}}$ et celui des matrices copositives-étoile est noté $\mathbf {CP_{*}}$ .

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

Propriétés immédiates

Les ensembles $\mathbf {CP_{s}}$ , $\mathbf {CP_{+}}$ , $\mathbf {CP_{*}}$ , $\mathbf {CP}$ sont des cônes non vides. Les cônes $\mathbf {CP_{s}}$ et $\mathbf {CP}$ sont convexes (intersections de demi-espaces).

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

\mathbf {CP_{s}} \subset \mathbf {CP_{+}} \subset \mathbf {CP_{*}} \subset \mathbf {CP} .

Aucun de ces ensembles n'est vide, car la matrice identité est strictement copositive (donc $\mathbf {CP_{s}} \neq \varnothing$ ). Par ailleurs, aucune de ces inclusions n'est une égalité car

$0\in \mathbf {CP_{+}} \setminus \mathbf {CP_{s}} ,\qquad {\begin{pmatrix}0&-1\\2&1\end{pmatrix}}\in \mathbf {CP_{*}} \setminus \mathbf {CP_{+}} \qquad {\mbox{et}}\qquad {\begin{pmatrix}0&1\\1&1\end{pmatrix}}\in \mathbf {CP} \setminus \mathbf {CP_{*}} .$

Seul le cône $\mathbf {CP}$ est fermé (intersection de demi-espaces fermés). Par ailleurs, si l'on note « $\operatorname {adh} A$ » l'adhérence d'un ensemble $A$ , on a (on approche $M\in \mathbf {CP}$ par $M+tI\in \mathbf {CP_{s}}$ avec $t\downarrow 0$ )

\operatorname {adh} \mathbf {CP_{s}} =\operatorname {adh} \mathbf {CP_{+}} =\operatorname {adh} \mathbf {CP_{*}} =\mathbf {CP} .

On montre aussi facilement les inclusions suivantes :

$\mathbf {DP} \subset \mathbf {CP_{s}} ,$

$\mathbf {SDP} \subset \mathbf {CP_{+}}$

$\mathbf {POS} \subset \mathbf {CP} ,$

où $\mathbf {DP}$ désigne l'ensemble des matrices définies positives, $\mathbf {SDP}$ désigne l'ensemble des matrices semi-définies positives (à forme quadratique associée positive) et $\mathbf {POS}$ désigne l'ensemble des matrices positives.

Propriétés des éléments — Si $M\in \mathbf {CP}$ , alors

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

Si $M\in \mathbf {CP_{s}}$ , alors

$M_{ii}>0$ , pour tout $i\in [\![1,n]\!]$ ,
$4M_{ii}M_{jj}>[(M_{ij}+M_{ji})^{-}]^{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 \mathbb {Q} ^{n\times n}$ est copositive est co-NP-complet[2].

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[3]). La notation $v>0$ signifie que toutes les composantes de $v$ sont/doivent être strictement positives.

Critères spectraux — Soit $M\in \mathbb {R} ^{n\times n}$ symétrique. Alors

$M\in \mathbf {CP}$ si, et seulement si, tous les vecteurs propres $v>0$ des sous-matrices principales de $M$ ont leur valeur propre $\geqslant 0$ ,
$M\in \mathbf {CP_{s}}$ 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[4]), Bundfuss et Dür (2008[5]).

Copositivité et complémentarité linéaire

Problème de complémentarité linéaire

Étant donnés une matrice réelle carrée $M\in \mathbb {R} ^{n\times n}$ et un vecteur $q\in \mathbb {R} ^{n}$ , un problème de complémentarité linéaire consiste à trouver un vecteur $x\in \mathbb {R} ^{n}$ tel que $x\geqslant 0$ , $Mx+q\geqslant 0$ et $x^{\!\top }(Mx+q)=0$ , ce que l'on écrit de manière abrégée comme suit :

${\mbox{CL}}(M,q):\qquad 0\leqslant x\perp (Mx+q)\geqslant 0.$

Existence de solution

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

Existence de solution avec matrice copositive — Si $M\in \mathbf {CP}$ et $q\in \{x\in \mathbb {R} _{+}^{n}:x^{\top }Mx=0,~Mx\geqslant 0\}^{+}$ (cône dual positif), alors $\operatorname {CL} (M,q)$ a une solution.

En corollaire, on a

\mathbf {CP_{s}} \subset \mathbf {CP} \cap \mathbf {R_{0}} \subset \mathbf {CP_{*}} \cap \mathbf {Q} ,

où

$\mathbf {R_{0}}$ désigne l'ensemble des R₀-matrices, c'est-à-dire des matrices $M$ telles que $\operatorname {Sol} (M,0)=\{0\}$ ou encore telles que $0\leqslant x\perp Mx\geqslant 0$ implique que $x=0$ ,
$\mathbf {Q}$ désigne l'ensemble des Q-matrices, c'est-à-dire des matrices $M\in \mathbb {R} ^{n\times n}$ pour lesquelles le problème de complémentarité linéaire $\operatorname {CL} (M,q)$ a une solution quel que soit $q\in \mathbb {R} ^{n}$ .

Propriétés variationnelles

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

${\displaystyle \varphi$

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

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

$M\in \mathbf {CP}$ si, et seulement si, pour tout $q\geqslant 0$ , $\varphi$ est bornée inférieurement sur $\mathbb {R} _{+}^{n}$ ,
$M\in \mathbf {CP_{s}}$ si, et seulement si, pour tout $q\in \mathbb {R} ^{n}$ , $\varphi$ est bornée inférieurement sur $\mathbb {R} _{+}^{n}$ .

Annexes

Notes

Selon Cottle, Pang et Stone (2009), la notion de matrice copositive symétrique a été introduite et étudiée par Motzkin en 1952 dans un rapport sans titre du National Bureau of Standards, le rapport 1818, pages 11-12.
Ce résultat a été obtenu par Murty et Kabadi (1987). Ils montrent que le problème de la somme de sous-ensembles (subset sum) peut se réduire à un test de copositivité. Voir aussi Dickinson et Gijben (2011).
(en) W. Kaplan, « A test for copositive matrices », Linear Algebra and its Applications, vol. 313,‎ 2000, p. 203–206.
(en) L.-E. Andersson, G. Chang et T. Elfving, « Criteria for copositive matrices using simplices and barycentric coordinates », Linear Algebra and its Applications, vol. 313 220,‎ 1995, p. 9–30.
(en) S. Bundfuss et M. Dür, « Algorithmic copositivity detection by simplicial partition », Linear Algebra and its Applications, vol. 428,‎ 2008, p. 1511–1523.

Bibliographie

(en) A. Berman et N. Shaked-Monderer, Completely Positive Matrices, River Edge, NJ, USA, World Scientific, 2003.
(en) S. Bundfuss, Copositive Matrices, Copositive Programming, and Applications, Universität Darmstadt, Dissertation, Technischen, 2009.
(en) R. W. Cottle, J.-S. Pang et R. E. Stone, The linear complementarity problem. Classics in Applied Mathematics, vol. 60, Philadelphia, PA, USA, SIAM, 2009.
(en) P.J.C. Dickinson et L. Gijben, On the computational complexity of membership problems for the completely positive cone and its dual, 2011 (lire en ligne)
(en) M. Hall et M. Newman, « Copositive and completely positive quadratic forms », Proceedings Cambridge Philos. Soc., vol. 59,‎ 1963, p. 329–339.
(en) K. G. Murty et S. N. Kabadi, « Some NP-complete problems in quadratic and nonlinear programming », Mathematical Programming, vol. 39,‎ 1987, p. 117–129.

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.