Brent

Vorbemerkungen

PRAXIS ist ein Algorithmus von Richard Brent für die Suche nach dem Minimum einer skalaren Funktion im N-dimensionalen Raum.
Hier wird eine Verbesserung für ein Teil dieses Algorithmus vorgeschlagen - nämlich für die Minimierung entlang einer Parabel.
Bei der Umsetzung der Ergebnisse aus Visual Basic in C wurde die C-Variante von Karl Gegenfurtner als Vorlage benutzt.

Literatur:

Brent, R.P. (2002). Algorithms for Minimization without Derivatives, Dover, 2002.

Gegenfurtner, K. (1992). Praxis: Brent's algorithm for function minimization.
Behavior Research Methods Instruments and Computers, 24, 560-564.

Wie ich auf die Idee gekommen bin

In einem anderen meinen Projekt wollte ich ein Funktion von 2 Variablen minimieren. Dazu hatte ich ein primitives Programm entwickelt, was da auch ausreichte. Jedoch danach hatte ich mir das Thema näher angenommen und einen nach meiner Meinung perfekten Algorithmus hervorgebracht, allerdings auch nur für 2 Dimensionen, auf mehr wäre er nicht erweiterbar. Jetzt schaute ich mich um, was es zu diesem Thema gebe – und kam auf PRAXIS.

Als ich das Programm in VB umgesetzt und für eine Testfunktion vergliechen hatte, musste ich einsehen, dass PRAXIS besser war. Jetzt wollte ich rauskriegen, wieso. So kam ich auf die parabolische Interpolation. Gut, könnte ich auch nachmachen. Was mich aber störte – die Parabel wurde durch 3 Punkte erstellt, was nicht eindeutig sein könnte. Nach der Visualisierung wurde dazu auch klar, dass die Parabel durch Punkte zieht, die von der eigentlichen Talsohle weit abstehen, s. letzte Grafiken. Da sollte eine Verbesserung möglich sein.

Diese Änderung will ich hier vorstellen. Zu meinem eigenen Programm bin ich nicht mehr zurückgekommen. Wie schon erwähnt, hatte ich mit Visual Basic gearbeitet. Für diese Veröffentlichung habe ich die Programme in C umgeschrieben und getestet. Als Vorlage habe ich die Programme von Karl Gegenfuertner benutzt, die auch kaum geändert in die Variante Using_Original hineingekommen sind.

Die Änderung.

Sie bestand für mich aus 3 Schritten:

Die Formel herzustellen für eine Parabel über 4 Punkte.
Es war mir gelungen während meines Urlaubs im Juni 2004. Man könnte wahrscheinlich auch fertige Formel finden, aber das hatte ich nicht versucht.
Die effektivste Ausgangspunkte für die Parabel innerhalb des Algorithmus zu bestimmen.
Im Original wird der Punkt benutzt, der nach der letzten linearen Minimierung einer Powell’schen Iteration erreicht wird, der am weitesten von der Talsohle entfernt ist. Ich benutze aus jeder Powell’schen Iteration 3 Punkte: 1. Den Punkt, der nach N–1 linearen Minimierungen aus dem gerade erwähnten Punkt erreicht wird. Das ist wieder ein Punkt in der Nähe der Talsohle. 2. Die zwei Ausgangspunkte Y und X der letzten linearen Minimierung einer Powell’schen Iteration.
Die Kriterien für Anfang und Ende dieser Extrapolation zu finden.
Als Anfangsbedingung werden die Komponenten der diagonalen Matrix D geprüft: Die Längen der beiden längsten Vektoren sollen sich nicht weniger als um einen bestimmten Faktor (bei mir - 3,3) unterscheiden. Sonst ist noch kein Tal zu vermuten. Als Endbedingung wird der Abstand zwischen zwei oben erwähnten Punkten ermittelt – den Punkt vor den ersten N-1 Minimierungen und den Punkt danach. Wenn dieser Abstand relativ zur Länge des vorherigen Vorrückens zu groß ist, wird QFlag = -1 gesetzt und damit die parabolische Iteration (weiter – das Verfahren) ausgeschaltet.

Es wurde versucht, das Verfahren womöglich glatt in die herkömmliche Struktur einzubinden. Solange das Verfahren läuft, wird jeder weitere Punkt mit nur N-1 Minimierungen ermittelt. Das sind die zur Tangente der Parabel konjugierten Richtungen. Wenn jedoch der Punkt nach diesen N-1 Minimierungen zu weit von dem Punkt vorher absteht - von dem Punkt aus der parabolischen Iteration also, liefert die Prozedur Quad() false und es wird einfach der Powell'sche Algorithmus fortgesetzt.

Beim Bewegen entlang der Parabel werden für den N-1 Iterationen immer wieder die N-1 Vektoren benutzt, die nach der letzten vollständigen Powell’schen Iteration per MinFit() ermittelt wurden. Natürlich verringert sich dabei ihr Wert. Um dem entgegenzuwirken, wird der Vektorensatz nach jedem Parabelschritt nachgedreht - Prozedur Rotate().

