Matrice complètement positive

En mathématiques et, plus particulièrement en algèbre linéaire, une matrice réelle carrée est dite complètement positive si elle admet une factorisation de la forme , avec positive. Il revient au même de dire qu'une matrice est complètement positive lorsqu'elle est une combinaison convexe de matrices de la forme , formées à partir de vecteurs positifs .

L'ensemble des matrices d'ordre complètement positives est un cône convexe fermé non vide de , l'ensemble des matrices symétriques d'ordre . C'est le cône dual (positif) du cône des matrices d'ordre symétriques copositives, pour le produit scalaire standard de , ce qui justifie la notation .

Notations

Soit l'espace vectoriel des matrices réelles symétriques d'ordre , que l'on suppose muni de son produit scalaire standard

désigne la trace du produit des matrices et . On note

le cône des matrices de qui sont semi-définies positives,

le cône des matrices de qui sont copositives et enfin

le cône des matrices de qui sont positives (élément par élément).

Définition

Matrice complètement positive  Une matrice réelle carrée d'ordre (un entier ) est dite complètement positive si elle admet la factorisation suivante

dans laquelle est une matrice positive (c'est-à-dire que tous les éléments de sont positifs).

On note l'ensemble des matrices complètement positives.

Une matrice complètement positive est donc nécessairement symétrique et la forme quadratique associée s'écrit comme une somme de carrés de fonctions linéaires à coefficients positifs.

Propriétés

Premières propriétés

On voit facilement que s'écrit comme une enveloppe convexe :

Le résultat suivant justifie la notation adoptée pour le cône des matrices complètement positives.

Cônes et   Les ensembles et sont deux cônes convexes fermés de , duaux l'un de l'autre, et l'on a

Dans les inclusions ci-dessus, les cônes et jouent une espèce de rôle de pivot, car ils sont autoduaux et que l'on a et .

Reconnaissance

  • Vérifier l'appartenance aux cônes et (c'est-à-dire, étant donnés et ou , décider si ou si ) est NP-ardu[1],[2], sans que l'on sache si le problème est dans NP.
  • Vérifier l'appartenance faible aux cônes et (c'est-à-dire, étant donnés , , ou et la boule unité fermée de , décider si ou si ) est NP-ardu[2], sans que l'on sache si le problème est dans NP.

Rayon extrême

Le résultat suivant est démontré par Hall et Newman (1963[3]).

Rayon extrême  Un rayon extrême de est de la forme , avec .

Approximation

On peut resserrer l'encadrement de en utilisant les deux cônes suivants :

Le «  » en exposant dans , qui indique la prise du dual, est justifié par la proposition ci-dessous. On peut aussi voir et comme des approximations de et , respectivement.

Cônes et   Les ensembles et sont deux cônes convexes fermés, duaux l'un de l'autre, et l'on a

On peut montrer que si [4]. Mais , si , comme le montre la matrice de Horn[5]

On montre en effet que engendre un rayon extrême de qui n'est pas dans .

Le cône est aussi le premier cône d'une suite croissante de cônes approchant par l'intérieur[6],[7] :

tandis que les cônes duaux approchent par l'extérieur :

Annexes

Notes

  1. (en) K.G. Murty, S.N. Kabadi (1987). Some NP-complete problems in quadratic and nonlinear programming. Mathematical Programming, 39, 117–129.
  2. (en) P.J.C. Dickinson, L. Gijben (2011). On the computational complexity of membership problems for the completely positive cone and its dual. Optimization Online
  3. Théorème 3.2 chez Hall et Newman (1963).
  4. P.H. Diananda (1962). On nonnegative forms in real variables some or all of which are nonnegative. Proceedings Cambridge Philos. Soc., 58, 17–25.
  5. M. Hall, M. Newman (1963). Copositive and completely positive quadratic forms. Proceedings Cambridge Philos. Soc., 59, 329–339.
  6. P.A. Parrilo (2000, May). Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. Thèse de doctorat, California Institute of Technology.
  7. I.M. Bomze, E. de Klerk (2002). Solving standard quadratic optimization problems via linear, semidefinite and copositive programming. Journal of Global Optimization, 24, 163–185.

Articles connexes

Bibliographie

  • (en) A. Berman, N. Shaked-Monderer (2003). Completely Positive Matrices. World Scientific, River Edge, NJ, USA.
  • (en) M. Hall, M. Newman (1963). Copositive and completely positive quadratic forms. Proceedings Cambridge Philos. Soc., 59, 329–339.
  • Portail des mathématiques
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.