Q0-matrice

En mathématiques, une Q₀-matrice est une matrice carrée réelle apportant des propriétés particulières aux problèmes de complémentarité linéaire. Ce sont celles qui assurent l'existence d'une solution dès que le problème est réalisable.

Définitions

Quelques notations

Pour un vecteur ${\displaystyle v\in \mathbb {R} ^{n}}$, la notation ${\displaystyle v\geqslant 0}$ signifie que toutes les composantes ${\displaystyle v_{i}}$ du vecteur sont positives.

On note ${\displaystyle \mathbb {R} _{ }^{n}:=\{x\in \mathbb {R} ^{n}:x\geqslant 0\}}$ l'orthant positif de ${\displaystyle \mathbb {R} ^{n}}$.

Si ${\displaystyle A}$ est une matrice d'ordre ${\displaystyle n}$, on note ${\displaystyle A(\mathbb {R} _{ }^{n}):=\{Ax:x\geqslant 0\}}$ l'image de ${\displaystyle \mathbb {R} _{ }^{n}}$ par ${\displaystyle A}$ ; c'est un cône polyédrique (donc un fermé).

Problème de complémentarité

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

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

Un point ${\displaystyle x}$ vérifiant ${\displaystyle x\geqslant 0}$ et ${\displaystyle Mx q\geqslant 0}$ est dit admissible pour le problème ${\displaystyle {\mbox{CL}}(M,q)}$ et l'ensemble

${\displaystyle {\mbox{Adm}}(M,q):=\{x\in \mathbb {R} ^{n}:x\geqslant 0,~Mx q\geqslant 0\}}$

est appelé l'ensemble admissible de ce problème. On dit que le problème ${\displaystyle {\mbox{CL}}(M,q)}$ est réalisable si ${\displaystyle {\mbox{Adm}}(M,q)\neq \varnothing }$.

Q₀-matrice

Pour ${\displaystyle M\in \mathbb {R} ^{n\times n}}$, on introduit les deux cônes de ${\displaystyle \mathbb {R} ^{n}}$ suivants

${\displaystyle {\begin{array}{rcl}Q_{R}(M)&:=&\{q\in \mathbb {R} ^{n}:\operatorname {CL} (M,q)~{\mbox{est réalisable}}\},\\Q_{S}(M)&:=&\{q\in \mathbb {R} ^{n}:\operatorname {CL} (M,q)~{\mbox{a une solution}}\}.\end{array}}}$

Évidemment ${\displaystyle Q_{S}(M)\subset Q_{R}(M)}$, sans que l'on ait nécessairement égalité (c'est ce qui motive l'introduction de la notion de Q₀-matrice). Le cône ${\displaystyle Q_{R}(M)}$ est convexe polyédrique car il s'écrit comme la somme de deux cônes convexes polyédriques :

Au contraire, ${\displaystyle Q_{S}(M)}$ n'est pas nécessairement convexe. En réalité, on montre que ${\displaystyle Q_{S}(M)}$ est une réunion de cônes convexes polyédriques^,, (disjoints quel que soit ${\displaystyle q}$ si et seulement si ${\displaystyle M}$ est suffisante en colonne) :

où ${\displaystyle K_{I}}$ est la matrice dont les colonnes sont données par

${\displaystyle (K_{I})^{I}=-M^{I}\qquad {\mbox{et}}\qquad (K_{I})^{I^{c}}=I^{I^{c}}.}$

On voit que les deux cônes dont ${\displaystyle Q_{R}(M)}$ est la somme sont contenus dans ${\displaystyle Q_{S}(M)}$ ; on les obtient en prenant ${\displaystyle I=\varnothing }$ et ${\displaystyle I=\{1,\ldots ,n\}}$. Ces observations conduisent à la définition suivante.

Annexes

Notes

Articles connexes

• Complémentarité linéaire
• P-matrice

Bibliographie

• (en) R. W. Cottle, J.-S. Pang et R. E. Stone, The linear complementarity problem, vol. 60, Philadelphia, PA, USA, SIAM, coll. « Classics in Applied Mathematics », 2009.

• Portail des mathématiques