www.wikidata.de-de.nina.az

Quasi Newton Verfahren sind eine Klasse von numerischen Verfahren zur Lösung nichtlinearer Minimierungsprobleme Die Verf

Quasi-Newton-Verfahren

Quasi-Newton-Verfahren sind eine Klasse von numerischen Verfahren zur Lösung nichtlinearer Minimierungsprobleme. Die Verfahren basieren auf dem Newton-Verfahren, berechnen die Inverse der Hesse-Matrix jedoch nicht direkt, sondern nähern sie lediglich an, um den Rechenaufwand pro Iteration zu verkleinern.

Der erste Algorithmus wurde Mitte der 1950er Jahre von William Davidon, einem Physiker am Argonne National Laboratory, entwickelt. Die bekanntesten Algorithmen sind Broyden-Fletcher-Goldfarb-Shanno (BFGS), benannt nach Roger Fletcher, Donald Goldfarb, David F. Shanno, Charles George Broyden, und Davidon-Fletcher-Powell (DFP) (nach Fletcher, Davidon und Michael J. D. Powell).

Grundlegender Algorithmus Bearbeiten

Eine zweifach differenzierbare Funktion wird mit einer Taylor-Entwicklung an der Stelle bis zum zweiten Grad angenähert.

Die Ableitung der Funktion muss für ein Minimum null ergeben. Daraus folgt:

Falls die Hesse-Matrix positiv definit ist, so handelt es sich bei besagter Nullstelle der Ableitung von tatsächlich um ein Minimum von und dieses lässt sich mit dem Newton-Verfahren iterativ annähern:

Problematisch ist hier, dass die Inverse der Hesse-Matrix berechnet und diese positiv definit sein muss. Das Quasi-Newton-Verfahren ersetzt durch einen Skalar und eine Matrix

Die Ableitungs-Gleichung von oben ergibt umgeformt für und

Daraus lässt sich ein Differenzterm definieren:

Man nimmt nun an, dass die Hesse-Matrix für und in etwa gleich sind, also und folgert daraus:

Für wählt man einen Korrekturterm der Form :

Die Gleichung lässt sich umstellen, so dass

Somit gilt

So lässt sich die Matrix eindeutig bestimmen, jedoch ist diese mit nur einem Korrekturterm nicht immer positiv definit.

Davidon-Fletcher-Powell (DFP) Bearbeiten

Die Matrix wird mit der Matrix und zwei Korrekturtermen approximiert:

Eigenschaften Bearbeiten

Falls eine quadratische Funktion ist, liefert der Algorithmus bei exakter Arithmetik nach einer endlichen Anzahl an Iterationen die exakte Lösung. Für alle anderen Funktionen gilt

Bei einer quadratischen Funktion mit Parametern wird idealerweise sogar in Schritten die Lösung erreicht. In der Praxis benötigt man etwas mehr Iterationen, z. B. wenn die lineare Schrittweitensuche nicht genau genug durchgeführt wird oder die Gradienten nicht genau genug ermittelt werden. Meist stoppt man die Optimierung, wenn z. B. der Gradient sehr klein ist oder eine bestimmte Anzahl von Iterationen erreicht wird.

Reguläre Quasi-Newton-Verfahren Bearbeiten

Der Versuch eine Übersicht über die verschiedenen Ansätze der Quasi Newtion Verfahren zu verfassen, wurde 1985 in dem Artikel "Reguläre Quasi-Newton-Verfahren" gemacht. Hier konnte eine umfassende Klasse dieser Verfahren, eine Darstellung aller Rang 1 - Formeln der sogenannten symmetrischen, novellierten Huang-Klasse entwickelt werden, die die bekannten Verfahren wie das Davidon-Fletcher-Powell (DFP), das Broyden-Fletcher-Goldfarb-Shanno (BFGS) und Self-Scaling-Variable-Metric (SSVM) Verfahren beinhaltet. Auch sind dort Vorschläge für eine weitere Optimierung des Lösungsverhaltens von Quasi-Newton-Verfahren gegeben. Dabei wurde folgende Klasse von regulären (d. h. wegen besonderer Eigenschaften bevorzugt zu benutzender) Quasi-Newton-Aufdatierungsformeln konstruiert:

