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 {\displaystyle 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 {\displaystyle z^{*}=1} entsprechen die FJ-Bedingungen genau den Karush-Kuhn-Tucker-Bedingungen. Ist (z^{*},x^{*},\mu ^{*},\lambda ^{*}) ein FJ-Punkt, so ist auch {\displaystyle (sz^{*},x^{*},s\mu ^{*},s\lambda ^{*})} mit {\displaystyle s>0} ein FJ-Punkt. Somit kann man davon ausgehen, dass wenn {\displaystyle z^{*}>0} ist, bereits ein KKT-Punkt vorliegt, dieser wird durch Reskalierung mit {\displaystyle z^{*}} erzeugt. Dann ist {\displaystyle (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

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

mit Restriktionsmenge

{\displaystyle 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 {\displaystyle x^{*}=(0,0)}. Daher existiert ein FJ-Punkt {\displaystyle (z^{*},0,0,\mu _{1}^{*},\mu _{2}^{*})}, so dass

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

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

Insbesondere gibt es keinen dazugehörigen KKT-Punkt. Setzt man {\displaystyle 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

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

mit Restriktionsmenge

{\displaystyle 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 {\displaystyle x^{*}=(0,1)}. Daher gibt es einen FJ-Punkt {\displaystyle (z^{*},0,1,\mu _{1}^{*},\mu _{2}^{*})}, so dass

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

gilt. Eine Lösung wäre {\displaystyle z^{*}=2,\,\mu _{1}^{*}=0,\,\mu _{2}^{*}=1}, was zu dem FJ-Punkt {\displaystyle (2,0,1,0,1)} führt. Eine Reskalierung mit {\displaystyle z^{*}} führt zu dem KKT-Punkt {\displaystyle (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.

Verwandte Konzepte

Für konvexe Optimierungsprobleme, bei denen die Funktionen nicht stetig differenzierbar sind, gibt es die Sattelpunktkriterien der Lagrange-Funktion. Sind alle beteiligten Funktionen stetig differenzierbar, so sind sie strukturell ähnlich den Fritz-John-Bedingungen und äquivalent zu den KKT-Bedingungen.

Literatur

Trenner
Basierend auf einem Artikel in: Wikipedia.de
Seitenende
Seite zurück
©  biancahoegel.de
Datum der letzten Änderung: Jena, den: 05.04. 2020