Algorithme de Newton-min

L'algorithme de Newton-min est un algorithme de résolution de problèmes de complémentarité linéaire ${\displaystyle 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 ${\displaystyle \min(x,Mx+q)=0}$. Il est bien défini si la matrice ${\displaystyle 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 ${\displaystyle M\in \mathbb {R} ^{n\times n}}$, non nécessairement symétrique, et un vecteur ${\displaystyle q\in \mathbb {R} ^{n}}$, un problème de complémentarité linéaire consiste à trouver un vecteur ${\displaystyle x\in \mathbb {R} ^{n}}$ tel que

${\displaystyle 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 : ${\displaystyle x\geqslant 0}$ signifie ${\displaystyle x_{i}\geqslant 0}$ pour tout indice ${\displaystyle i}$. Le symbole ${\displaystyle {}^{\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 :

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

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

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

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

Nœud

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

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

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

${\displaystyle x^{(I)}.}$

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

L'algorithme de Newton-min

L'algorithme consiste à résoudre ${\displaystyle {\mbox{CL}}(M,q)}$, 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 :

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

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

Algorithme de Newton-min — On se donne un point/itéré initial ${\displaystyle x^{0}\in \mathbb {R} ^{n}}$ et un seuil de tolérance ${\displaystyle \varepsilon \geqslant 0}$. L'algorithme de Newton-min définit une suite d'itérés ${\displaystyle 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 ${\displaystyle x^{k}}$ au nœud ${\displaystyle x^{k+1}}$ par les étapes suivantes.

1. Test d'arrêt : si ${\displaystyle \|\min(x^{k},Mx^{k}+q)\|\leqslant \varepsilon }$, arrêt.
2. Sélection d'indices : on choisit ${\displaystyle I_{k}}$ tel que
   
   ${\displaystyle \{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é : ${\displaystyle x^{k+1}=x^{(I_{k})}}$.

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

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

Complexité

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

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

Autre propriété

L'algorithme a aussi été utilisé pour caractériser les ${\displaystyle \mathbf {P} }$-matrices : une matrice ${\displaystyle M}$ est une ${\displaystyle \mathbf {P} }$-matrice si, et seulement si, quel que soit ${\displaystyle q}$, l'algorithme de Newton-min ne fait pas de cycle de 2 points, lorsqu'il est utilisé pour résoudre ${\displaystyle {\mbox{CL}}(M,q)}$^[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 ${\displaystyle \mathbf {P} }$-matricity. SIAM Journal on Matrix Analysis and Applications, 34, 904-916. Rapport de recherche INRIA RR-8004 doi

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.