Klassische, nichtlineare Optimierung - Einfhrung


(Contents)(Previous)(Next)

Einführung

Bei der nichtlinearen Optimierung werden Extremalwerte (Maxima oder Minima) einer Funktion von einer oder mehreren Variablen gesucht. Obwohl weder Funktion noch Variable reellwertig sein müssen, beschränken wir uns hier auf diesen Fall, wie in der Literatur üblich obwohl gerade Ingenieure Aufgaben zu lösen haben, bei denen die Reelwertigkeit nicht vorausgesetzt werden kann. Es ist typisch für die klassischen Verfahren, dass oft implizit zusätzliche Annahmen gemacht werden um gewisse theoretischen Beweise zu ermöglichen und dabei ausser Acht zu lassen, dass diese Annahmen die praktische Brauchbarkeit beeinträchtigen.

Die Zulassung komplexer oder vektorieller Variablen stellt keinerlei Probleme, da derartige Variable durch zwei oder mehrere reelle Variablen dargestellt werden können. Anders ist die Situation bei komplexen oder vektoriellen Funktionen, da hier zunächst zu definieren ist, was unter einem Extremalwert einer solchen Funktion zu verstehen ist. Die Definition eines Extremalwertes führt fast zwangsläufig auf einen einfachen, geordneten Zahlenraum wie den Raum der reellen Zahlen. Beispielsweise ist die Forderung "Minimiere den Geschwindigkeitsvektor" weder sinnvoll noch mögliches Ziel einer Optimierung, wohl aber "Minimiere den Betrag des Geschwindigkeitsvektors".

Ähnliche Probleme entstehen, wenn gleichzeitig mehrere Forderungen an ein Objekt gestellt werden. Zum Beispiel kann nach einer möglichst kleinen Antenne mit möglichst guter Richtwirkung und möglichst geringen Kosten gesucht werden. Angenommen, wir finden eine billige Antenne mit geringen Abmessungen und schlechter Richtwirkung und eine zweite, teurere und grössere mit besserer Richtwirkung. Welche ist besser? Es gibt verschiedenste Methoden um derartige Aufgabenstellungen zu lösen, wobei die verschiedenen Ziele implizite oder explizite durch eine einzige Zielfunktion ersetzt werden. So können beispielsweise die verschiedenen Zielfunktionen mit Gewichten multipliziert und anschliessend aufsummiert werden. Wie dem auch sei, bei klassischen Optimierungsverfahren geht man immer davon aus dass eine einzige, reellwertige Funktion definiert ist, von der die Extrema gesucht werden. Die Definition dieser Funktion bleibt dem Anwender überlassen.

In sehr vielen Fällen werden die Extrema unter zusätzlichen Nebenbedingungen gesucht. Solche Nebenbedingungen können den Suchbereich einschränken und damit die Aufgabe erleichtern. Betrachten wir als einfaches Beispiel die Suche nach den Minimalwerten von sin(1/x). Diese Funktion hat unendlich viele Minimalwerte, alle mit dem Wert 1. Werden die Nebenbedingungen x1<x<x2 gestellt, so reduziert sich die Anzahl der Minimalwerte auf eine endliche Zahl, falls das Suchintervall x1x2 den Nullpunkt nicht enthält. Nebenbedingungen können die Aufgabe natürlich auch erschweren, wie man sich leicht vorstellen kann.

Im obigen Beispiel haben wir eine Funktion mit unendlich vielen gleich grossen Extremalwerten gesehen. Obwohl es in der Mathematik viele solche Funktionen gibt, sind diese in der Praxis selten. Hingegen sind häufig Funktionen mit einem globalen und mehreren lokalen Optima anzutreffen. Es ist bezeichnend für klassische Suchalgorithmen, dass diese sehr zielgerichtet auf ein lokales Optimum zustreben, dieses aber nicht mehr verlassen. Dabei hängt das gefundene Optimum meist von Startpunkt der Suche ab. Dieser Zusammenhang kann selbst bei einfachen Algorithmen sehr kompliziert sein, wie das folgende Bild zeigt.

{bmct help0001.bmp}

Figur 1: Newton Suche der Nullstellen Funktion z5-1 in der komplexen Ebene. Die Grauwerte geben an zu welcher der fünf Nullstellen der Newton Algorithmus konvergiert, wenn am betreffenden Ort gestartet wird. Es handelt sich um ein Fraktal.

Um konkreter zu werden, betrachten wir im folgenden den besonders einfachen Fall einer reellwertigen Suchfunktion mit einer einzigen, reellen Variablen. Anschliessend betrachten wir Funktionen mit mehreren, reellen Variablen.


(Contents)(Previous)(Next)