Top Qs
Chronologie
Chat
Contexte

Matrice copositive

De Wikipédia, l'encyclopédie libre

Remove ads

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]).

Remove ads

Propriétés immédiates

Résumé
Contexte

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 .
Remove ads

Critères de copositivité

Résumé
Contexte

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]).

Remove ads

Copositivité et complémentarité linéaire

Résumé
Contexte

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 .
Remove ads

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 .
Remove ads

Annexes

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads