Algorithme de Josephy-Newton

L'algorithme de Josephy-Newton est une méthode de linéarisation pour résoudre une inclusion fonctionnelle, c'est-à-dire un problème de la forme

(P_{IF})\qquad F(x)+N(x)\ni 0,

où $F:\mathbb {E} \to \mathbb {F}$ est une fonction différentiable entre les deux espaces vectoriels $\mathbb {E}$ et $\mathbb {F}$ et $N:\mathbb {E} \multimap \mathbb {F}$ est une multifonction entre les mêmes espaces. Ce problème signifie que l'on cherche $x\in \mathbb {E}$ tel que l'ensemble $F(x)+N(x)$ contienne l'élément nul de $\mathbb {F}$ ou encore tel que l'ensemble $N(x)$ contienne $-F(x)$ . Ce formalisme est suffisamment général pour englober les problèmes variationnels, les problèmes d'inéquations variationnelles, les problèmes de complémentarité non linéaires et les conditions d'optimalité du premier ordre des problèmes d'optimisation.

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

F(x_{k})+F'(x_{k})(x-x_{k})+N(x)\ni 0.

On retrouve l'algorithme de Newton si $N\equiv \{0\}$ . Le fait de maintenir $N$ inchangé dans cette inclusion linéarisée, qui calcule le nouvel itéré, permet d'avoir les mêmes résultats de convergence superlinéaire ou quadratique qu'avec la méthode de Newton résolvant un système non linéaire, sous des hypothèses de lissité et de régularité similaires. Cependant, contrairement à l'algorithme de Newton, il ne suffit pas de résoudre un système linéaire à chaque itération pour calculer le nouvel itéré $x_{k+1}$ , car le système ci-dessus permettant de calculer celui-ci est une inclusion non linéaire, qui pourra demander beaucoup de temps de calcul.

L'algorithme de Josephy-Newton[modifier | modifier le code]

Cas général[modifier | modifier le code]

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

(JN)

F(x_{k})+M_{k}(x_{k+1}-x_{k})+N(x_{k+1})\ni 0,

où $M_{k}:\mathbb {E} \to \mathbb {F}$ est un opérateur linéaire valant $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 $x_{k+1}$ et doit s'arrêter. Par ailleurs, si la multifonction $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.

Exemples[modifier | modifier le code]

Problème de complémentarité[modifier | modifier le code]

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

(P_{CNL})\qquad K\ni x\perp F(x)\in K^{+}.

Alors le schéma de Josephy-Newton $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

K\ni x_{k+1}\perp F(x_{k})+M_{k}(x_{k+1}-x_{k})\in K^{+},

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

Conditions d'optimalité d'un problème d'optimisation[modifier | modifier le code]

Article détaillé : Optimisation quadratique successive.

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.

Système d'égalités et d'inégalités[modifier | modifier le code]

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

F(x)+N(x)\ni 0,

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

F_{E}(x_{k})+F'_{E}(x_{k})(x-x_{k})=0\quad {\mbox{et}}\quad F_{I}(x_{k})+F'_{I}(x_{k})(x-x_{k})\leqslant 0.

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

Convergence[modifier | modifier le code]

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

Comportement asymptotique[modifier | modifier le code]

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.

Conditions suffisantes de convergence superlinéaire et quadratique — Supposons que $F$ soit $C^{1}$ dans le voisinage d'une solution semistable $x_{*}$ de $(P_{IF})$ et que la suite $\{x_{k}\}$ vérifie la récurrence (JN) de l'algorithme de Josephy-Newton et converge vers $x_{*}$ .

