Voir la source de Matrice copositive

En [[mathématiques]] et plus particulièrement en [[algèbre linéaire]], en [[Optimisation (mathématiques)|optimisation]] et en [[complémentarité linéaire]], une [[Matrice (mathématiques)|matrice]] réelle [[Matrice carrée|carrée]] <math>M</math> est dite :
* '''copositive''' si pour tout <math>x\geqslant0</math>, <math>x^\top Mx\geqslant0</math> ;
* '''strictement copositive''' si pour tout <math>x\geqslant0</math> non nul, <math>x^\top Mx>0</math> ;
* '''copositive-plus''' si <math>M</math> est copositive et si <math>x^\top Mx=0</math> et <math>x\geqslant0</math> impliquent <math>(M+M^\top)x=0</math> ;
* '''copositive-étoile''' si <math>M</math> est copositive et si <math>x^\top Mx=0</math>, <math>Mx\geqslant0</math> et <math>x\geqslant0</math> impliquent <math>M^\top x\leqslant0</math>.

L'ensemble des matrices copositives est noté <math>\mathbf{CP}</math>, celui des matrices strictement copositives est noté <math>\mathbf{CP_s}</math>, celui des matrices copositives-plus est noté <math>\mathbf{CP_+}</math> et celui des matrices copositives-étoile est noté <math>\mathbf{CP_*}</math>.

La notion de matrice copositive ''symétrique'' a été introduite et étudiée par Motzkin (1952<ref>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 ''{{Langue|en|National Bureau of Standards}}'', le rapport 1818, pages 11-12.</ref>).

== Propriétés immédiates ==

Les ensembles <math>\mathbf{CP_s}</math>, <math>\mathbf{CP_+}</math>, <math>\mathbf{CP_*}</math>, <math>\mathbf{CP}</math> sont des [[Cône (analyse convexe)|cônes]] non vides. Les cônes <math>\mathbf{CP_s}</math> et <math>\mathbf{CP}</math> sont [[Ensemble convexe|convexes]] (intersections de demi-espaces).

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

{{Bloc emphase|espacement=1.5ex|<math>\mathbf{CP_s} \subset \mathbf{CP_+} \subset \mathbf{CP_*} \subset \mathbf{CP}.</math>}}

Aucun de ces ensembles n'est vide, car la [[matrice identité]] est strictement copositive (donc <math>\mathbf{CP_s}\ne\varnothing</math>). Par ailleurs, aucune de ces inclusions n'est une égalité car
<center>
<math>
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_*}.
</math>
</center>

Seul le cône <math>\mathbf{CP}</math> est [[Ensemble fermé|fermé]] (intersection de demi-espaces fermés). Par ailleurs, si l'on note « <math>\operatorname{adh}A</math> » l'[[Adhérence (mathématiques)|adhérence]] d'un ensemble <math>A</math>, on a (on approche <math>M\in\mathbf{CP}</math> par <math>M+tI\in\mathbf{CP_s}</math> avec <math>t\downarrow0</math>)
{{Bloc emphase|espacement=1.5ex|<math>\operatorname{adh}\mathbf{CP_s} = \operatorname{adh}\mathbf{CP_+} = \operatorname{adh}\mathbf{CP_*} = \mathbf{CP}.</math>}}

On montre aussi facilement les inclusions suivantes :

<center style="margin: 2em 0; overflow: hidden;">
{|  
|  style="border:1px solid #ff8822; padding: 0.5ex;" | 
&nbsp;&nbsp;<math>\mathbf{DP}\subset\mathbf{CP_s},</math>&nbsp;&nbsp;
| &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
|  style="border:1px solid #ff8822; padding: 0.5ex;" | 
&nbsp;&nbsp;<math>\mathbf{SDP}\subset\mathbf{CP_+}</math>&nbsp;&nbsp;
| &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;et &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
|  style="border:1px solid #ff8822; padding: 0.5ex;" | 
&nbsp;&nbsp;<math>\mathbf{POS}\subset\mathbf{CP},</math>&nbsp;&nbsp;
|}
</center>

