Algorithmes de quasi-Newton

Algorithmes de quasi-Newton

Dans ce chapitre, on s’intéresse à la résolution du problème d’optimisation sans contrainte  min f(x) x ∈ R n par des algorithmes à directions de descente particuliers. On note {xk}k>1 la suite des itérés et gk = ∇f(xk) le gradient de f en xk. Les itérés sont donc générés par la récurrence xk+1 = xk + αkdk, k > 1, où le pas αk > 0 est déterminé par recherche linéaire (section 6.3) et dk est une direction de descente. Dans les méthodes de quasi-Newton, dk est de la forme dk = −M−1 k gk. (11.1) Si Mk = ∇2f(xk), on retrouve la méthode de Newton, si bien que le nom donné aux méthodes décrites ci-dessous apparaît naturel. Cependant, tout algorithme ayant une direction de descente de la forme (11.1) ne se retrouve pas pour autant dans cette classe de méthodes. Le qualificatif quasi-Newton fait en effet référence à un ensemble de techniques mises au point à partir des années 1960 permettant de générer les matrices Mk à partir des gradients gk. Dans beaucoup de problèmes, on cherche à éviter le calcul des dérivées secondes, pour les raisons suivantes : l’évaluation de ∇2 f(xk) ou le produit de cete hessienne par un vecteur comme dans l’algorithme de Newton tronqué (section 10.3.1) peut demander trop de temps de calcul, on ne dispose pas toujours des dérivées secondes et leur calcul peut demander un investissement humain trop important, alors que l’on voudrait obtenir un résultat rapidement par des algorithmes peut-être plus lents que l’algorithme de Newton mais ne demandant que le calcul des dérivées premières, la fonction peut ne pas être deux fois dérivable, on ne dispose pas de place mémoire pour stocker les O(n 2 ) éléments d’une matrice (c’est la moins bonne des raisons, voir section 10.3.1). Ce sont des situations dans lesquelles les algorithmes de quasi-Newton sont très utiles. Dans ceux-ci, la matrice Mk dans (11.1) n’est pas égale à ∇2f(xk), mais est générée par des formules qui cherchent à ce que cette matrice soit proche de la hessienne de f. On parle de formules de mise à jour. Celles-ci ne font intervenir que les dérivées premières de f. C’est en utilisant la variation du gradient de f d’une itération à l’autre que ces formules permettent d’engranger de l’information sur la hessienne. Dans ce chapitre, on se propose d’introduire et d’étudier ces formules de mise à jour et les algorithmes de quasi-Newton qui les utilisent. Voici quelques propriétés de ces algorithmes. Localement (proche d’une solution), les algorithmes de quasi-Newton convergent moins rapidement que l’algorithme de Newton. Dans les implémentations correctes, les itérés convergent toutefois q-superlinéairement. Chaque itération demande moins de calcul au simulateur que dans l’algorithme de Newton : il ne faut pas évaluer les dérivées secondes. Dans leur version standard, ces algorithmes peuvent être utilisés pour un nombre de variables qui n’est pas trop grand, disons n 6 500 pour fixer les idées. Cette borne sur n vient d’une part du coup de l’itération (de l’ordre de O(n 2 ) opérations dans l’optimiseur) et du fait que les algorithmes deviennent plus lents lorsque n augmente. Notons qu’il existe des adaptations de ces algorithmes quasi-newtoniens pouvant être utilisées pour résoudre des problèmes de très grande taille, avec plusieurs millions de variables, par exemple. Ces méthodes sont dites à mémoire limitée car elles ne demandent pas que l’on garde Mk en mémoire. L’algorithme ℓ-BFGS de la section 11.2.5 est de ce type. Il est très utilisé. Hypothèse générale à ce chapitre. Nous développerons la théorie lorsque le produit scalaire que l’on se donne sur R n est le produit scalaire euclidien : (u, v) 7→ u Tv. Dans ce cas, ∇f(x) est le vecteur des dérivées partielles de f. On peut se placer dans un cadre plus général en ne faisant aucune hypothèse sur le produit scalaire (u, v) 7→ hu, vi utilisé. Il faut alors utiliser le produit tensoriel associé (u, v) 7→ u ⊗ v, où (u ⊗ v) est la matrice d’ordre n définie par (u ⊗ v)d := hv, di u, pour tout d ∈ R n. Pour obtenir des formules de mise à jour tenant compte du produit scalaire utilisé (et donc du pré conditionnement que cela implique), il suffit le plus souvent de remplacer dans les formules obtenues une matrice de la forme uvT par la matrice u⊗v. Voir par exemple [244] et ses références pour plus détails.

