Implementationsaufgabe Steilstes Abstiegsverfahren

Implementationsaufgabe Steilstes Abstiegsverfahren
Implementieren Sie in MATLAB (oder Octave wenn MATLAB nicht möglich) das steilste Abstiegsverfahren mit der unten beschriebenen Schrittweitenstrategie.
Sei wie in der Vorlesung f : C 1 (IRn , IR). Gegeben seien ferner die Parameter σ und ρ mit 0 < σ < ρ < 1,
η > 1, ε > 0, M > 0 und N ∈ IN sowie ein Startpunkt x0 ∈ IRn .
Die Methode generiert eine Folge {xk } von Vektoren im IRn wobei
xk+1 = xk + tk dk
mit dk = −∇f (xk ).
Die Schrittweite tk soll durch das unten beschriebene Verfahren auf Basis der Armijo bzw. Wolfe-PowellBedingung wie folgt ermittelt werden.
Eine Schrittweite t > 0 erfüllt die Armijo-Bedingung (A) im k-ten Schritt wenn
f (xk + tdk ) ≤ f (xk ) − σt||dk ||2
und die Wolfe-Powell-Bedingung (P) wenn
∇f (xk + tdk )t dk ≥ −ρ||dk ||2 .
Die Schrittweite tk wird durch das folgende Bisektionsverfahren bestimmt: Gestartet wird mit dem Suchintervall [0, t′k ] mit
t′k = min{η i | f (xk + η i dk ) > f (xk ) − ση i ||dk ||2 }.
i∈IN
Sei [τ0 , τ1 ] das aktuelle Suchintervall für tk . Betrachte nun τ = (τ0 + τ1 )/2.
• Wenn τ (A) und (P) erfüllt dann breche ab und setze tk = τ .
• Wenn τ (A) erfüllt aber nicht (P), dann setze mit dem Suchintervall [τ, τ1 ] fort.
• Wenn τ (A) nicht erfüllt, setze mit [τ0 , τ ] fort.
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).
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. Damit lässt sich der Code modular
anwenden und es müssen nur diese Funktionen ausgewechselt werden. Ihre Codes werden mit verschiedenen
von uns vorgegebenen Funktionen getestet.
Das Result soll eine Funktion sein der Form
[x cas] = steepest(xinit, sigma, rho, eta, epsilon, M, maxit)
sein. xinit soll ein Spaltenvektor sein und entspricht x0 . maxit steht für N .
Testen Sie Ihr Programm für verschiedene Funktionen, und auf jeden Fall für die
• Rosenbrock Funktion (welchen Einfluss hat ε?)
1
• diverse quadratische Funktionen z.B. jene aus Aufgabe 115 oder jene mit


14 9 −1


Q =  9 18 6 
−1 6
5
(c selbst wählen).
• f (x) = − exp(−||x|2 ) (verschiedene x0 testen)
Kommentar zur Abgabe: Bis spätestens 2 Stunden vor Übungsbeginn am 11.6. 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, steilster
Abstieg anführen (im Falle eines Octave Programms noch (Octave) anhängen). Nennen Sie Ihren File in
der Art Nachname+1.Buchstabe Vorname.m (lauter Kleinbuchstaben) - also z.B. bei mir klinzb.m.
2

Download Report