www.wikidata.de-de.nina.az

Innere Punkte Verfahren sind in der Optimierung eine Klasse von Algorithmen zur Lösung von Optimierungsaufgaben Ihr Haup

Innere-Punkte-Verfahren

Innere-Punkte-Verfahren sind in der Optimierung eine Klasse von Algorithmen zur Lösung von Optimierungsaufgaben. Ihr Hauptanwendungsgebiet sind lineare oder quadratische Programme. Sie werden aber auch zur Lösung (allgemeiner) nichtlinearer Programme, semidefinierter Programme oder Komplementaritätsproblemen eingesetzt.

Innere-Punkte-Verfahren nähern sich einer Optimallösung durch das Innere des Polyeders.

Im Vergleich zu den traditionelleren Active-Set-Methoden (z. B. Simplex-Verfahren) zeichnen sich Innere-Punkte-Verfahren durch bessere theoretische Eigenschaften (polynomiale Komplexität) und schnellere Konvergenz für sehr große dünnbesetzte Probleme aus. Ein Nachteil ist, dass sie vergleichbar ungeeignet zum Lösen einer Serie von Optimierungsaufgaben sind (was für viele Algorithmen der ganzzahligen Optimierung, wie z. B. Branch and Bound oder Schnittebenenverfahren, wichtig ist).

Aufgabenstellung Bearbeiten

Im einfachsten Fall werden Innere-Punkte-Verfahren benutzt, um das lineare Problem

zu lösen. Dabei ist A eine -Matrix, und c, b sind jeweils n- bzw. m-dimensionale Vektoren. Die zulässige Menge hat die Form eines Polyeders. Aus der Theorie der linearen Optimierung ist bekannt, dass eine optimale Lösung des Optimierungsproblems in einer der Ecken des Polyeders angenommen wird. Im Gegensatz zum Simplex-Verfahren, das sich entlang der Kanten von Ecke zu Ecke bewegt, versuchen Innere-Punkte-Verfahren einen Pfad zum Optimum durch das „Innere“ des Polyeders zu finden.

Geschichte Bearbeiten

Logarithmische-Barriere-Verfahren wurden erstmals von Ragnar Frisch (1956) beschrieben. Als wichtige frühe Referenz zum Thema Barriere-Verfahren gilt Fiacco und McCormick (1968). Sie galten damals jedoch als ineffizient und (durch das Logarithmieren sehr kleiner Zahlen) als numerisch instabil. Als Geburtsstunde der Inneren-Punkte-Verfahren gilt gemeinhin die Arbeit von Narendra Karmarkar von 1984, in der er zum ersten Mal einen polynomialen potentiell praktisch einsetzbaren Algorithmus für lineare Probleme beschreibt. Dieser Algorithmus wies schon viele Gemeinsamkeiten zu den modernen Verfahren auf, auch wenn die bedeutenden Durchbrüche, die Innere-Punkte-Verfahren zu einer echten Konkurrenz für das Simplex-Verfahren machten, erst in den 1990er Jahren geschahen (z. B. Mehrotra (1992)).

Herleitung Bearbeiten

Vom heutigen Standpunkt aus gibt es verschiedene Wege, um Innere-Punkte-Verfahren zu motivieren. Eine Möglichkeit ist über Logarithmische Barrieren: Hierbei werden die Positivitätsbedingungen durch logarithmische Strafterme in der Zielfunktion ersetzt (hierbei ist ein Parameter). Anstatt des Ursprungsproblems löst man also

Für kleine Werte von wird sehr groß, man versucht also durch Bestrafung kleiner x-Werte die Lösung des Optimierungsproblems im Inneren der Menge der positiven Koordinaten zu halten. Diese Bestrafung wird umso kleiner, je kleiner der Parameter ist. Im Grenzwert erwartet man, dass die Lösung des Barriereproblems gegen die Lösung des Ursprungsproblems konvergiert. Das Barriereproblem ist ein (streng) konvexes Problem, seine (einzige, globale) Lösung findet man durch Anwendung des lagrangeschen Multiplikatorensatz als Lösung des (nichtlinearen) Gleichungssystems

