Benutzer:Alva2004/KonvexeOptimierung

Dieser Artikel ist im Entstehen und noch nicht Bestandteil der freien Enzyklopädie Wikipedia.

Solltest du über eine Suchmaschine darauf gestoVorlage:SSen sein, bedenke, dass der Text noch unvollständig sein und Fehler oder ungeprüfte Aussagen enthalten kann. Wenn du Fragen zum Thema hast, nimm Kontakt mit dem Autor Alva2004 auf.

Die konvexe Optimierung ist ein Teilgebiet der mathematischen Optimierung und nichtlinearen 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.

Geschichte

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.

Definitionen

Konvexes Programm

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 $\mathbb {R} ^{n}$, das heißt das Problem hängt von $n$ Einflussparametern ab die im Vektor $x$ eingelagert sind. Die Zielfunktion $f:K\rightarrow \mathbb {R}$ sei konvex. Weiterhin seien die konvexen Funktionen $g_{i}:K\rightarrow \mathbb {R}$ mit $1\leq i\leq m$ und die affinen Funktionen $h_{j}:K\rightarrow \mathbb {R}$ mit $1\leq j\leq l$ gegeben. Hierbei ist $K$ eine konvexe Teilmenge des $\mathbb {R} ^{n}$.

Konvexes Programm:

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

$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.

Lagrange Funktion

Die Lösung wird erreicht, indem das Problem auf die Optimierung der zugehörigen Lagrange Funktion ohne NB zurück geführt wird. Die Lagrange Funktion lautet:

$L(x,y):=f(x)+\sum _{i=1}^{m}\mu _{i}g_{i}(x)+\sum _{j=1}^{l}\nu _{j}h_{j}(x)$

Darin ist $y$ der Spaltenvektor der Lagrange Multiplikatoren:

$y=(\mu _{1},...,\mu _{m},\nu _{1},...,\nu _{l})^{\mathrm {T} }\in Y=\{y\in \mathbb {R} ^{m+l}\mid y_{i}\geq 0\;\forall \;1\leq i\leq m\}$.

Fasst man auch die NB in einem Spaltenvektor $F$ zusammen

$F(x):=(g_{1},...,g_{m},h_{1},...,h_{l})^{\mathrm {T} }$,

kann man die Lagrange Funktion $L:\mathbb {R} ^{n}\times Y\mapsto \mathbb {R}$ kompakt als Matrixprodukt schreiben:

$L(x,y):=f(x)+y^{\mathrm {T} }F(x)$.

Sattelpunkt

Ein Punkt $({\bar {x}},{\bar {y}})\in \mathbb {R} ^{n}\times Y$ heißt Sattelpunkt von $L$ auf $\mathbb {R} ^{n}\times Y$, falls

$L(x,{\bar {y}})\geq L({\bar {x}},{\bar {y}})\geq L({\bar {x}},y)$ für alle $x\in \mathbb {R} ^{n}$ und $y\in Y$.

Beispiel

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 größer 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.

Konvexität

Bei einem konvexen Gebiet liegen alle Punkte auf der Verbindungslinie zweier beliebiger Punkte im Gebiet ebenfalls vollständig im Gebiet. Mathematisch:

$\lambda \in [0,1]\Rightarrow x+\lambda (y-x)\in X\quad \forall x,y\in X$

Beispiele für konvexe Gebiete sind Kreise, Ellipsen, Dreiecke und Quadrate.

Die Zielfunktion ist konvex, wenn alle Werte der Zielfunktion von Punkten auf der Geraden, die zwei Punkte im Gebiet verbinden, unter dieser Geraden liegen und konkav, wenn alle Punkte über dieser Geraden liegen. Mathematisch:

$\lambda \in [0,1]\Rightarrow f(x+\lambda (y-x))\leq f(x)+\lambda (f(y)-f(x))\quad \forall x,y\in X$ dann ist $f$ konvex,

oder

$\lambda \in [0,1]\Rightarrow f(x+\lambda (y-x))\geq f(x)+\lambda (f(y)-f(x))\quad \forall x,y\in X$dann ist $f$ konkav.

Die zu Beginn dieses Artikels gezeigte parabelförmige Optimierungsaufgabe hat eine konvexe Zielfunktion.

Bei konvexen Problemen ist jedes Optimum auch globales Optimum. Sind die Punkte $x_{i}\,,\;i=1,...,n$ optimal, dann sind alle Punkte „zwischen“ diesen Punkten optimal. Mathematisch:

$\alpha _{1},\alpha _{2},...,\alpha _{n}\in [0,1]\;\wedge \;\sum _{i=1}^{n}\alpha _{i}=1\quad \Rightarrow \quad f\left(\sum _{i=1}^{n}\alpha _{i}x_{i}\right)=f_{\text{opt}}$

Optimalitätsbedingungen

Zunächst werden notwendige Optimalitätsbedingungen vorgestellt. Dies sind Kriterien, die auf jeden Fall im Optimum ${\hat {x}}$ erfüllt sein müssen. Danach werden hinreichende Optimalitätsbedingungen formuliert. Diese zeigen, dass eine Lösung ${\hat {x}}$ wirklich optimal ist.

Fritz-John-Bedingungen

Sei ${\hat {x}}$ optimal für das obige konvexe Programm. Dann gibt es Multiplikatoren $\lambda ,~\mu _{1},\ldots ,\mu _{m},~\nu _{1},\ldots ,\nu _{l}$, die nicht sämtlich den Wert $0$ haben, mit den folgenden Eigenschaften:

