Accueil🇫🇷Chercher

Algorithme de Newton-min

L'algorithme de Newton-min est un algorithme de résolution de problèmes de complémentarité linéaire . On peut le voir comme l'algorithme de Newton semi-lisse appliqué à l'équation linéaire par morceaux équivalente . Il est bien défini si la matrice est non dégénérée.

L'algorithme

Le problème de complémentarité linéaire

Rappelons brièvement le problème de complémentarité linéaire, qui est décrit ailleurs. Étant donnés une matrice réelle carrée , non nécessairement symétrique, et un vecteur , un problème de complémentarité linéaire consiste à trouver un vecteur tel que

Les inégalités vectorielles doivent être comprises composante par composante : signifie pour tout indice . Le symbole ci-dessus est utilisé pour désigner la transposition du vecteur à sa gauche. On écrit souvent ce problème de manière concise comme suit :

Comme et doivent être positifs, l'orthogonalité requise de ces deux vecteurs revient à demander que leur produit de Hadamard soit nul :

Un point vérifiant cette égalité est dit complémentaire pour le problème (on dit aussi qu'il s'agit d'un nœud, voir ci-dessous). Par ailleurs, un point vérifiant et est dit admissible pour le problème . Le problème consiste donc à trouver un nœud admissible.

NÅ“ud

Un point complémentaire s'appelle aussi un nœud. Lorsque est non dégénérée, on peut définir un nœud en se donnant un ensemble d'indices et en calculant la solution unique de

où désigne le complémentaire de dans . Ce nœud est noté

Comme il y a ensembles d'indices , il y a au plus nœuds distincts, deux ensembles d'indices pouvant en effet conduire au même nœud (par exemple, il y a un unique nœud si, et seulement si, ).

L'algorithme de Newton-min

L'algorithme consiste à résoudre , au moyen d'itérations de Newton non lisse[1] appliquées à l'équation équivalente suivante, formulée au moyen de la C-fonction min :

L'algorithme de Newton-min requiert que soit non dégénérée.

Algorithme de Newton-min — On se donne un point/itéré initial et un seuil de tolérance . L'algorithme de Newton-min définit une suite d'itérés , qui sont des nœuds, jusqu'à ce qu'un test d'arrêt soit satisfait. Il passe de au nœud par les étapes suivantes.

  1. Test d'arrêt : si , arrêt.
  2. Sélection d'indices : on choisit tel que



  3. Nouvel itéré : .

En pratique, il faut prendre ; la valeur nulle de cette tolérance est admise uniquement pour simplifier l'expression des résultats de convergence ci-dessous. Il s'agit donc d'une méthode de Newton semi-lisse dans laquelle le système linéaire à résoudre à chaque itération est posé en utilisant une pseudo-jacobienne de en . On exclut souvent de les indices pour lesquels , dans le but de minimiser l'ordre du système linéaire à résoudre à l'étape 3 de chaque itération.

Les premières traces de cet algorithme se trouvent chez Chandrasekaran (1970[2]), mais il semble bien que ce soit Aganagić (1984[3]) qui l'ait clairement présenté et étudié, d'ailleurs sous une forme un peu plus générale que celle présentée ici. Il fut ensuite redécouvert et généralisé aux problèmes de commande optimale quadratiques par Bergounioux, Ito et Kunisch (1999[4]).

Propriétés de l'algorithme

Convergence

Voici quelques résultats de convergence connus pour cet algorithme en fonction de la classe de matrices à laquelle appartient (on suppose ci-dessous que ).

  • Si est non dégénérée et si a une solution, l'algorithme converge localement, en un nombre fini d'étapes[5].
  • Si est une -matrice, la convergence locale est superlinéaire[6] et la convergence globale est assurée si ou , mais ne l'est pas nécessairement pour (il existe des contre-exemples)[7].
  • Si est suffisamment proche d'une -matrice, l'algorithme converge globalement, avec croissante[6].
  • Si est une -matrice, l'algorithme converge globalement, avec croissante dès la seconde itération (pour l'ordre de induit par )[3] et en au plus itérations[8].

Complexité

Le seul résultat connu semble bien être celui de Kanzow (2004), déjà mentionné ci-dessus.

  • Si est une -matrice, l'algorithme de Newton-min converge en au plus itérations, quels que soient le vecteur et le point initial.

Autre propriété

L'algorithme a aussi été utilisé pour caractériser les -matrices : une matrice est une -matrice si, et seulement si, quel que soit , l'algorithme de Newton-min ne fait pas de cycle de 2 points, lorsqu'il est utilisé pour résoudre [9].

Annexes

Notes

  1. (en) L. Qi, J. Sun (1993). A nonsmooth version of Newton’s method. Mathematical Programming, 58, 353–367.
  2. (en) R. Chandrasekaran (1970). A special case of the complementary pivot problem. Opsearch, 7, 263–268.
  3. (en) M. Aganagić (1980). Newton’s method for linear complementarity problems. Mathematical Programming, 28, 349–362 (1984).
  4. (en) M. Bergounioux, K. Ito, K. Kunisch (1999). Primal-dual strategy for constrained optimal control problems. SIAM Journal on Control and Optimization, 37, 1176–1194.
  5. (en) A. Fischer, C. Kanzow (1996). On finite termination of an iterative method for linear complementarity problems. Mathematical Programming, 74, 279–292.
  6. (en) M. Hintermuüller, K. Ito, K. Kunisch (2003). The primal-dual active set strategy as a semismooth Newton method. SIAM Journal on Optimization, 13, 865–888.
  7. (en) I. Ben Gharbia, J.Ch. Gilbert (2012). Nonconvergence of the plain Newton-min algorithm for linear complementarity problems with a P-matrix. Mathematical Programming, 134, 349-364. doi lien Zentralblatt MATH
  8. (en) Ch. Kanzow (2004). Inexact semismooth Newton methods for large-scale complementarity problems. Optimization Methods and Software, 19, 309–325.
  9. (en) I. Ben Gharbia, J.Ch. Gilbert (2012). An algorithmic characterization of -matricity. SIAM Journal on Matrix Analysis and Applications, 34, 904-916. Rapport de recherche INRIA RR-8004 doi


Articles connexes

Ouvrages généraux

  • (en) R. W. Cottle, J.-S. Pang, R. E. Stone (2009). The linear complementarity problem. Classics in Applied Mathematics 60. SIAM, Philadelphia, PA, USA.


Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.