Kuhn-Tucker-Bedingungen

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, d.h. 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

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$, d.h. 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

Carl Friedrich Gauß

Die Disziplin der konvexen Optimierung entstand unter anderem aus der konvexen Analysis. Die erste Optimierungs-Technik, welche als Verfahren des steilsten Abstiegs 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 Shor 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 in der Master-Arbeit von W. Karush veröffentlicht. Bekannter wurden diese jedoch erst 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

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

Minimiere f(x) = (x − 1)² 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]$.

Der Zeichnung entnimmt man, dass für x = 1 der Optimalwert 0 angenommen wird.

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 λ > 0 sind sie hinreichend. In diesem Fall darf man sogar λ = 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 μ_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.

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 Lagrange-Multiplikatoren für die dynamische Optimierung und finden in der fortgeschrittenen neoklassischen Theorie Anwendung.

Notwendige Bedingungen

Sei $f:K\rightarrow\R$ die Zielfunktion und 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$ sind Nebenbedingungs-Funktionen. Es sei $\hat{x}$ ein zulässiger Punkt, d.h. es gilt $\hat{x} \in K$. Des Weiteren nimmt man an, dass die aktiven Funktionen g_i differenzierbar im Punkt $\hat{x}$ sind, die Funktionen h_j sind stetig differenzierbar im Punkt $\hat{x} \in K$. Falls $\hat{x}$ ein lokales Minimum ist, dann existieren Konstanten $\lambda \ge 0$, $\mu_i \ge 0$ mit $1 \leq i \leq m$ und ν_j mit $1 \leq j \leq l,$ so dass

$\lambda + \sum_{i=1}^m \mu_i + \sum_{j=1}^l |\nu_j| > 0,$

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

Außerdem gilt

$f(\hat{x})+\sum_{i=1}^m \mu_i g_i(\hat{x}) \leq f(x)+\sum_{i=1}^m \mu_i g_i(x)$ für alle $x\in K$

und die Komplementaritätsbedingung ist erfüllt:

$g_i (\hat{x}) <0 \Rightarrow \mu_i=0~ , 1 \leq i \leq m$

Regularitäts-Bedingungen

Für die obige notwendige Bedingung darf das duale Skalar λ 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.

Es existieren mehrere Bedingungen, welche sicherstellen sollen, dass die Lösung nicht-degeneriert ist, d.h. $\lambda \ne 0$. Diese werden Constraint Qualifications genannt.

Hinreichende Bedingungen

Sei $f:K\rightarrow\R$ die Zielfunktion und 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$ sind Nebenbedingungs-Funktionen. Es sei $\hat{x}$ ein zulässiger Punkt, d.h. 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 \ge 0$, $\mu_i \ge 0$ mit $1 \leq i \leq m$ und ν_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.

Constraint Qualifications

Ein Kriterium, welches sicherstellt, dass λ > 0 gilt, nennt man Constraint Qualification. Mit anderen Worten, eine Bedingung, die sicherstellt, dass die Fritz-John-Bedingungen auch die Karush-Kuhn-Tucker-Bedingungen erfüllen, nennt man Constraint Qualification.

Beispiele für Constraint Qualifications sind:

• Slater: Es treten keine Gleichungsnebenbedingungen auf. Des weiteren gibt es einen Punkt $\tilde{x}\in K$, so dass $g_i (\tilde{x})<0$ für alle $1 \leq i \leq m$. An dieser Stelle sei erwähnt, dass die Constraint Qualification von Slater im Allgemeinen als die wichtigste angesehen wird.
• Lineare Unabhängigkeit - Linear independence constraint qualification (LICQ): Die Gradienten der aktiven Ungleichungsbedingungen und die Gradienten der Gleichungsbedingungen sind linear unabhängig im Punkt $\hat{x}$.
• Mangasarian-Fromowitz - Mangasarian-Fromowitz constraint qualification (MFCQ): Die Gradienten der aktiven Ungleichungsbedingungen und die Gradienten der Gleichungsbedingungen sind positiv-linear unabhängig im Punkt $\hat{x}$.
• Konstanter Rang - Constant rank constraint qualification (CRCQ): Für jede Untermenge der Gradienten der Ungleichungsbedingungen, welche aktiv sind, und der Gradienten der Gleichungsbedingungen ist der Rang in der Nähe von $\hat{x}$ konstant.
• Konstante positive-lineare Abhängigkeit - Constant positive-linear dependence constraint qualification (CPLD): Für jede Untermenge der Gradienten, der Ungleichungsbedingungen, welche aktiv sind, und der Gradienten der Gleichungsbedingungen, und falls eine positive-lineare Abhängigkeit im Punkt $\hat{x}$ vorliegt, dann gibt es eine positiv-lineare Abhängigkeit in der Nähe von $\hat{x}$.

Man kann zeigen, dass die folgenden beiden Folgerungsstränge gelten

$\mbox{LICQ} \Rightarrow \mbox{MFCQ} \Rightarrow \mbox{CPLD}$ und $\mbox{LICQ} \Rightarrow \mbox{CRCQ} \Rightarrow \mbox{CPLD}$,

obwohl MFCQ nicht äquivalent zu CRCQ ist. In der Praxis werden schwächere Constraint Qualifications bevorzugt, da diese stärkere Optimalitäts-Bedingungen liefern.

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 λ 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 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.
• F. Jarre, J. Stoer: Optimierung. Springer, Berlin 2003, ISBN 3-540-43575-1.

Weblinks

• Skript zur Vorlesung Algorithmentechnik mit einem Kapitel zu konvexer Optimierung
• Buch Convex Optimization von Stephen Boyd und Lieven Vandenberghe im pdf-Format (engl.)