Algorithmes de Newton

Algorithmes de Newton

On donne aujourd’hui le nom de méthode de Newton à toute approche algorithmique procédant par linéarisation des fonctions définissant le système dont on cherche une solution. C’est faire un grand honneur, peut-être excessif, à Isaac Newton, cet important contributeur de la science. Le terme système est pris ici dans un sens très large puisqu’il peut s’agir d’équations, d’inéquations, d’inclusions, d’équations différentielles ou aux dérivées partielles, d’inéquations variationnelles, etc. De même, le terme linéarisation doit être pris dans un sens étendu, car on utilise aussi la méthode de Newton pour résoudre des systèmes définis par des fonctions non différentiables dans le sens classique. On peut donc mesurer le chemin parcouru depuis l’algorithme proposé au XVII e siècle par Newton pour déterminer une racine d’un polynôme réel d’une variable réelle, décrit dans les quelques lignes de l’épigraphe de ce chapitre, alors que la notion de dérivée n’existait pas encore. Il aurait d’ailleurs été préférable d’utiliser le nom de Simpson pour décrire ces méthodes (voir les notes de fin de chapitre), mais l’usage actuel en a décidé autrement. Nous aurions aussi pu utiliser la locution méthodes de linéarisation, mais nous n’avons pas franchi le pas et avons suivi la tradition. Il y a de nombreuses monographies consacrées à l’algorithme de Newton ou à un aspect de cette approche par linéarisation (voir les notes en fin de chapitre), si bien que notre présentation ne pourra être que partielle, se concentrant sur des sujets qui nous paraissent essentiels ou en rapport direct avec l’esprit de cet ouvrage. Notre description commencera par le cas simple et instructif dans lequel on cherche à résoudre un système d’équations non linéaires, à en trouver un zéro (section 10.1.1). Ce cas est important en optimisation pour au moins deux raisons. D’abord il se présente lorsqu’on cherche à minimiser la fonction nulle sous des contraintes d’égalité. Par ailleurs, l’algorithme de Newton en optimisation sans contrainte est un cas particulier du précédent, si bien que certaines de ses propriétés, non attractives pour l’optimisation, trouveront leur origine dans le fait que cette approche est d’abord destinée à la résolution d’équations non linéaires. Nous verrons ensuite comment adapter l’algorithme à la minimisation de fonctions sans contrainte (section 10.1.2) ; le cas des problèmes avec contraintes sera examiné en détail au chapitre 15. La propriété la plus attrayante de l’algorithme de Newton, qui en fait une référence, est sa convergence quadratique locale (théorèmes 10.2 et 10.3). Il a malheureusement aussi beaucoup de défauts ; nous les détaillerons. Comme remède à ces imperfections nous examinerons en détail les méthodes inexactes (section 10.2) et la globalisation de la convergence (section 10.3). Connaissances supposées. Conditions d’optimalité pour les problèmes sans contrainte (section 4.2) ; algorithme du gradient conjugué (chapitre 8, utile pour l’algorithme de Newton tronqué à la section 10.3.1).

Méthodes locales

Systèmes d’équations 

On s’intéresse ici à la recherche d’un zéro d’un système d’équations non linéaires, c’est-à-dire d’un point x ∈ R n qui vérifie F(x) = 0, (10.1) où F : R n → R n est une fonction différentiable. Il faut donc que Fi(x) = 0 pour tout i = 1, . . . , n. Le système (10.1) étant formé de n équations aux n inconnues x = (x1, . . . , xn), il a quelques chances d’être bien posé. L’algorithme de Newton génère une suite {xk} par une idée très simple, qui est illustrée à la figure 10.1 dans le cas où n = 1. On commence par linéariser l’équation en l’itéré courant xk, ce qui donne la fonction x 7→ F(xk) + F ′ (xk) · (x − xk) dont le graphe est représenté par la ligne en tirets à la figure 10.1. Puis on cherche un zéro de cette fonction linéaire, s’il existe. C’est un opération simple puisqu’il suffit de résoudre un système linéaire. Ce zéro est l’itéré suivant xk+1, qui est donc défini par F(xk) + F ′ (xk) · (xk+1 − xk) = 0 Cette équation peut certainement être résolue si F ′ (xk) est inversible. On renforcera l’analogie avec les méthodes à directions de descente du chapitre 6 en écrivant xk+1 = xk + dk, (10.2) où dk est la solution de l’équation de Newton, qui est le système linéaire suivant F ′ (xk)dk = −F(xk). (10.3) On peut maintenant décrire l’algorithme de Newton, que l’on qualifie de local car, comme on le verra, sa convergence n’est garantie que si le premier itéré est proche d’un zéro régulier de F. Algorithme 10.1 (Newton local pour système non linéaire) On suppose qu’au début de l’itération k, on dispose d’un itéré xk ∈ R n. 1. Test d’arrêt. Si F(xk) ≃ 0, arrêt de l’algorithme. 2. Direction. Calculer dk comme solution de (10.3). 3. Nouvel itéré. xk+1 := xk + dk. Le coût de l’itération repose essentiellement sur l’évaluation de la jacobienne F ′ (xk) et sur la résolution du système linéaire (10.3) à l’étape 2. Cet algorithme ramène donc la résolution du système non linéaire (10.1) à une suite de systèmes linéaires, plus simples à résoudre. L’intérêt principal de l’algorithme Newton est de générer des suites q-quadratiquement convergentes, c’est ce que nous allons montrer dans le théorème 10.2 cidessous. Les conditions assurant un tel comportement sont à peine plus fortes que celles requises pour que la méthode soit bien définie : il faut que F ait une dérivée lipschitzienne (alors que seule la dérivabilité de F est nécessaire à la définition de l’algorithme) et que F ′ soit inversible en la solution x∗ recherchée (alors F ′ (xk) sera inversible pour un itéré xk proche de x∗). Le théorème suivant analyse la convergence d’une méthode un peu plus générale que l’algorithme 10.1, dans laquelle, à l’étape 2, la direction dk est solution du système linéaire .

