Algorithme de Newton-min

L'algorithme de Newton-min est un algorithme de résolution de problèmes de complémentarité linéaire $0\leqslant x\perp (Mx+q)\geqslant 0$. On peut le voir comme l'algorithme de Newton semi-lisse appliqué à l'équation linéaire par morceaux équivalente $\min(x,Mx+q)=0$. Il est bien défini si la matrice $M$ 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 $M\in \mathbb {R} ^{n\times n}$, non nécessairement symétrique, et un vecteur $q\in \mathbb {R} ^{n}$, un problème de complémentarité linéaire consiste à trouver un vecteur $x\in \mathbb {R} ^{n}$ tel que

$x\geqslant 0,\qquad Mx+q\geqslant 0\qquad {\mbox{et}}\qquad x^{\!\top }(Mx+q)=0.$

Les inégalités vectorielles doivent être comprises composante par composante : $x\geqslant 0$ signifie $x_{i}\geqslant 0$ pour tout indice $i$. Le symbole ${}^{\top }$ 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 :

${\mbox{CL}}(M,q):\qquad 0\leqslant x\perp (Mx+q)\geqslant 0.$

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

$x\cdot (Mx+q)=0.$

Un point $x$ vérifiant cette égalité est dit complémentaire pour le problème ${\mbox{CL}}(M,q)$ (on dit aussi qu'il s'agit d'un nœud, voir ci-dessous). Par ailleurs, un point $x$ vérifiant $x\geqslant 0$ et $Mx+q\geqslant 0$ est dit admissible pour le problème ${\mbox{CL}}(M,q)$. Le problème ${\mbox{CL}}(M,q)$ consiste donc à trouver un nœud admissible.

Nœud

Un point complémentaire s'appelle aussi un nœud. Lorsque $M$ est non dégénérée, on peut définir un nœud en se donnant un ensemble d'indices $I\subset [1\,{:}\,n]:=\{1,\ldots ,n\}$ et en calculant la solution unique $x$ de

$x_{I^{c}}=0\qquad {\mbox{et}}\qquad (Mx+q)_{I}=0,$

où $I^{c}$ désigne le complémentaire de $I$ dans $[1\,{:}\,n]$. Ce nœud est noté

$x^{(I)}.$

Comme il y a $2^{n}$ ensembles d'indices $I\subset [1\,{:}\,n]$, il y a au plus $2^{n}$ 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, $q=0$).

L'algorithme de Newton-min

L'algorithme consiste à résoudre ${\mbox{CL}}(M,q)$, au moyen d'itérations de Newton non lisse appliquées à l'équation équivalente suivante, formulée au moyen de la C-fonction min :

$F_{\min }(x)\equiv \min(x,Mx+q)=0.$

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

Algorithme de Newton-min — On se donne un point/itéré initial $x^{0}\in \mathbb {R} ^{n}$ et un seuil de tolérance $\varepsilon \geqslant 0$. L'algorithme de Newton-min définit une suite d'itérés $x^{1},x^{2},\ldots \in \mathbb {R} ^{n}$, qui sont des nœuds, jusqu'à ce qu'un test d'arrêt soit satisfait. Il passe de $x^{k}$ au nœud $x^{k+1}$ par les étapes suivantes.

1. Test d'arrêt : si $\|\min(x^{k},Mx^{k}+q)\|\leqslant \varepsilon$, arrêt.
2. Sélection d'indices : on choisit $I_{k}$ tel que
   $\{i\in [1\,{:}\,n]:x_{i}^{k}>(Mx^{k}+q)_{i}\}\subseteq I_{k}\subseteq \{i\in [1\,{:}\,n]:x_{i}^{k}\geqslant (Mx^{k}+q)_{i}\}.$
   
   
3. Nouvel itéré : $x^{k+1}=x^{(I_{k})}$.

En pratique, il faut prendre $\varepsilon >0$ ; 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 $F_{\min }$ en $x$. On exclut souvent de $I_{k}$ les indices $i$ pour lesquels $x_{i}^{k}=(Mx^{k}+q)_{i}$, dans le but de minimiser l'ordre $|I_{k}|$ 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 $M$ appartient (on suppose ci-dessous que $\varepsilon =0$).

• Si $M$ est non dégénérée et si ${\mbox{CL}}(M,q)$ a une solution, l'algorithme converge localement, en un nombre fini d'étapes.
• Si $M$ est une $\mathbf {P}$-matrice, la convergence locale est superlinéaire et la convergence globale est assurée si $n=1$ ou $n=2$, mais ne l'est pas nécessairement pour $n\geqslant 3$ (il existe des contre-exemples).
• Si $M$ est suffisamment proche d'une $\mathbf {M}$-matrice, l'algorithme converge globalement, avec $\{\textstyle \sum _{i}x_{i}^{k}\}$ croissante.
• Si $M$ est une $\mathbf {M}$-matrice, l'algorithme converge globalement, avec $\{x^{k}\}$ croissante dès la seconde itération (pour l'ordre de $\mathbb {R} ^{n}$ induit par $\leqslant$) et en au plus $n$ itérations.

Complexité

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

• Si $M$ est une $\mathbf {M}$-matrice, l'algorithme de Newton-min converge en au plus $n$ itérations, quels que soient le vecteur $q$ et le point initial.

Autre propriété

L'algorithme a aussi été utilisé pour caractériser les $\mathbf {P}$-matrices : une matrice $M$ est une $\mathbf {P}$-matrice si, et seulement si, quel que soit $q$, l'algorithme de Newton-min ne fait pas de cycle de 2 points, lorsqu'il est utilisé pour résoudre ${\mbox{CL}}(M,q)$.

Annexes

Articles connexes

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

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.