Innere-Punkte-Verfahren

Innere Punkte Verfahren sind in der Optimierung eine Klasse von Algorithmen um Optimierungsaufgaben zu lösen. Ihr Hauptanwendungsgebiet sind lineare oder quadratische Programme. Sie werden aber auch zur Lösung (allgemeiner) 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 (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, z.B. Branch and Bound oder Cutting-Plane-Verfahren wichtig ist).

Aufgabenstellung

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

\min _{x}c^{T}x,\mathrm {~wobei~} Ax=b,x\geq 0

zu lösen. Dabei ist A eine mxn-Matrix, und c, b sind jeweils n-, m-dimensionale Vektoren. Die zulässige Menge $X=\{x:Ax=b,x\geq 0\}$ hat die Form eines Polyeders. Aus der Theorie der linearen Optimierung ist bekannt, dass die Lösung des Optimierungsproblemes 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" der Polyeders zu finden.

Geschichte

Logarithmische Barriere Verfahren wurden schon von Fiacco und McCormick (1968) beschrieben. Sie galten damals jedoch als ineffizient und (durch den das Logarithmieren sehr kleiner Zahlen) als numerisch instabil. Als Geburtsstunde der inneren Punkte Verfahren, gilt gemeinhin Karmarkars Arbeit von 1984, die zum ersten Mal einen polynomischen potentiell praktisch einsetzbaren Algorithmus für lineare Probleme beschreibt. Dieser Algorithmus wies schon viele Gemeinsamkeiten zu den modernen Verfahren auf, die bedeutenden Durchbrüche, die innere Punkte Verfahren zu einer echten Konkurrenz für das Simplex-Verfahren machten, geschahen jedoch erst in den 1990er Jahren (z.B. Mehrotra (1992)).

Herleitung

Vom heutigen Standpunkt aus gibt es verschiede Wege um Innere Punkte Verfahren zu motivieren. Eine Möglichkeit ist über Logarithmische Barrieren: Hierbei werden die Positivitätsbedingungen $x\geq 0$ durch logarithmische Terme $-\mu \ln x_{i}$ ersetzt (hierbei ist $\mu >0$ ein Parameter). Anstatt des Urprungsproblems löst man also

\min _{x}c^{T}x-\mu \sum _{i}^{n}\ln x_{i}\mathrm {~wobei~} Ax=b

Für kleine Werte von $x$ wird $-\ln x$ 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 $\mu$ ist, im Grenzwert $\mu \to 0$ 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 Lagrangen Multiplikatorensatz als Lösung des (nichtlinearen) Gleichungssystems

{\begin{matrix}Ax&=&b\\A^{T}y+s&=&c\\x_{i}s_{i}&=&\mu \\x,s&\geq &0\end{matrix}}

Für jeden Wert $\mu \geq 0$ ist dieses Gleichungssystem eindeutig lösbar. Die Menge aller Lösungen für verschiedene $\mu$ beschreibt einen Pfad (den zentralen Pfad), der das Analytische Zentrum des zulässigen Polyeders (für $\mu =\infty$ ) mit der Lösung des Ursprungsproblems (für $\mu =0$ ) verbindet. Algorithmisch kann das Gleichungssystem per Newton Verfahren gelöst werden. In Innere Punkte Verfahren wird nach jeder Iteration des Newton Verfahren der Parameter $\mu$ reduziert. Durch geeignete Heuristiken wird sicher gestellt dass die Konvergenz von $\mu \to 0$ und die des Newton Verfahrens synchron ablaufen.

Eigenschaften

Innere Punkte Verfahren sind global konvergent.
Die Kurzschrittvariante des Innere Punkte Verfahrens braucht im ungünstigsten Fall ${\mathcal {O}}({\frac {1}{\epsilon }}{\sqrt {n}})$ Iterationen um die Lösung eines linearen Problemes mit Genauigkeit $\epsilon$ zu finden. Dies ist zur Zeit die beste bekannte theoretische Schranke. Das Kurzschrittverfahren ist in der Praxis anderen Varianten jedoch unterlegen.
In der Praxis beobachtet man ${\mathcal {O}}(\log n)$ Iterationen.

Algorithmus

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

Varianten des Verfahrens und Umgebungen

Es gibt mehrere Varianten des Innere Punkte Verfahrens die sich im wesentlichen in der Wahl von $\mu _{neu}$ und $\alpha$ unterscheiden. Die wichtigsten sind Kurzschrittverfahren, Langschrittverfahren und Predictor-Corrector-Verfahren (in etwa Vorhersage und Korrektur). Um sie zu beschreiben werden die folgenden Umgebungen des zentralen Pfades benötigt:

{\mathcal {N}}_{2}(\theta )=\{(x,y,s)\in {\mathcal {F}}^{0}:\|XSe-\mu e\|_{2}\leq \theta \mu \}

und

{\mathcal {N}}_{-\infty }(\gamma )=\{(x,y,s)\in {\mathcal {F}}^{0}:x_{i}s_{i}\geq \gamma \mu ,i=1,\ldots ,n\}

dabei ist ${\mathcal {F}}^{0}=\{(x,y,s):Ax=b,A^{T}y+s=c,x>0,s>0\}$ das Innere der zulässigen Menge. Der zentrale Pfad ist durch die Bedingung $x_{i}s_{i}=\mu$ definiert. In der ${\mathcal {N}}_{2}$ -Umgebung wird die 2-Norm der Abweichung des Vektors $(x_{1}s_{1},\ldots ,x_{n}s_{n})$ von $(\mu ,\ldots ,\mu )$ beschränkt, bei der ${\mathcal {N}}_{-\infty }$ -Umgebung wird lediglich verlangt, dass die Produkte $x_{i}s_{i}$ nicht zu klein werden.

Die Varianten des Innere Punkte Verfahrens sind im einzelnen:

Kurzschrittverfahren: Für geignete Parameter $\theta ,\beta$ wird $\mu _{neu}=(1-\beta /{\sqrt {n}})\mu _{alt}$ und $\alpha =1$ gesetzt. Wenn der Startpunkt in ${\mathcal {N}}_{2}(\theta )$ ist, so gilt dies auch für alle weiteren Iterationspunkte.
Langschrittverfahren: $\gamma \in (0,1),0<\sigma _{min}<\sigma _{max}<1$ werden gewählt. Es wird $\mu _{neu}=\sigma _{k}\mu _{alt}$ mit $\sigma _{k}\in (\sigma _{min},\sigma _{max})$ gesetzt und $\alpha$ so gewählt, dass zusätzlich $(x,y,s)\in {\mathcal {N}}_{-\infty }(\gamma )$ gilt.
Predictor-Corrector-Verfahren: Es wird zuerst $\mu _{neu}=0$ gewählt, und das maximale $\alpha$ für diesen Fall bestimmt (Predictor). Dieses $\alpha$ liefert einen Schätzwert für das optimale $\mu _{neu}$ , das nun im zweiten Schritt gewählt wird. Im zweiten Schritt wird ausserdem versucht den Linearisierungsfehler der dritten Gleichung ( $XSe=\mu e$ ) 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. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. ISBN: 0-89871-382-X