• $\lambda ,~\mu _{1},\ldots ,\mu _{m}\geq 0$
• $g_{i}({\hat {x}})<0\Rightarrow \mu _{i}=0~,1\leq i\leq m$ (Complementary slackness condition)
• $\lambda f({\hat {x}})+\sum _{i=1}^{m}\mu _{i}g_{i}({\hat {x}})+\sum _{j=1}^{l}\nu _{j}h_{j}({\hat {x}})\leq \lambda f(x)+\sum _{i=1}^{m}\mu _{i}g_{i}(x)+\sum _{j=1}^{l}\nu _{j}h_{j}(x)$ für alle $x\in K$

Die Fritz-John-Bedingungen sind ein notwendiges Optimalitätskriterium. Für $\lambda >0$ sind sie hinreichend. In diesem Fall darf man sogar $\lambda =1$ setzen. Die complementary slackness condition wird im Deutschen auch Bedingung vom komplementären Schlupf genannt. Hierbei kann man beweisen, dass falls $g_{i}({\hat {x}})<0$ für alle $1\leq i\leq m$ gilt, dass dann alle Multiplikatoren $\mu _{i}=0$ für alle $1\leq i\leq m$ sein müssen. Diese Bedingung ist somit für den Aufbau und den Entwurf von Algorithmen von hoher Bedeutung.

Regularitäts-Bedingung von Slater

Für die obige notwendige Bedingung darf das duale Skalar $\lambda$ gleich Null sein. In solchen Fällen spricht man von degeneriert oder abnormal. Dann spielt die notwendige Bedingung keine Rolle für die Eigenschaften der Funktion, nur die Geometrie der Nebenbedingungen ist relevant.

Die Bedingung von Slater stellt sicher, dass die Lösung nicht-degeneriert ist, das heißt $\lambda \neq 0$. Sie fordert: Es gibt es einen Punkt ${\tilde {x}}\in K$, so dass $g_{i}({\tilde {x}})<0$ für alle nicht linearen Funktionen $g_{i}$ mit $1\leq i\leq m$.

Karush-Kuhn-Tucker-Bedingungen

Die Karush-Kuhn-Tucker-Bedingungen (auch bekannt als die KKT-Bedingungen) sind notwendig für die Optimalität einer Lösung in der nichtlinearen Optimierung. Sie sind die Verallgemeinerung der notwendigen Bedingung $\nabla f(x)=0$ von Optimierungsproblemen ohne Nebenbedingungen..

Sei $f:K\rightarrow \mathbb {R}$ die Zielfunktion und die konvexen Funktionen $g_{i}:K\rightarrow \mathbb {R}$ mit $1\leq i\leq m$ und die affinen Funktionen $h_{j}:K\rightarrow \mathbb {R}$ mit $1\leq j\leq l$ sind einmal differenzierbare Nebenbedingungs-Funktionen. Es sei ${\hat {x}}$ ein zulässiger Punkt in dem die Slater-Bedingung zutrifft. Falls ${\hat {x}}$ ein lokales Minimum ist, dann existieren Konstanten $\lambda \geq 0$, $\mu _{i}\geq 0$ mit $1\leq i\leq m$ und $\!\nu _{j}$ mit $1\leq j\leq l,$ so dass

$\nabla f({\bar {x}})+\sum _{i=1}^{m}\mu _{i}\nabla g_{i}({\bar {x}})+\sum _{j=1}^{l}\nu _{j}\nabla h_{j}({\bar {x}})=0$,

$g_{i}({\bar {x}})\leq 0\,,\;\mu _{i}\geq 0\,,\;\mu _{i}g_{i}({\bar {x}})=0$ für alle $1\leq i\leq m$,

$h_{j}({\bar {x}})=0$ für alle $1\leq j\leq l$.

Jeder Punkt, in dem diese Bedingungen erfüllt sind, heißt Karush-Kuhn-Tucker-Punkt ( kurz: KKT-Punkt).

Ist ${\bar {x}}$ ein innerer Punkt des zulässigen Gebietes, in dem also keine NB aktiv sind, insbesondere keine Gleichheitsnebenbedingungen $h_{j}(x)=0$ vorliegen, dann sind wegen $g_{i}({\bar {x}})<0$ alle $\mu _{i}=0$ und die obigen Bedingungen reduzieren sich auf die bekannte notwendige Bedingung unrestringierter Probleme $\nabla f({\bar {x}})=0$.

Hinreichende Bedingungen

Sei $f:K\rightarrow \mathbb {R}$ die Zielfunktion und die konvexen Funktionen $g_{i}:K\rightarrow \mathbb {R}$ mit $1\leq i\leq m$ und die affinen Funktionen $h_{j}:K\rightarrow \mathbb {R}$ mit $1\leq j\leq l$ sind Nebenbedingungs-Funktionen. Es sei ${\hat {x}}$ ein zulässiger Punkt, das heißt es gilt ${\hat {x}}\in K$. Des Weiteren nimmt man an, dass die aktiven Gradienten $\nabla g_{i}({\hat {x}})$ und die Gradienten $\nabla h_{j}({\hat {x}})$ linear unabhängig sind. Falls ${\hat {x}}$ ein lokales Minimum ist, dann existieren Konstanten $\lambda \geq 0$, $\mu _{i}\geq 0$ mit $1\leq i\leq m$ und $\nu _{j}$ mit $1\leq j\leq l,$ so dass

$\nabla f({\hat {x}})+\sum _{i=1}^{m}\mu _{i}\nabla g_{i}({\hat {x}})+\sum _{j=1}^{l}\nu _{j}\nabla h_{j}({\hat {x}})=0$

$\mu _{i}g_{i}({\hat {x}})=0$ für alle $1\leq i\leq m$

dann ist der Punkt ${\hat {x}}$ ein globales Minimum.

Konkretes Vorgehen

Lagrange-Funktion

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

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

• 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

• Buch Convex Optimization von Stephen Boyd und Lieven Vandenberghe im pdf-Format (engl.)

Kategorie:Optimierung