Méthodes à régions de confiance

L’algorithme de référence

 On suppose dans cette section que l’on cherche à résoudre numériquement le problème d’optimisation sans contrainte min x∈Rn f(x). (9.1) La fonction f est supposée (Fréchet-)différentiable. La technique des régions de confiance peut être vue comme une méthode de globalisation de la convergence d’algorithmes pour la résolution du problème (9.1), ce qui veut dire qu’elle permet de forcer la convergence des itérés lorsque le démarrage des algorithmes se fait en un point éloigné d’une solution (il ne s’agit aucunement ici de trouver des minima globaux de f). De ce point de vue, cette technique concurrence les méthodes à directions de descente. Un peu plus difficile à mettre en œuvre que ces dernières, elles ont divers avantages, notamment en ce qui concerne les résultats de convergence, qui sont plus forts sous des hypothèses plus faibles. Elles ont aussi la réputation d’être plus robustes, c’est-à-dire de pouvoir résoudre des problèmes plus difficiles, moins bien conditionnés. Elles offrent enfin un moyen naturel de faire face à la non-convexité éventuelle de f. 

Présentation de l’algorithme 

Les méthodes à régions de confiance sont fondées sur le principe suivant, qui est très général et peut donc s’appliquer à d’autres contextes. Au point courant xk ∈ R n , on suppose donné un modèle de la variation de f pour un incrément s de xk. En optimisation différentiable, il est raisonnable de considérer un modèle quadratique de la forme ψk(s) = g T k s + 1 2 s TMks, et hessienne sont supposés être calculés pour le produit sca P laire euclidien hu, vi = i uivi . On n’impose pas à la matrice Mk d’être définie positive (en particulier, elle peut être nulle). Cette souplesse contribue à la robustesse de cette approche. En optimisation non différentiable, on ne dispose pas des gradients de f. On pourra alors construire des modèles différents, comme celui obtenu à partir des plans tangents à l’épigraphe de f aux points (xk, f(xk)). On est alors très proche de l’algorithme connu sous le nom de méthode de faisceaux (voir [317 ; Tome 2]). Si Mk = ∇2f(xk), on a le développement limité à l’ordre 2 : f(xk + s) ≃ f(xk) + ψk(s). Dans ce cas, le modèle quadratique est adéquat pour s voisin de 0. Dans les méthodes à régions de confiance, on considère que ψk est un modèle de la variation de f qui est acceptable dans un voisinage de la forme : {x ∈ R n : kxk 6 ∆k}, où ∆k > 0 et k · k est la norme euclidienne. Ce domaine est appelé la région de confiance du modèle ψk et ∆k est appelé le rayon de confiance. Pour trouver l’accroissement sk à donner à xk, on minimise le modèle quadratique ψk sur la région de confiance. On doit donc résoudre le sous-problème quadratique (RCk)  min ψk(s) ksk 6 ∆k. Soit sk une solution (en général approchée) de ce sous-problème quadratique. Si f(xk+ sk) est suffisamment plus petit que f(xk), on accepte le pas sk et on passe à l’itération suivante avec xk+1 = xk + sk. Dans le cas contraire, on résout à nouveau (RCk) avec un rayon de confiance plus petit, car on considère que le modèle courant n’est pas fiable sur la boule B¯(0, ∆k). Nous verrons que, comme f et ψk coïncident au premier ordre, l’algorithme finit par trouver un rayon de confiance ∆k > 0 pour lequel la solution de (RCk) est acceptée. On ajuste ensuite le modèle à l’itéré suivant xk+1 : calcul de gk+1, de Mk+1 et de ∆k+1. L’ajustement du rayon de confiance est basé sur la comparaison entre la décroissance réelle de f en passant de xk à xk+1 et la décroissance prédite par le modèle, c’est-à-dire −ψk(sk). On peut alors passer à l’itération suivante. Décrivons de manière précise une itération de la méthode à régions de confiance, celle passant de l’itéré xk à xk+1. Nous commenterons ses différentes étapes par la suite. On se donne des constantes indépendantes de l’indice k des itérations, qui sont : – des seuils de succès : 0 < ω1 < ω2 < 1, – des facteurs de mise à jour de ∆k : 0 < τ1 6 τ2 < 1 < τ3. Des valeurs typiques sont : ω1 = 10−2 , ω2 = 0.8, τ1 = τ2 = 0.5 et τ3 ∈ [2, 4]. Étant donnés xk, gk, Mk et ∆k, on s’y prend alors de la manière suivante. Levons une ambiguïté de notation : on note dorénavant (sk, ∆k) la solution approchée et le rayon de confiance obtenus à la sortie de l’étape 2. On ne tient donc pas compte des valeurs intermédiaires prises par ce couple lorsque la condition ρk > ω1 n’est pas vérifiée du premier coup. Certains auteurs considèrent les essais de déplacements comme de vraies itérations, motivés sans doute par le fait que le calcul le plus coûteux de l’algorithme est la résolution des problèmes quadratiques. Cependant, dans les grands problèmes industriels, le coût d’une simulation (calcul de gk et Mk à l’étape 5) prédomine souvent. Nous considérerons donc ici qu’il y a une itération à chaque renouvellement de modèle. D’autre part, comme nous le verrons ci-dessous, cela permet de faciliter la comparaison des régions de confiance et de la recherche linéaire. Si à l’étape 2.1, il n’est pas possible de réaliser ψ(sk) < 0, c’est que gk = 0 et Mk est semi-définie positive. Ceci devrait vouloir dire qu’on ne peut pas faire décroître f non plus. Donc si l’on s’impose un modèle ψk convexe (Mk semi-définie positive), on ne pourra trouver qu’un point stationnaire de f. Si f est convexe, c’est aussi un minimum. Si f n’est pas convexe, il est préférable de ne pas maintenir artificiellement Mk semidéfinie positive mais d’y incorporer des informations sur la hessienne de f, afin d’éviter les points stationnaires qui ne sont pas des minima. Cette observation met en évidence une différence importante avec les méthodes à directions de descente. Dans ces dernières, la direction de descente s’obtient également en minimisant un modèle quadratique, mais sur R n tout entier. Dans ce cas, il est essentiel d’avoir Mk (semi-)définie positive, sinon le sous-problème quadratique n’a pas de solution. De plus, en prenant Mk définie positive, on est sûr que la direction est de descente pour f. Les conditions assurant le bon fonctionnement des régions de confiance sont donc moins restrictives. C’est exactement sur ce point, grâce au fait qu’elles ne demandent pas d’avoir un modèle fortement convexe, que les régions de confiance gagnent en robustesse. Cela se traduira par un affaiblissement des hypothèse garantissant la convergence de cette approche. Le prix à payer est la résolution d’un problème quadratique non trivial. Le ratio ρk calculé à l’étape 2.1 est appelé concordance. Celle-ci apprécie l’adéquation entre la fonction f et son modèle ψk courant. Il s’agit en effet du rapport entre la décroissance réelle de f (f(xk) − f(xk + sk)) et la décroissance prédite par le modèle (−ψk(sk) = ψk(0)−ψk(sk) > 0). Si ce rapport n’est pas assez grand (ρk 6 ω1, ρk sera négatif si le pas sk ne fait pas décroître f), l’algorithme considère que le modèle ne permet pas de prédire la variation réelle de f et ne convient donc pas. En diminuant ∆k on accroît l’importance de la partie linéaire de ψk qui coïncide avec l’approximation du premier ordre de f : ∇ψk(0) = ∇f(xk). On montre alors (Proposition 9.11) que si gk 6= 0 et si la résolution de (RCk) est suffisamment précise on finira par avoir ρk > ω1 (pour ∆k petit) et par passer à l’étape 3. On montre le même résultat (Proposition 9.14) lorsque gk = 0, à condition que l’on prenne Mk = ∇2f(xk) et que ∇2 f(xk) ait une valeur propre < 0. Lorsqu’il n’y a pas de bouclage à l’étape 2 de l’algorithme, on dit que l’itération k est un succès. Sinon, on dit que l’itération k est un échec. 

