Mangasarian-Fromovitz constraint qualification

Die Mangasarian-Fromovitz constraint qualification oder kurz MFCQ ist eine wichtige Voraussetzung, dass notwendige Optimalitätskriterien in der nichtlinearen Optimierung gelten. Die MFCQ ist eine Bedingung an die Regularität eines zulässigen Punktes. Ist die MFCQ in einem Punkt erfüllt und ist dieser Punkt ein lokales Minimum, so sind auch die Karush-Kuhn-Tucker-Bedingungen an diesem Punkt erfüllt. Gilt die MFCQ, so lässt sich also leicht überprüfen, ob ein gegebener Punkt ein Optimum ist oder nicht.

Sie i​st nach Olvi Mangasarian u​nd Stanley Fromovitz benannt.[1]

Definition

Gegeben i​st ein Optimierungsproblem i​n der Form

wobei

ist und alle Funktionen stetig differenzierbar sein sollen. Dann erfüllt ein zulässiger Punkt des restringierten Optimierungsproblems die MFCQ, wenn die beiden folgenden Bedingungen erfüllt sind:

  1. Die Gradienten der Gleichungsnebenbedingungen sind im Punkt linear unabhängig.
  2. Es existiert ein Vektor , so dass und , wenn ist.

Beispiel

MFCQ

Betrachten wir die Gleichungsrestriktion und die Ungleichungsrestriktion . Die durch diese Restriktionen beschriebene Menge ist der Rand des Einheitskreises, eingeschränkt auf die untere Hälfte des Koordinatensystems. Wir untersuchen den Punkt auf Zutreffen der MFCQ. Die Gradienten der Restriktionsfunktionen sind und die Ungleichung ist in aktiv.

Da nur eine Gleichungsnebenbedingung gegeben ist, folgt die lineare Unabhängigkeit direkt. Des Weiteren ist jeder Vektor der Form orthogonal zum Gradienten der Gleichungsnebenbedingung. Ist außerdem so ist . Damit würde zum Beispiel der Vektor alle geforderten Bedingungen erfüllen, die für die MFCQ gelten.

Abadie CQ ohne MFCQ

Betrachten wir die Funktionen und die durch sie beschriebene Restriktionsmenge

.

Diese Menge ist die Fläche, welche zwischen einer positiven und einer negativen Parabel eingeschlossen wird, eingeschränkt auf die rechte Seite des Koordinatensystems. Wir untersuchen nun die Menge auf Zutreffen der MFCQ und der Abadie CQ im Punkt .

Alle Ungleichungen sind in diesem Punkt aktiv und die Gradienten der Ungleichungrestrktionen sind . Die MFCQ kann nicht erfüllt werden, da sonst und gelten müsste. Die Abadie CQ ist aber erfüllt, da sowohl der Tangentialkegel als auch der linearisierte Tangentialkegel dem Strahl mit entsprechen.

Vergleich mit anderen constraint qualifications

Die MFCQ i​st unter d​en anderen constraint qualifications e​in Kompromiss a​us Allgemeingültigkeit u​nd guten Handhabbarkeit. Sie i​st schwerer z​u handhaben, a​ber allgemeiner a​ls die LICQ u​nd leichter z​u handhaben a​ls die Abadie CQ, a​ber nicht s​o allgemein gültig. Zwischen diesen constraint qualifications gelten d​ie Implikationen

.

Die Umkehrungen gelten a​ber nicht.

Literatur

Einzelnachweise

  1. Mangasarian, Fromovitz, The Fritz John necessary optimality conditions in the presence of equality and inequality constraints. J. Math. Anal. Appl., Band 17, 1967, S. 37–47
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.