www.wikidata.de-de.nina.az

Slater Bedingung Die oder auch Slater constraint qualification oder kurz Slater CQ ist eine wichtige Voraussetzung dass

Slater-Bedingung

Die Slater-Bedingung oder auch Slater constraint qualification oder kurz Slater CQ, ist eine wichtige Voraussetzung, dass notwendige Optimalitätskriterien in der konvexen Optimierung gelten. Die Slater-Bedingung ist eine Bedingung an die Regularität des gestellten Problems. Ist die Slater-Bedingung erfüllt und ist ein Punkt ein lokales Minimum, so sind auch die Karush-Kuhn-Tucker-Bedingungen an diesem Punkt erfüllt. Somit ist die Slater-Bedingung eine wichtige Voraussetzung, um für einen gegebenen Punkt überprüfen zu können, ob dieser ein Optimum ist.

Außerdem wird die Slater-Bedingung bei der Lagrange-Dualität als Voraussetzung für die starke Dualität genutzt.

Sie ist nach Morton L. Slater (1921–2002) benannt, einem Mathematiker an den Sandia National Laboratories.

Definition Bearbeiten

Starke Version Bearbeiten

Gegeben sei ein konvexes Optimierungsproblem von der Form

mit konvexer Zielfunktion , konvexen und nichtaffinen Ungleichungsrestriktionen sowie affinen Ungleichungs- und Gleichungsrestriktionsfunktionen und . Sei der Definitionsbereich des Problems, also die größte konvexe Menge, auf der alle und wohldefiniert und konvex sind. Das Problem erfüllt die Slater-Bedingung, wenn es mindestens einen relativ inneren Punkt von gibt, so dass

  • alle konvexen Ungleichungsnebenbedingungen strikt erfüllt sind:
  • alle affinen Ungleichungs- und Gleichungsnebenbedingungen erfüllt sind: und .

Schwache Variante Bearbeiten

Gelegentlich findet sich auch die schwächere Variante, dass für mindestens einen relativ inneren Punkt alle Ungleichungsnebenbedingungen strikt erfüllt sein müssen: und die Gleichungsrestriktionen erfüllt sein müssen. Dieser Fall ist in dem obigen Fall enthalten, aber in der Literatur häufig zu finden, da er leichter zu zeigen ist. Er deckt jedoch zum Beispiel nicht alle Fälle von starker Dualität bei linearen Programmen ab.

Bei verallgemeinerten Ungleichungen Bearbeiten

Verwendet man verallgemeinerte Ungleichungen und K-konvexe Funktionen und erhält damit Restriktionen wie

so ersetzt man das echtkleiner durch die strikte verallgemeinerte Ungleichung . Somit gilt bei konvexen Problemen mit verallgemeinerten Ungleichungen die Slater-Bedingung, wenn es einen relativ inneren Punkt gibt, so dass alle Gleichungsrestriktionen in erfüllt sind und für alle Ungleichungsrestriktionen gilt, dass ist.

Für fast konvexe Funktionen Bearbeiten

Ist ein Optimierungsproblem der Form

gegeben für einen Ordnungskegel mit nichtleerem Inneren und Abbildungen und . Dabei sind normierte reelle Vektorräume und die Funktion definiert durch ist fast konvex bezüglich des Kegles . sei eine beliebige nichtleere Teilmenge von .

Dann erfüllt das Problem die Slater-Bedingung, wenn es einen zulässigen Punkt gibt (das heißt ), so dass ist. Dabei ist das Innere der Menge . Diese Formulierung enthält sowohl den Fall mit verallgemeinerten Ungleichungen (dann ist ein echter Kegel) als auch die schwache Variante.

Beispiel Bearbeiten

Betrachten wir als Beispiel die Funktionen und . Die Menge ist Restriktionsmenge eines konvexen Problems. Angenommen, die Zielfunktion hat als Definitionsbereich den gesamten . Dann ist und es muss noch ein strikt zulässiger Punkt bezüglich gefunden werden, der zulässig bezüglich ist. Der Punkt erfüllt diese Voraussetzung, somit erfüllt das Problem die Slater-Bedingung.

Beziehung zu anderen constraint qualifications Bearbeiten

