mini|Nichtlineares Programm mit zulässigem Bereich und Optimum Die nichtlineare Optimierung (engl.: nonlinear programming, kurz: NLP) beschäftigt sich mit der Lösung nichtlinearer Optimierungsprobleme, also mit Optimierungsproblemen, deren Zielfunktion nichtlinear ist und/oder deren Nebenbedingungen durch nichtlineare Funktionen beschrieben werden. Sie ist ein Teilgebiet der mathematischen Optimierung und enthält als Spezialfall die konvexe Optimierung. In Abgrenzung zur konvexen Optimierung wird hier lediglich die stetige Differenzierbarkeit aller Funktionen, nicht jedoch ihre Konvexität, vorausgesetzt. Alle grundlegenden Begriffe wie Zielfunktion, Entscheidungsvariablen, Nebenbedingungen, zulässige Menge, lokale und globale Optimierung werden in den Artikeln zur mathematischen Optimierung und zu allgemeinen Optimierungsproblemen erklärt.
Anwendungsfelder Nichtlineare Optimierungsprobleme finden sich in vielfältiger Weise in der Wissenschaft und im Ingenieurwesen.
In der Wirtschaftswissenschaft kann es darum gehen, die Kosten eines Prozesses zu minimieren, der Einschränkungen in der Verfügbarkeit der Mittel und Kapazitäten unterliegt. Die Kostenfunktion kann darin nichtlinear sein. In der theoretischen Mechanik findet sich im Hamiltonschen Prinzip ein Extremalprinzip, dessen Lösung bei nichtlinearen Randbedingungen ein nichtlineares Programm darstellt.
Moderne Ingenieuranwendungen beinhalten oft und in komplizierter Weise Optimierungsaufgaben. So kann es darum gehen, das Gewicht eines Bauteils zu minimieren, das gleichzeitig bestimmten Anforderungen (z. B. Einschränkungen des Bauraumes, Obergrenzen für Verformungen bei gegebenen Lasten) genügen muss.
Bei der Anwendung eines mathematischen Modells kann es darum gehen, die Parameter des Modells an gemessene Werte anzupassen. Nichtlineare Einflüsse der Parameter und Einschränkungen an die Parameter (z. B. dass nur positive Werte zugelassen sind) führen hier auf ein nichtlineares Programm.
In diesen Fragestellungen ist oftmals nicht a priori bekannt, ob das gestellte Problem konvex ist oder nicht. Manchmal beobachtet man eine Abhängigkeit der gefundenen optimalen Lösung vom Startpunkt der Suche. Dann hat man lokale Optima gefunden und das Problem ist mit Sicherheit nicht konvex.
Problemdefinition Es gibt viele mögliche Formulierungen eines nicht linearen Programms. An dieser Stelle soll eine möglichst allgemeine Form gewählt werden. Der Eingabeparameter sei aus dem , das heißt, das Problem hängt von Einflussparametern ab, die im Vektor eingelagert sind. Die Zielfunktion sei einmal stetig differenzierbar. Weiterhin seien die Nebenbedingungen (NB) in Ungleichheitsform mit und in Gleichheitsform mit gegeben und einmal stetig differenzierbar. Dann lautet das Problem mathematisch: .
Der zulässige Bereich wird von den Nebenbedingungen (NB) eingeschränkt: Für alle Werte der Parameter aus dem zulässigen Bereich () sollen die NB erfüllt sein. Zulässig ist das Problem , wenn der zulässige Bereich nicht leer ist.
Zumeist beschränkt sich die theoretische Behandlung der nicht linearen Optimierung auf Minimierungsprobleme. In der Tat kann das Maximierungsproblem einer Funktion in ein Minimierungsproblem von oder , falls gesichert ist, umformuliert werden.
Vorgehen Das Problem wird mit den unten beschriebenen Verfahren auf die Optimierung einer Hilfsfunktion ohne NB zurückgeführt. Um sich die gradientenbasierten Methoden zu Nutze machen zu können, teilt man das abzusuchende Gebiet gegebenenfalls in solche auf, in denen die Zielfunktion differenzierbar ist. Wenn möglich, sollten die Teilgebiete konvex sein und die Zielfunktion in ihnen auch. Dann kann man die globalen Extrema in den Teilgebieten mit den in Mathematische Optimierung und Konvexe Optimierung aufgeführten Verfahren berechnen und das optimale auswählen.
Die Konstruktion der Hilfsfunktion soll anhand eines Beispiels erläutert werden: Zwei Kugeln in einer Mulde versuchen den tiefstmöglichen Punkt einzunehmen, dürfen sich dabei aber nicht durchdringen. Die Zielfunktion ist also die Lageenergie der Kugeln und nimmt im Gleichgewicht ein Minimum an. Die Nebenbedingung würde hier die Durchdringung der Kugeln und bezeichnen, wobei mit negativer Durchdringung ein positiver Abstand gemeint wird.
Lagrange-Multiplikatoren: Die NB werden mit reellen Faktoren, den Lagrange-Multiplikatoren, multipliziert und in die Zielfunktion eingebaut, so dass bei positiven Lagrange-Multiplikatoren die Verletzung der NB bestraft wird. Die so erhaltene Hilfsfunktion heißt Lagrange-Funktion. Die Lagrange-Multiplikatoren werden als Unbekannte in das Problem eingeführt und müssen ebenfalls bestimmt werden. Bei den Kugeln sind die Lagrange-Multiplikatoren gerade die Kontaktkräfte, die die Kugeln bei Berührung aufeinander ausüben, so dass sie sich nicht durchdringen. Barrierefunktionen: Die NB werden mit Barrierefunktionen dargestellt, die bei Annäherung an die Grenze des Definitionsbereiches positive Werte annehmen und auf der Grenze ins Unendliche wachsen. Die Barrierefunktionen werden mit Barriere-Parametern multipliziert und in die Zielfunktion eingebaut, so dass die Annäherung an die Grenze bestraft wird und so die Verletzung der NB verhindert wird. Im Kugelbild bekämen die Kugeln einen mehr oder weniger dicken Mantel, der immer steifer wird, je stärker er bei Berührung zusammengedrückt wird. Eine Verletzung der NB wird so verhindert zu dem Preis, dass bereits die Annäherung an die Bereichsgrenze bestraft wird. Die Methode wird bei Innere-Punkte-Verfahren angewendet. Straffunktionen: Die Straffunktionen werden wie die Barrierefunktionen eingesetzt. Die NB werden mit Straffunktionen dargestellt, die im zulässigen Bereich verschwinden und bei Verletzung der NB positiv sind. Die Straffunktionen werden mit Strafparametern multipliziert und in die Zielfunktion eingebaut, so dass die Verletzung der NB bestraft wird, daher der Name. Hier werden aktive NB evtl. verletzt und die Zulässigkeit der Lösung muss geprüft werden. Im Kugel-Bild entspricht die Straffunktion der „echten“ Durchdringung (die bei positivem Abstand der Kugeln verschwindet) und der Strafparameter einer Federsteifigkeit. Die Feder versucht eindringende Punkte wieder an die Oberfläche zu ziehen. Je steifer die Feder ausfällt, desto geringer wird die Eindringung sein. Erweiterte Lagrange-Methode (): Dies ist eine Kombination der Lagrange-Multiplikatoren und der Strafmethode. Der Lagrange-Multiplikator wird iterativ anhand der Verletzung der NB bestimmt. Trivial (und deshalb in den Quellen oftmals nicht behandelt), aber doch zu erwähnen und im praktischen Gebrauch ist, dass aktive NB dazu genutzt werden können, Variablen zu eliminieren. Die Variablen werden auf Werte festgelegt, derart dass eine Verletzung der NB nunmehr unmöglich ist. Im Kugel-Bild würde man Berührungspunkte der Kugeln aneinanderkoppeln (ihre Koordinaten gleichsetzen), so dass eine Durchdringung (dort) nicht mehr stattfinden kann.
Die Vor- und Nachteile der beschriebenen Methoden sind in der Tabelle zusammengefasst: Methode Vorteile Nachteile Lagrange-Multiplikatoren Erfüllt die NB exakt Das Vorzeichen des Multiplikators zeigt an, ob die NB aktiv ist oder nicht. Führt zusätzliche Unbekannte ein. Schleust verschwindende Diagonalglieder in das Gleichungssystem ein (problematisch bei Cholesky-Zerlegung). Barrierefunktionen Die NB werden eingehalten. Für geht die gefundene Lösung in die mit Lagrange-Multiplikatoren gefundene über. Die Höhenlinien der Hilfsfunktion stimmen nicht mit denen der Zielfunktion überein. Im Extremfall gibt es für einige Werte von gar kein Optimum. Bei Annäherung an die Grenze des zulässigen Bereiches und mit ist die Hesse-Matrix schlecht konditioniert. Strafverfahren Für geht die gefundene Lösung in die mit Lagrange-Multiplikatoren gefundene über. Die Nebenbedingung wird nur näherungsweise erfüllt. Mit ist die Hesse-Matrix schlecht konditioniert. Die Prüfung der Aktivität der NB kann nur durch Auswertung der Funktionen und erfolgen. Erweiterte Lagrange-Methode Mit zunehmender Anzahl an Iterationen geht die gefundene Lösung in die mit Lagrange-Multiplikatoren gefundene über. Erfüllt die NB beliebig genau. Das Vorzeichen des Multiplikators zeigt an, ob die Nebenbedingung aktiv ist oder nicht. Benötigt mehrere konvergierte Lösungen des globalen Problems. Eliminierung der Freiheitsgrade Reduziert die Anzahl an Unbekannten. Hält Gleichheitsnebenbedingungen exakt ein. Ist nur anwendbar, wenn die Aktivität der NB bekannt ist.
Theorie der Optimierung
Isolierte Punkte In einem nicht linearen Programm können NB den zulässigen Bereich in einigen Punkten derart einschränken, dass zwar aber kein Punkt in seiner Umgebung im zulässigen Bereich liegt. Mathematisch formuliert heißt das, dass es eine Umgebung gibt, so dass
gilt. Isolierte Punkte müssen alle einzeln, jeder für sich, auf Optimalität geprüft werden.
Regularitäts-Bedingungen, Tangenten- und Linearisierender Kegel mini|Beispiel eines Nicht Linearen Programms
Für die Formulierung von Optimalitätsbedingungen müssen die NB gewisse Anforderungen erfüllen, engl. constraint qualifications (CQ). Unter anderem geht es darum, optimale Punkte aus der Betrachtung auszuschließen, die isoliert sind oder in denen es redundante NB gibt. Es existieren mehrere unterschiedlich scharfe Formulierungen, welche die Erfüllung dieser CQ sicherstellen. Punkte, in denen die Anforderungen erfüllt sind, heißen regulär. Irreguläre Punkte, in denen keine dieser Anforderungen greift, müssen ausgeschlossen oder gesondert betrachtet werden.
Zentral für die Formulierung der Anforderungen an die NB und der Optimalitätsbedingungen ist der Begriff Tangentenkegel und Linearisierender Kegel. Um sich diese anschaulich klarzumachen, stellt man sich an einen Punkt im zulässigen Gebiet und läuft unter Beachtung der NB (die NB kann man sich als undurchdringliche Wände vorstellen) zum Zielpunkt . Der Tangentenkegel ist dann die Menge aller möglichen Richtungen, aus denen man im Zielpunkt ankommen kann. Beim linearisierenden Kegel werden zunächst die NB linearisiert, d. h. durch ihre Tangenten im Zielpunkt ersetzt. Der linearisierende Kegel ist dann die Menge aller möglichen Richtungen, aus denen man unter Beachtung der linearisierten NB im Zielpunkt ankommen kann. Der Tangentenkegel und Linearisierende Kegel unterscheiden sich dort, wo zwei Wände am Standort parallel verlaufen und der Zielpunkt sozusagen in einem Gang (der Breite 0) liegt. Im linearisierenden Kegel kann man dann aus beiden Richtungen des Gangs ankommen, er linearisierte ja die Wände. Wenn die zunächst parallelen Wände in einer Richtung unmittelbar ihre Parallelität verlieren und den Gang zumachen, so dass kein noch so kleiner Schritt in diese Richtung möglich ist, kann man im Tangentenkegel nur aus der offenen Richtung in ankommen. Das ist der Unterschied, siehe den ersten pathologischen Fall unten. In der Grafik stimmen Tangentenkegel und Linearisierender Kegel im optimalen Punkt überein und sind rot angedeutet.
Die Anforderungen an die NB stellen sicher, dass im optimalen Punkt der Tangentenkegel und der linearisierende Kegel übereinstimmen und der optimale Punkt nicht isoliert ist. Die Übereinstimmung von linearisierenden Kegel und Tangentialkegel wird manchmal auch als eigene Regularitätsbedingung aufgeführt und Abadie Constraint Qualification genannt. Beispiele für Regularitätsbedingungen sind:
Slater-Bedingung (nur für konvexe Probleme): Es gibt einen Punkt , so dass für alle und alle Gleichungsnebenbedingungen in erfüllt sind. An dieser Stelle sei erwähnt, dass die Constraint Qualification von Slater im Allgemeinen als die Wichtigste angesehen wird. Lineare Unabhängigkeit – (LICQ): Die Gradienten der aktiven Ungleichungsbedingungen und die Gradienten der Gleichungsbedingungen sind linear unabhängig im Punkt .