mit

Für genäherte, hinreichend exakte Strahlminimierung, positiv definites und beliebiges gilt für diese regulären Verfahren, die aus der obigen Formel entstehen:

1) Die Verfahren sind Quasi-Newton-Verfahren.

2) Die Matrizen sind für alle Iterationen positiv definit. Damit gilt

3) Für alle Iterationen erhalten wir Lösungen des Minimierungsproblems.

Für exakte Strahlminimierung und quadratische Zielfunktion bricht zudem jedes dieser Verfahren nach höchstens n Iterationsschritten im Minimalpunkt ab. Insbesondere besitzen also die regulären Quasi - Newton -Verfahren die guten Eigenschaften sowohl der erweiterten Greenstadt-Klasse als auch der symmetrischen, erweiterten Huang-Klasse bzgl. Konvergenz und Stabilität.

Es kann vermutet werden, dass alle besonders leistungsfähigen Quasi-Newton-Verfahren regulär sind.

Literatur Bearbeiten

  • William C. Davidon, Variable Metric Method for Minimization, SIOPT Volume 1 Issue 1, Pages 1-17, 1991 (zuerst als Argonne National Laboratory Report 1959).
  • Jorge Nocedal und Stephen J. Wright: Numerical Optimization, Springer-Verlag, 1999 ISBN 0-387-98793-2.
  • Edwin K.P. Chong and Stanislaw H.Zak: An Introduction to Optimization, 2ed, John Wiley & Sons Pte. Ltd. August 2001.
  • P. Gill, W. Murray und M. Wright: Practical Optimization, 1981
  • Guido Bacharach und Gerhard Freiling: "Reguläre Quasi-Newton-Verfahren", Universität Duisburg, 1985
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Quasi Newton Verfahren sind eine Klasse von numerischen Verfahren zur Losung nichtlinearer Minimierungsprobleme Die Verfahren basieren auf dem Newton Verfahren berechnen die Inverse der Hesse Matrix jedoch nicht direkt sondern nahern sie lediglich an um den Rechenaufwand pro Iteration zu verkleinern Der erste Algorithmus wurde Mitte der 1950er Jahre von William Davidon einem Physiker am Argonne National Laboratory entwickelt Die bekanntesten Algorithmen sind Broyden Fletcher Goldfarb Shanno BFGS benannt nach Roger Fletcher Donald Goldfarb David F Shanno Charles George Broyden und Davidon Fletcher Powell DFP nach Fletcher Davidon und Michael J D Powell Inhaltsverzeichnis 1 Grundlegender Algorithmus 2 Davidon Fletcher Powell DFP 2 1 Eigenschaften 3 Regulare Quasi Newton Verfahren 4 LiteraturGrundlegender Algorithmus BearbeitenEine zweifach differenzierbare Funktion f R n R displaystyle f colon mathbb R n rightarrow mathbb R nbsp wird mit einer Taylor Entwicklung an der Stelle x k displaystyle x k nbsp bis zum zweiten Grad angenahert f x q x f x k x x k T f x k 1 2 x x k T H x k x x k displaystyle f x approx q x f x k x x k T nabla f x k 1 over 2 x x k T H x k x x k nbsp Die Ableitung der Funktion q displaystyle q nbsp muss fur ein Minimum null ergeben Daraus folgt q x f x k H x k x x k 0 displaystyle nabla q x nabla f x k H x k x x k 0 nbsp Falls die Hesse Matrix H x k displaystyle H x k nbsp positiv definit ist so handelt es sich bei besagter Nullstelle der Ableitung von q displaystyle q nbsp tatsachlich um ein Minimum von q displaystyle q nbsp und dieses lasst sich mit dem Newton Verfahren iterativ annahern x k 1 x k H 1 x k f x k displaystyle x k 1 x k H 1 x k nabla f x k nbsp Problematisch ist hier dass die Inverse der Hesse Matrix berechnet und diese positiv definit sein muss Das Quasi Newton Verfahren ersetzt H 1 x k displaystyle H 1 x k nbsp durch einen Skalar a k displaystyle alpha k nbsp und eine Matrix M k displaystyle M k nbsp x k 1 x k a k M k f x k displaystyle x k 1 x k alpha k M k nabla f x k nbsp Die Ableitungs Gleichung von oben ergibt umgeformt fur x k displaystyle x k nbsp und x k 1 displaystyle x k 1 nbsp f x k H x k x x k displaystyle nabla f x k H x k x x k nbsp f x k 1 H x k 1 x x k 1 displaystyle nabla f x k 1 H x k 1 x x k 1 nbsp Daraus lasst sich ein Differenzterm D g k displaystyle Delta g k nbsp definieren D g k f x k 1 f x k displaystyle Delta g k nabla f x k 1 nabla f x k nbsp D g k H x k 1 x x k 1 H x k x x k displaystyle Delta g k H x k 1 x x k 1 H x k x x k nbsp Man nimmt nun an dass die Hesse Matrix fur x k displaystyle x k nbsp und x k 1 displaystyle x k 1 nbsp in etwa gleich sind also H x k H x k 1 displaystyle H x k approx H x k 1 nbsp und folgert daraus D g k H x k 1 x k x k 1 displaystyle Delta g k approx H x k 1 x k x k 1 nbsp M k 1 D g k x k 1 x k displaystyle M k 1 Delta g k x k 1 x k nbsp Fur M k 1 displaystyle M k 1 nbsp wahlt man einen Korrekturterm der Form c Z Z T displaystyle cZZ T nbsp M k 1 M k c Z Z T displaystyle M k 1 M k cZZ T nbsp M k 1 D g k M k D g k c Z Z T D g k x k 1 x k D x k displaystyle M k 1 Delta g k M k Delta g k cZZ T Delta g k x k 1 x k Delta x k nbsp Die Gleichung lasst sich umstellen so dass c Z D x k M k D g k Z T D g k displaystyle cZ Delta x k M k Delta g k over Z T Delta g k nbsp Somit gilt Z D x k M k D g k displaystyle Z Delta x k M k Delta g k nbsp c 1 Z T D g k displaystyle c 1 over Z T Delta g k nbsp So lasst sich die Matrix M k 1 displaystyle M k 1 nbsp eindeutig bestimmen jedoch ist diese mit nur einem Korrekturterm nicht immer positiv definit Davidon Fletcher Powell DFP BearbeitenDie Matrix M k 1 displaystyle M k 1 nbsp wird mit der Matrix M k displaystyle M k nbsp und zwei Korrekturtermen approximiert M k 1 M k c 1 Z 1 Z 1 T c 2 Z 2 Z 2 T M k 1 M k D x k D x k T D x k T D g k M k D g k D g k T M k D g k T M k D g k displaystyle begin aligned M k 1 amp M k c 1 Z 1 Z 1 T c 2 Z 2 Z 2 T M k 1 amp M k Delta x k Delta x k T over Delta x k T Delta g k M k Delta g k Delta g k T M k over Delta g k T M k Delta g k end aligned nbsp Eigenschaften Bearbeiten Falls f displaystyle f nbsp eine quadratische Funktion ist liefert der Algorithmus bei exakter Arithmetik nach einer endlichen Anzahl an Iterationen die exakte Losung Fur alle anderen Funktionen gilt f x k 1 lt f x k displaystyle f x k 1 lt f x k nbsp Bei einer quadratischen Funktion mit N displaystyle N nbsp Parametern wird idealerweise sogar in N displaystyle N nbsp Schritten die Losung erreicht In der Praxis benotigt man etwas mehr Iterationen z B wenn die lineare Schrittweitensuche nicht genau genug durchgefuhrt wird oder die Gradienten nicht genau genug ermittelt werden Meist stoppt man die Optimierung wenn z B der Gradient sehr klein ist oder eine bestimmte Anzahl von Iterationen erreicht wird Regulare Quasi Newton Verfahren BearbeitenDer Versuch eine Ubersicht uber die verschiedenen Ansatze der Quasi Newtion Verfahren zu verfassen wurde 1985 in dem Artikel Regulare Quasi Newton Verfahren gemacht Hier konnte eine umfassende Klasse dieser Verfahren eine Darstellung aller Rang 1 Formeln der sogenannten symmetrischen novellierten Huang Klasse entwickelt werden die die bekannten Verfahren wie das Davidon Fletcher Powell DFP das Broyden Fletcher Goldfarb Shanno BFGS und Self Scaling Variable Metric SSVM Verfahren beinhaltet Auch sind dort Vorschlage fur eine weitere Optimierung des Losungsverhaltens von Quasi Newton Verfahren gegeben Dabei wurde folgende Klasse von regularen d h wegen besonderer Eigenschaften bevorzugt zu benutzender Quasi Newton Aufdatierungsformeln konstruiert H i 1 B H i p i q i 8 i r i r i displaystyle H i 1 B H i p i q i theta i r i rho i nbsp mit B H p q 8 r r r H r s r t 8 s 2 p p T r 8 1 t H q q T H r 8 s p q T H H q p T displaystyle B H p q theta r rho rH rho sigma r tau theta over sigma 2 pp T r theta 1 over tau Hqq T H r theta over sigma pq T H Hqp T nbsp H R n x n displaystyle H in mathbb R nxn nbsp positiv definit p q R n ϵ p T H 1 p displaystyle p q in mathbb R n epsilon p T H 1 p nbsp s p T q t q T H q 8 r r R r gt 0 r s gt 0 displaystyle sigma p T q tau q T Hq theta r rho in mathbb R r gt 0 rho sigma gt 0 nbsp 8 ϵ t s 2 gt s 2 r t r s 8 r t r s 0 displaystyle theta epsilon tau sigma 2 gt sigma 2 r tau rho sigma theta r tau rho sigma geq 0 nbsp Fur genaherte hinreichend exakte Strahlminimierung positiv definites H 0 R n x n displaystyle H 0 in mathbb R nxn nbsp und beliebiges x 0 R n displaystyle x 0 in mathbb R n nbsp gilt fur diese regularen Verfahren die aus der obigen Formel entstehen 1 Die Verfahren sind Quasi Newton Verfahren 2 Die Matrizen H i displaystyle H i nbsp sind fur alle Iterationen positiv definit Damit gilt f x i 1 lt f x i displaystyle f x i 1 lt f x i nbsp fur alle Iterationen 3 Fur alle Iterationen i 0 displaystyle i geq 0 nbsp erhalten wir Losungen des Minimierungsproblems Fur exakte Strahlminimierung und quadratische Zielfunktion bricht zudem jedes dieser Verfahren nach hochstens n Iterationsschritten im Minimalpunkt ab Insbesondere besitzen also die regularen Quasi Newton Verfahren die guten Eigenschaften sowohl der erweiterten Greenstadt Klasse als auch der symmetrischen erweiterten Huang Klasse bzgl Konvergenz und Stabilitat Es kann vermutet werden dass alle besonders leistungsfahigen Quasi Newton Verfahren regular sind Literatur BearbeitenWilliam C Davidon Variable Metric Method for Minimization SIOPT Volume 1 Issue 1 Pages 1 17 1991 zuerst als Argonne National Laboratory Report 1959 Jorge Nocedal und Stephen J Wright Numerical Optimization Springer Verlag 1999 ISBN 0 387 98793 2 Edwin K P Chong and Stanislaw H Zak An Introduction to Optimization 2ed John Wiley amp Sons Pte Ltd August 2001 P Gill W Murray und M Wright Practical Optimization 1981 Guido Bacharach und Gerhard Freiling Regulare Quasi Newton Verfahren Universitat Duisburg 1985 Abgerufen von https de wikipedia org w index php title Quasi Newton Verfahren amp oldid 213605940