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

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), mais il semble bien que ce soit Aganagić (1984) 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).

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.
 Si  est une -matrice, la convergence locale est superlinéaire et la convergence globale est assurée si  ou , mais ne l'est pas nécessairement pour  (il existe des contre-exemples).
 Si  est suffisamment proche d'une -matrice, l'algorithme converge globalement, avec  croissante.
 Si  est une -matrice, l'algorithme converge globalement, avec  croissante dès la seconde itération (pour l'ordre de  induit par ) et en au plus  itérations.

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 .

Annexes

Notes

Articles connexes 

 Algorithme de Newton semi-lisse
 Complémentarité linéaire
 P-matrice (voir la section Complémentarité linéaire)

Ouvrages généraux 

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

Newton-min
Complémentarité