en fr

An algorithmic characterization of P-matricity II: adjustments, refinements, and validation

Une caractérisation algorithmique de la P-matricité II: ajustements, raffinements et validation

Résumé : L'article "An algorithmic characterization of P-matricity" (SIAM Journal on Matrix Analysis and Applications, 34:3 (2013) 904–916, par les mêmes auteurs qu'ici) suppose implicitement que les itérés générés par l'algorithme de Newton-min pour résoudre le problème de complémentarité linéaire de dimension n, qui s'écrit 0 ⩽ x ⊥ (M x + q) ⩾ 0, sont déterminés de manière unique par des sous-ensembles d'indices de [[1, n]]. Même si cette hypothèse est vérifiée pour un sous-ensemble de vecteurs q qui est dense dans R^n, elle n'est pas appropriée, en particulier dans les énoncés où le vecteur q n'est pas soumis à des restrictions. Le but du la contribution présente est de montrer que, malgré cette bévue, le résultat principal de l'article est préservé. Celui-ci affirme qu'une matrice non dégénérée M est une P-matrice si, et seulement si, l'algorithme de Newton-min ne cycle pas entre deux points distincts, quel que soit q. La démonstration n'est pas plus complexe et ne requiert que quelques ajustements, qui sont cependant essentiels.