Pour minimiser une fonction, la descente de gradient avance pas à pas dans la direction opposée au gradient. Elle fonctionne, mais elle peut demander des centaines d’itérations pour atteindre une précision correcte. La méthode de Newton fait mieux : dans les bonnes conditions, elle double le nombre de décimales exactes à chaque itération.
Cette méthode a été conçue au départ pour résoudre des équations du type f(x) = 0. En remarquant que minimiser une fonction revient à annuler sa dérivée, on obtient un algorithme d’optimisation redoutablement efficace. C’est aussi la méthode historique utilisée pour ajuster une régression logistique (via IRLS) et l’inspiration derrière BFGS, l’optimiseur par défaut de scipy.optimize.minimize.
Dans cet article, on construit la méthode de Newton de A à Z : itération pour trouver des zéros, extension à l’optimisation, interprétation géométrique par approximation quadratique, convergence quadratique (avec preuve d’idée), comparaison systématique avec la descente de gradient, applications en machine learning et trois exercices corrigés.
Newton-Raphson : résoudre f(x) = 0
La récurrence
Soit f : \mathbb{R} \to \mathbb{R} une fonction dérivable et x^\star un zéro de f. Partant d’un point x_k proche de x^\star, on approxime f par sa tangente en x_k :
T(x) = f(x_k) + f'(x_k) (x - x_k)
Le zéro de cette tangente est facile à calculer : T(x) = 0 donne x = x_k - f(x_k)/f'(x_k). On définit alors le point suivant comme ce zéro :
\boxed{x_{k+1} = x_k - \dfrac{f(x_k)}{f'(x_k)}}C’est l’itération de Newton-Raphson. Elle produit une suite (x_k) qui, sous des hypothèses raisonnables, converge vers le zéro x^\star de f.
Interprétation géométrique
Le mouvement x_k \to x_{k+1} a une lecture très concrète : on trace la tangente au graphe de f au point (x_k, f(x_k)) , on regarde où cette tangente coupe l’axe des abscisses, et on prend ce point comme nouvel itéré. Tant que la courbe reste proche d’une droite (c’est-à-dire tant que la courbure est modérée), ce zéro approché est très proche du zéro exact.
Exemple : calcul de √2
Prenons f(x) = x^2 - 2, dont la racine positive est \sqrt{2}. La récurrence devient :
x_{k+1} = x_k - \dfrac{x_k^2 - 2}{2 x_k} = \dfrac{x_k + 2/x_k}{2}C’est la célèbre méthode babylonienne (ou méthode de Héron) pour extraire une racine carrée, connue depuis l’Antiquité. Partons de x_0 = 2 :
| k | x_k | Erreur \lvert x_k - \sqrt{2} \rvert |
|---|---|---|
| 0 | 2 | 5,9 × 10⁻¹ |
| 1 | 3/2 = 1,5 | 8,6 × 10⁻² |
| 2 | 17/12 ≈ 1,4167 | 2,5 × 10⁻³ |
| 3 | 577/408 ≈ 1,41422 | 2,1 × 10⁻⁶ |
| 4 | 665857/470832 ≈ 1,4142135624 | 1,6 × 10⁻¹² |
En 4 itérations, on a déjà 12 décimales exactes. À chaque pas, le nombre de décimales exactes double à peu près : c’est la signature de la convergence quadratique, que l’on va formaliser plus loin.
À titre de comparaison, la dichotomie, l’autre méthode classique de recherche de zéros, ne gagne qu’environ une décimale toutes les 3 à 4 itérations. Elle est plus lente, mais plus robuste : pas besoin de dérivée, il suffit que f change de signe sur un intervalle. Newton, lui, exige une fonction dérivable et un point de départ suffisamment proche du zéro cherché.
De la recherche de zéros à l’optimisation
Annuler la dérivée
Minimiser une fonction f dérivable revient, sauf pathologies, à trouver ses points critiques : les x tels que f'(x) = 0. Il suffit donc d’appliquer Newton-Raphson à la dérivée f', ce qui donne :
\boxed{x_{k+1} = x_k - \dfrac{f'(x_k)}{f''(x_k)}}C’est la méthode de Newton pour l’optimisation en une dimension. On reconnaît la récurrence précédente appliquée à f' : (f')'(x) = f''(x), et les zéros de f' sont exactement les points critiques de f.
Extension en dimension quelconque
En dimension n, on cherche à minimiser f : \mathbb{R}^n \to \mathbb{R}. La dérivée est remplacée par le gradient \nabla f(x) \in \mathbb{R}^n. La dérivée seconde est remplacée par la matrice hessienne :
H(x) = \nabla^2 f(x) = \left(\dfrac{\partial^2 f}{\partial x_i \partial x_j}(x)\right)_{1 \leq i, j \leq n}C’est la matrice symétrique n \times n des dérivées partielles secondes, étudiée dans l’article sur les fonctions de plusieurs variables. La récurrence s’écrit alors :
\boxed{x_{k+1} = x_k - \bigl[H(x_k)\bigr]^{-1} \nabla f(x_k)}L’inverse de la Hessienne H^{-1} joue le rôle de 1/f'' en dimension un. En pratique, on ne calcule jamais cet inverse explicitement : on résout le système linéaire H(x_k) d = -\nabla f(x_k) pour obtenir la direction de Newton d, puis on pose x_{k+1} = x_k + d.
Interprétation : approximation quadratique
Le développement de Taylor à l’ordre 2
La manière la plus éclairante de comprendre Newton est géométrique. On remplace localement f par son développement de Taylor à l’ordre 2 autour de x_k. En dimension un :
q(x) = f(x_k) + f'(x_k) (x - x_k) + \tfrac{1}{2} f''(x_k) (x - x_k)^2C’est la parabole osculante : la parabole qui épouse la courbe de f en x_k aux ordres 0, 1 et 2 (même valeur, même pente, même courbure). Au voisinage de x_k, q(x) ressemble énormément à f(x).
Minimiser la parabole
L’idée de Newton est simple : plutôt que de minimiser la vraie fonction f (difficile), on minimise à chaque étape la parabole osculante q (facile). Le minimum de q s’obtient en annulant q'(x) = f'(x_k) + f''(x_k) (x - x_k), ce qui donne directement :
x_{k+1} = x_k - \dfrac{f'(x_k)}{f''(x_k)}On retrouve exactement la récurrence de Newton. Chaque itération consiste donc à remplacer localement f par sa meilleure approximation du second ordre, puis à se déplacer au minimum de cette approximation.
Pourquoi c’est mieux que le gradient
La descente de gradient remplace f par son approximation linéaire (sa tangente) et fait un pas de taille \eta dans la direction de plus forte pente. C’est une approximation d’ordre 1, qui ignore complètement la courbure.
Newton remplace f par son approximation quadratique et se place directement au minimum de cette approximation. C’est une approximation d’ordre 2, qui exploite l’information de courbure contenue dans la Hessienne. Le pas est automatiquement adapté : pas de taux d’apprentissage \eta à régler, la Hessienne fait tout le travail.
Application ML : si f est elle-même quadratique (par exemple, la perte d’une régression linéaire), alors la parabole osculante est exactement f, et Newton converge en une seule itération depuis n’importe quel point de départ. C’est d’ailleurs pourquoi la solution des moindres carrés est analytique : elle équivaut à une unique étape de Newton.
Convergence quadratique vs linéaire
Définitions
Soit (x_k) une suite qui converge vers x^\star et e_k = \lvert x_k - x^\star \rvert l’erreur à l’étape k. On dit que la convergence est :
- Linéaire si e_{k+1} \leq \rho e_k pour une constante \rho < 1. L’erreur est multipliée par \rho à chaque pas : elle décroît en progression géométrique.
- Quadratique si e_{k+1} \leq C e_k^2 pour une constante C. L’erreur à l’étape suivante est du même ordre que le carré de l’erreur actuelle.
Concrètement, si e_k = 10^{-3} :
- une convergence linéaire à \rho = 1/2 donne e_{k+1} = 5 \times 10^{-4} (un peu mieux),
- une convergence quadratique donne e_{k+1} \approx 10^{-6} (le nombre de décimales exactes double).
C’est cet effet de doublement qui rend Newton si puissant au voisinage d’un minimum.
Théorème de convergence locale
Théorème. Soit f deux fois continûment dérivable au voisinage d’un minimum local x^\star, avec f''(x^\star) > 0 (la Hessienne est définie positive en dimension supérieure). Alors il existe un voisinage de x^\star tel que, si x_0 est dans ce voisinage, la méthode de Newton converge vers x^\star avec une vitesse quadratique.
L’idée de la preuve est simple : en combinant le développement de Taylor de f' autour de x^\star et la récurrence de Newton, on montre que :
x_{k+1} - x^\star = \dfrac{f'''(\xi_k)}{2 f''(x_k)} (x_k - x^\star)^2pour un certain \xi_k entre x_k et x^\star, d’où la majoration e_{k+1} \leq C e_k^2 près du minimum.
IMAGE : graphiques/newton_vs_gradient.png — Alt : « Comparaison des vitesses de convergence : Newton (quadratique) et descente de gradient (linéaire) sur f(x) = x⁴ − 3x² + 2 depuis x₀ = 2, en échelle semi-logarithmique »
Comparatif pratique
| Newton | Descente de gradient | |
|---|---|---|
| Ordre d’approximation | Quadratique (Hessienne) | Linéaire (gradient) |
| Convergence locale | Quadratique | Linéaire |
| Itérations typiques | 5 à 20 | 100 à 10 000 |
| Coût par itération | O(n^3) (inversion H) | O(n) |
| Mémoire | O(n^2) (stockage H) | O(n) |
| Hyperparamètre | Aucun | Taux d’apprentissage \eta |
| Convergence globale | Non garantie | Oui si \eta bien choisi |
Newton est donc nettement supérieur par itération, mais chaque itération coûte beaucoup plus cher en temps et en mémoire. En pratique, on choisit Newton pour de l’optimisation de moyenne dimension (n \lesssim 10^4), et on se rabat sur la descente de gradient ou ses variantes pour les grandes dimensions.
Application en ML : régression logistique et IRLS
La log-vraisemblance logistique
La régression logistique est l’algorithme de classification binaire le plus classique. On modélise la probabilité qu’une observation x_i \in \mathbb{R}^d appartienne à la classe 1 par :
p_i(\theta) = \sigma(x_i^\top \theta) = \dfrac{1}{1 + e^{-x_i^\top \theta}}où \sigma est la sigmoïde. La log-vraisemblance à maximiser (voir l’article MLE) vaut :
\ell(\theta) = \sum_{i=1}^n \bigl[y_i \log p_i + (1 - y_i)\log(1 - p_i)\bigr]On peut montrer que cette log-vraisemblance est concave, donc qu’elle admet un unique maximum global (lorsqu’il existe). Pas de minima locaux parasites : c’est exactement le cadre où Newton brille.
L’algorithme IRLS
On applique Newton à -\ell (pour minimiser). Après calcul, le gradient vaut :
\nabla \ell(\theta) = X^\top (y - p)
et la Hessienne :
H(\theta) = -X^\top W X, \quad W = \operatorname{diag}\bigl(p_i (1 - p_i)\bigr)où X \in \mathbb{R}^{n \times d} est la matrice des observations et W une matrice diagonale de poids. L’itération de Newton devient :
\boxed{\theta_{k+1} = \theta_k + (X^\top W_k X)^{-1} X^\top (y - p_k)}On reconnaît une régression linéaire pondérée par W_k, qui change à chaque itération. C’est pour cette raison que l’algorithme s’appelle IRLS (Iteratively Reweighted Least Squares) : à chaque pas, on résout un système de moindres carrés avec des poids mis à jour.
IRLS converge typiquement en 5 à 15 itérations, contre plusieurs milliers de pas pour une descente de gradient classique. C’est historiquement l’algorithme par défaut pour ajuster une régression logistique (glm en R, statsmodels en Python).
Limites en grande dimension
Le coût dominant est l’inversion (ou la résolution) du système X^\top W X de taille d \times d, en O(d^3). Dès que d dépasse quelques milliers (vision par ordinateur, NLP, embeddings), cette opération devient prohibitive. On passe alors à des méthodes du premier ordre (descente de gradient stochastique, Adam) ou aux méthodes quasi-Newton décrites juste après.
Application ML : Newton apparaît aussi dans l’ajustement des modèles linéaires généralisés (GLM) au sens large (Poisson, Gamma, log-linéaire), dans l’estimation des GBMs (XGBoost utilise un pas de Newton sur la perte à chaque nouvel arbre), et en apprentissage par renforcement pour les méthodes natural gradient.
Quasi-Newton : BFGS et L-BFGS
Pourquoi « quasi » ?
Calculer la Hessienne exacte H(x_k) coûte O(n^2) opérations par itération et O(n^2) de mémoire pour la stocker. L’inverser coûte O(n^3). Pour n \sim 10^5 (réseau de neurones modeste), on sort des ressources disponibles.
Les méthodes quasi-Newton résolvent ce problème en remplaçant la vraie Hessienne H(x_k) (ou son inverse) par une approximation B_k construite à partir des gradients successifs \nabla f(x_0), \nabla f(x_1), \ldots. Elles gardent la convergence superlinéaire de Newton tout en évitant le calcul explicite de la Hessienne.
BFGS
L’algorithme BFGS (Broyden-Fletcher-Goldfarb-Shanno, 1970) est le quasi-Newton le plus célèbre. Il construit une suite de matrices B_k approchant la Hessienne, mises à jour à chaque itération par une formule de rang 2 qui satisfait la condition de sécante :
B_{k+1} (x_{k+1} - x_k) = \nabla f(x_{k+1}) - \nabla f(x_k)Cette condition impose à B_{k+1} de reproduire l’effet de la vraie Hessienne sur la variation observée. Les matrices B_k restent symétriques et définies positives, ce qui garantit que la direction proposée est une direction de descente.
L-BFGS : la version « limited memory »
Pour les problèmes de très grande dimension (n \geq 10^6), stocker la matrice B_k en mémoire devient impossible. L-BFGS (Limited-memory BFGS) contourne le problème en ne stockant que les m derniers couples (s_k, y_k) = (x_{k+1} - x_k, \nabla f(x_{k+1}) - \nabla f(x_k)) , typiquement m = 5 à 20. La multiplication par B_k se calcule alors à la volée, en O(m n) opérations seulement.
En pratique, L-BFGS est l’algorithme utilisé par défaut dans scipy.optimize.minimize, dans sklearn.linear_model.LogisticRegression, et dans de nombreux solveurs de régression logistique à grande échelle.
Exercices corrigés
Exercice 1 : Newton-Raphson pour √2
Soit f(x) = x^2 - 2. Écrire la récurrence de Newton-Raphson sous forme simplifiée, puis calculer x_1, x_2, x_3 à partir de x_0 = 2. Comparer l’erreur à chaque étape et commenter.
Correction.
On a f'(x) = 2x, donc la récurrence x_{k+1} = x_k - f(x_k)/f'(x_k) devient :
x_{k+1} = x_k - \dfrac{x_k^2 - 2}{2 x_k} = \dfrac{2 x_k^2 - x_k^2 + 2}{2 x_k} = \dfrac{x_k^2 + 2}{2 x_k} = \dfrac{1}{2}\left(x_k + \dfrac{2}{x_k}\right)C’est la moyenne de x_k et de 2/x_k : une moyenne géométrique adaptée. Calculons les itérés depuis x_0 = 2 :
x_1 = \dfrac{1}{2}\left(2 + 1\right) = \dfrac{3}{2} x_2 = \dfrac{1}{2}\left(\dfrac{3}{2} + \dfrac{4}{3}\right) = \dfrac{1}{2} \cdot \dfrac{9 + 8}{6} = \dfrac{17}{12}
x_3 = \dfrac{1}{2}\left(\dfrac{17}{12} + \dfrac{24}{17}\right) = \dfrac{1}{2} \cdot \dfrac{289 + 288}{204} = \dfrac{577}{408}Les erreurs e_k = \lvert x_k - \sqrt{2}\rvert valent approximativement :
e_0 \approx 5{,}9 \cdot 10^{-1}, \quad e_1 \approx 8{,}6 \cdot 10^{-2}, \quad e_2 \approx 2{,}5 \cdot 10^{-3}, \quad e_3 \approx 2{,}1 \cdot 10^{-6}Commentaire. L’erreur passe de 10^{-1} à 10^{-2}, puis à 10^{-3}, puis à 10^{-6} : le nombre de décimales exactes double à chaque étape, ce qui est la signature de la convergence quadratique. En 4 itérations, on obtient déjà 12 décimales exactes de \sqrt{2}.
Exercice 2 : convergence en une itération sur une fonction quadratique
Soit f : \mathbb{R}^2 \to \mathbb{R} définie par f(x, y) = (x - 1)^2 + 4(y - 2)^2. Montrer que, quel que soit le point de départ (x_0, y_0) , la méthode de Newton atteint le minimum en une seule itération.
Correction.
Étape 1. Calcul du gradient et de la Hessienne :
\nabla f(x, y) = \left(\begin{array}{c} 2(x - 1) \\ 8(y - 2) \end{array}\right), \quad H = \left(\begin{array}{cc} 2 & 0 \\ 0 & 8 \end{array}\right)La Hessienne H est constante (car f est quadratique) et définie positive. Son inverse est :
H^{-1} = \left(\begin{array}{cc} 1/2 & 0 \\ 0 & 1/8 \end{array}\right)Étape 2. Itération de Newton depuis un point quelconque (x_0, y_0) :
\left(\begin{array}{c} x_1 \\ y_1 \end{array}\right) = \left(\begin{array}{c} x_0 \\ y_0 \end{array}\right) - H^{-1} \nabla f(x_0, y_0) = \left(\begin{array}{c} x_0 \\ y_0 \end{array}\right) - \left(\begin{array}{c} \tfrac{1}{2} \cdot 2(x_0 - 1) \\ \tfrac{1}{8} \cdot 8(y_0 - 2) \end{array}\right)= \left(\begin{array}{c} x_0 - (x_0 - 1) \\ y_0 - (y_0 - 2) \end{array}\right) = \left(\begin{array}{c} 1 \\ 2 \end{array}\right)Conclusion. On atteint le minimum exact (1, 2) en une seule itération, peu importe le point de départ.
Interprétation. Ce résultat est général : dès que la fonction à minimiser est exactement quadratique, la parabole osculante coïncide avec la fonction elle-même, et Newton converge en un pas. C’est le cas notamment en régression linéaire, où la solution des moindres carrés correspond à une unique étape de Newton sur la fonction de perte.
Exercice 3 : comparaison Newton / descente de gradient
Soit f(x) = x^4 - 3 x^2 + 2 sur \mathbb{R}. On cherche à minimiser f depuis x_0 = 2.
- Calculer les points critiques de f et identifier les minima.
- Appliquer 4 itérations de la méthode de Newton.
- Appliquer 4 itérations d’une descente de gradient à pas fixe \eta = 0{,}03.
- Dresser un tableau comparatif et commenter.
Correction.
1. On a f'(x) = 4 x^3 - 6 x = 2 x (2 x^2 - 3), qui s’annule pour x = 0 et x = \pm \sqrt{3/2}. La dérivée seconde f''(x) = 12 x^2 - 6 vaut -6 < 0 en 0 (maximum local) et 18 > 0 en \pm \sqrt{3/2} (minima locaux). On cherche donc le minimum x^\star = \sqrt{3/2} \approx 1{,}2247.
2. Récurrence de Newton : x_{k+1} = x_k - f'(x_k)/f''(x_k). Les itérés depuis x_0 = 2 :
| k | x_k | Erreur e_k |
|---|---|---|
| 0 | 2 | 7,75 × 10⁻¹ |
| 1 | ≈ 1,5238 | 2,99 × 10⁻¹ |
| 2 | ≈ 1,2947 | 6,99 × 10⁻² |
| 3 | ≈ 1,2300 | 5,28 × 10⁻³ |
| 4 | ≈ 1,22478 | 3,38 × 10⁻⁵ |
3. Récurrence de la descente de gradient : x_{k+1} = x_k - \eta f'(x_k) avec \eta = 0{,}03. Les itérés depuis x_0 = 2 :
| k | x_k | Erreur e_k |
|---|---|---|
| 0 | 2 | 7,75 × 10⁻¹ |
| 1 | 1,4 | 1,75 × 10⁻¹ |
| 2 | ≈ 1,3227 | 9,80 × 10⁻² |
| 3 | ≈ 1,2831 | 5,84 × 10⁻² |
| 4 | ≈ 1,2606 | 3,58 × 10⁻² |
4. Tableau comparatif.
| Itération | Newton | Gradient |
|---|---|---|
| 1 | 2,99 × 10⁻¹ | 1,75 × 10⁻¹ |
| 2 | 6,99 × 10⁻² | 9,80 × 10⁻² |
| 3 | 5,28 × 10⁻³ | 5,84 × 10⁻² |
| 4 | 3,38 × 10⁻⁵ | 3,58 × 10⁻² |
Commentaire. Newton démarre légèrement moins vite que le gradient (itération 1), mais dès l’itération 3 l’écart est énorme : l’erreur de Newton est inférieure à celle du gradient d’un facteur 10, puis 1000. La raison est mécanique : chaque itération de Newton exploite la courbure locale via f''(x_k), alors que le gradient est aveugle à cette information. Pour atteindre la précision obtenue par Newton en 4 pas, il faudrait plusieurs dizaines d’itérations de descente de gradient.
Exercices d’entraînement
- Appliquer Newton-Raphson à f(x) = x^3 - 5 pour obtenir une valeur approchée de \sqrt[3]{5}. Écrire la récurrence, calculer trois itérations depuis x_0 = 2, et vérifier que le nombre de décimales exactes double à chaque pas.
- Soit f(x, y) = x^2 + x y + 2 y^2 - 4 x - 3 y. Calculer le gradient et la Hessienne, vérifier que la Hessienne est définie positive, puis donner la position du minimum unique de f en une itération de Newton depuis (0, 0) .
- On applique Newton-Raphson à f(x) = \arctan(x) depuis x_0 = 2. Calculer x_1, x_2, x_3. La méthode converge-t-elle ? Justifier. On rappelle f'(x) = 1/(1 + x^2).
FAQ
a méthode de Newton est un algorithme itératif pour résoudre une équation f(x) = 0 ou pour minimiser une fonction. Partant d’un point x_k, on approxime f par sa tangente (pour la recherche de zéros) ou par sa parabole osculante (pour l’optimisation), puis on prend comme nouveau point le zéro ou le minimum de cette approximation. La formule générale en optimisation est x_{k+1} = x_k − H⁻¹ ∇f, où H est la matrice hessienne.
Parce qu’elle exploite une information supplémentaire : la courbure de la fonction, encodée dans la matrice hessienne. La descente de gradient ne voit que la pente locale (ordre 1) alors que Newton construit une approximation quadratique (ordre 2). Au voisinage d’un minimum, la convergence de Newton est quadratique, ce qui signifie que le nombre de décimales exactes double environ à chaque itération. La descente de gradient n’a qu’une convergence linéaire, bien plus lente.
Dans les problèmes d’optimisation de dimension modérée (jusqu’à quelques milliers de paramètres) où la Hessienne est calculable et inversible. L’exemple historique est la régression logistique, ajustée par IRLS qui est exactement Newton appliqué à la log-vraisemblance. Newton sert aussi dans XGBoost (boosting sur arbres avec un pas de Newton à chaque split), dans certains algorithmes d’apprentissage par renforcement (natural gradient) et en économétrie bayésienne. Pour les grandes dimensions, on utilise plutôt les variantes quasi-Newton comme BFGS et L-BFGS.
Newton-Raphson est la méthode originale, conçue pour résoudre des équations f(x) = 0 par itération x_{k+1} = x_k − f(x_k)/f'(x_k). Newton pour l’optimisation applique cette même méthode à la dérivée f’, puisque minimiser f revient à annuler f’. On obtient alors x_{k+1} = x_k − f'(x_k)/f »(x_k) en dimension un, et x_{k+1} = x_k − H⁻¹ ∇f en dimension supérieure. Les deux reposent sur la même idée d’approximation locale par une tangente ou une parabole.
