Q0-matrice

matrice mathématique carrée réelle

En mathématiques, une Q0-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.

Définitions

modifier

Quelques notations

modifier

Pour un vecteur  , la notation   signifie que toutes les composantes   du vecteur sont positives.

On note   l'orthant positif de  .

Si   est une matrice d'ordre  , on note   l'image de   par   ; c'est un cône polyédrique (donc un fermé).

Problème de complémentarité

modifier

Étant donnés une matrice réelle carrée   et un vecteur  , un problème de complémentarité linéaire consiste à trouver un vecteur   tel que  ,   et  , ce que l'on écrit de manière abrégée comme suit :

 

Un point   vérifiant   et   est dit admissible pour le problème   et l'ensemble

 

est appelé l'ensemble admissible de ce problème. On dit que le problème   est réalisable si  .

Q0-matrice

modifier

Pour  , on introduit les deux cônes de   suivants

 

Évidemment  , sans que l'on ait nécessairement égalité (c'est ce qui motive l'introduction de la notion de Q0-matrice). Le cône   est convexe polyédrique car il s'écrit comme la somme de deux cônes convexes polyédriques :

 .

Au contraire,   n'est pas nécessairement convexe. En réalité, on montre que   est une réunion de cônes convexes polyédriques[1],[2],[3] (disjoints quel que soit   si et seulement si   est suffisante en colonne[4]) :

 ,

  est la matrice dont les colonnes sont données par

 

On voit que les deux cônes dont   est la somme sont contenus dans   ; on les obtient en prenant   et  . Ces observations conduisent à la définition suivante.

Q0-matrice — On dit qu'une matrice   est une Q0-matrice si elle vérifie l'une des conditions équivalentes suivantes :

  1. le problème   a une solution s'il est réalisable,
  2.  ,
  3.   est convexe.

On note   l'ensemble des Q0-matrices.

Annexes

modifier
  1. Selon Cottle, Pang et Venkateswaran (1989), les cônes   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).
  2. (en) H. Samelson, R. M. Thrall et O. Wesler, « A partition theorem for the Euclidean n-space », Proceedings of the American Mathematical Society, vol. 9,‎ , p. 805–807.
  3. (en) K.G. Murty, « On the number of solutions to the complementarity problem and spanning properties of complementarity cones », Linear Algebra and its Applications, vol. 5,‎ , p. 65–108.
  4. (en) R.W. Cottle, J.-S. Pang et V. Venkateswaran, « Sufficient matrices and the linear complementarity problem », Linear Algebra and its Applications, vol. 114,‎ , p. 231–249 (DOI 10.1016/0024-3795(89)90463-1)

Articles connexes

modifier

Bibliographie

modifier
  • (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 », .