Implementationsaufgabe BFGS Quasi Newton Implementieren Sie in MATLAB (oder Octave wenn MATLAB nicht möglich) das (inverse) BFGS Quasi Newtonverfahren wie in der Vorlesung behandelt. Es reicht, wenn Sie die lokale Variante implementieren und abbrechen, wenn die Matrix Bk+1 nicht definiert ist. Sei wie in der Vorlesung f : C 2 (IRn , IR). Gegeben seien ferner die Parameter σ und ρ mit 0 < σ < 1/2 und σ < ρ < 1, ε > 0, loc ∈ {0, 1}, µ > 0, M > 0 und N ∈ IN sowie ein Startpunkt x0 ∈ IRn . • Für loc=1 soll das lokale Verfahren ausgeführt werden. Es gilt xk+1 = xk + dk . Es reicht wenn Sie diese Variante implementieren. Hier spielen die Parameter σ und ρ keine Rolle. • Für die globalisierte Variante (wird mit loc=1 aufgerufen) mit Einbau der Wolfe-Powell Schrittweitensuche gibt es im Fall der Korrektheit einen Sonderpunkt. Hier gilt xk+1 = xk + tk dk . • Gestartet werden soll mit der Matrix B0 = µI. • Die Richtung dk wird bestimmt als dk = −Bk ∇f (xk ) • Im (inversen) BFGS Verfahren erfolgt der Update der Bk Matrizen wie folgt Bk+1 = Bk + (sk − Bk y k )(sk )t + sk (sk − Bk y k )t (sk − Bk y k )t y k k k t − s (s ) (y k )t sk ((y k )t sk )2 wobei y k = ∇f (xk+1 ) − ∇f (xk ) und sk = xk+1 − xk . Abgebrochen werden sollte wenn eine der folgenden Bedingungen erfüllt ist: • ||∇f (xk )|| ≤ ε. Dann soll x = xk gesetzt werden und der Fallparameter cas auf 0 gesetzt werden. • wenn die Iterationszahl k über N steigt, soll mit x = xk abgebrochen werden und der Fallparameter cas auf 1 (zuviele Iterationen) gesetzt werden. • ||xk || ≥ M , dann soll mit x = xk und cas=2 abgebrochen werden (möglicherweise unbeschränktes Problem). • Wenn in der lokalen Variante Bk+1 nicht ermittelt werden kann weil eine Division durch 0 auftreten würde, dann soll mit x = xk und cas=3 abgebrochen werden. Als Norm soll die Euklidische Norm verwendet werden. Für die Funktions- und Gradientenauswertung soll auf die Funktionen (mit genau diesen Namen) funct(x) und gradient(x) zurückgegriffen werden, die f (x) und ∇f (x) (als Spaltenvektor) liefern. Das Result soll eine Funktion sein der Form [x cas] = bfgs(xinit, sigma, rho, epsilon, mu, M, maxit,loc) sein. xinit soll ein Spaltenvektor sein und entspricht x0 . maxit steht für N . Die anderen Parameter wurden bereits erklärt. Testen Sie Ihr Programm für verschiedene Funktionen aus den Übungen und vergleichen Sie mit dem Gradientenverfahren und dem Newtonverfahren. Kommentar zur Abgabe: Bis spätestens 2 Stunden vor Übungsbeginn am 2.7. ist ein einzelner File mit Ihrer Abgabe per e-mail an [email protected] (beide Gruppen) und im Fall der Übungsgruppe Hatzl zusätzlich an [email protected] zu schicken. Im Subjectfeld bitte Optimierung 1, BFGS anführen (im Falle eines Octave Programms noch (Octave) anhängen). Nennen Sie Ihren File in der Art Nachname+1.Buchstabe Vorname5.m (lauter Kleinbuchstaben) - also z.B. bei mir klinzb5.m. 1