Matrice suffisante

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\R^{n\times n}$ est dite

suffisante en colonne si $x\cdot(Mx)\leqslant 0$ implique que $x\cdot(Mx)=0$ ,

suffisante en ligne si $x\cdot(M^{\top}x)\leqslant 0$ implique que $x\cdot(M^{\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^\top$ désigne la matrice transposée de $M$ . Il faut comprendre « $x\cdot(Mx)\leqslant 0$ implique que $x\cdot(Mx)=0$ » comme suit : « tout point $x$ vérifiant $x\cdot(Mx)\leqslant 0$ vérifie aussi $x\cdot(Mx)=0$ ».

Les matrices suffisantes en colonne sont 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 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^[1]). La terminologie anglaise originale est column sufficient, row sufficient et sufficient. Les qualificatifs en colonne et en ligne ne sont guère intuitifs. Il semble que l'appellation suffisante en colonne provienne de l'analogie avec la définition d'une matrice adéquate en colonne, notion introduite par Ingleton (1966^[2]) et qui signifie que

$\forall\,x\in\R^n:\qquad x\cdot(Mx)\leqslant 0 \quad\Longrightarrow\quad Mx=0.$

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

Sommaire

1 Problème de complémentarité

1.1 Définitions

1.2 Problème quadratique associé

2 Matrice suffisante en colonne

2.1 Définition

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

3 Matrice suffisante en ligne

3.1 Définition

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

4 Matrice suffisante

4.1 Définition

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

5 Annexes

5.1 Notes

5.2 Article connexe

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\R^n$ , la notation $v\geqslant 0$ signifie que toutes les composantes $v i$ du vecteur sont positives.

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

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

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

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

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

$Sol(M, q)$

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

Problème quadratique associé

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

$\mbox{(PQ)}\qquad \left\{\begin{array}{l} \min\;x^{\!\top}(Mx+q)\\ x\geqslant 0\\ Mx+q\geqslant 0. \end{array}\right.$

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

$\mbox{(KKT)}\qquad \left\{\begin{array}{cl} (a) & (M+M^{\top})x + q - s - M^{\top} z = 0\\ (b) & 0\leqslant x\perp s \geqslant 0 \\ (c) & 0\leqslant (Mx+q) \perp z \geqslant 0. \end{array}\right.$

On note

$Sta(M, q)$

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

Matrice suffisante en colonne

Définition

Matrice suffisante en colonne — On dit qu'une matrice carrée réelle $M\in\mathbb{R}^{n\times n}$ est suffisante en colonne si pour tout $x\in\R^n$ tel que $x\cdot(M x)\leqslant 0$ , on a $x\cdot(M x)=0$ ; ce que l'on peut résumer ainsi :

$x\cdot(M x)\leqslant 0 \qquad\Longrightarrow\qquad x\cdot(M x)=0.$

On note $\mathbf{SC}$ l'ensemble des matrices suffisantes en colonne.

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

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

$\mathbf{SC}$ -matrice et convexité de $\operatorname{Sol}(M,q)$ — Pour une matrice $M\in\mathbb{R}^{n\times n}$ , les propriétés suivantes sont équivalentes :

$M\in\mathbf{SC}$ ,

$\forall\,q\in\R^n,~\operatorname{Sol}(M,q)$ est convexe.

Matrice suffisante en ligne

Définition

Matrice suffisante en ligne — On dit qu'une matrice carrée réelle $M\in\mathbb{R}^{n\times n}$ est suffisante en ligne si sa transposée est suffisante en colonne ; ce que l'on peut résumer ainsi :

$x\cdot(M^{\top} x)\leqslant 0 \qquad\Longrightarrow\qquad x\cdot(M^{\top} x)=0.$

On note $\mathbf{SL}$ l'ensemble des matrices suffisantes en ligne.

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

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

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

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

$\mathbf{SL}$ -matrice et l'égalité $\operatorname{Sol}(M,q)=\mbox{Sta}(M,q)$ — Pour une matrice $M\in\mathbb{R}^{n\times n}$ , les propriétés suivantes sont équivalentes :

$M\in\mathbf{SL}$ ,

$\forall\,q\in\R^n,~\operatorname{Sol}(M,q)=\mbox{Sta}(M,q)$ .

Si on note $\mathbf{P}$ l'ensemble des P-matrices, $\mathbf{P_0}$ l'ensemble des P0-matrices et $\mathbf{Q_0}$ l'ensemble des Q0-matrices, on a^[1]
$\mathbf{P}\subset\mathbf{SL}\subset\mathbf{P}_0\cap\mathbf{Q}_0.$
Les inclusions $\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 $q$ est tel que $\operatorname{Adm}(M,q)\ne\varnothing$ , alors le problème quadratique (PQ) a une solution^[3], qui est un point stationnaire de ce problème ; maintenant, si $M$ est suffisante en ligne, ce point stationnaire est solution de $\operatorname{CL}(M,q)$ ; donc $\mathbf{SL}\subset\mathbf{Q}_0$ .

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

Matrice suffisante

Définition

Matrice suffisante — On dit qu'une matrice carrée réelle $M\in\mathbb{R}^{n\times n}$ est suffisante si elle est à la fois suffisante en colonne et suffisante en ligne.

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

Matrice suffisante et complémentarité — Pour une matrice $M\in\R^{n\times n}$ , les propriétés suivantes sont équivalentes :

$M$ est suffisante,

$\forall\,q\in\R^n,~\operatorname{Sol}(M,q)=\mbox{Sta}(M,q)$ et cet ensemble est convexe.

Annexes

Notes

↑ ^{a, b, c et d} (en) R.W. Cottle, J.-S. Pang, V. Venkateswaran (1989). Sufficient matrices and the linear complementarity problem. Linear Algebra and its Applications, 114, 231–249. doi

↑ (en) A.W. Ingleton (1966). A problem in linear inequalities. Proc. London Math. Soc., 2, 519–536.

↑ ^{a et b} (en) M. Frank, P. Wolfe (1956). An algorithm for quadratic programming. Naval Research Logistics Quarterly, 3, 95–110.

↑ (en) M.J.M. Janssen (1983). On the structure of the solution set of a linear complementarity problem. Cahiers Centre Études Rech. Opér., 25, 41–48.

↑ (en) C.E. Lemke (1965). Bimatrix equilibrium points and mathematical programming. Management Science, 11, 681–689. doi

↑ (en) R.W. Cottle, G.B. Dantzig (1968). Complementarity pivot theory of mathematical programming. Linear Algebra and its Applications, 1, 103–125. doi

Article connexe

Complémentarité linéaire

Portail des mathématiques

Catégories :
Matrice
Complémentarité linéaire

Contenu soumis à la licence CC-BY-SA. Source : Article Matrice suffisante de Wikipédia en français (auteurs)

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

Matrice Nilpotente — Une matrice nilpotente est une matrice dont il existe une puissance égale à la matrice nulle. Elle correspond à la notion d endomorphisme nilpotent. Cette notion joue un rôle important dans le monde des matrices. En effet, pour un maniement plus… … Wikipédia en Français
Matrice Définie Positive — En algèbre linéaire, la notion de matrice définie positive est analogue à celle de nombre réel strictement positif. On introduit tout d abord les notations suivantes ; si a est une matrice à éléments réels ou complexes : aT désigne la… … Wikipédia en Français
Matrice definie positive — Matrice définie positive En algèbre linéaire, la notion de matrice définie positive est analogue à celle de nombre réel strictement positif. On introduit tout d abord les notations suivantes ; si a est une matrice à éléments réels ou… … Wikipédia en Français
Matrice De Contrôle — Une matrice de contrôle est un concept de théorie des codes utilisé dans le cas des codes correcteurs linéaires. Elle correspond à la matrice d une application linéaire ayant pour noyau le code. La notion de matrice de contrôle possède à la fois… … Wikipédia en Français
Matrice de controle — Matrice de contrôle Une matrice de contrôle est un concept de théorie des codes utilisé dans le cas des codes correcteurs linéaires. Elle correspond à la matrice d une application linéaire ayant pour noyau le code. La notion de matrice de… … Wikipédia en Français
Matrice unimodulaire — En algèbre linéaire, une matrice unimodulaire sur l anneau des entiers relatifs est une matrice carrée à coefficients entiers dont le déterminant vaut +1 ou 1. Plus généralement[1], une matrice unimodulaire sur un anneau commutatif A est une… … Wikipédia en Français
Matrice définie positive — En algèbre linéaire, la notion de matrice définie positive est analogue à celle de nombre réel strictement positif : une matrice définie positive est une matrice positive inversible (la réciproque est fausse). On introduit tout d abord les… … Wikipédia en Français
Matrice nilpotente — Une matrice nilpotente est une matrice dont il existe une puissance égale à la matrice nulle. Elle correspond à la notion d endomorphisme nilpotent sur un espace vectoriel de dimension finie. Cette notion facilite souvent le calcul matriciel. En… … Wikipédia en Français
Matrice hessienne — En mathématiques, la matrice hessienne (ou simplement la hessienne) d une fonction numérique f est la matrice carrée, notée H(f), de ses dérivées partielles secondes. Plus précisément, étant donnée une fonction f à valeurs réelles f(x1, x2, ...,… … Wikipédia en Français
Matrice diagonalisable — Exemple de matrice diagonalisable sur le corps des complexes mais pas sur celui des réels, son polynôme caractéristique étant X2 + 1. En mathématiques, une matrice diagonalisable est une matrice carrée semblable à une matrice diagonale. Cette p … Wikipédia en Français

Mark and share
Search through all dictionaries
Translate…
Search Internet

Share the article and excerpts