Regularisiertes Newton-Verfahren

• Das Newton-Verfahren zur Lösung der Gleichung
  grad ( F(x) ) = 0 kann so modifiziert werden, daß es geeignet wird, unrestringierte Minimierungsaufgaben mit schlechten Startwerten zu lösen. Zu einer Funktion F in C¹ ist also 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₀ wird iteriert:
  x_k+1 = x_k + sigma_kd_k.
  Hierbei wird d_k als die Lösung des Gleichungssystems
  (Hesse(F(x_k)) + gamma*L*L^T)d_k = -grad(F(x_k))
  bestimmt. Der Regularisierungsparameter gamma bewirkt, daß die Eigenwerte des Diagonalteils D der Bunch-Parlett-Zerlegung der Hesse-Matrix alle positiv sind. L ist dabei der Linksdreiecksfaktor in
  P*H*P^T = L*D*L^T (P Permutationsmatrix)
  Die Schrittweite 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, während man kappa wählen kann. Defaultwert ist kappa=0.9. kappa darf nicht kleiner als delta=0.01 gewählt werden.
• Die Hessematrix (Matrix der zweiten Ableitungen) und der Gradient von F(x) werden duch numerische Differentiation sehr hoher Genauigkeit bestimmt, was für größeres n einen erheblichen Aufwand bedeutet. (6n(n+1) skalare Funktionswerte pro Schritt, der Gradient wird praktisch auf Maschinengenauigkeit approximiert.)
• Da als erste Schrittweite stets sigma=1 getestet wird, konvergiert das Verfahren bei "richtiger" Einstellung der Parameter global und zugleich lokal quadratisch.

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, den Wert für kappa und einen Regularisierungswert für die Hessematrix. (Gefordert wird, daß die Konditionszahl des Diagonalteils D der Bunch-Parlett-Zerlegung kleiner als 1/regul ist.) Ist regul zu klein, so kann die Berechnung der Abstiegsrichtung wegen der Rundungsfehler versagen, ist es zu groß, dann wird die schnelle Konvergenz des Verfahrens zerstört weil bei Regularisierung der Hessematrix die quadratische Konvergenz verlorengeht.
• 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 die Indices der beiden 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 ihren berechneten Optimalwert gesetzt. Achtung : Die Erzeugung der Graphik dauert etwas !

Die Ausgaben

• CPU-Zeit.
• Den Grund des Rechnungsabbruchs.
• Die berechneten Optimalwerte f(x_opt) und x(1)_opt,...,x(n)_opt.
• Die Anzahl der Funktionsaufrufe, den Wert des letzten Regularisierungsshifts und die Frobeniuskonditionszahl der Hesse-Matrix.
• 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