Skalierungsinvarianz für Algorithmen für die Zeilensuche und den Vertrauensbereich

In Nocedal & Wrights Buch über numerische Optimierung gibt es in Abschnitt 2.2 (Seite 27) eine Aussage: "Im Allgemeinen ist es einfacher, die Skaleninvarianz für Liniensuchalgorithmen als für Vertrauensbereichsalgorithmen beizubehalten." Im selben Abschnitt wird über neue Variablen gesprochen, bei denen es sich um skalierte Versionen der ursprünglichen Variablen handelt, die sowohl bei der Zeilensuche als auch bei der Vertrauensregion hilfreich sein können. Ein anderer Ansatz ist die Vorkonditionierung. Bei Methoden für Vertrauensbereiche entspricht die Vorkonditionierung elliptischen Vertrauensbereichen und bietet somit eine Skaleninvarianz. Eine ähnliche Intuition ist jedoch für die Vorkonditionierung für die Zeilensuche nicht klar. Inwiefern eignet sich die Zeilensuche besser für die Skaleninvarianz? Gibt es einige praktische Überlegungen?

Außerdem habe ich eine Frage zur Vorkonditionierung für Trust-Region-Methoden. Reduziert ein guter Vorkonditionierer bei einem stark schlecht konditionierten Problem sowohl die Anzahl der äußeren Newton-Iterationen als auch der inneren CG-Iterationen oder nur die letzteren? Da der Vertrauensbereich im ursprünglichen Raum ellipsoid ist, sollte ein guter Vorkonditionierer zu einem Ellipsoid führen, das besser zur Landschaft passt. Ich bin der Meinung, dass dies die Anzahl der äußeren Newton-Iterationen verringern könnte, indem der Algorithmus gezwungen wird, bessere Richtungen einzuschlagen. Ist das richtig?

Ich nehme an, es könnte einen Unterschied geben, wie Liniensuche und Vertrauensbereichsmethoden mit Skalierung umgehen, aber ich sehe es in der Praxis wirklich nicht, solange wir uns der Skalierung bewusst sind. Und um klar zu sein, sprach das Buch von Nocedal und Wright über affine Skalierung. Die nichtlineare Skalierung ist etwas schwieriger zu quantifizieren.

Um zu sehen, warum, sagen wir, wir wollen minimieren , aber wir wollen die Variablen mit einer Art nicht singulärem, selbstadjunktem Operator A ∈ L ( X ) skalieren . Definieren Sie J : X → R als skalierte Zielfunktion. Dann ist 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}$ Der wahre Unterschied bei den Algorithmen besteht darin, was mit der SkalierungApassiert. In Newtons Methode lösen wir ∇2J(x)δx=-∇J(x) oder A∇2f(Ax)Aδx=-A∇f(Ax) Unter der Annahme, dass der Hessische nicht singulär ist, haben wir

$$\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)$$ Grundsätzlich wird die Skalierung aufgehoben und verschwindet, sodass die Richtung nicht beeinflusst wird. Deshalb sagen wir, dass Newtons Methode eine affine Skaleninvariante ist. $$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)$$ ungenau mit CG. Dies ist genau die Verwendung von Steihaug-Toint in der Einstellung für die Vertrauensregion (S. 171 in Nocedal und Wright) oder Newton-CG für die Zeilensuche (S. 169 in Nocedal und Wright). Sie arbeiten ziemlich ähnlich und kümmern sich nicht um affine Skalierung. Sie erfordern auch keine Speicherung des Hessischen, sondern nur Hessische Vektorprodukte. Wirklich, diese Algorithmen sollten die Arbeitspferde für die meisten Probleme sein und sie kümmern sich nicht um affine Skalierung.

Was die Voraussetzung für das Problem der Vertrauensregion betrifft, gibt es meines Erachtens keine einfache Möglichkeit, apriori zu sagen, ob Sie die Anzahl der gesamten Optimierungsiterationen verbessern wollen oder nicht. Letztendlich arbeiten Optimierungsmethoden in zwei Modi. Im ersten Modus sind wir zu weit vom Konvergenzradius der Newton-Methode entfernt. Daher globalisieren wir die Iterationen und erzwingen sie, um sicherzustellen, dass das Ziel sinkt. Vertrauensregion ist eine Möglichkeit. Die Zeilensuche ist eine andere. Im zweiten Modus befinden wir uns im Konvergenzradius der Newton-Methode, also versuchen wir, uns nicht damit herumzuschlagen und lassen die Newton-Methode ihren Job machen. Tatsächlich können wir dies an den Konvergenznachweisen von Dingen wie Methoden der Vertrauensregion erkennen. Schauen Sie sich zum Beispiel Satz 4.9 an (S.93 in Nocedal und Wright). Sehr explizit geben sie an, wie die Vertrauensregion inaktiv wird. Was ist in diesem Zusammenhang der Nutzen des Vorkonditionierers? Wenn wir uns im Konvergenzradius der Newton-Methode befinden, arbeiten wir sicherlich viel weniger und die Anzahl der CG-Iterationen nimmt ab. Was passiert, wenn wir uns außerhalb dieses Radius befinden? Es kommt irgendwie darauf an. Wenn wir den Full-Newton-Schritt berechnen, besteht der Vorteil darin, dass wir weniger Arbeit geleistet haben. Wenn wir unseren Schritt aufgrund des Abschneidens von abgeschnittenem CG vorzeitig abbrechen, liegt unsere Richtung im Krylov-Unterraum

$$\{-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))\}?$$

Dies bedeutet nicht, dass es keinen Wert hat, einen guten Vorkonditionierer zu definieren. Ich bin mir jedoch nicht sicher, wie jemand einen Vorkonditionierer definiert, der bei der Optimierung von Punkten außerhalb des Konvergenzradius der Newton-Methode hilft. Typischerweise entwerfen wir einen Vorkonditionierer, um die Eigenwerte der hessischen Näherung zu gruppieren, was ein greifbares, messbares Ziel ist.

tldr; In der Praxis gibt es für eine Zeilensuchmethode eine größere Vielfalt an Möglichkeiten, eine Iteration zu generieren als für eine Vertrauensbereichsmethode. Daher gibt es möglicherweise eine erstaunliche Möglichkeit, die affine Skalierung zu handhaben. Verwenden Sie jedoch einfach eine ungenaue Newton-Methode, und es spielt keine Rolle. Ein Vorkonditionierer beeinflusst die Leistung eines Algorithmus außerhalb des Konvergenzradius der Newtonschen Methode, aber es ist schwer zu quantifizieren, wie. Entwerfen Sie daher einfach einen Vorkonditionierer, um die Eigenwerte der Hessiasn-Näherung zu gruppieren.