où <math>\mathbf{DP}</math> désigne l'ensemble des [[Matrice définie positive|matrices définies positives]], <math>\mathbf{SDP}</math> désigne l'ensemble des [[Matrice semi-définie positive|matrices semi-définies positives]] (à [[forme quadratique]] associée positive) et <math>\mathbf{POS}</math> désigne l'ensemble des [[Matrice à coefficients positifs|matrices positives]].

{{Théorème|Propriétés des éléments|Si <math>M\in\mathbf{CP}</math>, alors
* <math>M_{ii}\geqslant0</math>, pour tout <math>i\in[\![1,n]\!]</math>,
* <math>4M_{ii}M_{jj}\geqslant[(M_{ij}+M_{ji})^-]^2</math>, pour tout <math>i\ne j</math> dans <math>[\![1,n]\!]</math> ; en particulier, <math>M_{ii}=0</math> implique que <math>M_{ij}+M_{ji}\geqslant0</math> pour tout <math>j\in[\![1,n]\!]</math>.
Si <math>M\in\mathbf{CP_s}</math>, alors
* <math>M_{ii}>0</math>, pour tout <math>i\in[\![1,n]\!]</math>,
* <math>4M_{ii}M_{jj}>[(M_{ij}+M_{ji})^-]^2</math>, pour tout <math>i\ne j</math> dans <math>[\![1,n]\!]</math>.}}

== Critères de copositivité ==

Le [[problème de décision]] consistant à déterminer si une matrice <math>M\in\mathbb{Q}^{n\times n}</math> est copositive est [[co-NP-complet]]<ref>Ce résultat a été obtenu par Murty et Kabadi (1987). Ils montrent que le [[problème de la somme de sous-ensembles]] (''{{lang|en|subset sum}}'') peut se réduire à un test de copositivité. Voir aussi Dickinson et Gijben (2011).</ref>.

=== 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<ref>{{article |lang=en |auteur1=W. Kaplan |année=2000 |titre=A test for copositive matrices |périodique=[[Linear Algebra and its Applications]] |volume=313 |pages=203–206}}.</ref>). La notation <math>v>0</math> signifie que toutes les composantes de <math>v</math> sont/doivent être strictement positives.

{{Théorème|Critères spectraux|Soit <math>M\in\R^{n\times n}</math> ''symétrique''. Alors
* <math>M\in\mathbf{CP}</math> si, et seulement si, tous les vecteurs propres <math>v>0</math> des sous-matrices principales de <math>M</math> ont leur valeur propre <math>\geqslant0</math>,
* <math>M\in\mathbf{CP_s}</math> si, et seulement si, tous les vecteurs propres <math>v>0</math> des sous-matrices principales de <math>M</math> ont leur valeur propre <math>>0</math>.}}

=== Critères simplexiques ===

Pour les matrices ''symétriques'', voir Andersson, Chang et Elfving (1995<ref>{{article |lang=en |auteur1=L.-E. Andersson |auteur2=G. Chang |auteur3=T. Elfving |année=1995 |titre=Criteria for copositive matrices using simplices and barycentric coordinates |périodique=[[Linear Algebra and its Applications]]|volume=313 220 |pages=9–30}}.</ref>), Bundfuss et Dür (2008<ref>{{article |lang=en |auteur1=S. Bundfuss |auteur2=M. Dür |année=2008 |titre=Algorithmic copositivity detection by simplicial partition |périodique=Linear Algebra and its Applications |volume=428 |pages=1511–1523}}.</ref>).

== Copositivité et complémentarité linéaire ==

=== Problème de complémentarité linéaire ===

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

=== Existence de solution ===

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

{{Théorème|Existence de solution avec matrice copositive|Si <math>M\in\mathbf{CP}</math> et <math>q\in\{x\in\R^n_+:x^\top Mx=0,~Mx\geqslant0\}^+</math> ([[cône dual]] positif), alors <math>\operatorname{CL}(M,q)</math> a une solution.}}

