Matrice suffisante

En mathématiques, les termes suffisante en colonne, suffisante en ligne et suffisante qualifient des matrices carrées réelles apportant des propriétés particulières aux problèmes de complémentarité linéaire. Brièvement, une matrice $M\in {ℝ}^{n\times n}$ est dite

• suffisante en colonne si $x\cdot (Mx)⩽0$ implique que $x\cdot (Mx)=0$,
• suffisante en ligne si $x\cdot (M^{\mathrm{\top }}x)⩽0$ implique que $x\cdot (M^{\mathrm{\top }}x)=0$,
• suffisante si elle est à la fois suffisante en colonne et suffisante en ligne.

Dans ces définitions, $u\cdot v$ désigne le produit de Hadamard des vecteurs $u$ et $v$, qui est un vecteur dont la composante $i$ est $u_i{v}_i$, et $M^{\mathrm{\top }}$ désigne la matrice transposée de $M$. Il faut comprendre « $x\cdot (Mx)⩽0$ implique que $x\cdot (Mx)=0$ » comme suit : « tout point $x$ vérifiant $x\cdot (Mx)⩽0$ vérifie aussi $x\cdot (Mx)=0$ ».

Les matrices suffisantes en colonne sont aussi celles qui assurent la convexité de l'ensemble des solutions d'un problème de complémentarité linéaire. Les matrices suffisantes en ligne sont aussi celles qui assurent que l'ensemble des solutions d'un tel problème est identique à l'ensemble des points stationnaires de son problème quadratique associé.

Ces notions ont été introduites par Cottle, Pang et Venkateswaran (1989). La terminologie anglaise originale est column sufficient, row sufficient et sufficient. Les qualificatifs en colonne et en ligne ne sont guère intuitifs. En réalité, l'appellation suffisante en colonne a été choisie en partie pour plaisanter et parodier le terme adéquate en colonne, notion introduite par Ingleton (1966) et qui signifie que

$\mathrm{\forall }x\in {ℝ}^n:x\cdot (Mx)⩽0⟹Mx=0.$

Comme cette notion revient à dire que pour tout $I\subset \{1,\dots ,n\}$ non vide, $\det M_{I,I}=0$ si, et seulement si, les colonnes $M_{\bullet I}$ de $M$ sont linéairement dépendantes, le qualificatif en colonne se justifie plus aisément dans ce dernier cas.

Problème de complémentarité

Ce sont les problèmes de complémentarité qui ont motivé l'introduction des notions de matrice suffisante. Nous rappelons donc ici quelques notions liées à ces problèmes.

Définitions

Pour un vecteur $v\in {ℝ}^n$, la notation $v⩾0$ signifie que toutes les composantes $v_i$ du vecteur sont positives.

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

$\text{CL}(M,q):0⩽x\perp (Mx+q)⩾0.$

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

$\text{Adm}(M,q):=\{x\in {ℝ}^n:x⩾0,Mx+q⩾0\}$

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

$\text{Sol}(M,q)$

l'ensemble des solutions du problème de complémentarité linéaire $\text{CL}(M,q)$.

Problème quadratique associé

Considérons le problème d'optimisation quadratique en $x\in {ℝ}^n$ suivant :