Si $(M_{k}-F'(x_{*}))(x_{k+1}-x_{k})=o(\|x_{k+1}-x_{k}\|)$ , alors la convergence de $\{x_{k}\}$ est superlinéaire.
Si $(M_{k}-F'(x_{*}))(x_{k+1}-x_{k})=O(\|x_{k+1}-x_{k}\|^{2})$ et si $F$ est $C^{1,1}$ dans un voisinage de $x_{*}$ , alors la convergence de $\{x_{k}\}$ est quadratique.

Corollaire — Supposons que $F$ soit $C^{1}$ dans le voisinage d'une solution semistable $x_{*}$ de $(P_{IF})$ et que la suite $\{x_{k}\}$ vérifie la récurrence (JN) et converge vers $x_{*}$ .

Si $M_{k}\to F'(x_{*})$ , alors la convergence de $\{x_{k}\}$ est superlinéaire.
Si $M_{k}-F'(x_{*})=O(\|x_{k}-x_{*}\|)$ et si $F$ est $C^{1,1}$ dans un voisinage de $x_{*}$ , alors la convergence de $\{x_{k}\}$ est quadratique.

Convergence locale[modifier | modifier le code]

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

Convergence locale de l'algorithme de Josephy-Newton — Supposons que $F$ soit $C^{1}$ dans le voisinage d'une solution semistable et hémistable $x_{*}$ de $(P_{IF})$ et que $M_{k}=F'(x_{k})$ dans l'algorithme de Josephy-Newton (JN). Alors, il existe $\varepsilon >0$ , tel que si le premier itéré $x_{1}\in B(x_{*},\varepsilon )$ , alors

l'algorithme de Josephy-Newton peut générer une suite $\{x_{k}\}$ dans $B(x_{*},\varepsilon )$ ,
toute suite $\{x_{k}\}$ générée dans $B(x_{*},\varepsilon )$ par l'algorithme de Josephy-Newton converge superlinéairement vers $x_{*}$ (et quadratiquement si $F$ est $C^{1,1}$ ).

L'algorithme de Josephy-Newton peut donc générer une suite convergeant vers $x_{*}$ si le premier itéré est assez proche d'une solution semistable et hémistable $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 $x_{*}$ à chaque itération.

Annexes[modifier | modifier le code]

Note[modifier | modifier le code]

↑ Voir Josephy (1979a) pour la version newtonienne et Josephy (1979b) pour la version quasi-newtonienne.

Articles connexes[modifier | modifier le code]

Lien externe[modifier | modifier le code]

(en) J.Ch. Gilbert (2015). Advanced Continuous Optimization, planches du cours du M2 Optimization à l'université Paris-Saclay.

Bibliographie[modifier | modifier le code]

(en) J.F. Bonnans (1994). Local analysis of Newton-type methods for variational inequalities and nonlinear programming. Applied Mathematics and Optimization, 29, 161–186.
(en) A.F. Izmailov, M.V. Solodov (2014). Newton-Type Methods for Optimization and Variational Problems, Springer Series in Operations Research and Financial Engineering, Springer.
(en) N.H. Josephy (1979a). Newton’s method for generalized equations. Technical Summary Report 1965, Mathematics Research Center, University of Wisconsin, Madison, WI, USA.
(en) N.H. Josephy (1979b). Quasi-Newton’s method for generalized equations. Summary Report 1966, Mathematics Research Center, University of Wisconsin, Madison, WI, USA.

Portail de l'analyse

[1] Voir Josephy (1979a) pour la version newtonienne et Josephy (1979b) pour la version quasi-newtonienne.

[1]

v · m Méthodes de résolution d'équations
Équations polynomiales	Équation du premier degré Équation du second degré Équation cubique Méthode de Cardan Substitution de Viète Méthode de Lagrange Méthode de Tschirnhaus Méthode de Bézout Équation quartique Méthode de Lagrange Méthode de Ferrari Méthode de Descartes Équation quintique Méthode d'Hermite
Recherche d'un zéro	Méthode de dichotomie Méthode de Householder Méthode de Newton Méthode de Halley Méthode de la sécante Méthode de Muller Méthode de Brent Méthode de Chandrupatla Méthode de la fausse position Méthode de Héron Méthode de Laguerre Méthode quasi-Newton Méthode du cercle de séparation

v · m Analyse numérique
Recherche de zéro	Méthode de Josephy-Newton Méthode de la sécante Méthode de Newton Point fixe
Transformations de matrice	Matrice de Hessenberg Décomposition LU Factorisation de Cholesky
Résolutions de systèmes	Méthode de Gauss-Seidel Méthode de surrelaxation successive (SOR) Méthode de Jacobi Décomposition QR Décomposition LU
Intégration numérique	Méthode du point médian Méthode des trapèzes Méthode de Simpson Méthodes de quadrature de Gauss Formule de Newton-Cotes Méthode de Romberg Méthode de Monte-Carlo
Équations différentielles	Méthode d'Euler (et semi-implicite) Méthodes de Runge-Kutta Intégration de Verlet Leapfrog Méthode multi-pas linéaire (en) (Adams-Bashforth, backward differentiation formula (en))
Interpolation numérique	Spline Interpolation polynomiale Interpolation lagrangienne Interpolation d'Hermite Suite de polynômes orthogonaux