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 ${\tilde {x}}$ 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.

Definition

Gegeben ist ein Optimierungsproblem in der Form

$\min _{x\in X}f(x)$

wobei

$X=\{x\in \mathbb {R} ^{n}\,|\,g_{i}(x)\leq 0,h_{j}(x)=0\}$

ist und alle Funktionen stetig differenzierbar sein sollen. Dann erfüllt ein zulässiger Punkt ${\tilde {x}}\in X$ des restringierten Optimierungsproblems die MFCQ, wenn die beiden folgenden Bedingungen erfüllt sind:

1. Die Gradienten der Gleichungsnebenbedingungen $h_{j}(x)$ sind im Punkt ${\tilde {x}}$ linear unabhängig.
2. Es existiert ein Vektor $d\in \mathbb {R} ^{n}$, so dass $\nabla h_{j}({\tilde {x}})^{T}d=0$ und $\nabla g_{i}({\tilde {x}})^{T}d<0$, wenn $g_{i}({\tilde {x}})=0$ ist.

Beispiel

MFCQ

Betrachten wir die Gleichungsrestriktion $h(x)=x_{1}^{2}+x_{2}^{2}-1=0$ und die Ungleichungsrestriktion $g(x)=x_{2}\leq 0$. Die durch diese Restriktionen beschriebene Menge ist der Rand des Einheitskreises, eingeschränkt auf die untere Hälfte des Koordinatensystems. Wir untersuchen den Punkt ${\tilde {x}}=(1,0)$ auf Zutreffen der MFCQ. Die Gradienten der Restriktionsfunktionen sind $\nabla g({\tilde {x}})=(0,1)\,,\,\nabla h({\tilde {x}})=(2,0)$ und die Ungleichung ist in ${\tilde {x}}$ aktiv.

Da nur eine Gleichungsnebenbedingung gegeben ist, folgt die lineare Unabhängigkeit direkt. Des Weiteren ist jeder Vektor der Form $(0,t)$ orthogonal zum Gradienten der Gleichungsnebenbedingung. Ist außerdem $t<0$ so ist $\nabla g_{i}({\tilde {x}})^{T}(0,t)<0$. Damit würde zum Beispiel der Vektor $d=(0,-1)$ alle geforderten Bedingungen erfüllen, die für die MFCQ gelten.

Abadie CQ ohne MFCQ

Betrachten wir die Funktionen $g_{1}(x)=-x_{1}\,,\,g_{2}(x)=-x_{1}^{2}-x_{2}\,,\,g_{3}=-x_{1}^{2}+x_{2}$ und die durch sie beschriebene Restriktionsmenge

$X=\{x\in \mathbb {R} ^{2}\,|\,g_{i}(x)\leq 0,\,i=1,2,3\}$.

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 $X$ auf Zutreffen der MFCQ und der Abadie CQ im Punkt ${\tilde {x}}=(0,0)$.

Alle Ungleichungen sind in diesem Punkt aktiv und die Gradienten der Ungleichungrestrktionen sind $\nabla g_{1}({\tilde {x}})=(-1,0)^{T}\,,\,\nabla g_{2}({\tilde {x}})=(0,-1)^{T}\,,\,\nabla g_{3}({\tilde {x}})=(0,1)^{T}$. Die MFCQ kann nicht erfüllt werden, da sonst $d_{2}>0$ und $d_{2}<0$ gelten müsste. Die Abadie CQ ist aber erfüllt, da sowohl der Tangentialkegel als auch der linearisierte Tangentialkegel dem Strahl $(0,\lambda )$ mit $\lambda \geq 0$ entsprechen.

Vergleich mit anderen constraint qualifications

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

${\text{LICQ}}\implies {\text{MFCQ}}\implies {\text{Abadie CQ}}$.

Die Umkehrungen gelten aber nicht.

Literatur

• C. Geiger, C. Kanzow: Theorie und Numerik restringierter Optimierungsaufgaben. Springer, 2002. ISBN 3-540-42790-2. https://books.google.de/books?id=spmzFyso_b8C&hl=de