Konvexe Optimierung

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Die konvexe Optimierung ist ein Teilgebiet der mathematischen Optimierung.

Es ist eine bestimmte Größe zu minimieren, die sogenannte Zielfunktion, welche von einem Parameter, welcher mit x bezeichnet wird, abhängt. Außerdem sind bestimmte Nebenbedingungen einzuhalten, das heißt, die Werte x, die man wählen darf, sind gewissen Einschränkungen unterworfen. Diese sind meist in Form von Gleichungen und Ungleichungen gegeben. Sind für einen Wert x alle Nebenbedingungen eingehalten, so sagt man, dass x zulässig ist. Man spricht von einem konvexen Optimierungsproblem oder einem konvexen Programm, falls sowohl die Zielfunktion als auch die Menge der zulässigen Punkte konvex ist. Viele Probleme der Praxis sind konvexer Natur. Oft wird zum Beispiel auf Quadern optimiert, welche stets konvex sind, und als Zielfunktion finden oft quadratische Formen Verwendung, die unter bestimmten Voraussetzungen ebenfalls konvex sind (siehe Definitheit). Ein anderer wichtiger Spezialfall ist die Lineare Optimierung, bei der eine lineare Zielfunktion über einem konvexen Polyeder optimiert wird.

Eine wichtige Eigenschaft der konvexen Optimierung im Unterschied zur nicht-konvexen Optimierung ist, dass jedes lokale Optimum auch ein globales Optimum ist. Anschaulich bedeutet dies, dass eine Lösung, die mindestens so gut ist wie alle anderen Lösungen in einer Umgebung, auch mindestens so gut ist wie alle zulässigen Lösungen. Dies erlaubt es, einfach nach lokalen Optima zu suchen.

Einleitung[Bearbeiten]

Es gibt viele mögliche Formulierungen eines konvexen Programms. An dieser Stelle soll eine möglichst allgemeine Form gewählt werden. Der Eingabeparameter x sei aus dem \R^n, das heißt, das Problem hängt von n Einflussparametern ab. Die Zielfunktion f:K\rightarrow\R sei konvex. Weiterhin seien die konvexen Funktionen g_i :K\rightarrow\R mit 1 \leq i \leq m und die affinen Funktionen h_j :K\rightarrow\R mit 1 \leq j \leq l gegeben. Hierbei ist K eine konvexe Teilmenge des \R^n.

Konvexes Programm:

Minimiere f(x) mit x\in K unter den Nebenbedingungen

g_i (x)\leq 0  ~ ,1 \leq i \leq m
h_j (x) = 0  ~, 1 \leq j \leq l

Eine Restriktion mit g_i (x)= 0 bezeichnet man als aktiv. Die Funktionen g_i stellen die sogenannten Ungleichungsnebenbedingungen und die Funktionen h_j stellen die sogenannten Gleichungsnebenbedingungen dar.

Geschichte[Bearbeiten]

Carl Friedrich Gauß

Die Disziplin der konvexen Optimierung entstand unter anderem aus der konvexen Analysis. Die erste Optimierungs-Technik, welche als Gradientenverfahren bekannt ist, geht auf Gauß zurück. Im Jahre 1947 wurde das Simplex-Verfahren durch George Dantzig eingeführt. Des Weiteren wurden im Jahr 1968 erstmals Innere-Punkte-Verfahren durch Fiacco und McCormick vorgestellt. In den Jahren 1976 und 1977 wurde die Ellipsoid-Methode von David Yudin und Arkadi Nemirovski und unabhängig davon von Naum Schor zur Lösung konvexer Optimierungsprobleme entwickelt. Narendra Karmarkar beschrieb im Jahr 1984 zum ersten Mal einen polynomialen potentiell praktisch einsetzbaren Algorithmus für lineare Probleme. Im Jahr 1994 entwickelten Arkadi Nemirovski und Yurii Nesterov Innere-Punkte-Verfahren für die konvexe Optimierung, welche große Klassen von konvexen Optimierungsproblemen in polynomialer Zeit lösen konnten.

Bei den Karush-Kuhn-Tucker-Bedingungen wurden die notwendigen Bedingungen für die Ungleichheits-Einschränkung zum ersten Mal 1939 in der Master-Arbeit (unveröffentlicht) von William Karush aufgeführt. Bekannter wurden diese jedoch erst 1951 nach einem Konferenz-Paper von Harold W. Kuhn und Albert W. Tucker.

