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

et

$\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 $\mathbf {R_{0}}$ -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 $\mathbf {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 (2000). A test for copositive matrices. Linear Algebra and its Applications, 313, 203–206.
(en) L.-E. Andersson, G. Chang, T. Elfving (1995). Criteria for copositive matrices using simplices and barycentric coordinates. Linear Algebra and its Applications, 220, 9–30.
(en) S. Bundfuss, M. Dür (2008). Algorithmic copositivity detection by simplicial partition. Linear Algebra and its Applications, 428, 1511–1523.

Articles connexes

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

Bibliographie

(en) A. Berman, N. Shaked-Monderer (2003). Completely Positive Matrices. World Scientific, River Edge, NJ, USA.
(en) S. Bundfuss (2009). Copositive Matrices, Copositive Programming, and Applications. Dissertation, Technischen Universität Darmstadt.
(en) R. W. Cottle, J.-S. Pang, R. E. Stone (2009). The linear complementarity problem. Classics in Applied Mathematics 60. SIAM, Philadelphia, PA, USA.
(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
(en) M. Hall, M. Newman (1963). Copositive and completely positive quadratic forms. Proceedings Cambridge Philos. Soc., 59, 329–339.
(en) K. G. Murty, S. N. Kabadi (1987). Some NP-complete problems in quadratic and nonlinear programming. Mathematical Programming, 39, 117–129.

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.

[1] 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.

[2] 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).

[3] (en) W. Kaplan (2000). A test for copositive matrices. Linear Algebra and its Applications, 313, 203–206.

[4] (en) L.-E. Andersson, G. Chang, T. Elfving (1995). Criteria for copositive matrices using simplices and barycentric coordinates. Linear Algebra and its Applications, 220, 9–30.

[5] (en) S. Bundfuss, M. Dür (2008). Algorithmic copositivity detection by simplicial partition. Linear Algebra and its Applications, 428, 1511–1523.