Formules de mise à jour 

Principes 

Supposons que Mk soit connue et cherchons quelle valeur donner à Mk+1 pour que cette matrice approche ∇2f(xk+1). On cherche à ce que Mk+1 soit proche de la hessienne de f pour que l’algorithme hérite des bonnes propriétés de convergence locale de l’algorithme de Newton. Soient sk := xk+1 − xk et yk := gk+1 − gk,Si n > 1, les conditions (11.2) et (11.3) ne suffisent pas pour déterminer Mk+1 : il y a n(n + 1)/2 inconnues et n équations seulement. Ce manque de conditions laisse une liberté dont ne se sont pas privé les spécialistes en optimisation numérique. Les années 1960-80 ont vu ainsi naître de nombreuses formules de mise à jour. Les plus importantes en optimisation sont la formule SR1 et la formule de BFGS. Avant d’introduire ces formules, notons que lorsque n = 1, les conditions (11.2) et (11.3) déterminent Mk+1, qui est le scalaire yk/sk (on suppose xk+1 6= xk). L’algorithme de quasi-Newton avec pas unité associé donne (en décalant les indices d’une unité et en supposant gk−1 6= gk et gk 6= 0) : xk+1 = xk − sk−1 yk−1 gk ou xk − xk+1 gk − 0 = xk−1 − xk gk−1 − gk . On reconnaît l’algorithme de la sécante. Les méthodes de quasi-Newton portent d’ailleurs parfois ce nom. La figure 11.1 rappelle ce qu’est l’algorithme de la sécante en dimension 1 et le compare à l’algorithme de Newton lorsqu’on cherche à minimiser une fonction x ∈ R 7→ f(x) ∈ R en annulant sa dérivée. Dans l’algorithme de Newton (à gauche), le nouvel itéré xk+1 est obtenu en calculant l’intersection avec l’axe des abscisses de la droite tangente à la courbe x 7→ f ′ (x) en (xk, f′ (xk)) (c’est le zéro de la fonction f ′ linéarisée en xk), tandis que dans l’algorithme de la sécante (à droite), on prend l’intersection du même axe avec la droite passant par (xk−1, f′ (xk−1)) et (xk, f′ (xk)). Dans ce dernier algorithme, on ne doit pas linéariser f ′ (c’est-à-dire calculer la dérivée seconde de f), mais on doit utiliser la valeur de f ′ aux deux points xk−1 et xk. 

Formule SR1 

Une première idée est de rechercher parmi les matrices vérifiant (11.2) et (11.3), une matrice Mk+1 suffisamment proche de Mk en imposant que la différence entre les deux matrices soit de rang 1. On prend une correction de faible rang de manière à assurer une certaine stabilité à la suite {Mk}. Il semble en effet raisonnable de souhaiter que ces matrices n’oscillent pas trop au cours des itérations. On cherche donc une mise à jour de la forme Mk+1 = Mk + uvT , où u et v sont deux vecteurs de R n à déterminer. Si on veut que Mk+1 vérifie l’équation de quasi-Newton (11.2), il faut que u et v satisfassent yk = Mksk + (v T sk)u. Si v Tsk = 0, soit Mk vérifie déjà l’équation de quasi-Newton, soit une correction de rang 1 de Mk ne permet pas d’obtenir une matrice vérifiant cette équation. Si v Tsk 6= 0,