Mangasarian-Fromovitz constraint qualification

Voraussetzung, dass notwendige Optimalitätskriterien in der nichtlinearen Optimierung gelten

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 ist nach Olvi Mangasarian und Stanley Fromovitz benannt.[1]

Definition

Bearbeiten

Gegeben ist ein Optimierungsproblem in 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

Bearbeiten

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

Bearbeiten

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

Bearbeiten

Die MFCQ ist unter den anderen constraint qualifications ein Kompromiss aus Allgemeingültigkeit und guten Handhabbarkeit. Sie ist schwerer zu handhaben, aber allgemeiner als die LICQ und leichter zu handhaben als die Abadie CQ, aber nicht so allgemein gültig. Zwischen diesen constraint qualifications gelten die Implikationen

 .

Die Umkehrungen gelten aber nicht.

Literatur

Bearbeiten

Einzelnachweise

Bearbeiten
  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