Koordinatenweise Minimierung

• Die koordinatenweise Minimierung ist eine Methode, unrestringierte Minimierungsaufgaben zu lösen. Das heißt, zu einer Funktion F in C¹ ist ein x^opt gesucht, für welches F(x^opt) <= F(x) für alle x aus einer Umgebung von x^opt gilt.
• Hier wird koordinatenweise minimiert. Hier wird also als Abstiegsrichtung ein Koordinateneinheitsvektor gewählt, wobei sich das Vorzeichen nach dem Vorzeichen der i-ten Koordinate der Gradienten von F (i=(k mod(n))+1) richtet.
• Ausgehend von einem Startvektor x₀ wird iteriert: x_k+1 = x_k - sigma_kd_k.
  Hierbei ist d_k = +/- e^{(k mod(n))+1} mit grad(F(x_k))^Td_k >= 0 , wobei e^j der j-te Einheitsvektor ist.
• Die Schrittweite sigma_k wird hier mit dem Schrittweitenverfahren von AlBaali und Fletcher (J.O.T.A. 1985) 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 . kappa ist wählbar.
• Im quadratischen Fall f(x) = 1/2x^TAx - b^T mit positiv definiter Matrix A entsteht das Einzelschrittverfahren zur Lösung des Gleichungssystems Ax = b, da die erste Testschrittweite aus den Werten psi(0), psi^'(0) und psi(1), psi(sigma)=f(x-sigma*d) durch Minimierung der interpolierenden Parabel berechnet wird, also in diesem Fall optimal ist.

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.
  (Standardabbruch: ||grad f|| <= 1.E-7 und ||x-x_prev|| <= 1.E-7*(||x||+1))
  Eigene Kriterien bedeutet noch die Angabe einer Abbruchtoleranz eps für den Gradienten und die Änderung in x, sowie den Powell-Wolfe-Parameter kappa.
• 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. Achtung : Die Erzeugung der Graphik dauert etwas!

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 Plots des Logarithmus 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