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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y} der Spaltenvektor der Lagrange Multiplikatoren:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y = ( \mu_1, ...,\mu_m, \nu_1,...,\nu_l )^\mathrm{T} \in Y = \{ y \in\mathbb{R}^{m+l}\mid y_i \ge 0\;\forall\;1\le i\le m \} } .

Fasst man auch die NB in einem Spaltenvektor Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle F} zusammen

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle F(x) := ( g_1, ...,g_m, h_1,...,h_l )^\mathrm{T}} ,

kann man die Lagrange Funktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L: \R^n \times Y \mapsto \R} kompakt als Matrixprodukt schreiben:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L( x, y ) := f(x) + y^\mathrm{T}F(x)} .

Sattelpunkt

Ein Punkt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (\bar{x},\bar{y})\in \R^n \times Y} heißt Sattelpunkt von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L} auf Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \R^n \times Y} , falls

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L(x,\bar{y})\ge L(\bar{x},\bar{y}) \ge L( \bar{x},y)} für alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x\in\R^n} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y \in Y} .

Beispiel

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

Minimiere

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(x)=(x-2)^2} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x\in K=[0,\infty)}

unter der Nebenbedingung:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g(x)= x^2 - 1 \leq 0}

Der zulässige Bereich ist gegeben durch die konvexe Menge

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \{x\in K:g(x)\leq 0\}=[0,1]} ,

denn für Werte größer 1 ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g(x) \leq 0} nicht erfüllt. Der Zeichnung kann entnommen werden, dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(x)} für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x = 1} den Optimalwert Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \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:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lambda \in [0,1] \Rightarrow f(x + \lambda (y-x)) \le f(x) + \lambda (f(y)-f(x)) \quad \forall x,y \in X} dann ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f} konvex,

oder

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lambda \in [0,1] \Rightarrow f(x + \lambda (y-x)) \ge f(x) + \lambda (f(y)-f(x)) \quad \forall x,y \in X} dann ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_i\,,\; i=1,...,n} optimal, dann sind alle Punkte „zwischen“ diesen Punkten optimal. Mathematisch:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \hat{x}} erfüllt sein müssen. Danach werden hinreichende Optimalitätsbedingungen formuliert. Diese zeigen, dass eine Lösung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \hat{x}} wirklich optimal ist.

Fritz-John-Bedingungen

Sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \hat{x}} optimal für das obige konvexe Programm. Dann gibt es Multiplikatoren Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lambda,~\mu_1,\ldots,\mu_m,~\nu_1,\ldots,\nu_l} , die nicht sämtlich den Wert Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 0} haben, mit den folgenden Eigenschaften:

• Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lambda,~\mu_1,\ldots,\mu_m\geq 0}
• Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g_i (\hat{x}) <0 \Rightarrow \mu_i=0~ , 1 \leq i \leq m} (Complementary slackness condition)
• Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x\in K}

Die Fritz-John-Bedingungen sind ein notwendiges Optimalitätskriterium. Für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lambda>0} sind sie hinreichend. In diesem Fall darf man sogar Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lambda=1} setzen. Die complementary slackness condition wird im Deutschen auch Bedingung vom komplementären Schlupf genannt. Hierbei kann man beweisen, dass falls Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g_i (\hat{x}) <0} für alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1 \leq i \leq m} gilt, dass dann alle Multiplikatoren Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mu_i=0} für alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lambda \ne 0} . Sie fordert: Es gibt es einen Punkt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tilde{x}\in K} , so dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g_i (\tilde{x})<0} für alle nicht linearen Funktionen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g_i} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \nabla f(x) = 0} von Optimierungsproblemen ohne Nebenbedingungen..

Sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f:K\rightarrow\R} die Zielfunktion und die konvexen Funktionen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g_i :K\rightarrow\R} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1 \leq i \leq m} und die affinen Funktionen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle h_j :K\rightarrow\R} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1 \leq j \leq l} sind einmal differenzierbare Nebenbedingungs-Funktionen. Es sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \hat{x}} ein zulässiger Punkt in dem die Slater-Bedingung zutrifft. Falls Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \hat{x}} ein lokales Minimum ist, dann existieren Konstanten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lambda \ge 0} , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mu_i \ge 0} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1 \leq i \leq m} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \!\nu_j} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1 \leq j \leq l,} so dass

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \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} ,

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g_i (\bar{x})\le 0\,,\; \mu_i \ge 0\,,\;\mu_i g_i (\bar{x}) = 0 } für alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1 \leq i \leq m} ,

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle h_j(\bar{x}) = 0} für alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1 \le j \leq l} .

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

Ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \bar{x}} ein innerer Punkt des zulässigen Gebietes, in dem also keine NB aktiv sind, insbesondere keine Gleichheitsnebenbedingungen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle h_j(x)=0} vorliegen, dann sind wegen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g_i(\bar{x})<0} alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mu_i = 0} und die obigen Bedingungen reduzieren sich auf die bekannte notwendige Bedingung unrestringierter Probleme Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \nabla f(\bar{x}) = 0} .

Hinreichende Bedingungen

Sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f:K\rightarrow\R} die Zielfunktion und die konvexen Funktionen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g_i :K\rightarrow\R} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1 \leq i \leq m} und die affinen Funktionen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle h_j :K\rightarrow\R} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1 \leq j \leq l} sind Nebenbedingungs-Funktionen. Es sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \hat{x}} ein zulässiger Punkt, das heißt es gilt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \hat{x} \in K} . Des Weiteren nimmt man an, dass die aktiven Gradienten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \nabla g_i(\hat{x})} und die Gradienten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \nabla h_j(\hat{x})} linear unabhängig sind. Falls Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \hat{x}} ein lokales Minimum ist, dann existieren Konstanten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lambda \ge 0} , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mu_i \ge 0} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1 \leq i \leq m} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \nu_j} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1 \leq j \leq l,} so dass

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \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 }

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mu_i g_i (\hat{x}) = 0 } für alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1 \leq i \leq m}

dann ist der Punkt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \hat{x}} ein globales Minimum.

Konkretes Vorgehen

Lagrange-Funktion

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

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L(x,\lambda)=f(x)+\sum_{i=1}^m \mu_i g_i(x)+\sum_{j=1}^l \nu_j h_j(x)} ,

wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \hat{x}} , für den gilt: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \nabla f(\hat{x})=0} ? Falls ja, dann ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \hat{x}} optimal. Sonst fahre mit dem nächsten Schritt fort.
• Bestimme den Gradienten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \nabla_x L(x,\lambda)} der Lagrange-Funktion.
• Löse das System Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 0} sein. Findet man eine Lösung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \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