imported>Thomas Dresler: Format

2025-07-02T10:52:34Z

Format

Neue Seite

[[Datei:Interior-point-method-three-dimensions.png|thumb|Innere-Punkte-Verfahren nähern sich einer Optimallösung durch das Innere des Polyeders.]]
'''Innere-Punkte-Verfahren''' sind in der [[Optimierung (Mathematik)|Optimierung]] eine Klasse von Algorithmen zur Lösung von Optimierungsaufgaben.
Ihr Hauptanwendungsgebiet sind [[Lineare Optimierung|lineare]] oder [[Quadratische Optimierung|quadratische Programme]]. Sie werden aber auch zur Lösung (allgemeiner) [[Optimierung (Mathematik)#Nichtlineare Optimierung|nichtlinearer Programme]], semidefinierter Programme oder Komplementaritätsproblemen eingesetzt.

Im Vergleich zu den traditionelleren [[Active-Set-Methoden]] (z. B. [[Simplex-Verfahren]]) zeichnen sich Innere-Punkte-Verfahren durch bessere theoretische Eigenschaften ([[Polynomialzeit|polynomiale Komplexität]]) und schnellere [[Grenzwert (Folge)|Konvergenz]] für sehr große [[Dünnbesetzte Matrix|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 [[Ganzzahlige lineare Optimierung|ganzzahligen Optimierung]], wie z. B. [[Branch and Bound]] oder [[Schnittebenenverfahren]], wichtig ist).

== Aufgabenstellung ==
Im einfachsten Fall werden Innere-Punkte-Verfahren benutzt, um das [[Lineare Optimierung|lineare Problem]]
:<math>\min_x c^T x, \mathrm{~wobei~} Ax = b, x\ge 0</math>
zu lösen. Dabei ist A eine <math>m \times n</math>-Matrix, und c, b sind jeweils n- bzw. m-dimensionale Vektoren. Die ''zulässige Menge'' <math>X = \{x:Ax=b,\, x\ge 0\}</math> hat die Form eines [[Polyeder]]s. 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 ==
Logarithmische-Barriere-Verfahren wurden erstmals von [[Ragnar Anton Kittil Frisch |Ragnar Frisch]] (1956) beschrieben.<ref>Ragnar Frisch: [http://www.jstor.org/stable/20075373 ''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.</ref> 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 [[Polynomialzeit|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 ==
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 <math>x\ge 0</math> durch logarithmische Strafterme <math>-\mu \ln x_i</math> in der Zielfunktion ersetzt (hierbei ist <math>\mu>0</math> ein Parameter). Anstatt des Ursprungsproblems löst man also
:<math> \min_x c^Tx -\mu\sum_i^n \ln x_i\mathrm{~wobei~} Ax=b</math>
Für kleine Werte von <math>x</math> wird <math>-\ln x</math> 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 <math>\mu</math> ist. Im Grenzwert <math>\mu\to 0</math> 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 [[Lagrange-Multiplikator|lagrangeschen Multiplikatorensatz]] als Lösung des (nichtlinearen) Gleichungssystems
:<math>\begin{matrix}
Ax &=& b\\
A^T y + s &=& c\\
x_is_i &=& \mu\\
x, s &\ge& 0
\end{matrix}
</math>
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 [[Schlupfvariable]]n und die dritte Zeile dem [[Komplementärer Schlupf|komplementären Schlupf]].
Für jeden Wert <math>\mu\ge0</math> ist dieses Gleichungssystem eindeutig lösbar. Die Menge aller Lösungen für verschiedene <math>\mu</math> beschreibt einen Pfad (den ''zentralen Pfad''), der das ''Analytische Zentrum'' des zulässigen Polyeders (für <math>\mu = \infty</math>) mit der Lösung des Ursprungsproblems (für <math>\mu=0</math>) verbindet.
Algorithmisch kann das Gleichungssystem per [[Newton-Verfahren]] gelöst werden. In Innere-Punkte-Verfahren wird nach jeder Iteration des Newton-Verfahrens der Parameter <math>\mu</math> reduziert. Durch geeignete Heuristiken wird sichergestellt, dass die Konvergenz von <math>\mu\to 0 </math> und die des Newton-Verfahrens synchron ablaufen.

== Eigenschaften ==
* Innere-Punkte-Verfahren sind global konvergent.
* Die ''Kurzschritt''variante des Innere-Punkte-Verfahrens braucht im ungünstigsten Fall <math>\mathcal{O}\left(\frac{1}{\varepsilon}\sqrt{n}\right)</math> Iterationen, um die Lösung eines linearen Problems mit Genauigkeit <math>\varepsilon</math> 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 <math>\mathcal{O}(\log n)</math> Iterationen.

== Algorithmus ==
# Wähle primale und duale Startvektoren <math>x, y, s > 0</math>.
# Setze <math>\mu_{alt} = x^Ts/n</math>
# Reduziere <math>\mu: 0<\mu_{\operatorname{neu}}<\mu_{\operatorname{alt}}</math>.
# Berechne die Newton-Richtung durch Lösen des linearen Gleichungssystems:<math>\begin{bmatrix}0 & A^T & I\\ A & 0 & 0 \\ S & 0 & 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}
</math>(dabei sind <math>X, S</math> [[Diagonalmatrix|Diagonalmatrizen]], auf deren [[Hauptdiagonale|Diagonale]] die Elemente der Vektoren x, s stehen, sowie <math> e = (1,\ldots,1)^T</math>).
# Wähle eine Schrittweite <math>\alpha>0</math>, so dass <math>x +\alpha \Delta x >0, s + \alpha \Delta s >0</math> komponentenweise gilt. Einige Varianten des Innere-Punkte-Verfahrens stellen weitere Bedingungen an <math>\alpha</math>.
# Setze <math> x \leftarrow x+\alpha \Delta x, y\leftarrow y+\alpha \Delta y, s\leftarrow s+\alpha \Delta s</math>
# Zurück zu Schritt 2

== Varianten des Verfahrens und Umgebungen ==
Es gibt mehrere Varianten von Innere-Punkte-Verfahren, die sich im Wesentlichen in der Wahl von <math>\mu_{\operatorname{neu}}</math> und <math>\alpha</math> 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:
:<math>\mathcal{N}_2(\theta) = \{(x, y, s)\in \mathcal{F}^0:\|XSe-\mu e\|_2\le\theta\mu\}</math>
und
:<math>\mathcal{N}_{-\infty}(\gamma) = \{(x, y, s)\in \mathcal{F}^0:x_is_i\ge\gamma\mu, i=1,\ldots,n\}</math>
dabei ist <math>\mathcal{F}^0 = \{(x, y, s): Ax=b, A^Ty+s=c, x>0, s>0\}</math> das Innere der zulässigen Menge. Der zentrale Pfad ist durch die Bedingung <math>x_is_i=\mu</math> definiert. In der <math>\mathcal{N}_2</math>-Umgebung wird die [[Euklidische Norm]] der Abweichung des Vektors <math>(x_1s_1,\ldots,x_ns_n)</math> von <math>(\mu,\ldots,\mu)</math> beschränkt, bei der <math>\mathcal{N}_{-\infty}</math>-Umgebung wird lediglich verlangt, dass die Produkte <math>x_is_i</math> nicht zu klein werden.

Die Varianten des Innere-Punkte-Verfahrens sind im Einzelnen:
* '''Kurzschrittverfahren''': Für. geeignete Parameter <math>\theta, \beta</math> wird <math>\mu_{\operatorname{neu}} = (1-\beta/\sqrt{n})\mu_{\operatorname{alt}}</math> und <math>\alpha=1</math> gesetzt. Wenn der Startpunkt in <math>\mathcal{N}_2(\theta)</math> ist, so gilt dies auch für alle weiteren Iterationspunkte.
* '''Langschrittverfahren''': <math>\gamma\in(0,1), 0<\sigma_{\min}<\sigma_{\max}<1</math> werden gewählt. Es wird <math>\mu_{\operatorname{neu}} = \sigma_k\mu_{\operatorname{alt}}</math> mit <math>\sigma_k\in(\sigma_{\min},\sigma_{\max})</math> gesetzt und <math>\alpha</math> so gewählt, dass zusätzlich <math>(x, y, s)\in \mathcal{N}_{-\infty}(\gamma)</math> gilt.
* '''Predictor-Corrector-Verfahren''': Es wird zuerst <math>\mu_{\operatorname{neu}}=0</math> gewählt, und das maximale <math>\alpha</math> für diesen Fall bestimmt (Predictor). Dieses <math>\alpha</math> liefert einen Schätzwert für das optimale <math>\mu_{\operatorname{neu}}</math>, das nun im zweiten Schritt gewählt wird. Im zweiten Schritt wird außerdem versucht, den Linearisierungsfehler der dritten Gleichung (<math>XSe=\mu e</math>) 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 ==
* 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 ==
<references />

[[Kategorie:Lineare Optimierung]]
[[Kategorie:Nichtlineare Optimierung]]
[[Kategorie:Optimierungsalgorithmus]]

Innere-Punkte-Verfahren - Versionsgeschichte

imported>Thomas Dresler: Format