Ein Beenden des Verfahrens kann bedeuten, dass wir am unteren Ende des Tals angekommen sind. Es ist jedoch nicht ausgeschlossen, dass es wieder eingeschaltet wird. Ein möglicher Grund – die N-1 Vektoren müssten neu ermittelt werden.

Weil bei N > 2 die 4 Punkte nicht in einer Ebene liegen müssen, wird der Drall ermittelt, um damit die Qualität der Prognose zu verbessern. Um diese Ergänzung zu Testen, wurde eine weitere Funktion zu den von R.Brent benutzten Tests zugefügt – der „Helix long“. Es ist eine Schraube entlang eines elliptischen Zylinders, also eine Kurve mit einem variablen Drall. Der Effekt hält sich jedoch in Grenzen, wahrscheinlich weil der Drall sich relativ zur Krümmung relativ schnell ändert. Es ist eigentlich falsch zu vermuten, dass in einem Raum N > 2 eine Tal-Eigenschaft als eindimensionale Kurve auftritt, eher wurde es eine (N-1)-dimensionale Untermenge sein.

Weiter werden Tabellen und Grafiken angeführt, die den Effekt der Änderung veranschaulichen.

Zu den Tabellen und Grafiken.

Die Tabellen sind mit der Table 7.1 im "Algorithms for minimization without derivates" vor Richard P. Brent, 2002, zu vergleichen. Beide Tabellen sind mit Programmen erstellt worden, die in Eclipse mit gcc (vom 24.04.2008) umgewandelt worden sind. Zum Vergleich sind noch mal dieselbe Tabellen mit denselben Programmen erstellt worden, die jedoch innerhalb "MS Visual Studio 2008 Express Edition" umgewandelt und ausgeführt worden sind. Die Unterschiede zeigen die Abhängigkeit vom Compiler und erklären damit auch die Abweichungen meiner Original-Variante von Brent's Tabelle, die auch noch mit einem Algol-Programm erstellt wurde. Vielleicht sollte man die Ausgangskoordinaten der Tests geringfügig variieren und den Einfluss auf NF ermitteln - der Mittelwert und Dispersion hätten mehr Substanz.

Die Spalten QNE und QNY sagen etwas über die parabolische Interpolation aus. In der Original-Variante sind die Werte gleich und geben die Anzahl der Quad()-Aufrufe an. In der New-Varinte ist QNE die Anzahl der Quad()-Aufrufe, die QNY – die Zahl der Erfolgreichen parabolischen Iterationen. Also wenn QNE = 22 und QNY = 17 ist, dann wurde das Verfahren 5 Mal neu angefangen.

Mit dem Wert in der Zeile Summary habe ich versucht eine integrale Bewertung zu erstellen. Er wird errechnet als Mittelwert der ( NF / NF_Orig) ^ 2 über alle Zeilen. Als NF_Orig werden die NF-Werte der ersten Tabelle genommen, so dass für sie ein Wert 1 rauskommt.

Die erste Grafik ist mit Diagram 7.1 aus Brent 2002 zu vergleichen. Die grüne Linie entspricht dem neuen Verfahren. Die Rückgänge am Ende der Suche kommen von der zusätzlichen Prüfung, ob es nicht ein falsches Minimum ist, s. dazu Brent 2002, 7, Section 5 „The resolution ridge problem“. Die entsprechenden Diagramme für die weiteren Tests können aus den Dateien Diagramm.txt aufgestellt werden, die während der Testabläufe ausgegeben werden. Ich habe dazu ein Programm benutzt, entwickelt in VB.

Die beiden weiteren Grafiken visualisieren die Iterationen im Original und im neuen Verfahren für die Funktion Rosenbrock 1.

Downloads.

Varianten der C-Programmen:


	Test		Using
	Original	Neu	Original	Neu
MACHINE.H	A	A	A	A
MINFIT.C	A	A	A	A
PRAXIS.C	O	N	O1	N1
ROSEN.C	A	A	B	B
TP.C	A	A	B	B

Hier soll klar werden, dass z. B. das MINFIT.C in jeder der 4 Varianten gleich ist, von ROSEN.C gibt es nur 2 verschiedene Varianten und vom PRAXIS.C - 4. Die Bezeichnungen A, B, O1 sind selbst ohne Bedeutung, wichtig nur, ob sie in der Zeile gleich sind oder unterschiedlich.

Die Testversionen: Sie sind mit allen Funktionen erweitert, PRAXIS erstellt per Aufrufe der Funktionen report() und diagram() zwei Textdateien, die RANDOM-Funktion wurde auf die von Brent umgestellt.

Die Using-Versionen: Sind vorgesehen für die, die die Programme nur benutzen wollen, aus entsprechendem PRAXIS.C wurde alles entfernt, was unter der Bedingung (jdTest) ausgeführt wurde, die Versionen enthalten auch die MAKE-Datei aus der …

Zum Download werden also 4 zip-Dateien angeboten: