www.wikidata.de-de.nina.az

Mangasarian Fromovitz constraint qualification Die oder kurz MFCQ ist eine wichtige Voraussetzung dass notwendige Optima

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

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

MFCQ 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

  • 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 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
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Die Mangasarian Fromovitz constraint qualification oder kurz MFCQ ist eine wichtige Voraussetzung dass notwendige Optimalitatskriterien in der nichtlinearen Optimierung gelten Die MFCQ ist eine Bedingung an die Regularitat eines zulassigen Punktes Ist die MFCQ in einem Punkt x displaystyle tilde x erfullt und ist dieser Punkt ein lokales Minimum so sind auch die Karush Kuhn Tucker Bedingungen an diesem Punkt erfullt Gilt die MFCQ so lasst sich also leicht uberprufen ob ein gegebener Punkt ein Optimum ist oder nicht Sie ist nach Olvi Mangasarian und Stanley Fromovitz benannt 1 Inhaltsverzeichnis 1 Definition 2 Beispiel 2 1 MFCQ 2 2 Abadie CQ ohne MFCQ 3 Vergleich mit anderen constraint qualifications 4 Literatur 5 EinzelnachweiseDefinition BearbeitenGegeben ist ein Optimierungsproblem in der Form min x X f x displaystyle min x in X f x nbsp wobei X x R n g i x 0 h j x 0 displaystyle X x in mathbb R n g i x leq 0 h j x 0 nbsp ist und alle Funktionen stetig differenzierbar sein sollen Dann erfullt ein zulassiger Punkt x X displaystyle tilde x in X nbsp des restringierten Optimierungsproblems die MFCQ wenn die beiden folgenden Bedingungen erfullt sind Die Gradienten der Gleichungsnebenbedingungen h j x displaystyle h j x nbsp sind im Punkt x displaystyle tilde x nbsp linear unabhangig Es existiert ein Vektor d R n displaystyle d in mathbb R n nbsp so dass h j x T d 0 displaystyle nabla h j tilde x T d 0 nbsp und g i x T d lt 0 displaystyle nabla g i tilde x T d lt 0 nbsp wenn g i x 0 displaystyle g i tilde x 0 nbsp ist Beispiel BearbeitenMFCQ Bearbeiten Betrachten wir die Gleichungsrestriktion h x x 1 2 x 2 2 1 0 displaystyle h x x 1 2 x 2 2 1 0 nbsp und die Ungleichungsrestriktion g x x 2 0 displaystyle g x x 2 leq 0 nbsp Die durch diese Restriktionen beschriebene Menge ist der Rand des Einheitskreises eingeschrankt auf die untere Halfte des Koordinatensystems Wir untersuchen den Punkt x 1 0 displaystyle tilde x 1 0 nbsp auf Zutreffen der MFCQ Die Gradienten der Restriktionsfunktionen sind g x 0 1 h x 2 0 displaystyle nabla g tilde x 0 1 nabla h tilde x 2 0 nbsp und die Ungleichung ist in x displaystyle tilde x nbsp aktiv Da nur eine Gleichungsnebenbedingung gegeben ist folgt die lineare Unabhangigkeit direkt Des Weiteren ist jeder Vektor der Form 0 t displaystyle 0 t nbsp orthogonal zum Gradienten der Gleichungsnebenbedingung Ist ausserdem t lt 0 displaystyle t lt 0 nbsp so ist g i x T 0 t lt 0 displaystyle nabla g i tilde x T 0 t lt 0 nbsp Damit wurde zum Beispiel der Vektor d 0 1 displaystyle d 0 1 nbsp alle geforderten Bedingungen erfullen die fur die MFCQ gelten Abadie CQ ohne MFCQ Bearbeiten Betrachten wir die Funktionen g 1 x x 1 g 2 x x 1 2 x 2 g 3 x 1 2 x 2 displaystyle g 1 x x 1 g 2 x x 1 2 x 2 g 3 x 1 2 x 2 nbsp und die durch sie beschriebene Restriktionsmenge X x R 2 g i x 0 i 1 2 3 displaystyle X x in mathbb R 2 g i x leq 0 i 1 2 3 nbsp Diese Menge ist die Flache welche zwischen einer positiven und einer negativen Parabel eingeschlossen wird eingeschrankt auf die rechte Seite des Koordinatensystems Wir untersuchen nun die Menge X displaystyle X nbsp auf Zutreffen der MFCQ und der Abadie CQ im Punkt x 0 0 displaystyle tilde x 0 0 nbsp Alle Ungleichungen sind in diesem Punkt aktiv und die Gradienten der Ungleichungrestrktionen sind g 1 x 1 0 T g 2 x 0 1 T g 3 x 0 1 T 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 nbsp Die MFCQ kann nicht erfullt werden da sonst d 2 gt 0 displaystyle d 2 gt 0 nbsp und d 2 lt 0 displaystyle d 2 lt 0 nbsp gelten musste Die Abadie CQ ist aber erfullt da sowohl der Tangentialkegel als auch der linearisierte Tangentialkegel dem Strahl 0 l displaystyle 0 lambda nbsp mit l 0 displaystyle lambda geq 0 nbsp entsprechen Vergleich mit anderen constraint qualifications BearbeitenDie MFCQ ist unter den anderen constraint qualifications ein Kompromiss aus Allgemeingultigkeit 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 gultig Zwischen diesen constraint qualifications gelten die Implikationen LICQ MFCQ Abadie CQ displaystyle text LICQ implies text MFCQ implies text Abadie CQ nbsp Die Umkehrungen gelten aber nicht Literatur BearbeitenC Geiger C Kanzow Theorie und Numerik restringierter Optimierungsaufgaben Springer 2002 ISBN 3 540 42790 2 https books google de books id spmzFyso b8C amp hl deEinzelnachweise Bearbeiten 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 Abgerufen von https de wikipedia org w index php title Mangasarian Fromovitz constraint qualification amp oldid 228821573