Q₀-matrice

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é).

É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 :

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

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

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

É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 :

${\displaystyle Q_{R}(M)=R_{+}^{n}-M(R_{+}^{n})}$.

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[1] - [2] - [3] (disjoints quel que soit ${\displaystyle q}$ si et seulement si ${\displaystyle M}$ est suffisante en colonne[4]) :

${\displaystyle Q_{S}(M)=\displaystyle \bigcup _{I\subset \{1,\ldots ,n\}}\,K_{I}(\mathbb {R} _{+}^{n})}$,

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

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.

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

• (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.