Die Slater-Bedingung impliziert die Abadie CQ, die Umkehrung gilt aber nicht. Der Hauptunterschied zu anderen constraint qualifications ist, dass die Slater-Bedingung eine Bedingung an das gestellte Problem ist und nicht wie bei anderen CQ an einen gewissen Punkt. Dies macht die Slater-Bedingung leichter zu überprüfen und liefert die Regularität aller zulässigen Punkte des Problems. Eingeschränkt wird ihre Verwendung durch die Tatsache, dass sie nur für konvexe Probleme gilt.

Literatur Bearbeiten

  • Florian Jarre, Josef Stoer: Optimierung. Springer, Berlin 2004, ISBN 3-540-43575-1.
  • 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

Weblinks Bearbeiten

Einzelnachweise Bearbeiten

  1. Slater, Lagrange Multipliers Revisited (Report), Cowles Commission Discussion Paper No. 403, 1950
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 Slater Bedingung oder auch Slater constraint qualification oder kurz Slater CQ ist eine wichtige Voraussetzung dass notwendige Optimalitatskriterien in der konvexen Optimierung gelten Die Slater Bedingung ist eine Bedingung an die Regularitat des gestellten Problems Ist die Slater Bedingung erfullt und ist ein Punkt x displaystyle tilde x ein lokales Minimum so sind auch die Karush Kuhn Tucker Bedingungen an diesem Punkt erfullt Somit ist die Slater Bedingung eine wichtige Voraussetzung um fur einen gegebenen Punkt uberprufen zu konnen ob dieser ein Optimum ist Ausserdem wird die Slater Bedingung bei der Lagrange Dualitat als Voraussetzung fur die starke Dualitat genutzt Sie ist nach Morton L Slater 1921 2002 benannt 1 einem Mathematiker an den Sandia National Laboratories Inhaltsverzeichnis 1 Definition 1 1 Starke Version 1 2 Schwache Variante 1 3 Bei verallgemeinerten Ungleichungen 1 4 Fur fast konvexe Funktionen 2 Beispiel 3 Beziehung zu anderen constraint qualifications 4 Literatur 5 Weblinks 6 EinzelnachweiseDefinition BearbeitenStarke Version Bearbeiten Gegeben sei ein konvexes Optimierungsproblem von der Form Minimiere f x unter den Nebenbedingungen g i x 0 i 1 k l j x a j T x b j 0 j 1 l h k x a k T x b k 0 k 1 m displaystyle begin aligned text Minimiere amp f x amp text unter den Nebenbedingungen amp g i x leq 0 amp i 1 dots k amp l j x a j T x b j leq 0 amp j 1 dots l amp h k x a k T x b k 0 amp k 1 dots m end aligned nbsp mit konvexer Zielfunktion f displaystyle f nbsp konvexen und nichtaffinen Ungleichungsrestriktionen g i x displaystyle g i x nbsp sowie affinen Ungleichungs und Gleichungsrestriktionsfunktionen l j x displaystyle l j x nbsp und h k x displaystyle h k x nbsp Sei D R n displaystyle D subset mathbb R n nbsp der Definitionsbereich des Problems also die grosste konvexe Menge auf der alle g i x displaystyle g i x nbsp und f displaystyle f nbsp wohldefiniert und konvex sind Das Problem erfullt die Slater Bedingung wenn es mindestens einen relativ inneren Punkt x displaystyle tilde x nbsp von D displaystyle D nbsp gibt so dass alle konvexen Ungleichungsnebenbedingungen strikt erfullt sind g i x lt 0 displaystyle g i tilde x lt 0 nbsp alle affinen Ungleichungs und Gleichungsnebenbedingungen erfullt sind l j x 0 displaystyle l j tilde x leq 0 nbsp und h k x 0 displaystyle h k tilde x 0 nbsp Schwache Variante Bearbeiten Gelegentlich findet sich auch die schwachere Variante dass fur mindestens einen relativ inneren Punkt x displaystyle tilde x nbsp alle Ungleichungsnebenbedingungen strikt erfullt sein mussen g i x lt 0 l j x lt 0 displaystyle g i tilde x lt 0 l j tilde x lt 0 nbsp und die Gleichungsrestriktionen erfullt sein mussen Dieser Fall ist in dem obigen Fall enthalten aber in der Literatur haufig zu finden da er leichter zu zeigen ist Er deckt jedoch zum Beispiel nicht alle Falle von starker Dualitat bei linearen Programmen ab Bei verallgemeinerten Ungleichungen Bearbeiten Verwendet man verallgemeinerte Ungleichungen und K konvexe Funktionen und erhalt damit Restriktionen wie g i x K i 0 displaystyle g i x preccurlyeq K i 0 nbsp so ersetzt man das echtkleiner durch die strikte verallgemeinerte Ungleichung K i displaystyle prec K i nbsp Somit gilt bei konvexen Problemen mit verallgemeinerten Ungleichungen die Slater Bedingung wenn es einen relativ inneren Punkt x displaystyle tilde x nbsp gibt so dass alle Gleichungsrestriktionen in x displaystyle tilde x nbsp erfullt sind und fur alle Ungleichungsrestriktionen gilt dass g i x K i 0 displaystyle g i tilde x prec K i 0 nbsp ist Fur fast konvexe Funktionen Bearbeiten Ist ein Optimierungsproblem der Form Minimiere f x unter den Nebenbedingungen g x K x R displaystyle begin aligned text Minimiere amp f x text unter den Nebenbedingungen amp g x in K amp x in R end aligned nbsp gegeben fur einen Ordnungskegel K displaystyle K nbsp mit nichtleerem Inneren und Abbildungen f V R displaystyle f V mapsto mathbb R nbsp und g V Y displaystyle g V mapsto Y nbsp Dabei sind V Y displaystyle V Y nbsp normierte reelle Vektorraume und die Funktion K V R Y displaystyle K V mapsto mathbb R times Y nbsp definiert durch K x f x g x displaystyle K x f x g x nbsp ist fast konvex bezuglich des Kegles R K displaystyle mathbb R times K nbsp R displaystyle R nbsp sei eine beliebige nichtleere Teilmenge von V displaystyle V nbsp Dann erfullt das Problem die Slater Bedingung wenn es einen zulassigen Punkt x displaystyle tilde x nbsp gibt das heisst x R g x K displaystyle tilde x in R g tilde x in K nbsp so dass g x int K displaystyle g tilde x in operatorname int K nbsp ist Dabei ist int M displaystyle operatorname int M nbsp das Innere der Menge M displaystyle M nbsp Diese Formulierung enthalt sowohl den Fall mit verallgemeinerten Ungleichungen dann ist K displaystyle K nbsp ein echter Kegel als auch die schwache Variante Beispiel BearbeitenBetrachten wir als Beispiel die Funktionen g 1 x x 1 2 2 x 2 2 1 g 2 x x 1 2 x 2 2 2 1 displaystyle g 1 x x 1 2 2 x 2 2 1 g 2 x x 1 2 x 2 2 2 1 nbsp und l 1 x x 1 x 2 displaystyle l 1 x x 1 x 2 nbsp Die Menge x R 2 g 1 x 0 g 2 x 0 l 1 x 0 displaystyle x in mathbb R 2 g 1 x leq 0 g 2 x leq 0 l 1 x leq 0 nbsp ist Restriktionsmenge eines konvexen Problems Angenommen die Zielfunktion hat als Definitionsbereich den gesamten R 2 displaystyle mathbb R 2 nbsp Dann ist D R 2 displaystyle D mathbb R 2 nbsp und es muss noch ein strikt zulassiger Punkt bezuglich g 1 g 2 displaystyle g 1 g 2 nbsp gefunden werden der zulassig bezuglich l 1 displaystyle l 1 nbsp ist Der Punkt 0 5 0 5 displaystyle 0 5 0 5 nbsp erfullt diese Voraussetzung somit erfullt das Problem die Slater Bedingung Beziehung zu anderen constraint qualifications BearbeitenDie Slater Bedingung impliziert die Abadie CQ die Umkehrung gilt aber nicht Der Hauptunterschied zu anderen constraint qualifications ist dass die Slater Bedingung eine Bedingung an das gestellte Problem ist und nicht wie bei anderen CQ an einen gewissen Punkt Dies macht die Slater Bedingung leichter zu uberprufen und liefert die Regularitat aller zulassigen Punkte des Problems Eingeschrankt wird ihre Verwendung durch die Tatsache dass sie nur fur konvexe Probleme gilt Literatur BearbeitenFlorian Jarre Josef Stoer Optimierung Springer Berlin 2004 ISBN 3 540 43575 1 C 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 deWeblinks BearbeitenBuch Convex Optimization von Stephen Boyd und Lieven Vandenberghe PDF engl Einzelnachweise Bearbeiten Slater Lagrange Multipliers Revisited Report Cowles Commission Discussion Paper No 403 1950 Abgerufen von https de wikipedia org w index php title Slater Bedingung amp oldid 214158869