Matrice suffisante

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.

É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 }$. On note

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

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

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[4]). On en déduit alors que

${\displaystyle x\in \operatorname {Sol} (M,q)\quad \Longleftrightarrow \quad x}$ est solution de (PQ) avec un coût optimal nul.

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 ${\displaystyle \operatorname {CL} (M,q)}$. On rappelle qu'un point ${\displaystyle x\in \mathbb {R} ^{n}}$ est stationnaire pour le problème (PQ) s'il existe des multiplicateurs ${\displaystyle s\in \mathbb {R} ^{n}}$ et ${\displaystyle z\in \mathbb {R} ^{n}}$ tels que les conditions de Karush, Kuhn et Tucker suivantes soient vérifiées :

On note

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

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

On note ${\displaystyle \mathbf {P_{0}} }$ l'ensemble des ${\displaystyle \mathbf {P_{0}} }$-matrices. Si ${\displaystyle M\notin \mathbf {P_{0}} }$, il existe un ${\displaystyle x\neq 0}$ tel que, pour tout indice ${\displaystyle i}$, ${\displaystyle x_{i}\neq 0}$ ${\displaystyle \Rightarrow }$ ${\displaystyle x_{i}(Mx)_{i}<0}$. Cette propriété n'est pas compatible avec la ${\displaystyle \mathbf {SC} }$-matricité. On a donc l'inclusion suivante.

${\displaystyle \mathbf {SC} \subset \mathbf {P_{0}} }$.

Si ${\displaystyle x\in \mathbb {R} ^{n}}$ est solution du problème de complémentarité linéaire ${\displaystyle \operatorname {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 ${\displaystyle s\in \mathbb {R} ^{n}}$ et ${\displaystyle z\in \mathbb {R} ^{n}}$. On a donc

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

Si on note ${\displaystyle \mathbf {P} }$ l'ensemble des P-matrices, ${\displaystyle \mathbf {P_{0}} }$ l'ensemble des P0-matrices ${\displaystyle \mathbf {Q_{0}} }$ l'ensemble des Q0-matrices et ${\displaystyle \mathbf {SDP} }$ l'ensemble des matrices semi-définies positives (non nécessairement symétriques), on a[1]

${\displaystyle (\mathbf {SDP} \cup \mathbf {P} )\subset \mathbf {SL} \subset (\mathbf {P} _{0}\cap \mathbf {Q} _{0})}$.

Les inclusions ${\displaystyle \mathbf {P} \subset \mathbf {SL} \subset \mathbf {P_{0}} }$ résultent des définitions des SL-matrices, des P-matrices et des P0-matrices. On observe ensuite que, si ${\displaystyle q}$ est tel que ${\displaystyle \operatorname {Adm} (M,q)\neq \varnothing }$, alors le problème quadratique (PQ) a une solution[4], qui est un point stationnaire de ce problème ; maintenant, si ${\displaystyle M}$ est suffisante en ligne, ce point stationnaire est solution de ${\displaystyle \operatorname {CL} (M,q)}$ ; donc ${\displaystyle \mathbf {SL} \subset \mathbf {Q} _{0}}$. Enfin, l'inclusion ${\displaystyle \mathbf {SDP} \subset \mathbf {SL} }$ est due à Dorn (1961[6]).

Les matrices suffisantes en ligne sont donc exactement celles qui permettent de démontrer l'existence d'une solution de ${\displaystyle \operatorname {CL} (M,q)}$ en passant par les conditions d'optimalité (KKT) du problème quadratique (PQ)[1]. Le fait que ${\displaystyle \mathbf {SL} }$ ne soit pas tout ${\displaystyle \mathbf {Q_{0}} }$ laisse penser qu'il doit exister d'autres approches analytiques permettant de montrer l'existence de solution de ${\displaystyle \operatorname {CL} (M,q)}$ ; les matrices copositives-plus introduites par Lemke (1965[7]) sont un exemple familier de classe de matrices qui ne sont pas suffisantes en ligne[8] - [1].

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

${\displaystyle (\mathbf {SDP} \cup \mathbf {P} )\subset \mathbf {SU} =\mathbf {P_{*}} }$.

• Complémentarité linéaire

• (en) W. S. Dorn, « Self-dual quadratic programs », Journal of the Society for Industrial and Applied Mathematics, vol. 9,‎ 1961, p. 51–54 (DOI 10.1137/0109006).
• (en) S.-M. Guu et R. W. Cottle, « On a subclass of ${\displaystyle \mathbf {P_{0}} }$ », Linear Algebra and its Applications, vol. 223/224,‎ 1995, p. 325–335.
• (en) M. Kojima, N. Megiddo, T. Noma et A. Yoshise, A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems, Berlin, Springer-Verlag, coll. « Lecture Notes in Computer Science » (n^o 538), 1991.
• (en) H. Väliaho, « ${\displaystyle \mathbf {P_{*}} }$-matrices are just sufficient », Linear Algebra and its Applications, vol. 239,‎ 1996, p. 103–108.