Vor 1990 lag die Anwendung der konvexen Optimierung hauptsächlich im Operations Research und weniger im Bereich der Ingenieure. Seit 1990 boten sich jedoch immer mehr Anwendungsmöglichkeiten in der Ingenieurwissenschaft. Hier lässt sich unter anderem die Kontroll- und Signal-Steuerung, die Kommunikation und der Schaltungsentwurf nennen. Außerdem entstanden neue Problemklassen wie semidefinite und Kegel-Optimierung 2. Ordnung und robuste Optimierung.

Beispiel[Bearbeiten]

Konvexes Optimierungsproblem

Als Beispiel wird ein eindimensionales Problem ohne Gleichungsnebenbedingungen und mit nur einer Ungleichungsnebenbedingung betrachtet:

Minimiere

f(x)=(x-2)^2 mit x\in K=[0,\infty)

unter der Nebenbedingung:

g(x)= x^2 - 1 \leq 0

Der zulässige Bereich ist gegeben durch die konvexe Menge

\{x\in K:g(x)\leq 0\}=[0,1],

denn für Werte x > 1 ist g(x) \leq 0 nicht erfüllt. Der Zeichnung kann entnommen werden, dass f(x) für x = 1 den Optimalwert 1 annimmt.

Optimalitätsbedingungen[Bearbeiten]

Für konvexe Probleme gibt es einige wichtige Optimalitätskriterien. Zuerst werden die notwendigen Kriterien beschrieben, das heißt, wenn ein Optimum erreicht wird, dann sind diese Kriterien erfüllt. Danach die hinreichenden Kriterien, dass heißt wenn diese Kriterien in einem Punkt erfüllt sind, dann handelt es sich um einen Optimalpunkt.

Notwendige Kriterien[Bearbeiten]

Karush-Kuhn-Tucker-Bedingungen[Bearbeiten]

Die Karush-Kuhn-Tucker-Bedingungen (auch bekannt als die KKT-Bedingungen) sind eine Verallgemeinerung der Lagrange-Multiplikatoren von Optimierungsproblemen unter Nebenbedingungen und finden in der fortgeschrittenen neoklassischen Theorie Anwendung. Ein zulässiger Punkt  x^* des konvexen Problem erfüllt die KKT-Bedingungen, wenn gilt

\nabla f(x^*) + \sum_{i=1}^m \mu^*_i \nabla g_i(x^*) + \sum_{j=1}^l \lambda^*_j \nabla h_j(x^*)=0
g_i(x^*) \le 0, \mbox{ für } i = 1, \ldots, m
h_j(x^*) = 0, \mbox{ für } j = 1, \ldots, l \,\!
\mu^*_i \ge 0, \mbox{ für } i = 1, \ldots, m
\mu^*_i g_i (x^*) = 0, \mbox{für }\; i = 1,\ldots,m.

Diese Bedingungen werden die Karush-Kahn-Tucker-Bedingungen oder kurz KKT-Bedingungen genannt.

Ein Punkt  (x^*, \mu^*, \lambda^*) \in \mathbb{R}^{n+m+l} heißt dann Karush-Kuhn-Tucker-Punkt oder kurz KKT-Punkt des obigen Optimierungsproblems, wenn er die obigen Bedingungen erfüllt.

Das eigentliche notwendige Optimalitätskriterium lautet nun: Ist ein Punkt  x^* ein lokales (und aufgrund der konvexität auch globales) Minimum des konvexen Problems, und erfüllt er gewisse Regularitätsvorraussetzungen, so gibt es  \mu^*, \lambda^* , so dass  (x^*, \mu^*, \lambda^*) ein KKT-Punkt ist. Gängige Regularitätsbedingungen (auch constraint qualifications genannt) sind die LICQ, die MFCQ, die Abadie CQ oder speziell für konvexe Probleme die Slater-Bedingung. Mehr Regularitätsvorraussetzungen finden sich im Hauptartikel zu den KKT-Bedingungen.

Fritz-John-Bedingungen[Bearbeiten]

Hauptartikel: Fritz-John-Bedingungen

