4. Exercise

Technische Universität Chemnitz
Prof. Dr. R. Herzog, Dr. A. Günnel
Chemnitz, 1. Dezember 2015
Nichtlineare Optimierung
Übung 4
Aufgabe 8: Implementierung des BFGS-Verfahrens
Implementieren Sie das Quasi-Newtonverfahren mit inversem BFGS-Update (Algorithmus 4.35) mit (strenger) Wolfe-Schrittweitenstrategie in Matlab. Verwenden Sie
function X = quasi_newton_BFGS ( fhandle , x0 , Minv , atol , ,→
parameters )
als erste Zeile. Dabei bezeichnet fhandle das Handle auf eine Funktion und x0 den
Startpunkt. Das Argument Minv ist eine Funktion, die das Matrix-Vektor-Produkt
M −1 y berechnet und kann für das Abbruchkriterium (4.16) verwendet werden. Weiter
ist atol die absolute Toleranz und es sei τrel = 0 in dem Abbruchkriterium (4.16).
Die Struktur parameters enthält die Parameter für die strenge Wolfe-Liniensuche. Als
Startmatrix B0 für das BFGS-Update können Sie die Identität I verwenden.
Zurückgegeben werden soll eine Matrix X = [x0 , x1 , x2 , . . .], welche den gesamten
Iterationsverlauf enthält.
Das inverse BFGS-Update (4.42) soll in einer eigenen Datei implementiert werden.
Die erste Zeile in BFGS_update.m soll
function [ B_new ] = BFGS_update (B , s , y )
BFGS mittels (4.42) berechnen.
lauten und Bk+1
Teste das implementierte Verfahren an verschiedenen Funktionen und Startwerten.
Interpretiere dabei auch die Anzahl der benötigten Iterationen.
Aufgabe 9: Implementierung des LM-BFGS-Verfahrens
Implementieren Sie das Quasi-Newtonverfahren mit (inversem) Limited-Memory BFGSUpdate (Algorithmus 4.38) mit (strenger) Wolfe-Schrittweitenstrategie in Matlab. Verwenden Sie
function X = quasi_newton_LMBFGS ( fhandle , x0 , Minv , atol , ,→
parameters )
als erste Zeile. Dabei bezeichnet fhandle das Handle auf eine Funktion und x0 den
Startpunkt. Das Argument Minv ist eine Funktion, die das Matrix-Vektor-Produkt
M −1 y berechnet und wir nutzen B LM-BFGS = M −1 . Für das Abbruchkriterium (4.16)
1
bezeichnet atol die absulte Toleranz und es sei τrel = 0. Die Struktur parameters enthält die Parameter für die strenge Wolfe-Liniensuche, sowie die Anzahl zu speichernder
Vektoren in der Variablen parameters.m.
Zurückgegeben werden soll eine Matrix X = [x0 , x1 , x2 , . . .], welche den gesamten
Iterationsverlauf enthält.
Die Auswertung von BkLM-BFGS g (Algorithmus 4.37) soll in einer eigenen Datei implementiert werden. Die erste Zeile in apply_LMBFGS.m soll
function [ d ] = apply_LMBFGS (Y ,S , B0 , g )
lauten. Die Matrizen Y und S enthalten die Vektor {yi }i=k−m,...,k−1 und {si }i=k−m,...,k−1
als Spalten. Beachte: Der Wert für m ergibt sich damit gerade aus der Anzahl der
Spalten von Y bzw. S.
Teste das implementierte Verfahren an verschiedenen Funktionen und Startwerten.
Wie wirken sich verschiedene Werte von m auf die Iterationen aus?
2

Download Report