Hierbei entspricht die erste Zeile der Zulässigkeit bezüglich des Primalen Problems, die zweite Zeile der Zulässigkeit bezüglich des Dualen Problems nach der Einführung von Schlupfvariablen und die dritte Zeile dem komplementären Schlupf. Für jeden Wert ist dieses Gleichungssystem eindeutig lösbar. Die Menge aller Lösungen für verschiedene beschreibt einen Pfad (den zentralen Pfad), der das Analytische Zentrum des zulässigen Polyeders (für ) mit der Lösung des Ursprungsproblems (für ) verbindet. Algorithmisch kann das Gleichungssystem per Newton-Verfahren gelöst werden. In Innere-Punkte-Verfahren wird nach jeder Iteration des Newton-Verfahrens der Parameter reduziert. Durch geeignete Heuristiken wird sichergestellt, dass die Konvergenz von und die des Newton-Verfahrens synchron ablaufen.

Eigenschaften Bearbeiten

  • Innere-Punkte-Verfahren sind global konvergent.
  • Die Kurzschrittvariante des Innere-Punkte-Verfahrens braucht im ungünstigsten Fall Iterationen, um die Lösung eines linearen Problems mit Genauigkeit zu finden. Dies ist zurzeit die beste bekannte theoretische Schranke. Das Kurzschrittverfahren ist in der Praxis anderen Varianten jedoch unterlegen.
  • In der Praxis beobachtet man Iterationen.

Algorithmus Bearbeiten

  1. Wähle primale und duale Startvektoren .
  2. Setze
  3. Reduziere .
  4. Berechne die Newton-Richtung durch Lösen des linearen Gleichungssystems:(dabei sind Diagonalmatrizen, auf deren Diagonale die Elemente der Vektoren x, s stehen, sowie ).
  5. Wähle eine Schrittweite , so dass komponentenweise gilt. Einige Varianten des Innere-Punkte-Verfahrens stellen weitere Bedingungen an .
  6. Setze
  7. Zurück zu Schritt 2

Varianten des Verfahrens und Umgebungen Bearbeiten

Es gibt mehrere Varianten von Innere-Punkte-Verfahren, die sich im Wesentlichen in der Wahl von und unterscheiden. Die wichtigsten sind Kurzschrittverfahren, Langschrittverfahren und Predictor-Corrector-Verfahren (Vorhersage und Korrektur). Um sie zu beschreiben, werden die folgenden Umgebungen des zentralen Pfades benötigt:

und

dabei ist das Innere der zulässigen Menge. Der zentrale Pfad ist durch die Bedingung definiert. In der -Umgebung wird die Euklidische Norm der Abweichung des Vektors von beschränkt, bei der -Umgebung wird lediglich verlangt, dass die Produkte nicht zu klein werden.

Die Varianten des Innere-Punkte-Verfahrens sind im Einzelnen:

  • Kurzschrittverfahren: Für. geeignete Parameter wird und gesetzt. Wenn der Startpunkt in ist, so gilt dies auch für alle weiteren Iterationspunkte.
  • Langschrittverfahren: werden gewählt. Es wird mit gesetzt und so gewählt, dass zusätzlich gilt.
  • Predictor-Corrector-Verfahren: Es wird zuerst gewählt, und das maximale für diesen Fall bestimmt (Predictor). Dieses liefert einen Schätzwert für das optimale , das nun im zweiten Schritt gewählt wird. Im zweiten Schritt wird außerdem versucht, den Linearisierungsfehler der dritten Gleichung () durch das Newton-Verfahren zu korrigieren. Im Predictor-Corrector-Verfahren wird das obige Newton-Gleichungssystem für zwei verschiedene rechte Seiten gelöst. Es ist möglich, dies sehr effizient zu implementieren (Cholesky-Zerlegung).

Das Predictor-Corrector-Verfahren ist den anderen Varianten in der Praxis überlegen, ist jedoch schwerer zu analysieren und besitzt schlechtere theoretische Eigenschaften.

Literatur Bearbeiten

  • A.V. Fiacco, G.P. McCormick, Nonlinear Programming: Sequential Unconstrained Minimization Techniques, John Willey & Sons, 1968.
  • N. Karmarkar, A new polynomial-time algorithm for linear programming. Combinatorica 4 (1984), no. 4, 373--395.
  • S. Mehrotra, On the implementation of a primal-dual interior point method. SIAM J. Optim. 2 (1992), no. 4, 575--601.
  • S.J. Wright, Primal-dual interior-point methods. SIAM, Philadelphia, PA, 1997. ISBN 0-89871-382-X
  • Yinyu Ye: Interior-Point Algorithms: Theory and Analysis, Wiley 1997

