Algorithme de Josephy-Newton

Comme spécifié dans l'introduction, l'algorithme de Josephy-Newton de résolution de ${\displaystyle (P_{IF})}$ consiste à générer une suite ${\displaystyle \{x_{k}\}\subset \mathbb {E} }$, où le nouvel itéré ${\displaystyle x_{k+1}}$ est calculé à partir de l'itéré courant ${\displaystyle x_{k}}$ en résolvant (si possible) l'inclusion partiellement linéarisée

où ${\displaystyle M_{k}:\mathbb {E} \to \mathbb {F} }$ est un opérateur linéaire valant ${\displaystyle F'(x_{k})}$ ou une approximation de cette dérivée (on pense ici surtout à des approximations quasi-newtoniennes). On ne « linéarise » donc que le premier terme qui est supposé différentiable ; le second est laissé inchangé. Sans hypothèse particulière, il se peut que l'inclusion fonctionnelle linéarisée (JN) n'ait pas de solution, auquel cas l'algorithme ne peut pas calculer l'itéré suivant ${\displaystyle x_{k+1}}$ et doit s'arrêter. Par ailleurs, si la multifonction ${\displaystyle N}$ est complexe, l'itération pourra requérir beaucoup de temps de calcul (elle est toutefois plus simple que le problème initial), mais la convergence locale rapide peut laisser espérer qu'une solution sera trouvée en très peu d'itérations. Il se peut aussi que l'on ne connaisse pas de méthode pour résoudre (JN), auquel cas il faudra se tourner vers d'autres algorithmes de résolution.

Ce schéma algorithmique prenant en compte un grand nombre de situations a été introduit par Josephy en 1979^[1].

Examinons à présent quelques cas particuliers.

Si ${\displaystyle F:\mathbb {E} \to \mathbb {E} }$ et si la multifonction ${\displaystyle N}$ est le cône normal ${\displaystyle \operatorname {N} _{K}}$ à un cône convexe fermé non vide ${\displaystyle K\subset \mathbb {E} }$, le problème d'inclusion fonctionnelle ${\displaystyle F(x)+\operatorname {N} _{K}(x)\ni 0}$ s'écrit comme le problème de complémentarité non linéaire

Alors le schéma de Josephy-Newton ${\displaystyle F(x_{k})+M_{k}(x_{k+1}-x_{k})+\operatorname {N} _{K}(x_{k+1})\ni 0}$ s'écrit comme le problème de complémentarité linéaire

dans lequel on s'est contenté de linéariser ${\displaystyle F}$ en ${\displaystyle x_{k}}$.

Lorsque l'algorithme de Josephy-Newton est appliqué aux conditions d'optimalité d'un problème d'optimisation avec contraintes d'égalité et d'inégalité, on retrouve l'optimisation quadratique successive.

Un système d'égalités ${\displaystyle F_{E}(x)=0}$ et d'inégalités ${\displaystyle F_{I}(x)\leqslant 0}$, avec les ensembles d'indices ${\displaystyle E}$ et ${\displaystyle I}$ formant une partition de ${\displaystyle [1:m]}$, peut s'écrire comme une inclusion fonctionnelle

en prenant comme multifonction ${\displaystyle N:\mathbb {E} \multimap \mathbb {R} ^{m}}$, la multifonction constante ${\displaystyle N(\cdot )\equiv \mathbb {R} ^{m_{E}}\times \mathbb {R} _{+}^{m_{I}}}$, où ${\displaystyle m_{E}:=|E|}$ et ${\displaystyle m_{I}:=|I|}$. L'algorithme de Josephy-Newton consiste dans ce cas à résoudre à l'itération ${\displaystyle k}$ le système d'équations linéarisées en ${\displaystyle x}$ suivant

Celui-ci peut ne pas avoir de solution, même lorsque ${\displaystyle x_{k}}$ est proche d'un point ${\displaystyle x}$ vérifiant les égalités ${\displaystyle F_{E}(x)=0}$ et les inégalités ${\displaystyle F_{I}(x)\leqslant 0}$, auquel cas l'algorithme doit s'interrompre.

Les résultats de cette section sont repris de (Bonnans 1994).

La notion de semistabilité permet d'avoir des conditions suffisantes de convergence superlinéaire et quadratique d'une suite générée par l'algorithme de Josephy-Newton.

La semi-stabilité n'assure en rien l'existence d'une solution de l'équation linéarisée et donc d'un nouvel itéré de l'algorithme de Josephy-Newton, même si cet itéré est proche d'une solution. C'est la raison d'être de la propriété d'hémistabilité. En réalité, comme le montre le résultat suivant, c'est à la fois la semistabilité et l'hémistabilité d'une solution de ${\displaystyle (P_{IF})}$ qui assurent le caractère bien posé de l'algorithme de Josephy-Newton démarrant proche de cette solution et la convergence de la suite générée vers celle-ci.

L'algorithme de Josephy-Newton peut donc générer une suite convergeant vers ${\displaystyle x_{*}}$ si le premier itéré est assez proche d'une solution semistable et hémistable ${\displaystyle x_{*}}$, mais rien ne dit qu'il en sera ainsi si la solution de l'inclusion linéarisée n'est pas choisie assez proche de ${\displaystyle x_{*}}$ à chaque itération.

• Optimisation quadratique successive
• Inclusion fonctionnelle

• Jean Charles Gilbert, « Advanced Continuous Optimization : M2 course at the "Institut Polytechnique de Paris" », sur Inria, 2015

• J. Frédéric Bonnans, « Local analysis of Newton-type methods for variational inequalities and nonlinear programming », Applied Mathematics and Optimization, vol. 29,‎ 1994, p. 161-186 (DOI 10.1007/BF01204181)
• Alexey F. Izmailov et Mikhail V. Solodov, Newton-Type Methods for Optimization and Variational Problems, Springer Cham, coll. « Springer Series in Operations Research and Financial Engineering », 2014, xix + 573 p. (ISBN 978-3-319-04246-6 et 978-3-319-35384-5, ISSN 1431-8598, DOI 10.1007/978-3-319-04247-3)
• Norman H. Josephy, Newton’s method for generalized equations, Mathematics Research Center, Université du Wisconsin à Madison, coll. « Technical Summary Report » (n^o 1965), 1979a
• Norman H. Josephy, Quasi-Newton’s method for generalized equations, Mathematics Research Center, université du Wisconsin à Madison, coll. « Technical Summary Report » (n^o 1966), 1979b

• Portail de l'analyse