Das BFGS-Verfahren neu

• Das BFGS-Verfahren ist eine sogenannte quasi Newton-Methode zur Lösung unrestringierter Minimierungsaufgaben unter Verwendung der ersten Ableitungen. Das heißt, zu einer Funktion F in C¹ ist ein x^opt gesucht, für das F(x^opt) <= F(x) für alle x aus einer Umgebung von x^opt gilt.
• Ausgehend von einem Startvektor x₀ und einer positiv definiten Matrix A₀ wird iteriert: x_k+1 = x_k - sigma_kd_k.
  Hierbei wird d_k als die Lösung der Gleichung
  A_kd_k = grad(F(x_k))
  bestimmt. A_k+1 wird durch die BFGS-Update-Formel bestimmt:
  A_k+1 = A_k+(y_ky_k^T)/(y_k^Ts_k)- A_ks_ks_k^TA_k/(s_k^TA_ks_k)
  A_k+1 erfüllt die sog. Sekantenrelation
  A_k+1s_k = y_k,
  mit
  s_k=x_k+1-x_k, y_k= grad(F(x_k+1))- grad(F(x_k))
  Das Gleichungssystem für d_k wird mit der Cholesky-Zerlegung von A_k gelöst, wobei diese von Schritt zu Schritt aufdatiert wird. sigma_k wird hier mit dem Schrittweitenverfahren von Albaali und Fletcher berechnet. Dies ist ein Einschachtelungsverfahren zur Erfüllung der strengen Powell-Wolfe-Abstiegskriterien:
  |grad F(x_next)'d| <= kappa*|grad F(x)'d|
  F(x)-F(x_next) >= sigma*delta*|grad F(x)'d|.
  Hier ist stets delta=0.01, für kappa gibt es den Defaultwert 0.9.

Die Eingaben

• Sie haben die Wahl zwischen 14 vorgegebenen Funktionen, zu denen Sie auch eine genauere Beschreibung nachlesen können. Oder Sie geben eine eigene Funktion f, abhängig von n Variablen x(1),...,x(n), und die Startwerte zu diesen Variablen an.
• Sie können entweder Standardabbruchkriterien wählen oder eigene Kriterien angeben. Letzteres bedeutet dann noch die Angabe von Abbruchtoleranzen für den Gradienten und die Änderung in x und den Parameter im Powell-Wolfe-Abstiegstest.
• Für die festeingestellten Funktionen ist noch eine Angabe der Startwerte der Variablen möglich, wobei Sie auch hier eine Standardinitialisierung wählen können. Sie finden die jeweilige Anzahl n der Variablen bei den Kurzbeschreibungen oben im Eingabeformular.
• Des weiteren haben Sie die Wahl, ob Sie einen Höhenlinienplot als Ausgabe möchten. Wenn ja, dann wird noch der Index der Variablen, bezüglich derer das Bild geplottet werden soll, sowie entsprechende Intervallangaben benötigt. Bei der Berechnung der Höhenlinien werden die anderen Variablen auf den berechneten Optimalwert gesetzt.

Die Ausgaben

• CPU-Zeit.
• Den Grund des Rechnungsabbruchs.
• Die berechnenten Optimalwerte f(x_opt) und x(1)_opt,...,x(n)_opt.
• Die Anzahl der Funktionsaufrufe.
• Zwei logarithmische Plots des Fehlers f - f_opt sowie der Norm des Gradienten von f.
• Und den Höhenlinienplot, falls Sie diesen gewünscht hatten.

Das Eingabeformular

Zurück: Unrestringierte Minimierung