Einzelnachweise Bearbeiten

  1. Ragnar Frisch: La résolution des problèmes de programme linéaire par la méthode du potentiel logarithmique. In: Cahiers du Séminaire d’Économétrie 4, 1956, S. 7–23.
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:
Innere Punkte Verfahren sind in der Optimierung eine Klasse von Algorithmen zur Losung von Optimierungsaufgaben Ihr Hauptanwendungsgebiet sind lineare oder quadratische Programme Sie werden aber auch zur Losung allgemeiner nichtlinearer Programme semidefinierter Programme oder Komplementaritatsproblemen eingesetzt Innere Punkte Verfahren nahern sich einer Optimallosung durch das Innere des Polyeders Im Vergleich zu den traditionelleren Active Set Methoden z B Simplex Verfahren zeichnen sich Innere Punkte Verfahren durch bessere theoretische Eigenschaften polynomiale Komplexitat und schnellere Konvergenz fur sehr grosse dunnbesetzte Probleme aus Ein Nachteil ist dass sie vergleichbar ungeeignet zum Losen einer Serie von Optimierungsaufgaben sind was fur viele Algorithmen der ganzzahligen Optimierung wie z B Branch and Bound oder Schnittebenenverfahren wichtig ist Inhaltsverzeichnis 1 Aufgabenstellung 2 Geschichte 3 Herleitung 4 Eigenschaften 5 Algorithmus 6 Varianten des Verfahrens und Umgebungen 7 Literatur 8 EinzelnachweiseAufgabenstellung BearbeitenIm einfachsten Fall werden Innere Punkte Verfahren benutzt um das lineare Problem min x c T x w o b e i A x b x 0 displaystyle min x c T x mathrm wobei Ax b x geq 0 nbsp zu losen Dabei ist A eine m n displaystyle m times n nbsp Matrix und c b sind jeweils n bzw m dimensionale Vektoren Die zulassige Menge X x A x b x 0 displaystyle X x Ax b x geq 0 nbsp hat die Form eines Polyeders Aus der Theorie der linearen Optimierung ist bekannt dass eine optimale Losung des Optimierungsproblems in einer der Ecken des Polyeders angenommen wird Im Gegensatz zum Simplex Verfahren das sich entlang der Kanten von Ecke zu Ecke bewegt versuchen Innere Punkte Verfahren einen Pfad zum Optimum durch das Innere des Polyeders zu finden Geschichte BearbeitenLogarithmische Barriere Verfahren wurden erstmals von Ragnar Frisch 1956 beschrieben 1 Als wichtige fruhe Referenz zum Thema Barriere Verfahren gilt Fiacco und McCormick 1968 Sie galten damals jedoch als ineffizient und durch das Logarithmieren sehr kleiner Zahlen als numerisch instabil Als Geburtsstunde der Inneren Punkte Verfahren gilt gemeinhin die Arbeit von Narendra Karmarkar von 1984 in der er zum ersten Mal einen polynomialen potentiell praktisch einsetzbaren Algorithmus fur lineare Probleme beschreibt Dieser Algorithmus wies schon viele Gemeinsamkeiten zu den modernen Verfahren auf auch wenn die bedeutenden Durchbruche die Innere Punkte Verfahren zu einer echten Konkurrenz fur das Simplex Verfahren machten erst in den 1990er Jahren geschahen z B Mehrotra 1992 Herleitung BearbeitenVom heutigen Standpunkt aus gibt es verschiedene Wege um Innere Punkte Verfahren zu motivieren Eine Moglichkeit ist uber Logarithmische Barrieren Hierbei werden die Positivitatsbedingungen x 0 displaystyle x geq 0 nbsp durch logarithmische Strafterme m ln x i displaystyle mu ln x i nbsp in der Zielfunktion ersetzt hierbei ist m gt 0 displaystyle mu gt 0 nbsp ein Parameter Anstatt des Ursprungsproblems lost man also min x c T x m i n ln x i w o b e i A x b displaystyle min x c T x mu sum i n ln x i mathrm wobei Ax b nbsp Fur kleine Werte von x displaystyle x nbsp wird ln x displaystyle ln x nbsp sehr gross man versucht also durch Bestrafung kleiner x Werte die Losung des Optimierungsproblems im Inneren der Menge der positiven Koordinaten zu halten Diese Bestrafung wird umso kleiner je kleiner der Parameter m displaystyle mu nbsp ist Im Grenzwert m 0 displaystyle mu to 0 nbsp erwartet man dass die Losung des Barriereproblems gegen die Losung des Ursprungsproblems konvergiert Das Barriereproblem ist ein streng konvexes Problem seine einzige globale Losung findet man durch Anwendung des lagrangeschen Multiplikatorensatz als Losung des nichtlinearen Gleichungssystems A x b A T y s c x i s i m x s 0 displaystyle begin matrix Ax amp amp b A T y s amp amp c x i s i amp amp mu x s amp geq amp 0 end matrix nbsp Hierbei entspricht die erste Zeile der Zulassigkeit bezuglich des Primalen Problems die zweite Zeile der Zulassigkeit bezuglich des Dualen Problems nach der Einfuhrung von Schlupfvariablen und die dritte Zeile dem komplementaren Schlupf Fur jeden Wert m 0 displaystyle mu geq 0 nbsp ist dieses Gleichungssystem eindeutig losbar Die Menge aller Losungen fur verschiedene m displaystyle mu nbsp beschreibt einen Pfad den zentralen Pfad der das Analytische Zentrum des zulassigen Polyeders fur m displaystyle mu infty nbsp mit der Losung des Ursprungsproblems fur m 0 displaystyle mu 0 nbsp verbindet Algorithmisch kann das Gleichungssystem per Newton Verfahren gelost werden In Innere Punkte Verfahren wird nach jeder Iteration des Newton Verfahrens der Parameter m displaystyle mu nbsp reduziert Durch geeignete Heuristiken wird sichergestellt dass die Konvergenz von m 0 displaystyle mu to 0 nbsp und die des Newton Verfahrens synchron ablaufen Eigenschaften BearbeitenInnere Punkte Verfahren sind global konvergent Die Kurzschrittvariante des Innere Punkte Verfahrens braucht im ungunstigsten Fall O 1 e n displaystyle mathcal O left frac 1 varepsilon sqrt n right nbsp Iterationen um die Losung eines linearen Problems mit Genauigkeit e displaystyle varepsilon nbsp zu finden Dies ist zurzeit die beste bekannte theoretische Schranke Das Kurzschrittverfahren ist in der Praxis anderen Varianten jedoch unterlegen In der Praxis beobachtet man O log n displaystyle mathcal O log n nbsp Iterationen Algorithmus BearbeitenWahle primale und duale Startvektoren x y s gt 0 displaystyle x y s gt 0 nbsp Setze m a l t x T s n displaystyle mu alt x T s n nbsp Reduziere m 0 lt m neu lt m alt displaystyle mu 0 lt mu operatorname neu lt mu operatorname alt nbsp Berechne die Newton Richtung durch Losen des linearen Gleichungssystems 0 A T I A 0 0 S 0 X D x D y D s c A T y s b A x m neu e X S e displaystyle begin bmatrix 0 amp A T amp I A amp 0 amp 0 S amp 0 amp X end bmatrix begin bmatrix Delta x Delta y Delta s end bmatrix begin bmatrix c A T y s b Ax mu operatorname neu e XSe end bmatrix nbsp dabei sind X S displaystyle X S nbsp Diagonalmatrizen auf deren Diagonale die Elemente der Vektoren x s stehen sowie e 1 1 T displaystyle e 1 ldots 1 T nbsp Wahle eine Schrittweite a gt 0 displaystyle alpha gt 0 nbsp so dass x a D x gt 0 s a D s gt 0 displaystyle x alpha Delta x gt 0 s alpha Delta s gt 0 nbsp komponentenweise gilt Einige Varianten des Innere Punkte Verfahrens stellen weitere Bedingungen an a displaystyle alpha nbsp Setze x x a D x y y a D y s s a D s displaystyle x leftarrow x alpha Delta x y leftarrow y alpha Delta y s leftarrow s alpha Delta s nbsp Zuruck zu Schritt 2Varianten des Verfahrens und Umgebungen BearbeitenEs gibt mehrere Varianten von Innere Punkte Verfahren die sich im Wesentlichen in der Wahl von m neu displaystyle mu operatorname neu nbsp und a displaystyle alpha nbsp unterscheiden Die wichtigsten sind Kurzschrittverfahren Langschrittverfahren und Predictor Corrector Verfahren Vorhersage und Korrektur Um sie zu beschreiben werden die folgenden Umgebungen des zentralen Pfades benotigt N 2 8 x y s F 0 X S e m e 2 8 m displaystyle mathcal N 2 theta x y s in mathcal F 0 XSe mu e 2 leq theta mu nbsp und N g x y s F 0 x i s i g m i 1 n displaystyle mathcal N infty gamma x y s in mathcal F 0 x i s i geq gamma mu i 1 ldots n nbsp dabei ist F 0 x y s A x b A T y s c x gt 0 s gt 0 displaystyle mathcal F 0 x y s Ax b A T y s c x gt 0 s gt 0 nbsp das Innere der zulassigen Menge Der zentrale Pfad ist durch die Bedingung x i s i m displaystyle x i s i mu nbsp definiert In der N 2 displaystyle mathcal N 2 nbsp Umgebung wird die Euklidische Norm der Abweichung des Vektors x 1 s 1 x n s n displaystyle x 1 s 1 ldots x n s n nbsp von m m displaystyle mu ldots mu nbsp beschrankt bei der N displaystyle mathcal N infty nbsp Umgebung wird lediglich verlangt dass die Produkte x i s i displaystyle x i s i nbsp nicht zu klein werden Die Varianten des Innere Punkte Verfahrens sind im Einzelnen Kurzschrittverfahren Fur geeignete Parameter 8 b displaystyle theta beta nbsp wird m neu 1 b n m alt displaystyle mu operatorname neu 1 beta sqrt n mu operatorname alt nbsp und a 1 displaystyle alpha 1 nbsp gesetzt Wenn der Startpunkt in N 2 8 displaystyle mathcal N 2 theta nbsp ist so gilt dies auch fur alle weiteren Iterationspunkte Langschrittverfahren g 0 1 0 lt s min lt s max lt 1 displaystyle gamma in 0 1 0 lt sigma min lt sigma max lt 1 nbsp werden gewahlt Es wird m neu s k m alt displaystyle mu operatorname neu sigma k mu operatorname alt nbsp mit s k s min s max displaystyle sigma k in sigma min sigma max nbsp gesetzt und a displaystyle alpha nbsp so gewahlt dass zusatzlich x y s N g displaystyle x y s in mathcal N infty gamma nbsp gilt Predictor Corrector Verfahren Es wird zuerst m neu 0 displaystyle mu operatorname neu 0 nbsp gewahlt und das maximale a displaystyle alpha nbsp fur diesen Fall bestimmt Predictor Dieses a displaystyle alpha nbsp liefert einen Schatzwert fur das optimale m neu displaystyle mu operatorname neu nbsp das nun im zweiten Schritt gewahlt wird Im zweiten Schritt wird ausserdem versucht den Linearisierungsfehler der dritten Gleichung X S e m e displaystyle XSe mu e nbsp durch das Newton Verfahren zu korrigieren Im Predictor Corrector Verfahren wird das obige Newton Gleichungssystem fur zwei verschiedene rechte Seiten gelost Es ist moglich dies sehr effizient zu implementieren Cholesky Zerlegung Das Predictor Corrector Verfahren ist den anderen Varianten in der Praxis uberlegen ist jedoch schwerer zu analysieren und besitzt schlechtere theoretische Eigenschaften Literatur BearbeitenA V Fiacco G P McCormick Nonlinear Programming Sequential Unconstrained Minimization Techniques John Willey amp Sons 1968 N Karmarkar A new polynomial time algorithm for linear programming Combinatorica 4 1984 no 4 373 395 S Mehrotra On the implementation of a primal dual interior point method SIAM J Optim 2 1992 no 4 575 601 S J Wright Primal dual interior point methods SIAM Philadelphia PA 1997 ISBN 0 89871 382 X Yinyu Ye Interior Point Algorithms Theory and Analysis Wiley 1997Einzelnachweise Bearbeiten Ragnar Frisch La resolution des problemes de programme lineaire par la methode du potentiel logarithmique In Cahiers du Seminaire d Econometrie 4 1956 S 7 23 Abgerufen von https de wikipedia org w index php title Innere Punkte Verfahren amp oldid 194721823