Q0-matrice

Q0-matrice: En mathématiques, une $\mathbf{Q_0}$ -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.

Sommaire

1 Définitions

1.1 Quelques notations

1.2 Problème de complémentarité

1.3 Q0-matrice

2 Annexes

2.1 Note

2.2 Articles connexes

2.3 Bibliographie

Définitions

Quelques notations

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

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

Si $A$ est une matrice d'ordre $n$ , on note $A(\R^n_+):=\{Ax:x\geqslant 0\}$ l'image de $\R^n_+$ par $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 $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$ .

Q0-matrice

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

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

Évidemment $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 $\mathbf{Q_0}$ -matrice). Le cône $Q R (M)$ est convexe polyédrique car il s'écrit comme la somme de deux cônes convexes polyédriques :
$Q_R(M)=R^n_+-M(R^n_+)$ .
Au contraire, $Q S (M)$ n'est pas nécessairement convexe. En réalité, on montre que $Q S (M)$ est une réunion de cônes convexes polyédriques^[1]^,^[2]^,^[3] (disjoints quel que soit $q$ si et seulement si $M$ est suffisante en colonne^[4]) :
$Q_S(M)=\displaystyle\bigcup_{I\subset\{1,\ldots,n\}}\,K_I(\R^n_+)$ ,
où $K I$ est la matrice dont les colonnes sont données par

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

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

Q0-matrice — On dit qu'une matrice $M\in\R^{n\times n}$ est une $\mathbf{Q_0}$ -matrice si elle vérifie l'une des conditions équivalentes suivantes :

le problème $\operatorname{CL}(M,q)$ a une solution s'il est réalisable,

$Q S (M) = Q R (M)$ ,

$Q S (M)$ est convexe.

On note $\mathbf{Q_0}$ l'ensemble des $\mathbf{Q_0}$ -matrices.

Annexes

Note

↑ Selon Cottle, Pang et Venkateswaran (1989), les cônes $K_I(\R^n_{++})$ ont été introduits par Samelson, Thrall et Wesler (1958) et ont été étudiés dans le contexte des problèmes de complémentarité linéaire par Murty (1972).

↑ (en) H. Samelson, R. M. Thrall, O. Wesler (1958). A partition theorem for the Euclidean n-space. Proceedings of the American Mathematical Society, 9, 805–807.

↑ (en) K.G. Murty (1972). On the number of solutions to the complementarity problem and spanning properties of complementarity cones. Linear Algebra and its Applications, 5, 65–108.

↑ (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

Articles connexes

Complémentarité linéaire

P-matrice

Bibliographie

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

Portail des mathématiques

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

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

Игры ⚽ Поможем написать курсовую

Regardez d'autres dictionnaires:

Matrice (algèbre) — Matrice (mathématiques) Pour les articles homonymes, voir Matrice. En mathématiques, les matrices servent à interpréter en termes calculatoire … Wikipédia en Français
Matrice (mathematiques) — Matrice (mathématiques) Pour les articles homonymes, voir Matrice. En mathématiques, les matrices servent à interpréter en termes calculatoire … Wikipédia en Français
Matrice carrée — Matrice (mathématiques) Pour les articles homonymes, voir Matrice. En mathématiques, les matrices servent à interpréter en termes calculatoire … Wikipédia en Français
Matrice Diagonalisable — En algèbre linéaire, une matrice carrée M d ordre n ( ) à coefficients dans un corps commutatif K, est dite diagonalisable si elle est semblable à une matrice diagonale, c est à dire s il existe une matrice inversible P et une matrice diagonale D … Wikipédia en Français
matrice — [ matris ] n. f. • 1265; lat. matrix 1 ♦ Vieilli Utérus. Inflammation de la matrice. ⇒ métrite. Fig. « La terre, inépuisable et suprême matrice » (Hugo). 2 ♦ (1556 ) Techn. Moule qui, après avoir reçu une empreinte particulière en creux et en… … Encyclopédie Universelle
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 Inversible — En mathématiques et plus particulièrement en algèbre linéaire, une matrice carrée A d ordre n est dite inversible ou régulière ou encore non singulière, s il existe une matrice B d ordre n telle que AB = BA = In, ( AB = In suffit d aprés le… … 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 inverse — Matrice inversible En mathématiques et plus particulièrement en algèbre linéaire, une matrice carrée A d ordre n est dite inversible ou régulière ou encore non singulière, s il existe une matrice B d ordre n telle que AB = BA = In, ( AB = In… … Wikipédia en Français
Matrice non singulière — Matrice inversible En mathématiques et plus particulièrement en algèbre linéaire, une matrice carrée A d ordre n est dite inversible ou régulière ou encore non singulière, s il existe une matrice B d ordre n telle que AB = BA = In, ( AB = In… … Wikipédia en Français
Matrice par blocs — Matrice par bloc En théorie des matrices, une matrice par bloc ou matrice partitionnée est une matrice pouvant être divisée en matrices rectangulaires de dimensions inférieures appelées blocs. On peut dire également que la matrice est écrite en… … Wikipédia en Français

Mark and share
Search through all dictionaries
Translate…
Search Internet

Share the article and excerpts