Das CG-Verfahren

• Das CG-Verfahren, das ursprünglich zur Lösung linearer Gleichungssysteme mit positiv definiter symmetrischer Matrix entwickelt wurde, kann fast wörtlich auf beliebige unrestringierte Minimierungsaufgaben mit differenzierbarer Zielfunktion angewendet werden. Das heißt, zu einer Funktion F in C¹ ist ein Punkt x^opt gesucht, für den F(x^opt) <= F(x) für alle x aus einer Umgebung von x^opt gilt.
• Hier wird die Variante nach Fletcher und Reeves verwendet, die die nächstliegende Verallgemeinerung des CG-Verfahrens von Hestenes und Stiefel darstellt. Ausserdem wird ein Modifikationsfaktor beim Gradienten benutzt, der sicherstellt, dass unabhängig von der Genauigkeit der Schrittweitenbestimmung die Richtung immer gradientenbezogen ist (Lippold).
• Die Schrittweite wird mit dem Verfahren von AlBaali und Fletcher bestimmt. 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. Der Defaultwert für kappa ist 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 kappa für die eindimensionale Minimierung.
• 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 werden noch die Indices 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 ihre berechneten Optimalwerte 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 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