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

$\underset{x\in D}{\min }f(x)$

unter den Nebenbedingungen

$g_i(x)\le 0,1\le i\le m$

$h_j(x)=0,1\le j\le l$.

Dabei sind alle betrachteten Funktionen $f(x),g_i(x),h_j(x):D\to ℝ$ stetig differenzierbar und $D$ ist eine nichtleere Teilmenge des ${ℝ}^n$.

Aussage

Ein Punkt $(z^{\ast },x^{\ast },{\mu }^{\ast },{\lambda }^{\ast })\in {ℝ}^{1+n+m+l}$ heißt Fritz-John-Punkt oder kurz FJ-Punkt des obigen Optimierungsproblems, wenn er die folgenden Bedingungen erfüllt:

$z^{\ast }\mathrm{\nabla }f(x^{\ast })+\sum _{i=1}^m{\mu }_i^{\ast }\mathrm{\nabla }{g}_i(x^{\ast })+\sum _{j=1}^l{\lambda }_j^{\ast }\mathrm{\nabla }{h}_j(x^{\ast })=0$

$g_i(x^{\ast })\le 0,\text{ für }i=1,\dots ,m$

$h_j(x^{\ast })=0,\text{ für }j=1,\dots ,l$

${\mu }_i^{\ast }\ge 0,\text{ für }i=1,\dots ,m$

${\mu }_i^{\ast }{g}_i(x^{\ast })=0,\text{für }i=1,\dots ,m.$

$z^{\ast }\ge 0$

Diese Bedingungen werden die Fritz-John-Bedingungen oder kurz FJ-Bedingungen genannt.

Ist der Punkt $x^{\ast }$ lokales Minimum des Optimierungsproblems, so gibt es ${\mu }^{\ast },{\lambda }^{\ast },z^{\ast }$, so dass $(z^{\ast },x^{\ast },{\mu }^{\ast },{\lambda }^{\ast })$ ein FJ-Punkt ist und $(z^{\ast },{\mu }^{\ast },{\lambda }^{\ast })$ 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^{\ast }=1$ entsprechen die FJ-Bedingungen genau den Karush-Kuhn-Tucker-Bedingungen. Ist $(z^{\ast },x^{\ast },{\mu }^{\ast },{\lambda }^{\ast })$ ein FJ-Punkt, so ist auch $(s{z}^{\ast },x^{\ast },s{\mu }^{\ast },s{\lambda }^{\ast })$ mit $s>0$ ein FJ-Punkt. Somit kann man davon ausgehen, dass wenn $z^{\ast }>0$ ist, bereits ein KKT-Punkt vorliegt, dieser wird durch Reskalierung mit $z^{\ast }$ erzeugt. Dann ist $(x^{\ast },{\mu }^{\ast }/z^{\ast },{\lambda }^{\ast }/z^{\ast })$ 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^{\ast }>0$ garantieren.

Beispiele

FJ ohne KKT

Betrachte als Beispiel das Optimierungsproblem

$\underset{x\in X}{\min }-x_1$

mit Restriktionsmenge

$X=\{x\in {ℝ}^2|g_1(x)=-x_2\le 0,g_2(x)=x_2+x_1^5\le 0\}$.

Minimum des Problems ist der Punkt $x^{\ast }=(0,0)$. Daher existiert ein FJ-Punkt $(z^{\ast },0,0,{\mu }_1^{\ast },{\mu }_2^{\ast })$, so dass

$z^{\ast }(-1,0{)}^T+{\mu }_1^{\ast }(0,-1{)}^T+{\mu }_2^{\ast }(0,1{)}^T=(0,0{)}^T$.

Daraus folgt direkt, dass $z^{\ast }=0,{\mu }_1^{\ast }={\mu }_2^{\ast }>0$ für einen FJ-Punkt gilt.

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

FJ und KKT

Betrachte als Beispiel das Optimierungsproblem

$\underset{x\in X}{\min }-x_2+x_1^2$

mit Restriktionsmenge

$X=\{x\in {ℝ}^2|g_1(x)=x_1+x_2-1\le 0,g_2(x)=x_1^2+x_2^2-1\le 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^{\ast }=(0,1)$. Daher gibt es einen FJ-Punkt $(z^{\ast },0,1,{\mu }_1^{\ast },{\mu }_2^{\ast })$, so dass

$z^{\ast }(0,-1{)}^T+{\mu }_1^{\ast }(1,1{)}^T+{\mu }_2^{\ast }(0,2{)}^T=(0,0{)}^T$

gilt. Eine Lösung wäre $z^{\ast }=2,{\mu }_1^{\ast }=0,{\mu }_2^{\ast }=1$, was zu dem FJ-Punkt $(2,0,1,0,1)$ führt. Eine Reskalierung mit $z^{\ast }$ führt zu dem KKT-Punkt $(x^{\ast },{\mu }_1^{\ast }/z^{\ast },{\mu }_2^{\ast }/z^{\ast })=(0,1,0,1/2)$. Tatsächlich ist im Punkt $x^{\ast }$ 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

• 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)