Die Fritz-John-Bedingungen oder FJ-Bedingungen sind eine Verallgemeinerung der KKT-Bedingungen und kommen im Gegensatz zu diesen ohne Regularitätsvorraussetzungen aus. Unter gewissen Umständen sind beide Bedingungen Äquivalent. Ein Punkt  (z^*,x^*, \mu^*, \lambda^*) \in \mathbb{R}^{1+n+m+l} heißt Fritz-John-Punkt oder kurz FJ-Punkt des konvexen Problems, wenn er die folgenden Bedingungen erfüllt:

z^*\nabla f(x^*) + \sum_{i=1}^m \mu^*_i \nabla g_i(x^*) + \sum_{j=1}^l \lambda^*_j \nabla h_j(x^*)=0
g_i(x^*) \le 0, \mbox{ für } i = 1, \ldots, m
h_j(x^*) = 0, \mbox{ für } j = 1, \ldots, l \,\!
\mu^*_i \ge 0, \mbox{ für } i = 1, \ldots, m
\mu^*_i g_i (x^*) = 0, \mbox{für }\; i = 1,\ldots,m.
 z^* \geq 0

Diese Bedingungen werden die Fritz-John-Bedingungen oder kurz FJ-Bedingungen genannt.

Ist der Punkt  x^* lokales (und aufgrund der konvexität auch globales) Minimum des Optimierungsproblems, so gibt es  \mu^*, \lambda^*,z^* , so dass  (z^*,x^*, \mu^*, \lambda^*) ein FJ-Punkt ist und  (z^*, \mu^*, \lambda^*) ungleich dem Nullvektor ist.

Hinreichende Kriterien[Bearbeiten]

Ist  (x^*, \mu^*, \lambda^*) ein KKT-Punkt, so ist  x^* ein globales Minimum des konvexen Problems. Somit sind die KKT-Bedingungen im konvexen Fall schon hinreichend für die Optimalität des Punktes. Insbesondere werden dazu keine weiteren Regularitätsvorraussetzungen benötigt. Da sich zeigen lässt, dass man aus jedem FJ-Punkt einen KKT-Punkt konstruieren kann, wenn  z^*>0 ist, sind auch schon die FJ-Bedingungen hinreichend für die Optimalität, wenn  z^*>0 gilt.

Konkretes Vorgehen[Bearbeiten]

Lagrange-Funktion[Bearbeiten]

Zunächst wird die folgende abkürzende Schreibweise eingeführt:

L(x,\lambda)=f(x)+\sum_{i=1}^m \mu_i g_i(x)+\sum_{j=1}^l \nu_j h_j(x),

wobei \lambda der Vektor aus allen Multiplikatoren ist.

Lagrangesche Multiplikatorenregel für das konvexe Problem[Bearbeiten]

Vergleiche hierzu auch mit Lagrangesche Multiplikatorenregel. Konkretes Vorgehen:

  • Überprüfe, ob alle auftretenden Funktionen stetig partiell differenzierbar sind. Falls nein, ist diese Regel nicht anwendbar.
  • Gibt es einen zulässigen Punkt \hat{x}, für den gilt: \nabla f(\hat{x})=0? Falls ja, dann ist \hat{x} optimal. Sonst fahre mit dem nächsten Schritt fort.
  • Bestimme den Gradienten \nabla_x L(x,\lambda) der Lagrange-Funktion.
  • Löse das System \nabla_x L(x,\lambda)(x-\hat{x})\geq 0~(x\in K), wobei kein Multiplikator negativ sein darf. Falls eine Restriktion nicht aktiv ist, muss der zugehörige Multiplikator sogar gleich 0 sein. Findet man eine Lösung \hat{x}, so ist diese optimal.

Literatur[Bearbeiten]

  • Avriel, Mordecai: Nonlinear Programming: Analysis and Methods. Dover Publishing, 2003, ISBN 0-486-43227-0.
  • R. Andreani, J. M. Martínez, M. L. Schuverdt: On the relation between constant positive linear dependence condition and quasinormality constraint qualification. Journal of optimization theory and applications, vol. 125, no2, 2005, pp. 473–485.
  • Florian Jarre, Josef Stoer: Optimierung. Springer, Berlin 2003, ISBN 3-540-43575-1.

Weblinks[Bearbeiten]