$\text{(PQ)}\{\begin{array}{c}\min x^{\mathrm{\top }}(Mx+q)\\ x⩾0\\ Mx+q⩾0.\end{array}$

Comme le coût de ce problème est borné inférieurement sur l'ensemble admissible (il y est positif), ce problème a toujours une solution (Frank et Wolfe, 1956). On en déduit alors que Modèle:Bloc emphase Toutefois, le problème quadratique (PQ) peut, en général, avoir des minima locaux ou des points stationnaires qui ne sont pas solution de $\mathrm{CL}(M,q)$. On rappelle qu'un point $x\in {ℝ}^n$ est stationnaire pour le problème (PQ) s'il existe des multiplicateurs $s\in {ℝ}^n$ et $z\in {ℝ}^n$ tels que les conditions de Karush, Kuhn et Tucker suivantes soient vérifiées :

$\text{(KKT)}\{\begin{array}{cc}(a)& (M+M^{\mathrm{\top }})x+q-s-M^{\mathrm{\top }}z=0\\ (b)& 0⩽x\perp s⩾0\\ (c)& 0⩽(Mx+q)\perp z⩾0.\end{array}$

On note

$\text{Sta}(M,q)$

l'ensemble des points stationnaires du problème quadratique (PQ).

Matrice suffisante en colonne

Rôle dans les problèmes de complémentarité

En toute généralité, l'ensemble $\mathrm{Sol}(M,q)$ des solutions d'un problème de complémentarité linéaire est une réunion de polyèdres convexes. Les matrices suffisantes en colonne sont celles pour lesquelles l'ensemble de ces solutions est un unique polyèdre convexe.

Lien avec d'autres classes de matrices

On note ${𝐏}_{\mathrm{𝟎}}$ l'ensemble des ${𝐏}_{\mathrm{𝟎}}$-matrices. Si $M\notin {𝐏}_{\mathrm{𝟎}}$, il existe un $x\ne 0$ tel que, pour tout indice $i$, $x_i\ne 0$ $\Rightarrow$ $x_i(Mx{)}_i<0$. Cette propriété n'est pas compatible avec la $𝐒𝐂$-matricité. On a donc l'inclusion suivante.

Matrice suffisante en ligne

Rôle dans les problèmes de complémentarité

Si $x\in {ℝ}^n$ est solution du problème de complémentarité linéaire $\mathrm{CL}(M,q)$, il est également solution du problème quadratique (PQ). Comme les contraintes de ce dernier sont qualifiées, les conditions de Karush, Kuhn et Ticker (KKT) sont vérifiées pour des multiplicateurs $s\in {ℝ}^n$ et $z\in {ℝ}^n$. On a donc

$\mathrm{Sol}(M,q)\subset \mathrm{Sta}(M,q).$

Le résultat suivant montre que l'on a égalité dans cette relation, quel que soit $q\in {ℝ}^n$, si, et seulement si, la matrice $M$ est suffisante en ligne.

Liens avec d'autres classes de matrices

Si on note $𝐏$ l'ensemble des P-matrices, ${𝐏}_{\mathrm{𝟎}}$ l'ensemble des P0-matrices ${𝐐}_{\mathrm{𝟎}}$ l'ensemble des Q0-matrices et $𝐒𝐃𝐏$ l'ensemble des matrices semi-définies positives (non nécessairement symétriques), on a

Les inclusions $𝐏\subset 𝐒𝐋\subset {𝐏}_{\mathrm{𝟎}}$ résultent des définitions des SL-matrices, des P-matrices et des P0-matrices. On observe ensuite que, si $q$ est tel que $\mathrm{Adm}(M,q)\ne \varnothing$, alors le problème quadratique (PQ) a une solution, qui est un point stationnaire de ce problème ; maintenant, si $M$ est suffisante en ligne, ce point stationnaire est solution de $\mathrm{CL}(M,q)$ ; donc $𝐒𝐋\subset {𝐐}_0$. Enfin, l'inclusion $𝐒𝐃𝐏\subset 𝐒𝐋$ est due à Dorn (1961).

Les matrices suffisantes en ligne sont donc exactement celles qui permettent de démontrer l'existence d'une solution de $\mathrm{CL}(M,q)$ en passant par les conditions d'optimalité (KKT) du problème quadratique (PQ). Le fait que $𝐒𝐋$ ne soit pas tout ${𝐐}_{\mathrm{𝟎}}$ laisse penser qu'il doit exister d'autres approches analytiques permettant de montrer l'existence de solution de $\mathrm{CL}(M,q)$ ; les matrices copositives-plus introduites par Lemke (1965) sont un exemple familier de classe de matrices qui ne sont pas suffisantes en ligneModèle:,.

Matrice suffisante

Liens avec d'autres classes de matrices

Si on note $𝐒𝐃𝐏$ l'ensemble des matrices semi-définies positives (non nécessairement symétriques), $𝐏$ l'ensemble des P-matrices et ${𝐏}_{\mathbf{*}}$ l'ensemble des $P_{*}$-matrices, on a les inclusion et égalité suivantes.

Annexes

Article connexe

• Complémentarité linéaire

Références

• Modèle:Article.
• Modèle:Article.
• Modèle:Ouvrage.
• Modèle:Article.

Modèle:Portail