invariance d'échelle pour les algorithmes de recherche de ligne et de région de confiance

Dans le livre de Nocedal & Wright sur l'optimisation numérique, il y a une déclaration dans la section 2.2 (page 27), "D'une manière générale, il est plus facile de conserver l'invariance d'échelle pour les algorithmes de recherche de ligne que pour les algorithmes de région de confiance". Dans cette même section, ils parlent d'avoir de nouvelles variables qui sont des versions à l'échelle des variables d'origine, ce qui peut aider à la fois la recherche de ligne et la région de confiance. Une autre approche est le préconditionnement. Pour les méthodes de région de confiance, le préconditionnement équivaut à avoir des régions de confiance elliptiques et, par conséquent, fournit une invariance d'échelle. Cependant, une intuition similaire n'est pas claire pour le préconditionnement de la recherche de ligne. De quelle manière la recherche de ligne est-elle mieux adaptée à l'invariance d'échelle? Y a-t-il des considérations pratiques?

J'ai également une question concernant le préconditionnement des méthodes de région de confiance. Pour un problème très mal conditionné, un bon préconditionneur réduira-t-il à la fois le nombre d'itérations externes de Newton et les itérations internes de CG ou seulement ces dernières? Étant donné que la région de confiance est ellipsoïdale dans l'espace d'origine, un bon préconditionneur devrait conduire à un ellipsoïde qui correspondra mieux au paysage. Je pense que cela pourrait réduire le nombre d'itérations externes de Newton en forçant l'algorithme à prendre de meilleures directions. Est-ce correct?

Je suppose qu'il pourrait y avoir une différence entre la façon dont les méthodes de recherche de ligne et de région de confiance gèrent la mise à l'échelle, mais je ne vois vraiment pas que cela se concrétise tant que nous sommes conscients de la mise à l'échelle. Et, pour être clair, le livre de Nocedal et Wright parlait de mise à l'échelle affine. La mise à l'échelle non linéaire est quelque peu plus délicate à quantifier.

Pour voir pourquoi, disons que nous voulons minimiser , mais nous voulons mettre à l'échelle les variables par une sorte d'opérateur non-singulier, auto-adjoint A ∈ L ( X ) . Définissez J : X → R comme fonction d'objectif mise à l'échelle. Alors, J ( x ) = f ( A x ) ∇ J ( x ) = A ∇ f ( A x ) ∇ 2 J ( x $f:X\rightarrow \mathbb{R}$$A\in\mathscr{L}(X)$$J:X\rightarrow \mathbb{R}$ La vraie différence dansalgorithmes est ce qui se passe à l'échelleA. Dans la méthode de Newton, nous résolvons ∇2J(x)δx=-∇J(x) ou A∇2f(Ax)Aδx=-A∇f(Ax) En supposant que la Hesse est non singulière, nous avons

$$\begin{align*} J(x) =& f(Ax)\\ \nabla J(x) =& A\nabla f(Ax)\\ \nabla^2 J(x) =& A\nabla^2 f(Ax) A \end{align*}$$ $A$ $$\nabla^2 J(x) \delta x = -\nabla J(x)$$ $$A\nabla^2 f(Ax) A \delta x = -A\nabla f(Ax)$$ Fondamentalement, la mise à l'échelle s'annule et disparaît, de sorte qu'elle n'affecte pas la direction. C'est pourquoi nous disons que la méthode de Newton est invariante à l'échelle affine. $$A \delta x = -\nabla^2 f(Ax)^{-1} \nabla f(Ax)$$

$$H \delta x = -\nabla J(x)$$ $H$ $$H \delta x = -A \nabla f(Ax)$$ $A$$H$

$\phi$

$$\delta x = \phi(-A\nabla f(Ax))$$ $\phi$$\phi$$\phi$$A$

$$\nabla^2 J(x) \delta x = -\nabla J(x)$$ en utilisant inexactement CG. Il s'agit précisément d'utiliser Steihaug-Toint dans le cadre de la région de confiance (p. 171 dans Nocedal et Wright) ou Newton-CG pour la recherche de ligne (p. 169 dans Nocedal et Wright). Ils fonctionnent assez près de la même chose et ne se soucient pas de la mise à l'échelle affine. Ils ne nécessitent pas non plus de stockage de la toile de jute, seuls les produits à vecteur de hesse sont requis. Vraiment, ces algorithmes devraient être les chevaux de bataille pour la plupart des problèmes et ils ne se soucient pas de la mise à l'échelle affine.

En ce qui concerne le préconditionneur pour le problème de la région de confiance, je ne pense pas qu'il existe un moyen facile de dire aux apriori si vous allez améliorer le nombre d'itérations d'optimisation globales ou non. En réalité, au bout du compte, les méthodes d'optimisation fonctionnent selon deux modes. Dans le mode un, nous sommes trop loin du rayon de convergence de la méthode de Newton, donc nous globalisons et forçons simplement les itérations pour assurer que l'objectif descend. La région de confiance est un moyen. La recherche en ligne en est un autre. Dans le mode deux, nous sommes dans le rayon de convergence de la méthode de Newton, nous essayons donc de ne pas jouer avec lui et de laisser la méthode de Newton faire son travail. En fait, nous pouvons le voir dans les preuves de convergence de choses comme les méthodes de région de confiance. Par exemple, regardez le théorème 4.9 (p.93 dans Nocedal et Wright). Très explicitement, ils indiquent comment la région de confiance devient inactive. Dans ce contexte, quelle est l'utilité du préconditionneur? Certes, lorsque nous sommes dans le rayon de convergence de la méthode de Newton, nous faisons beaucoup moins de travail et le nombre d'itérations CG diminue. Que se passe-t-il lorsque nous sommes en dehors de ce rayon? Cela dépend en quelque sorte. Si nous calculons le pas de Newton complet, alors l'avantage est que nous avons fait moins de travail. Si nous interrompons notre étape tôt en raison de la troncature du CG tronqué, alors notre direction sera dans le sous-espace Krylov

$$\{-P\nabla J(x),-(PH)(P\nabla J(x)),\dots,-(PH)^k(P\nabla J(x))\}$$ $P$$H$ $$\{-\nabla J(x),-(H)(\nabla J(x)),\dots,-(H)^k(\nabla J(x))\}?$$

Cela ne signifie pas qu'il n'est pas utile de définir un bon préconditionneur. Cependant, je ne sais pas comment quelqu'un définit un préconditionneur pour aider à l'optimisation des points éloignés du rayon de convergence de la méthode de Newton. En règle générale, nous concevons un préconditionneur pour regrouper les valeurs propres de l'approximation de Hesse, qui est un objectif tangible et mesurable.

tldr; En pratique, il existe une plus grande variété de façons pour une méthode de recherche de ligne de générer une itération qu'une méthode de région de confiance, il est donc possible qu'il existe une façon étonnante de gérer la mise à l'échelle affine. Cependant, utilisez simplement une méthode Newton inexacte et cela n'a pas d'importance. Un préconditionneur affecte les performances d'un algorithme loin du rayon de convergence de la méthode de Newton, mais il est difficile de quantifier comment, il suffit donc de concevoir un préconditionneur pour regrouper les valeurs propres de l'approximation de Hessiasn.