En corollaire, on a

{{Bloc emphase|espacement=1.5ex|<math>\mathbf{CP_s}\subset\mathbf{CP}\cap\mathbf{R_0}\subset \mathbf{CP_*}\cap\mathbf{Q},</math>}}

où
* <math>\mathbf{R_0}</math> désigne l'ensemble des [[R0-matrice|R{{ind|0}}-matrices]], c'est-à-dire des matrices <math>M</math> telles que <math>\operatorname{Sol}(M,0)=\{0\}</math> ou encore telles que <math>0\leqslant x \perp Mx \geqslant 0</math> implique que <math>x=0</math>,
* <math>\mathbf{Q}</math> désigne l'ensemble des [[Q-matrice|Q-matrices]], c'est-à-dire des matrices <math>M\in\R^{n\times n}</math> pour lesquelles le problème de complémentarité linéaire <math>\operatorname{CL}(M,q)</math> a une solution quel que soit <math>q\in\R^n</math>.

== Propriétés variationnelles ==

Les caractérisations suivantes de la copositivité (stricte) d'une matrice <math>M\in\R^{n\times n}</math> se font au moyen de la fonction quadratique
<center>
<math>
\varphi:\R^n\to\R:x\mapsto x^\top(Mx+q),
</math>
</center>
où <math>q\in\R^n</math>. On y a noté <math>\R^n_+:=\{x\in\R^n:x\geqslant0\}</math> l'ensemble des vecteurs dont les composantes sont positives.

{{Théorème|Caractérisations de la copositivité|Soit <math>M\in\R^{n\times n}</math>. On a
* <math>M\in\mathbf{CP}</math> si, et seulement si, pour tout <math>q\geqslant0</math>, <math>\varphi</math> est bornée inférieurement sur <math>\R^n_+</math>,
* <math>M\in\mathbf{CP_s}</math> si, et seulement si, pour tout <math>q\in\R^n</math>, <math>\varphi</math> est bornée inférieurement sur <math>\R^n_+</math>.}}

== Annexes ==

=== Notes ===

{{références|colonnes=2}}

=== Articles connexes ===

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

=== Bibliographie ===

* {{ouvrage |lang=en |auteur1=A. Berman |auteur2=N. Shaked-Monderer |année=2003 |titre=Completely Positive Matrices |éditeur=World Scientific |lieu=River Edge, NJ, USA}}.
* {{ouvrage |lang=en |auteur1=S. Bundfuss |année=2009 |titre=Copositive Matrices, Copositive Programming, and Applications |éditeur=Dissertation, Technischen  |lieu=Universität Darmstadt}}.
* {{ouvrage |lang=en |auteur1=R. W. Cottle |auteur2=J.-S. Pang |auteur3=R. E. Stone |année=2009 |titre=The linear complementarity problem''. Classics in Applied Mathematics |volume=60 |éditeur=SIAM |lieu=Philadelphia, PA, USA}}.
* {{ouvrage |lang=en |auteur1=P.J.C. Dickinson |auteur2=L. Gijben |année=2011 |titre=On the computational complexity of membership problems for the completely positive cone and its dual |lire en ligne=http://www.optimization-online.org/DB_FILE/2011/05/3041.pdf}}
* {{article |lang=en |auteur1=M. Hall |auteur2=M. Newman |année=1963 |titre=Copositive and completely positive quadratic forms |périodique=Proceedings Cambridge Philos. Soc. |volume=59 |pages=329–339}}.
* {{article |lang=en |auteur1=K. G. Murty |auteur2=S. N. Kabadi |année=1987 |titre=Some NP-complete problems in quadratic and nonlinear programming |périodique=Mathematical Programming |volume=39 |pages=117–129}}.

{{Palette Matrices}}
{{Portail|mathématiques}}

[[Catégorie:Matrice remarquable|copositive]]