Fritz-John-Bedingungen

Die Fritz-John-Bedingungen (abgekürzt FJ-Bedingungen) sind in der Mathematik ein notwendiges Optimalitätskriterium erster Ordnung in der nichtlinearen Optimierung. Sie sind eine Verallgemeinerung der Karush-Kuhn-Tucker-Bedingungen und kommen im Gegensatz zu diesen ohne Regularitätsbedingungen aus. Benannt sind sie nach dem US-amerikanischen Mathematiker deutscher Abstammung, Fritz John.

Rahmenbedingungen

Die Fritz-John-Bedingungen ermöglichen Aussagen über ein Optimierungsproblem der Form

\min _{x\in D}f(x)

unter den Nebenbedingungen

g_{i}(x)\leq 0~,1\leq i\leq m

h_{j}(x)=0~,1\leq j\leq l

.

Dabei sind alle betrachteten Funktionen $f(x),g_{i}(x),h_{j}(x)\colon D\to \mathbb {R}$ stetig differenzierbar und $D$ ist eine nichtleere Teilmenge des $\mathbb {R} ^{n}$ .

Aussage

Ein Punkt $(z^{*},x^{*},\mu ^{*},\lambda ^{*})\in \mathbb {R} ^{1+n+m+l}$ heißt Fritz-John-Punkt oder kurz FJ-Punkt des obigen Optimierungsproblems, 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^{*})\leq 0,{\mbox{ für }}i=1,\ldots ,m

h_{j}(x^{*})=0,{\mbox{ für }}j=1,\ldots ,l\,\!

\mu _{i}^{*}\geq 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 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.

Somit sind die FJ-Bedingungen ein notwendiges Optimalitätskriterium erster Ordnung.

Beziehung zu den Karush-Kuhn-Tucker-Bedingungen

Für $z^{*}=1$ entsprechen die FJ-Bedingungen genau den Karush-Kuhn-Tucker-Bedingungen. Ist $(z^{*},x^{*},\mu ^{*},\lambda ^{*})$ ein FJ-Punkt, so ist auch $(sz^{*},x^{*},s\mu ^{*},s\lambda ^{*})$ mit $s>0$ ein FJ-Punkt. Somit kann man davon ausgehen, dass wenn $z^{*}>0$ ist, bereits ein KKT-Punkt vorliegt, dieser wird durch Reskalierung mit $z^{*}$ erzeugt. Dann ist $(x^{*},\mu ^{*}/z^{*},\lambda ^{*}/z^{*})$ der zu einem FJ-Punkt gehörende KKT-Punkt. Umgekehrt lassen sich nun die constraint qualifications der KKT-Bedingungen so interpretieren, dass sie für die FJ-Bedingungen $z^{*}>0$ garantieren.

Beispiele

FJ ohne KKT

Betrachte als Beispiel das Optimierungsproblem

\min _{x\in X}-x_{1}

mit Restriktionsmenge

X=\{x\in \mathbb {R} ^{2}\,|\,g_{1}(x)=-x_{2}\leq 0,\,g_{2}(x)=x_{2}+x_{1}^{5}\leq 0\}

.

Minimum des Problems ist der Punkt $x^{*}=(0,0)$ . Daher existiert ein FJ-Punkt $(z^{*},0,0,\mu _{1}^{*},\mu _{2}^{*})$ , so dass

z^{*}(-1,0)^{T}+\mu _{1}^{*}(0,-1)^{T}+\mu _{2}^{*}(0,1)^{T}=(0,0)^{T}

.

Daraus folgt direkt, dass $z^{*}=0,\,\mu _{1}^{*}=\mu _{2}^{*}>0$ für einen FJ-Punkt gilt.

Insbesondere gibt es keinen dazugehörigen KKT-Punkt. Setzt man $z^{*}=1$ , so ist das Gleichungssystem der Gradienten nicht lösbar. Tatsächlich ist im Punkt $x^{*}$ keine Regularitätsbedingung erfüllt, speziell nicht die allgemeinste, die Abadie CQ.

FJ und KKT

Betrachte als Beispiel das Optimierungsproblem

\min _{x\in X}-x_{2}+x_{1}^{2}

mit Restriktionsmenge

X=\{x\in \mathbb {R} ^{2}\,|\,g_{1}(x)=x_{1}+x_{2}-1\leq 0,\,g_{2}(x)=x_{1}^{2}+x_{2}^{2}-1\leq 0\}

.

Die Restriktionsmenge ist der Einheitskreis, bei dem am ersten Quadranten die Krümmung des Kreises entfernt wurde. Minimum des Problems ist der Punkt $x^{*}=(0,1)$ . Daher gibt es einen FJ-Punkt $(z^{*},0,1,\mu _{1}^{*},\mu _{2}^{*})$ , so dass

z^{*}(0,-1)^{T}+\mu _{1}^{*}(1,1)^{T}+\mu _{2}^{*}(0,2)^{T}=(0,0)^{T}

gilt. Eine Lösung wäre $z^{*}=2,\,\mu _{1}^{*}=0,\,\mu _{2}^{*}=1$ , was zu dem FJ-Punkt $(2,0,1,0,1)$ führt. Eine Reskalierung mit $z^{*}$ führt zu dem KKT-Punkt $(x^{*},\mu _{1}^{*}/z^{*},\mu _{2}^{*}/z^{*})=(0,1,0,1/2)$ . Tatsächlich ist im Punkt $x^{*}$ auch die LICQ erfüllt, deshalb gelten hier auch die KKT-Bedingungen.

Literatur

Florian Jarre, Josef Stoer: Optimierung. Springer, Berlin 2004, ISBN 3-540-43575-1.
C. Geiger, C. Kanzow: Theorie und Numerik restringierter Optimierungsaufgaben. Springer, 2002, ISBN 3-540-42790-2, books.google.de

Weblinks

Stephen Boyd, Lieven Vandenberghe: Convex Optimization. (PDF; englisch)

Einzelnachweise

↑ F. John: Extremum problems with inequalities as subsidiary conditions. In: Kurt Friedrichs, Otto Neugebauer, J. J. Stoker (Hrsg.): Studies and Essays. Courant Anniversary Volume, Wiley, 1948, S. 187–204, nachgedruckt in: Fritz John: Collected Papers. Birkhäuser 1985, S. 543–560

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] F. John: Extremum problems with inequalities as subsidiary conditions. In: Kurt Friedrichs, Otto Neugebauer, J. J. Stoker (Hrsg.): Studies and Essays. Courant Anniversary Volume, Wiley, 1948, S. 187–204, nachgedruckt in: Fritz John: Collected Papers. Birkhäuser 1985, S. 543–560