Défauts et remèdes 

Les inconvénients de la méthode de Newton pour résoudre des systèmes d’équations non linéaires [resp. des problèmes d’optimisation] sont bien connus : 1. il faut calculer les dérivées premières de F [resp. les dérivées secondes de f], ce qui peut être coûteux en temps de calcul (n 2 éléments à évaluer), en effort humain (l’expression analytique de ces dérivées n’est pas toujours simple à obtenir) et en espace mémoire ; 2. l’algorithme n’est pas globalement convergent (si le premier itéré est éloigné d’une solution, le comportement des itérés suivants est souvent erratique) ; 3. l’algorithme n’est pas nécessairement défini aux points x où F ′ (x) [resp. ∇2f(x)] est singulière ; 4. pour les problèmes d’optimisation, si f n’est pas fortement convexe, l’algorithme ne génère pas nécessairement des directions de descente de f ; 

5. un système linéaire d’ordre n doit être résolu à chaque itération. Voilà bien des défauts pour un algorithme aux propriétés locales tant souhaitées (il converge localement quadratiquement). Dans les sections suivantes, nous étudions des modifications de la méthode de Newton qui remédient partiellement à ces points faibles, tout en essayant de conserver son intérêt majeur qui est de générer des suites convergeant rapidement. Les remèdes foisonnent et il n’est pas aisé de les exposer de manière concise. On peut en effet s’intéresser à la résolution de systèmes non linéaires ou à l’optimisation ; la globalisation de la convergence peut se faire par recherche linéaire, par région de confiance ou des méthodes de suivi de chemin ; le système de Newton peut être résolu exactement ou de manière approchée, par des méthodes directes ou itératives ; les algorithmes peuvent faire l’effort de ne pas utiliser la transposée de la jacobienne F ′ (x) ou pas. Voilà donc beaucoup de possibilités à décrire et elles peuvent toutes être intéressantes en fonction du problème à résoudre. Nous serons brefs sur certaines approches si elles peuvent se déduire de méthodes déjà décrites ailleurs. Par ailleurs, nous ne considérerons pas les cas singuliers, où la jacobienne n’est pas inversible en la solution, où la fonction est non lisse, où la solution recherchée n’est pas isolée, etc, qui sont tous très importants pour pouvoir aborder des problèmes plus généraux que les deux considérés ici (annuler une fonction non linéaire et l’optimisation), comme les problèmes d’inéquations variationnelles ou de complémentarité, l’optimisation sous contrainte, etc. Mais soyons clair : nonobstant cette abondance, il n’y a pas d’algorithme newtonien qui garantisse la convergence vers un zéro d’une fonction non linéaire F arbitraire quel que soit l’itéré initial. Cependant, les techniques numériques que nous allons présenter dans les sections suivantes améliorent grandement les qualités (efficacité et robustesse) des algorithmes en pratique, si bien qu’on ne peut les négliger. La difficulté se rencontre déjà en dimension 1, pour la fonction suivante F(x) = 1 2 + 3x 2 − 7 2 x 3 , F 0 1 (10.8) laquelle a un unique zéro en x = 1. Si l’on prend comme itéré initial x0 = 0, les algorithmes échouent lamentablement. Il faut noter que la jacobienne de F y est nulle et donc que la direction de Newton n’y est pas définie. Par ailleurs, la fonction x 7→ |F(x)| a un minimum local en zéro, ce qui rend ce point attrayant aux yeux de beaucoup d’algorithmes. En réalité, il n’y a pas aujourd’hui de remède universel à cette difficulté fondamentale, qui trouve son origine dans le fait que l’algorithme de Newton est une méthode locale (en chaque itéré, elle n’utilise que les valeurs de F et de sa dérivée) alors que la détermination d’un zéro de F est de nature globale (dans l’exemple ci-dessus, en n’examinant F que dans le voisinage de 0, il est très difficile de savoir s’il faut s’éloigner de 0 en partant vers la gauche ou vers la droite — ce n’est pas impossible de faire le bon choix lorsque F est analytique et que l’on dispose des dérivées de tous ordres de F en zéro, mais en pratique il n’est possible d’utiliser qu’une quantité finie d’information)