Accueil🇫🇷Chercher

Matrice copositive

En mathématiques et plus particulièrement en algèbre linéaire, en optimisation et en complémentarité linéaire, une matrice réelle carrée est dite :

  • copositive si pour tout , ;
  • strictement copositive si pour tout non nul, ;
  • copositive-plus si est copositive et si et impliquent ;
  • copositive-étoile si est copositive et si , et impliquent .

L'ensemble des matrices copositives est noté , celui des matrices strictement copositives est noté , celui des matrices copositives-plus est noté et celui des matrices copositives-étoile est noté .

La notion de matrice copositive symétrique a été introduite et étudiée par Motzkin (1952[1]).

Propriétés immédiates

Les ensembles , , , sont des cônes non vides. Les cônes et sont convexes (intersections de demi-espaces).

Les ensembles , , , sont reliés entre eux par la chaîne d'inclusions suivante :

Aucun de ces ensembles n'est vide, car la matrice identité est strictement copositive (donc ). Par ailleurs, aucune de ces inclusions n'est une égalité car

Seul le cône est fermé (intersection de demi-espaces fermés). Par ailleurs, si l'on note « » l'adhérence d'un ensemble , on a (on approche par avec )

On montre aussi facilement les inclusions suivantes :

et

désigne l'ensemble des matrices définies positives, désigne l'ensemble des matrices semi-définies positivesforme quadratique associée positive) et désigne l'ensemble des matrices positives.

Propriétés des éléments Si , alors

  • , pour tout ,
  • , pour tout dans ; en particulier, implique que pour tout .

Si , alors

  • , pour tout ,
  • , pour tout dans .

Critères de copositivité

Le problème de décision consistant à déterminer si une matrice est copositive est co-NP-complet[2].

Critères fondés sur les sous-matrices principales

Pour les matrices symétriques, on dispose de critères utilisant la décomposition spectrale des sous-matrices principales. Le résultat suivant est dû à Kaplan (2000[3]). La notation signifie que toutes les composantes de sont/doivent être strictement positives.

Critères spectraux Soit symétrique. Alors

  • si, et seulement si, tous les vecteurs propres des sous-matrices principales de ont leur valeur propre ,
  • si, et seulement si, tous les vecteurs propres des sous-matrices principales de ont leur valeur propre .

Critères simplexiques

Pour les matrices symétriques, voir Andersson, Chang et Elfving (1995[4]), Bundfuss et Dür (2008[5]).

Copositivité et complémentarité linéaire

Problème de complémentarité linéaire

É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 :

Existence de solution

En général, la copositivité de ne suffit pas pour que ait une solution, quel que soit . Par exemple, , mais a une solution si, et seulement si, . Le résultat suivant donne des conditions sur avec pour que ait une solution.

Existence de solution avec matrice copositive Si et (cône dual positif), alors a une solution.

En corollaire, on a

  • désigne l'ensemble des R0-matrices, c'est-à-dire des matrices telles que ou encore telles que implique que ,
  • désigne l'ensemble des Q-matrices, c'est-à-dire des matrices pour lesquelles le problème de complémentarité linéaire a une solution quel que soit .

Propriétés variationnelles

Les caractérisations suivantes de la copositivité (stricte) d'une matrice se font au moyen de la fonction quadratique

. On y a noté l'ensemble des vecteurs dont les composantes sont positives.

Caractérisations de la copositivité Soit . On a

  • si, et seulement si, pour tout , est bornée inférieurement sur ,
  • si, et seulement si, pour tout , est bornée inférieurement sur .

Annexes

Notes

  1. Selon Cottle, Pang et Stone (2009), la notion de matrice copositive symétrique a été introduite et étudiée par Motzkin en 1952 dans un rapport sans titre du National Bureau of Standards, le rapport 1818, pages 11-12.
  2. Ce résultat a été obtenu par Murty et Kabadi (1987). Ils montrent que le problème de la somme de sous-ensembles (subset sum) peut se réduire à un test de copositivité. Voir aussi Dickinson et Gijben (2011).
  3. (en) W. Kaplan, « A test for copositive matrices », Linear Algebra and its Applications, vol. 313, , p. 203–206.
  4. (en) L.-E. Andersson, G. Chang et T. Elfving, « Criteria for copositive matrices using simplices and barycentric coordinates », Linear Algebra and its Applications, vol. 313 220, , p. 9–30.
  5. (en) S. Bundfuss et M. Dür, « Algorithmic copositivity detection by simplicial partition », Linear Algebra and its Applications, vol. 428, , p. 1511–1523.

Articles connexes

Bibliographie

  • (en) A. Berman et N. Shaked-Monderer, Completely Positive Matrices, River Edge, NJ, USA, World Scientific, .
  • (en) S. Bundfuss, Copositive Matrices, Copositive Programming, and Applications, Universität Darmstadt, Dissertation, Technischen, .
  • (en) R. W. Cottle, J.-S. Pang et R. E. Stone, The linear complementarity problem. Classics in Applied Mathematics, vol. 60, Philadelphia, PA, USA, SIAM, .
  • (en) P.J.C. Dickinson et L. Gijben, On the computational complexity of membership problems for the completely positive cone and its dual, (lire en ligne)
  • (en) M. Hall et M. Newman, « Copositive and completely positive quadratic forms », Proceedings Cambridge Philos. Soc., vol. 59, , p. 329–339.
  • (en) K. G. Murty et S. N. Kabadi, « Some NP-complete problems in quadratic and nonlinear programming », Mathematical Programming, vol. 39, , p. 117–129.
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.