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 ${\displaystyle {\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 i​st nach Olvi Mangasarian u​nd Stanley Fromovitz benannt.[1]

Definition

Gegeben i​st ein Optimierungsproblem i​n der Form

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

wobei

${\displaystyle 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 ${\displaystyle {\tilde {x}}\in X}$ des restringierten Optimierungsproblems die MFCQ, wenn die beiden folgenden Bedingungen erfüllt sind:

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

Beispiel

MFCQ

Betrachten wir die Gleichungsrestriktion ${\displaystyle h(x)=x_{1}^{2}+x_{2}^{2}-1=0}$ und die Ungleichungsrestriktion ${\displaystyle 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 ${\displaystyle {\tilde {x}}=(1,0)}$ auf Zutreffen der MFCQ. Die Gradienten der Restriktionsfunktionen sind ${\displaystyle \nabla g({\tilde {x}})=(0,1)\,,\,\nabla h({\tilde {x}})=(2,0)}$ und die Ungleichung ist in ${\displaystyle {\tilde {x}}}$ aktiv.

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

Abadie CQ ohne MFCQ

Betrachten wir die Funktionen ${\displaystyle 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

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

Alle Ungleichungen sind in diesem Punkt aktiv und die Gradienten der Ungleichungrestrktionen sind ${\displaystyle \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 ${\displaystyle d_{2}>0}$ und ${\displaystyle d_{2}<0}$ gelten müsste. Die Abadie CQ ist aber erfüllt, da sowohl der Tangentialkegel als auch der linearisierte Tangentialkegel dem Strahl ${\displaystyle (0,\lambda )}$ mit ${\displaystyle \lambda \geq 0}$ 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

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

Die Umkehrungen gelten a​ber 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

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