Bedingungslose Optimierung. Konjugierte Gradientenmethode
Die Newton-Methode und die im vorherigen Absatz besprochenen Quasi-Newton-Methoden sind als Mittel zur Lösung uneingeschränkter Minimierungsprobleme sehr effektiv. Allerdings stellen sie recht hohe Anforderungen an die Menge des verwendeten Computerspeichers. Dies liegt daran, dass die Auswahl einer Suchrichtung Lösungssysteme erfordert lineare Gleichungen, sowie die aufkommende Notwendigkeit, Matrizen des Typs zu speichern. Daher kann die Verwendung dieser Methoden für große Matrizen unmöglich sein. Methoden mit konjugierter Richtung weisen diesen Nachteil weitgehend nicht auf.
1. Das Konzept der konjugierten Richtungsmethoden.
Betrachten Sie das Problem der Minimierung der quadratischen Funktion
mit einer symmetrischen positiv definiten Matrix A. Denken Sie daran, dass ihre Lösung einen Schritt der Newton-Methode erfordert und nicht mehr als Schritte der Quasi-Newton-Methode es Ihnen ermöglichen, den Minimalpunkt der Funktion (10.33) in nicht mehr zu finden als Schritte. Dies kann durch eine spezielle Auswahl der Suchrichtungen erreicht werden.
Wir werden sagen, dass Vektoren ungleich Null untereinander konjugiert sind (in Bezug auf Matrix A), wenn überhaupt
Mit der Methode der konjugierten Richtungen zur Minimierung der quadratischen Funktion (10.33) meinen wir die Methode
in denen die Richtungen zueinander konjugiert sind, und die Schritte
erhält man als Lösung eindimensionaler Minimierungsprobleme:
Satz 10.4. Mit der Methode der konjugierten Richtungen können Sie den Minimalpunkt der quadratischen Funktion (10 33) in nur Schritten ermitteln.
Die Methoden für konjugierte Richtungen unterscheiden sich voneinander in der Art und Weise, wie konjugierte Richtungen konstruiert werden. Die bekannteste davon ist die konjugierte Gradientenmethode.
2. Konjugierte Gradientenmethode.
Bei dieser Methode bilden Anweisungen eine Regel
Da der erste Schritt dieser Methode mit dem Schritt der Methode des steilsten Abstiegs zusammenfällt. Es kann gezeigt werden (das werden wir nicht tun), dass die Richtungen (10.34) tatsächlich stimmen
konjugiert bezüglich der Matrix A. Darüber hinaus erweisen sich die Gradienten als zueinander orthogonal.
Beispiel 10.5. Lassen Sie uns die Methode des konjugierten Gradienten verwenden, um die quadratische Funktion zu minimieren – aus Beispiel 10.1. Schreiben wir es in der Form wo
Nehmen wir die erste Näherung
Der 1. Schritt der Methode fällt mit dem ersten Schritt der Methode des steilsten Abstiegs zusammen. Daher (siehe Beispiel 10.1)
2. Schritt. Rechnen wir
Denn die Lösung fand sich in zwei Schritten.
3. Konjugierte Gradientenmethode zur Minimierung nichtquadratischer Funktionen.
Damit diese Methode zur Minimierung einer beliebigen glatten Funktion angewendet werden kann, wird die Formel (10.35) zur Berechnung des Koeffizienten in die Form umgewandelt
oder zur Aussicht
Der Vorteil der Formeln (10 36), (10.37) besteht darin, dass sie die Matrix A nicht explizit enthalten.
Die Funktion wird durch die konjugierte Gradientenmethode gemäß den Formeln minimiert
Die Koeffizienten werden mit einer der Formeln (10.36), (10.37) berechnet.
Der iterative Prozess endet hier nicht mehr nach einer endlichen Anzahl von Schritten, und die Richtungen sind im Allgemeinen nicht bezüglich einer Matrix konjugiert.
Eindimensionale Minimierungsprobleme (10.40) müssen numerisch gelöst werden. Wir stellen auch fest, dass der Koeffizient bei der konjugierten Gradientenmethode häufig nicht mit den Formeln (10.36), (10.37) berechnet, sondern angenommen wird gleich Null. In diesem Fall wird der nächste Schritt tatsächlich mit der Methode des steilsten Abstiegs durchgeführt. Durch diese „Aktualisierung“ der Methode können wir den Einfluss von Rechenfehlern reduzieren.
Für eine stark konvexe glatte Funktion weist die konjugierte Gradientenmethode unter einigen zusätzlichen Bedingungen eine hohe superlineare Konvergenzrate auf. Gleichzeitig ist die Arbeitsintensität gering und vergleichbar mit der Komplexität der Methode des steilsten Abstiegs. Wie die Rechenpraxis zeigt, ist es den Quasi-Newton-Methoden in der Effizienz etwas unterlegen, stellt aber deutlich geringere Anforderungen an den verwendeten Computerspeicher. Für den Fall, dass das Problem der Minimierung einer Funktion mit sehr eine große Anzahl Variablen scheint die konjugierte Gradientenmethode die einzig geeignete universelle Methode zu sein.
Gradientenmethoden basieren nur auf der Gradientenberechnung R(X), sind Methoden erster Ordnung, da sie auf dem Schrittintervall die nichtlineare Funktion ersetzen R(X) linear.
Methoden zweiter Ordnung, die nicht nur die erste, sondern auch die zweite Ableitung von verwenden R(X) am aktuellen Punkt. Diese Methoden haben jedoch ihre eigenen hartnäckigen Probleme – die Berechnung zweiter Ableitungen an einem Punkt, und darüber hinaus kann die Matrix der zweiten Ableitungen, weit vom Optimum entfernt, schlecht konditioniert werden.
Die konjugierte Gradientenmethode ist ein Versuch, die Vorteile von Methoden erster und zweiter Ordnung zu kombinieren und gleichzeitig deren Nachteile zu beseitigen. Im Anfangsstadium (fern vom Optimum) verhält sich die Methode wie eine Methode erster Ordnung, in der Nähe des Optimums nähert sie sich Methoden zweiter Ordnung an.
Der erste Schritt ähnelt dem ersten Schritt der Methode des steilsten Abstiegs. Der zweite und der nächste Schritt werden jeweils in der Richtung ausgewählt, die als lineare Kombination der Gradientenvektoren an einem bestimmten Punkt und der vorherigen Richtung gebildet wird.
Der Methodenalgorithmus kann wie folgt geschrieben werden (in Vektorform):
x 1 = x 0 – h grad R(x 0),
x i+1 = x i – h .
Der Wert α kann näherungsweise aus dem Ausdruck ermittelt werden
Der Algorithmus funktioniert wie folgt. Vom Ausgangspunkt X 0 Suche min R(X) in Richtung des Gradienten (unter Verwendung der Methode des steilsten Abstiegs), dann wird ausgehend vom gefundenen Punkt und weiter die Suchrichtung min durch den zweiten Ausdruck bestimmt. Die Suche nach dem Minimum in der Richtung kann auf beliebige Weise durchgeführt werden: Sie können die sequentielle Scanmethode verwenden, ohne den Scanschritt beim Passieren des Minimums anzupassen, sodass die Genauigkeit beim Erreichen des Minimums in der Richtung von der Schrittgröße abhängt H.
Für eine quadratische Funktion R(X) Eine Lösung finden Sie in P Schritte (P– Dimension des Problems). Bei anderen Funktionen ist die Suche langsamer und erreicht in manchen Fällen aufgrund des starken Einflusses von Rechenfehlern möglicherweise überhaupt nicht das Optimum.
Eine der möglichen Trajektorien für die Suche nach dem Minimum einer zweidimensionalen Funktion mithilfe der konjugierten Gradientenmethode ist in Abb. dargestellt. 1.
Algorithmus der konjugierten Gradientenmethode zum Finden des Minimums.
Erste Stufe. Ausführung der Gradientenmethode.
Legen Sie die anfängliche Näherung fest X 1 0 ,X 20 . Bestimmen des Werts des Kriteriums R(X 1 0 ,X 20). Setzen Sie k = 0 und fahren Sie mit Schritt 1 der Anfangsphase fort.
Schritt 1. 
Und 
.
Schritt 2. Wenn das Gradientenmodul 
Schritt 3.
X k+1 = X k – H grad R(X k)).
Schritt 4. R(X 1 k +1 , X 2 k +1). Wenn R(X 1 k +1 , X 2 km +1)< R(X 1k, X 2 k), dann setze k = k+1 und gehe zu Schritt 3. Wenn R(X 1 k +1 , X 2 k +1) ≥ R(X 1k, X 2 km), dann geht es zur Hauptbühne.
Hauptbühne.
Schritt 1. Berechnen Sie R(x 1 k + g, x 2 k), R(x 1 k – g, x 2 k), R(x 1 k , x 2 k + g), R(x 1 k , x 2 k) . Berechnen Sie gemäß dem Algorithmus aus einer zentralen oder gepaarten Stichprobe den Wert partieller Ableitungen 
Und 
. Berechnen Sie den Gradientenmodulwert 
.
Schritt 2. Wenn das Gradientenmodul 
, stoppen Sie dann die Berechnung und betrachten Sie den Punkt (x 1 k, x 2 k) als den optimalen Punkt. Andernfalls fahren Sie mit Schritt 3 fort.
Schritt 3. Berechnen Sie den Koeffizienten α nach der Formel:
Schritt 4. Führen Sie den Arbeitsschritt durch, indem Sie mit der Formel rechnen
x k+1 = x k – h .
Schritt 5. Bestimmen Sie den Kriteriumswert R(X 1 k +1 , X 2 k +1). Setzen Sie k = k+1 und fahren Sie mit Schritt 1 fort.
Beispiel.
Betrachten Sie zum Vergleich die Lösung des vorherigen Beispiels. Den ersten Schritt machen wir mit der Methode des steilsten Abstiegs (Tabelle 5).
Tabelle 5
Der beste Punkt wurde gefunden. Wir berechnen an dieser Stelle die Ableitungen: DR/ dx 1 = –2.908; DR/ dx 2 =1.600; Wir berechnen den Koeffizienten α, der den Einfluss der Steigung am vorherigen Punkt berücksichtigt: α = 3,31920 ∙ 3,3192/8,3104 2 =0,160. Wir machen einen Arbeitsschritt entsprechend dem Algorithmus der Methode, die wir erhalten X 1 = 0,502, X 2 = 1.368. Dann wird alles auf die gleiche Weise wiederholt. Unten in der Tabelle. 6 zeigt die aktuellen Suchkoordinaten für die nächsten Schritte.
Tabelle 6
In den vorherigen Unterabschnitten wurden die Methoden von Cauchy und Newton besprochen. Es wurde festgestellt, dass die Cauchy-Methode bei der Suche in erheblichen Entfernungen vom Minimalpunkt effektiv ist X* und „funktioniert“ in der Nähe dieses Punktes schlecht, während Newtons Methode bei der Suche nicht sehr zuverlässig ist X* Aus der Ferne erweist es sich jedoch in Fällen, in denen es sehr effektiv ist X(k) liegt nahe dem Minimalpunkt. In diesem und den folgenden Unterabschnitten werden Methoden besprochen, die die positiven Eigenschaften der Cauchy- und Newton-Methoden aufweisen und auf der Berechnung der Werte nur der ersten Ableitungen basieren. Somit sind diese Methoden einerseits sehr zuverlässig bei der Suche X* von einem entfernten Standort aus X* und andererseits in der Nähe des Minimalpunktes schnell konvergieren.
Methoden, die es ermöglichen, näherungsweise Lösungen für Probleme mit quadratischen Zielfunktionen zu erhalten N Schritte, vorbehaltlich der Verwendung von nicht-dezimalen Brüchen, werden wir aufrufen quadratisch konvergent. Unter solchen Methoden können wir eine Klasse von Algorithmen unterscheiden, die auf der Konstruktion basieren konjugierte Richtungen. Oben wurde die Konjugationsbedingung für das Richtungssystem formuliert S(k) , k = 1, 2, 3,…, R ≤ N, und symmetrische Matrix MIT Befehl N N. Es wurde auch ein Zusammenhang zwischen der Konstruktion der angegebenen Richtungen und der Transformation einer beliebigen quadratischen Funktion in die Form der Summe hergestellt
1) Probleme dieser Art treten beispielsweise auf in Regressionsanalyse - Notiz Übersetzung
Quadrate; Es wurde der Schluss gezogen, dass jeweils eine sequentielle Suche erforderlich ist N Wegbeschreibung zur Immobilie MIT-Konjugation ermöglicht es Ihnen, den Minimalpunkt der quadratischen Funktion zu finden N Variablen. Es wird das Verfahren zur Bestimmung eines Systems konjugierter Richtungen betrachtet, bei dem nur die Werte der Zielfunktion verwendet werden. Im Folgenden wird die quadratische Näherung verwendet, um konjugierte Richtungen zu erhalten f(x) und die Werte der Gradientenkomponenten. Darüber hinaus werden wir verlangen, dass die betrachteten Methoden sicherstellen, dass die Zielfunktion beim Übergang von Iteration zu Iteration abnimmt.
Gegeben seien zwei beliebige Divergenzpunkte im Raum der Regelvariablen X(0) und X(1) . Der Gradient der quadratischen Funktion ist
f(x) = q(x) =Cx + b = g(x) (3.60)
Um das Schreiben der Formel zu vereinfachen, wird hier die Notation g(x) eingeführt. Auf diese Weise,
G(X (0)) = CX (0) + B,
G(X (1)) = CX (1) + B.
Schreiben wir die Änderung des Gradienten auf, wenn wir uns von einem Punkt aus bewegen X(0) zu zeigen X (1) :
g(x) = G(X (1)) -G(X (0)) = C(X (1) - X (0)), (3.61)
g(x) = C X
Gleichheit (3.61) drückt eine Eigenschaft quadratischer Funktionen aus, die im Folgenden verwendet wird.
Im Jahr 1952 schlugen Estens und Stiefel einen effizienten iterativen Algorithmus zur Lösung linearer Gleichungssysteme vor, der im Wesentlichen die Methode des konjugierten Gradienten war. Sie betrachteten die linken Seiten linearer Gleichungen als Komponenten des Gradienten einer quadratischen Funktion und lösten das Problem der Minimierung dieser Funktion. Später begründeten Fletcher und Reeves die quadratische Konvergenz der Methode und verallgemeinerten sie auf den Fall nichtquadratischer Funktionen. Fried und Metzler demonstrierten (allerdings mit einigen Ungenauigkeiten) die Möglichkeit, die Methode zur Lösung einzusetzen lineare Systeme mit einer dünn besetzten Koeffizientenmatrix. (Siehe Anhang A für die Definition einer Sparse-Matrix.) Sie betonten die einfache Implementierung der Methode im Vergleich zu anderen, allgemeineren Algorithmen, was aus der Perspektive unserer Präsentation ein besonders wichtiges Merkmal ist.
Wir betrachten die Methode unter der Annahme, dass die Zielfunktion quadratisch ist:
f(x) = q(x) = a + b T x + ½ x TCX,
Iterationen werden nach Formel (3.42) durchgeführt, d.h.
x = x +α s(x).
Die Suchrichtungen bei jeder Iteration werden mithilfe der folgenden Formeln bestimmt:
S(k) = -G(k) + (3.62)
S (0) = -G (0) , (3.63)
Wo G(k) = F(X). Da nach der Bestimmung des Richtungssystems eine sequentielle Suche entlang jeder Richtung durchgeführt wird, ist es sinnvoll, sich daran zu erinnern, dass die Bedingung normalerweise als Kriterium für die Beendigung einer eindimensionalen Suche verwendet wird
F (X)T s(k) = 0 (3,64)
Werte ,ich= 1, 2, 3,...,k - 1, werden so gewählt, dass die Richtung S(k) war MIT-verbunden mit allen zuvor erstellten Suchrichtungen. Betrachten wir die erste Richtung
S (1) = –G(1) + γ (0) S (0) = –G(1) –γ (0) g (0)
und legen Sie die Bedingung seiner Konjugation mit fest S (0)
S (1)T C s(0) = 0,
Wo TC s(0) = 0.
Bei der ersten Iteration
S (0) = ;
somit,
TC = 0
Mit der Eigenschaft quadratischer Funktionen (3.61) erhalten wir
T G = 0, (3.65)
γ (0) = – ( g T g (1))/( g T g(0)). (3.66)
Aus Gleichung (3.65) folgt das
g (1) T g (1) + γ (0) g (0) T g (1) – g (1) T g(0) – γ (0) g (0) T g(0) = 0.
Bei geeigneter Wahl von α (0) und unter Berücksichtigung der Formel (3.64) gilt
g (1) T g(0) = 0.
Auf diese Weise,
S (2) = –G(2) + γ (0) S(0) + γ (1) S (1) .
und wähle γ (0) γ (1) so, dass die Bedingungen erfüllt sind
s(2) TC s(0) = 0 und s(2) C s(1) = 0,
d.h. Bedingungen MIT-Konjugation der Richtung s (2) mit den Richtungen s (0) und s (1). Mithilfe der Formeln (3.61) und (3.64) kann gezeigt werden (dies wird dem Leser als Übung überlassen), dass hier γ (0) = 0 und im allgemeinen Fall γ ( ich) = 0, ich = 0, 1, 2,...,k-2, um jeden Wert k. Daraus folgt, dass die allgemeine Formel für Suchanweisungen in der von Fletcher und Reeves vorgeschlagenen Form geschrieben werden kann:
S ( k) = –G (k) + s (3,68)
Wenn f(x)- quadratische Funktion, um den Mindestpunkt zu finden, der bestimmt werden muss N-1 solche Anweisungen und ausführen N sucht entlang einer geraden Linie (ohne Rundungsfehler). Wenn die Funktion f(x) nicht quadratisch ist, nimmt die Anzahl der Richtungen und entsprechenden Suchen zu.
Einige Forscher schlagen basierend auf der Erfahrung bei der Durchführung von Computerexperimenten vor, dass nach der Implementierung jeder Reihe von N oder N+ 1 Schritte kehren zur ursprünglichen Iteration des Algorithmus zurück und setzen s(x) = -g(x). Dieser Vorschlag bleibt Gegenstand der Untersuchung, da die Minimierung von Funktionen allgemeiner Form in einigen Fällen eine Verlangsamung der Konvergenz mit sich bringt. Andererseits erhöhen zyklische Übergänge zur anfänglichen Iteration die Zuverlässigkeit des Algorithmus, da die Wahrscheinlichkeit, linear abhängige Richtungen zu konstruieren, abnimmt. Wenn sich herausstellt, dass die resultierende Richtung eine lineare Kombination einer oder mehrerer zuvor erhaltener Richtungen ist, führt die Methode möglicherweise nicht zu einer Lösung, da im entsprechenden Unterraum gesucht wird R N wurde bereits durchgeführt. Es ist jedoch zu beachten, dass solche Situationen in der Praxis eher selten sind. Die Methode erweist sich als sehr effektiv bei der Lösung praktischer Probleme; sie zeichnet sich durch die Einfachheit eines Ein-Parameter-Rechenschemas und einen geringen Computerspeicherbedarf für die Suche aus. Aufgrund der relativ geringen Anforderungen an den Computerspeicher sind die Fletcher-Reeves-Methode (FR) und ihre Modifikationen besonders nützlich für die Lösung umfangreicher Probleme.
Beispiel 3.9. Fletcher-Reeves-Methode
Finden Sie den Minimalpunkt einer Funktion
f(x) = 4x+ 3X - 4x x + x
Wenn x = T.
Schritt 1. f(x) =T,
S (0) = – F(X (0)) = – T.
Schritt 2. Suchen Sie entlang einer geraden Linie:
x = x –α F(X (0)) → α = ⅛,
x =T - ⅛ T = [– ⅛, 0]T
Schritt 3. k = 1.
S (1) = – T -[¼, 1] T = [– ¼, ½] T.
Schritt 4. Suchen Sie entlang einer geraden Linie:
x = x+ α S(1) → α = ¼,
x =[– ⅛, 0]T - ¼ [¼, ½] T = [– , ]T,
F(X (2)) = T.
Auf diese Weise, x = x*. Die Lösung wurde als Ergebnis zweier eindimensionaler Suchen erhalten, da die Zielfunktion quadratisch ist und keine Rundungsfehler auftreten.
Mil und Cantrell verallgemeinerten den Ansatz von Fletcher und Reeves, indem sie die Formel vorschlugen
x = x +α {– F(X (k)) + γ S(X)} (3.69)
wobei α und γ - Parameter, deren Werte bei jeder Iteration bestimmt werden. Diese Methode, bekannt als Gradientenmethode mit Speicher,ist hinsichtlich der Anzahl der zur Lösung des Problems erforderlichen Iterationen sehr effizient, erfordert jedoch mehr Berechnungen von Funktionswerten und Gradientenkomponenten als die Fletcher-Reeves-Methode. Daher ist der Mil- und Cantrell-Algorithmus nur in Fällen nützlich, in denen die Schätzung der Werte der Zielfunktion und der Gradientenkomponenten keine Schwierigkeiten bereitet.
Erinnern wir uns daran, dass die Betrachtung der Fletcher-Reeves-Methode unter der Annahme durchgeführt wurde, dass die Zielfunktion quadratisch war und es bei der Suche entlang der Linie keine Rundungsfehler gab. Bei der Implementierung mehrerer Methoden werden jedoch konjugierte Richtungen bestimmt, ohne eine dieser Annahmen (oder sogar beide Annahmen) zu berücksichtigen. Unter diesen Methoden verdient die von Polzk und Ribière im Jahr 1969 entwickelte wahrscheinlich die größte Aufmerksamkeit. Die Methode basiert auf einem exakten Suchverfahren entlang einer Linie und auf einer allgemeineren Annahme der Approximation der Zielfunktion. Dabei
γ
= 
, (3.70)
während zuvor,
G(X)= g(X) -G(X). (3.71)
Wenn α - ein Parameter, dessen Wert als Ergebnis einer Suche entlang einer Geraden bestimmt wird, und γ ist ein Parameter, dessen Wert mit der Formel (3.70) berechnet wird Polak-Ribiera-Methode mit konjugiertem Gradienten wird mithilfe der folgenden Beziehungen implementiert:
x = x +α S(X),
S(X) = – F (X) + γ S(X). (3.72)
Es ist leicht zu erkennen, dass der einzige Unterschied zwischen der Polak-Ribier- und der Fletcher-Reeves-Methode in den Methoden zur Auswahl des Parameters γ liegt.
Es sind auch andere ähnliche Methoden bekannt, die ebenfalls auf der Durchführung exakter Berechnungen während einer eindimensionalen Suche und auf einer allgemeineren (als quadratischen) Näherung der Zielfunktion basieren (siehe z. B.). Crowder und Wolf und dann Powell bewiesen 1972, dass konjugierte Gradientenmethoden eine lineare Konvergenzrate aufweisen, wenn keine periodische Rückkehr zur ursprünglichen Iteration erfolgt. Diese Rückgaben werden nach einem speziellen Verfahren durchgeführt, das den Prozess der Konstruktion von Suchrichtungsvektoren unterbricht und dann die Berechnungen analog zur Konstruktion fortsetzt S(X(0)). Oben wurde darauf hingewiesen, dass das Vorhandensein einer Prozedur zur Rückkehr zur ursprünglichen Iteration aus mehreren Gründen die Stabilität des Algorithmus erhöht, da dadurch eine lineare Konstruktion vermieden werden kann abhängige Vektoren Suchanweisungen. Powell hat bewiesen, dass die Polak-Ribière-Methode auch durch eine lineare Konvergenzrate gekennzeichnet ist, wenn keine Rückkehr zur ursprünglichen Iteration erfolgt, sie hat jedoch bei der Lösung von Problemen mit allgemeinen Zielfunktionen zweifellos einen Vorteil gegenüber der Fletcher-Reeves-Methode und ist weniger empfindlich zu Rundungsfehlern bei der Durchführung eindimensionaler Suchen.
Die Entwicklung wirksamer Verfahren und Methoden, die eine Rückkehr zur ursprünglichen Iteration gewährleisten und gleichzeitig eine geringe Empfindlichkeit gegenüber Rundungsfehlern aufweisen, ist weiterhin Gegenstand aktiver Forschung. Beal schlug eine Methode für konjugierte Gradienten vor, die dem Standardverfahren von Fletcher-Reeves ähnelt, verwendet aber gleichzeitig nicht die Richtung entlang des Gradienten, wenn zur ursprünglichen Iteration zurückgekehrt wird. Er zeigte, wie es auf der Grundlage der Analyse der Richtung, die kurz vor der Rückkehr zur ersten Iteration erhalten wurde, möglich ist, die Menge der erforderlichen Berechnungen bei der Lösung von Problemen zu reduzieren, die mehrere Rückgaben erfordern. Powell untersuchte Beals Strategie sowie andere Strategien zur Rückkehr zur ursprünglichen Iteration und schlug die Verwendung eines Verfahrens vor, bei dem entweder nach jeder Serie von zurückgekehrt wird N Schritte oder wenn die Ungleichung erfüllt ist
| G(X)Tg(X) | ≥ 0.2 ||G(X)|| . (3.73)
Er zeigte, dass Beales Strategie, ergänzt durch Bedingung (3.73), sowohl zusammen mit der Fletcher-Reeves-Formel als auch mit der Polak-Ribière-Formel erfolgreich angewendet werden kann, und führte eine Reihe von Computerexperimenten durch, deren Ergebnisse die Überlegenheit der Formel bestätigen Polak-Ribière-Methode (mit Rückgabe) . Shannault untersuchte die Auswirkung von Rundungsfehlern bei Zeilensuchen und verschiedenen Backtracking-Strategien auf die Leistung konjugierter Gradientenmethoden. Er zeigte, dass die Strategie von Beale (unter Verwendung der entsprechenden Zwei-Parameter-Formel), ergänzt durch die Backtracking-Bedingung von Powell, zu einer erheblichen Verringerung der erforderlichen Genauigkeit einer eindimensionalen Suche und damit zu einer erheblichen Steigerung der Effizienz der vollständigen Suche führt Rechenschema der konjugierten Gradientenmethode. Shannault präsentierte auch numerische Ergebnisse, die die Überlegenheit der Polak-Ribière-Methode unter Verwendung von Backtracking- und Rundungsverfahren bei der Suche entlang einer Linie belegen. Die Arbeit demonstriert die führende Rolle konjugierter Gradientenmethoden bei der Lösung hochdimensionaler nichtlinearer Programmierprobleme.
Quasi-Newton-Methoden
Diese Methoden ähneln den im Unterabschnitt besprochenen Methoden. 3.3.5, da sie auch auf den Eigenschaften quadratischer Funktionen basieren. Gemäß den oben beschriebenen Methoden erfolgt die Suche nach einer Lösung entlang eines Systems konjugierter Richtungen, während Quasi-Newton-Methoden die positiven Eigenschaften der Newton-Methode aufweisen, jedoch nur die ersten Ableitungen verwenden. Bei allen Methoden dieser Klasse erfolgt die Konstruktion von Suchrichtungsvektoren nach Formel (3.42), in der S(X(k)) wird geschrieben als
S(X) = –A F (X), (3.74)
Wo A- Bestellmatrix N N, Was heisst Metriken. Suchmethoden entlang der durch diese Formel bestimmten Richtungen werden Methoden genannt variable Metrik, da sich Matrix A bei jeder Iteration ändert. Genauer gesagt handelt es sich um die Methode der variablen Metrik quasi-Newtonsch Methode, wenn dementsprechend die Bewegung des Prüfpunkts die folgende Bedingung erfüllt:
x =C G. (3.75)
Leider gibt es in der Fachliteratur keine einheitlichen und konkreten Empfehlungen für die Verwendung der oben genannten Begriffe; wir betrachten sie als austauschbar, da sie gleichermaßen wichtige Informationen über die Besonderheiten der Entwicklung und Umsetzung der jeweiligen Methoden enthalten.
Um die Matrix invers zur Hesse-Matrix anzunähern, verwenden wir die folgende Wiederholungsbeziehung:
A = A+ A(3.76)
Wo A- Korrekturmatrix. Matrix A wird in den Formeln (3.74) und (3.42) verwendet. Die Aufgabe besteht darin, eine Matrix zu konstruieren A damit die Reihenfolge A (0) , A (1) , A (2) ,...,A(k +1) ergab eine Annäherung an N -1 = F (X*) -1 ; um eine Lösung zu erhalten X* eine zusätzliche Suche entlang einer Geraden ist erforderlich, wenn f(x)- quadratische Funktion. Wie oben bereits mehrfach betont wurde, gibt es bestimmte Gründe zu der Annahme, dass eine Methode, die das Auffinden der Optima quadratischer Funktionen gewährleistet, zum Erfolg bei der Lösung von Problemen mit nichtlinearen Zielfunktionen allgemeiner Form führen kann.
Kehren wir zur wichtigen Eigenschaft quadratischer Funktionen (3.75) zurück und nehmen an, dass die Matrix MIT-1 wird durch die Formel angenähert
MIT-1 = β A, (3.77)
wobei p eine skalare Größe ist. Die am meisten bevorzugte Näherung ist eine, die (3.75) erfüllt, d. h.
X= A G. (3.78)
Es ist jedoch klar, dass es unmöglich ist, eine solche Näherung zu konstruieren, da um sie zu finden G, müssen Sie die Matrix kennen A. Dabei werden folgende Notationen verwendet:
X= X– X, (3.79)
G= G(X) – G(X). (3.80)
Andererseits kann man verlangen, dass die neue Näherung die Formel (3.75) erfüllt:
X= β A G. (3.81)
Wenn wir den Ausdruck (3.76) in (3.81) einsetzen, erhalten wir
A G= X– A G. (3.82)
Mithilfe der direkten Substitution können Sie die Matrix überprüfen
A = – (3.83)
ist die Lösung dieser Gleichung. Hier bei Und z- beliebige Vektoren, d.h. Formel (3.83) definiert eine bestimmte Lösungsfamilie. Wenn Sie sagen
j = X Und z =A G, (3.84)
dann erhalten wir eine Formel, die das Bekannte und weit verbreitete umsetzt Davidons Methode- Fletcher- Powell(DFP):
A= A + 
– 
. (3.85)
Es kann gezeigt werden, dass diese wiederkehrende Formel die Eigenschaften der Symmetrie und der positiven Bestimmtheit von Matrizen bewahrt. Deshalb wenn A(0) ist eine symmetrische positiv definite Matrix, dann die Matrizen A (1) , A(2) , ... erweisen sich auch dann als symmetrisch und positiv definit, wenn keine Rundungsfehler vorliegen; Normalerweise ist die Auswahl bequem A (0) = ICH.
Erste Variante f(x) gleich
f(x) = F (X) X. (3.86)
Mit den Formeln (3.42) und (3.74) erhalten wir
f(x) = F (X) α A F (X), (3.87)
f(x) = – α F (X) A F (X), (3.88)
und Ungleichheit F (x(k+1)) < F(x k) ist für alle Werte von α > 0 erfüllt, wenn A ist eine positiv definite Matrix. Somit stellt der Algorithmus sicher, dass die Zielfunktion beim Übergang von Iteration zu Iteration abnimmt. Die Davidon-Fletcher-Powell-Methode ist seit einigen Jahren die am weitesten verbreitete Gradientenmethode. Es ist stabil und wird erfolgreich zur Lösung verschiedenster in der Praxis auftretender Probleme eingesetzt. Der Hauptnachteil derartiger Methoden besteht in der Notwendigkeit, eine Matrix im Computerspeicher zu speichern A Befehl N N.
Einführung
Die konjugierte Gradientenmethode ist eine iterative Methode für bedingungslose Optimierung im mehrdimensionalen Raum. Der Hauptvorteil der Methode besteht darin, dass sie ein quadratisches Optimierungsproblem in endlich vielen Schritten löst. Daher wird zunächst die konjugierte Gradientenmethode zur Optimierung des quadratischen Funktionals beschrieben, iterative Formeln abgeleitet und Schätzungen der Konvergenzrate angegeben. Anschließend wird gezeigt, wie die adjungierte Methode verallgemeinert wird, um ein beliebiges Funktional zu optimieren, verschiedene Varianten der Methode werden betrachtet und die Konvergenz wird diskutiert.
Darstellung des Optimierungsproblems
Es sei eine Menge gegeben und auf dieser Menge definiert Zielfunktion (Zielfunktion). Das Optimierungsproblem besteht darin, die genaue Ober- oder Untergrenze der Menge zu finden Zielfunktion.
Die Menge der Punkte, an denen die untere Grenze der Zielfunktion erreicht wird, wird mit bezeichnet.
Wenn , dann heißt das Optimierungsproblem bedingungslos (uneingeschränkt). Wenn , dann heißt das Optimierungsproblem bedingt (eingeschränkt).
Konjugierte Gradientenmethode für quadratische Funktionen
Erklärung der Methode
Betrachten Sie das folgende Optimierungsproblem:
Hier ist eine symmetrische positiv definite Matrix der Größe. Dieses Optimierungsproblem heißt quadratisch. Beachte das . Die Bedingung für das Extremum einer Funktion entspricht dem System. Die Funktion erreicht ihre untere Grenze an einem einzelnen durch die Gleichung definierten Punkt. Somit reduziert sich dieses Optimierungsproblem auf die Lösung eines linearen Gleichungssystems
Die Idee der konjugierten Gradientenmethode ist wie folgt:
Sei eine Basis in . Dann wird für jeden Punkt der Vektor in die Basis erweitert, sodass er in der Form dargestellt werden kann
Jede weitere Näherung wird nach folgender Formel berechnet:
Definition. Die beiden Vektoren werden aufgerufen konjugieren bezüglich einer symmetrischen Matrix B, wenn
Beschreiben wir die Methode zur Konstruktion einer Basis in der konjugierten Gradientenmethode. Wir wählen einen beliebigen Vektor als anfängliche Näherung. Bei jeder Iteration werden die folgenden Regeln ausgewählt:
Basisvektoren werden nach den Formeln berechnet:
Die Koeffizienten werden so gewählt, dass die Vektoren und bezüglich A konjugiert sind.
Wenn wir mit bezeichnen, erhalten wir nach mehreren Vereinfachungen die endgültigen Formeln, die bei der praktischen Anwendung der konjugierten Gradientenmethode verwendet werden:
Analyse der Methode
Für die konjugierte Gradientenmethode gilt der folgende Satz:
Satz Wo ist eine symmetrische positiv definite Matrix der Größe? Dann konvergiert die konjugierte Gradientenmethode in nur Schritten und es gelten die folgenden Beziehungen:
Konvergenz der Methode
Wenn alle Berechnungen korrekt sind und die Anfangsdaten korrekt sind, konvergiert die Methode dahingehend, dass das System in nicht mehr als Iterationen gelöst wird, wobei die Dimension des Systems angegeben wird. Eine verfeinerte Analyse zeigt, dass die Anzahl der Iterationen nicht überschreitet, wobei die Anzahl der verschiedenen Eigenwerte der Matrix A ist. Um die Konvergenzrate abzuschätzen, ist die folgende (eher grobe) Schätzung korrekt:
Damit können Sie die Konvergenzrate abschätzen, wenn Schätzungen für die maximalen und minimalen Eigenwerte der Matrix bekannt sind. In der Praxis wird am häufigsten das folgende Stoppkriterium verwendet:
.Rechenkomplexität
Bei jeder Iteration der Methode werden Operationen ausgeführt. Diese Anzahl an Operationen ist zur Berechnung des Produkts erforderlich – dies ist der zeitaufwändigste Vorgang bei jeder Iteration. Andere Berechnungen erfordern O(n) Operationen. Die Gesamtrechenkomplexität der Methode überschreitet nicht, da die Anzahl der Iterationen nicht mehr als n beträgt.
Numerisches Beispiel
Wenden wir die konjugierte Gradientenmethode an, um das System zu lösen, wo
Mithilfe der konjugierten Gradientenmethode wird die Lösung dieses Systems in zwei Iterationen erhalten. Die Eigenwerte der Matrix sind 5, 5, -5 – darunter gibt es also zwei verschiedene theoretische Beurteilung Die Anzahl der Iterationen durfte zwei nicht überschreiten
Abschluss
Die konjugierte Gradientenmethode ist eine der am weitesten verbreiteten wirksame Methoden Lösungen von SLAEs mit einer positiv definiten Matrix. Das Verfahren garantiert Konvergenz in einer endlichen Anzahl von Schritten und die erforderliche Genauigkeit kann viel früher erreicht werden. Das Hauptproblem besteht darin, dass durch die Anhäufung von Fehlern die Orthogonalität der Basisvektoren verletzt werden kann, was die Konvergenz beeinträchtigt
Die konjugierte Gradientenmethode im Allgemeinen
Betrachten wir nun eine Modifikation der konjugierten Gradientenmethode für den Fall, dass das minimierte Funktional nicht quadratisch ist: Wir werden das Problem lösen:
.Stetig differenzierbare Funktion. Um die konjugierte Gradientenmethode zur Lösung dieses Problems zu modifizieren, muss für Formeln, die Matrix A nicht enthalten, Folgendes ermittelt werden:
Sie können mit einer von drei Formeln berechnen:
Wenn die Funktion quadratisch und streng konvex ist, liefern alle drei Formeln das gleiche Ergebnis. Wenn es sich um eine beliebige Funktion handelt, entspricht jede der Formeln einer eigenen Modifikation der konjugierten Gradientenmethode. Die dritte Formel wird selten verwendet, da sie die Funktion und die Berechnung des Hesse-Werts der Funktion in jedem Schritt der Methode erfordert.
Analyse der Methode
Wenn die Funktion nicht quadratisch ist, konvergiert die konjugierte Gradientenmethode möglicherweise nicht in einer endlichen Anzahl von Schritten. Darüber hinaus ist eine genaue Berechnung bei jedem Schritt nur in seltenen Fällen möglich. Die Anhäufung von Fehlern führt daher dazu, dass die Vektoren nicht mehr die Abnahmerichtung der Funktion angeben. Irgendwann geht man dann davon aus. Die Menge aller Zahlen, bei denen , akzeptiert wird, wird mit bezeichnet. Die Nummern werden aufgerufen Momente der Methodenaktualisierung. In der Praxis wird oft dort gewählt, wo die Raumdimension liegt.
Konvergenz der Methode
Für die Fletcher-Reeves-Methode gibt es einen Konvergenzsatz, der nicht allzu strenge Bedingungen an die zu minimierende Funktion stellt:
Satz.
Folgende Bedingungen seien erfüllt:
setzt M: .
Dann
Für das Polak-Reiber-Verfahren wird die Konvergenz unter der Annahme bewiesen, dass es sich um eine streng konvexe Funktion handelt. Im allgemeinen Fall ist es unmöglich, die Konvergenz der Polak-Reiber-Methode zu beweisen. Im Gegenteil, der folgende Satz ist wahr:
Satz.
Nehmen wir an, dass bei der Polak-Reiber-Methode die Werte bei jedem Schritt genau berechnet werden. Dann gibt es eine Funktion und eine anfängliche Näherung, sodass %200,%20%5Cforall%20k%20=%200,%201,%202,%20...%20%5Cquad%20%7C%7Cf(x_k) % 7C%7C%20>%20%5Cdelta" alt="\exists \delta > 0, \forall k = 0, 1, 2, ... \quad ||f(x_k)|| > \delta">.!}
In der Praxis funktioniert jedoch die Polak-Reiber-Methode besser.
Das in der Praxis am häufigsten vorkommende Abbruchkriterium: Die Steigungsnorm unterschreitet einen bestimmten Schwellenwert
Der Wert der Funktion ist über mehrere aufeinanderfolgende Iterationen nahezu unverändert geblieben.
Rechenkomplexität
Bei jeder Iteration der Polak-Reiber- oder Fletcher-Reeves-Methode werden die Funktion und ihr Gradient einmal berechnet und das eindimensionale Optimierungsproblem gelöst. Somit liegt die Komplexität eines Schritts der Methode des konjugierten Gradienten in der gleichen Größenordnung wie die Komplexität eines Schritts der Methode des steilsten Abstiegs. In der Praxis zeigt sich die konjugierte Gradientenmethode bessere Geschwindigkeit Konvergenz.
Numerisches Beispiel
Wir werden mit der konjugierten Gradientenmethode nach dem Minimum der Funktion suchen. Das Minimum dieser Funktion ist 1 und wird bei Punkt (5, 4) erreicht. Vergleichen wir am Beispiel dieser Funktion die Methoden Polak-Reiber und Fletcher-Reeves. Iterationen in beiden Methoden werden beendet, wenn im aktuellen Schritt die quadratische Norm des Gradienten kleiner wird als . Zur Auswahl kommt die Methode des Goldenen Schnitts zum Einsatz
| Fletcher-Reeves-Methode | Polak-Reiber-Methode | |||||
|---|---|---|---|---|---|---|
| Anzahl der Iterationen | Lösung gefunden | Funktionswert | Anzahl der Iterationen | Lösung gefunden | Funktionswert | |
| 0.01 | 18 | (5.01382198,3.9697932) | 1.00110367 | 15 | (5.03942877,4.00003512) | 1.00155463 |
| 0.001 | 20 | (5.01056482,3.99018026) | 1.00020805 | 18 | (4.9915894,3.99999044) | 1.00007074 |
| 0.0001 | 24 | (4.9979991,4.00186173) | 1.00000747 | 20 | (5.00336181,4.0000018) | 1.0000113 |
| 0.00001 | 25 | (4.99898277,4.00094645) | 1.00000193 | 22 | (4.99846808,3.99999918) | 1.00000235 |
| 0.00001 | 29 | (4.99974658,4.0002358) | 1.00000012 | 26 | (4.99955034,3.99999976) | 1.0000002 |
Es wurden zwei Versionen der konjugierten Gradientenmethode implementiert: zur Minimierung einer quadratischen Funktion und zur Minimierung einer beliebigen Funktion. Im ersten Fall wird die Methode durch die Funktion implementiert
Vektor
Hier A Und B- Matrix und Vektor, die in der Definition eines quadratischen Optimierungsproblems vorkommen.
Um willkürliche Funktionalität zu minimieren, können Sie eine von zwei Funktionen verwenden:
Vektor
Vektor
Die Parameter für beide Funktionen sind gleich und haben folgende Bedeutung:
spaceSize- Raumdimension (Anzahl der Variablen, von denen das minimierte Funktional abhängt)
F- Zeiger auf die zu minimierende Funktion. Die Funktion muss die Form double haben<имя функции>(Vektor
GradF– Zeiger auf eine Funktion, die den Gradienten der minimierten Funktion berechnet
Beide Methoden verwenden eine Hilfsfunktion, um ein eindimensionales Optimierungsproblem zu lösen. Das Programm implementiert eine eindimensionale Optimierung mithilfe der Methode des Goldenen Schnitts.
Abschluss
Die konjugierte Gradientenmethode verwendet nur Informationen über den linearen Teil des Inkrements an einem Punkt, wie bei Gradientenabstiegsmethoden. Darüber hinaus können Sie mit der konjugierten Gradientenmethode quadratische Probleme in einer endlichen Anzahl von Schritten lösen. Auch bei vielen anderen Problemen übertrifft die konjugierte Gradientenmethode die Gradientenabstiegsmethode. Die Konvergenz des Gradientenverfahrens hängt maßgeblich davon ab, wie genau das eindimensionale Optimierungsproblem gelöst wird. Mögliche Methodenschleifen werden durch Updates aufgelöst. Wenn eine Methode jedoch in ein lokales Minimum einer Funktion gelangt, wird sie höchstwahrscheinlich nicht in der Lage sein, diesem zu entkommen.
siehe auch
Referenzliste
- Wassiljew F. P. Optimierungsmethoden – Factorial Press Publishing House, 2002
- Nocedal J., Wright S.J. Numerische Optimierung, Springer, 1999
Regeln für die Eingabe von Funktionen:
Beispiel: x 1 2 +x 1 x 2, schreiben Sie als x1^2+x1*x2Erzeugt Suchrichtungen, die besser mit der Geometrie der zu minimierenden Funktion übereinstimmen.
Definition. Es werden zwei n-dimensionale Vektoren x und y aufgerufen konjugiert in Bezug auf Matrix A (oder A-Konjugat), wenn Skalarprodukt(x, Aу) = 0 . Hier ist A eine symmetrische positiv definite Matrix der Größe n x n.
Schema des Algorithmus der konjugierten Gradientenmethode
Setze k=0.Ø. 1 Sei x 0 der Ausgangspunkt; ,
d 0 =-g 0 ; k=0.
Sh. 2 Bestimmen Sie x k +1 =x k +λ k d k, wobei
.Dann d k+1 =-g k+1 +β k d k ,
,β k ergibt sich aus der Bedingung d k +1 Ad k =0 (konjugiert bezüglich Matrix A).
Sh. 3 Setzen Sie k=k+1 → Sh.
Das Kriterium zum Stoppen einer eindimensionalen Suche entlang jeder Richtung d k wird wie folgt geschrieben:
.Werte
werden so gewählt, dass die Richtung d k A-konjugiert zu allen zuvor konstruierten Richtungen ist. Fletcher-Reeves-Methode
Strategie der Fletcher-Reeves-Methode besteht darin, eine Folge von Punkten (x k ), k=0, 1, 2, ... zu konstruieren, so dass f(x k +1)< f(x k), k=0, 1, 2, ...Die Punkte der Folge (x k) werden nach der Regel berechnet:
x k +1 =x k -t k d k , k = 0, 1, 2,…
d k = ▽f(x k) + b k -1 ▽f(x k -1)
Die Schrittgröße wird aus der Bedingung des Minimums der Funktion f(x) über t in Bewegungsrichtung gewählt, also als Ergebnis der Lösung des eindimensionalen Minimierungsproblems:
f(x k -t k d k) → min (t k >0)
Im Fall einer quadratischen Funktion f(x) = (x, Hx) + (b, x) + und die Richtungen d k, d k -1 werden H-konjugiert sein, d.h. (d k , Hd k -1)=0
Darüber hinaus an den Punkten der Sequenz (x k) Funktionsgradienten f(x) stehen senkrecht aufeinander, d.h. (▽f(x k +1),▽f(x k))=0, k =0, 1, 2…
Bei der Minimierung nichtquadratischer Funktionen ist die Fletcher-Reeves-Methode nicht endlich. Für nichtquadratische Funktionen wird die folgende Modifikation der Fletcher-Reeves-Methode (Polak-Ribière-Methode) verwendet, wenn der Wert b k -1 wie folgt berechnet wird:
Hier ist I eine Reihe von Indizes: I = (0, n, 2n, 3n, ...), d. h. die Polak-Ribière-Methode beinhaltet die Verwendung der Iteration des steilsten Gradientenabfalls alle n Schritte, wobei x 0 durch x n +1 ersetzt wird.
Die Konstruktion der Folge (x k) endet an der Stelle, für die |▽f(x k)| gilt<ε.
Die geometrische Bedeutung der konjugierten Gradientenmethode ist wie folgt. Von einem gegebenen Startpunkt x 0 aus erfolgt der Abstieg in Richtung d 0 = ▽f(x 0). Am Punkt x 1 wird der Gradientenvektor ▽f(x 1) bestimmt, da x 1 der Minimalpunkt ist der Funktion in Richtung d 0, dann ist ▽f (x 1) orthogonal zum Vektor d 0 . Dann wird der Vektor d 1 gefunden, H-konjugiert zu d 0 . Als nächstes wird das Minimum der Funktion entlang der Richtung d 1 usw. gefunden.
Algorithmus der Fletcher-Reeves-Methode
Erste Stufe.Setze x 0 , ε > 0.
Finden Sie den Gradienten einer Funktion an einem beliebigen Punkt
k=0.
Hauptbühne
Schritt 1. Berechnen Sie ▽f(x k)
Schritt 2. Überprüfen Sie die Erfüllung des Stoppkriteriums |▽f(x k)|< ε
a) Wenn das Kriterium erfüllt ist, ist die Berechnung abgeschlossen, x * =x k
b) Wenn das Kriterium nicht erfüllt ist, fahren Sie mit Schritt 3 fort, wenn k=0, andernfalls fahren Sie mit Schritt 4 fort.
Schritt 3. Bestimmen Sie d 0 = ▽f(x 0)
Schritt 4. Bestimmen Sie oder im Fall einer nichtquadratischen Funktion
Schritt 5. Bestimmen Sie d k = ▽f(x k) + b k -1 ▽f(x k -1)
Schritt 6. Berechnen Sie die Schrittgröße t k aus der Bedingung f(x k - t k d k) → min (t k >0)
Schritt 7. Berechnen Sie x k+1 =x k -t k d k
Schritt 8. Stellen Sie k= k +1 ein und fahren Sie mit Schritt 1 fort.
Konvergenz der Methode
Satz 1. Wenn eine quadratische Funktion f(x) = (x, Hx) + (b, x) + a mit einer nichtnegativen definiten Matrix H ihren Minimalwert auf Rn erreicht, dann stellt die Fletcher-Reeves-Methode sicher, dass das Minimum erreicht wird Der Punkt wird in nicht mehr als n Schritten gefunden.Satz 2. Die Funktion f(x) sei differenzierbar und nach unten auf R m beschränkt, und zwar Gradient erfüllt die Lipschitz-Bedingung. Für einen beliebigen Ausgangspunkt gilt dann für die Polac-Ribière-Methode
Satz 2 garantiert die Konvergenz der Folge (x k ) zum stationären Punkt x *, wobei ▽f(x *)=0. Daher erfordert der gefundene Punkt x * zusätzliche Forschung, um ihn zu klassifizieren. Das Polak-Ribière-Verfahren garantiert die Konvergenz der Folge (x k ) zum Minimalpunkt nur für hochkonvexe Funktionen.
Die Schätzung der Konvergenzrate wurde nur für erhalten stark konvexe Funktionen, in diesem Fall konvergiert die Folge (x k ) zum Minimalpunkt der Funktion f(x) mit der Geschwindigkeit: |x k+n – x*| ≤ C|x k – x*|, k = (0, n, 2, …)
Beispiel. Finden Sie das Minimum der Funktion mithilfe der konjugierten Gradientenmethode: f(X) = 2x 1 2 +2x 2 2 +2x 1 x 2 +20x 1 +10x 2 +10.
Lösung. Wählen Sie als Suchrichtung den Gradientenvektor am aktuellen Punkt aus:
|
