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.[1]

Rahmenbedingungen

Bearbeiten

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

 

unter den Nebenbedingungen

 
 .

Dabei sind alle betrachteten Funktionen   stetig differenzierbar und   ist eine nichtleere Teilmenge des  .

Ein Punkt   heißt Fritz-John-Punkt oder kurz FJ-Punkt des obigen Optimierungsproblems, wenn er die folgenden Bedingungen erfüllt:

 
 
 
 
 
 

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

Ist der Punkt   lokales Minimum des Optimierungsproblems, so gibt es  , so dass   ein FJ-Punkt ist und   ungleich dem Nullvektor ist.

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

Beziehung zu den Karush-Kuhn-Tucker-Bedingungen

Bearbeiten

Für   entsprechen die FJ-Bedingungen genau den Karush-Kuhn-Tucker-Bedingungen. Ist   ein FJ-Punkt, so ist auch   mit   ein FJ-Punkt. Somit kann man davon ausgehen, dass wenn   ist, bereits ein KKT-Punkt vorliegt, dieser wird durch Reskalierung mit   erzeugt. Dann ist   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   garantieren.

Beispiele

Bearbeiten

FJ ohne KKT

Bearbeiten

Betrachte als Beispiel das Optimierungsproblem

 

mit Restriktionsmenge

 .

Minimum des Problems ist der Punkt  . Daher existiert ein FJ-Punkt  , so dass

 .

Daraus folgt direkt, dass   für einen FJ-Punkt gilt.

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

FJ und KKT

Bearbeiten

Betrachte als Beispiel das Optimierungsproblem

 

mit Restriktionsmenge

 .

Die Restriktionsmenge ist der Einheitskreis, bei dem am ersten Quadranten die Krümmung des Kreises entfernt wurde. Minimum des Problems ist der Punkt  . Daher gibt es einen FJ-Punkt  , so dass

 

gilt. Eine Lösung wäre  , was zu dem FJ-Punkt   führt. Eine Reskalierung mit   führt zu dem KKT-Punkt  . Tatsächlich ist im Punkt   auch die LICQ erfüllt, deshalb gelten hier auch die KKT-Bedingungen.

Verwandte Konzepte

Bearbeiten

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

Bearbeiten
Bearbeiten

Einzelnachweise

Bearbeiten
  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