Préconditionnement des méthodes à régions de confiance

 Dans les problèmes d’optimisation, il est classique de préconditionner une méthode numérique, soit en faisant un changement de variables et en utilisant l’algorithme dans l’espace transformé, soit en utilisant un produit scalaire différent du produit scalaire euclidien. Sous certaines conditions les deux approches donnent le même préconditionnement

Conditions d’optimalité 

Le résultat suivant est fondamental pour l’étude des méthodes à régions de confiance. Il est aussi remarquable car il donne des conditions nécessaires et suffisantes d’optimalité pour un problème non convexe (on ne suppose pas que M est semi-définie positive), ce qui est assez rare. Cela vient de la structure particulière du problème : un critère quadratique (non nécessairement convexe) et une seule contrainte quadratique convexe (ksk 2 6 ∆2 ). On note ℓ : (s, λ) ∈ R n × R 7→ ℓ(s, λ) = g Ts + 1 2 s TMs + 1 2 λ(ksk 2 − ∆2 ), le lagrangien du problème (RC), dans lequel la contrainte à été rendue différentiable en remplaçant ksk 6 ∆ par la contrainte équivalente ksk 2 6 ∆2 . Selon le théorème 4.32, les conditions de KKT en un couple stationnaire (ˆs, λˆ) s’écrivent (on utilise la notation compacte (4.32)) (M + λIˆ )ˆs = −g et 0 6 λˆ ⊥ (∆ − ksˆk) > 0. (9.9) On rappelle que, lorsque A est une matrice symétrique, la notation A < 0 signifie que A est semi-définie positive.