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.
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

Im einfachsten Fall werden Innere-Punkte-Verfahren benutzt um das lineare Problem
min⁡xcTx\min_x c^T x , wobei Ax=b,x≥0 Ax = b, x\ge 0
zu lösen. Dabei ist A eine m×nm\cross n-Matrix, und cc, bb sind jeweils nn- bzw. mm-dimensionale Vektoren. Die zulässige Menge X={x:Ax=b, x≥0}X = \{x:Ax=b,\, x\ge 0\} 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

Logarithmische-Barriere-Verfahren wurden schon von Fiacco und McCormick (1968) beschrieben. 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, die 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

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 x≥0x\ge 0 durch logarithmische Terme −μln⁡xi-\mu \ln x_i ersetzt (hierbei ist μ>0\mu>0 ein Parameter). Anstatt des Urprungsproblems löst man also
min⁡xcTx−μ∑inln⁡xi \min_x c^Tx -\mu\sum\limits_i^n \ln x_i wobei Ax=bAx=b
Für kleine Werte von xx wird −ln⁡x-\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 μ→0\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 Multiplikatorensatzes als Lösung des (nichtlinearen) Gleichungssystems
Ax=bATy+s=cxisi=μx,s≥0\begin{matrix} Ax &=& b\\ A^T y + s &=& c\\ x_is_i &=& \mu\\ x, s &\ge& 0 \end{matrix}
Für jeden Wert μ≥0\mu\ge0 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 μ=0\mu=0) verbindet. Algorithmisch kann das Gleichungssystem per Newton-Verfahren gelöst werden. Im Innere-Punkte-Verfahren wird nach jeder Iteration des Newton-Verfahrens der Parameter μ\mu reduziert. Durch geeignete Heuristiken wird sichergestellt, dass die Konvergenz von μ→0\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 O(1εn)\mathcal{O}\left(\dfrac{1}{\varepsilon}\sqrt{n}\right) Iterationen, um die Lösung eines linearen Problems mit Genauigkeit ε\varepsilon 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 O(log⁡n)\mathcal{O}(\log n) Iterationen.

Algorithmus

  1. Wähle primale und duale Startvektoren x,y,s>0x, y, s > 0.
  2. Setze μalt=xTs/n\mu_{alt} = x^Ts/n
  3. Reduziere μ:0<μneu<μalt\mu: 0<\mu_{neu}<\mu_{alt}.
  4. Berechne die Newton-Richtung durch Lösen des linearen Gleichungssystems:[0ATIA00S0X][ΔxΔyΔs]=[c−ATy−sb−Axμneue−XSe]\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,SX, S Diagonalmatrizen, auf deren Diagonale die Elemente der Vektoren xx, ss stehen, sowie e=(1,…,1)T e = (1,\ldots,1)^T).
  5. Wähle eine Schrittweite α>0\alpha>0, so dass x+αΔx>0,s+αΔs>0x +\alpha \Delta x >0, s + \alpha \Delta s >0 komponentenweise gilt. Einige Varianten des Innere-Punkte-Verfahrens stellen weitere Bedingungen an α\alpha.
  6. Setze x←x+αΔx,y←y+αΔy,s←s+αΔs x \leftarrow x+\alpha \Delta x, y\leftarrow y+\alpha \Delta y, s\leftarrow s+\alpha \Delta s
  7. 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 μneu\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:
N2(θ)={(x,y,s)∈F0:∥XSe−μe∥2≤θμ}\mathcal{N}_2(\theta) = \{(x, y, s)\in \mathcal{F}^0:\|XSe-\mu e\|_2\le\theta\mu\}
und
N−∞(γ)={(x,y,s)∈F0:xisi≥γμ,i=1,…,n}\mathcal{N}_{-\infty}(\gamma) = \{(x, y, s)\in \mathcal{F}^0:x_is_i\ge\gamma\mu, i=1,\ldots,n\}
dabei ist F0={(x,y,s):Ax=b,ATy+s=c,x>0,s>0}\mathcal{F}^0 = \{(x, y, s): Ax=b, A^Ty+s=c, x>0, s>0\} das Innere der zulässigen Menge. Der zentrale Pfad ist durch die Bedingung xisi=μx_is_i=\mu definiert. In der N2\mathcal{N}_2-Umgebung wird die 2-Norm der Abweichung des Vektors (x1s1,…,xnsn)(x_1s_1,\ldots,x_ns_n) von (μ,…,μ)(\mu,\ldots,\mu) beschränkt, bei der N−∞\mathcal{N}_{-\infty}-Umgebung wird lediglich verlangt, dass die Produkte xisix_is_i nicht zu klein werden.
Die Varianten des Innere-Punkte-Verfahrens sind im einzelnen:
  • Kurzschrittverfahren: Für geeignete Parameter θ,β\theta, \beta wird μneu=(1−β/n)μalt\mu_{neu} = (1-\beta/\sqrt{n})\mu_{alt} und α=1\alpha=1 gesetzt. Wenn der Startpunkt in N2(θ)\mathcal{N}_2(\theta) ist, so gilt dies auch für alle weiteren Iterationspunkte.
  • Langschrittverfahren: γ∈(0,1),0<σmin<σmax<1\gamma\in(0,1), 0<\sigma_{min}<\sigma_{max}<1 werden gewählt. Es wird μneu=σkμalt\mu_{neu} = \sigma_k\mu_{alt} mit σk∈(σmin,σmax)\sigma_k\in(\sigma_{min},\sigma_{max}) gesetzt und α\alpha so gewählt, dass zusätzlich (x,y,s)∈N−∞(γ)(x, y, s)\in \mathcal{N}_{-\infty}(\gamma) gilt.
  • Predictor-Corrector-Verfahren: Es wird zuerst μneu=0\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 μneu\mu_{neu}, das nun im zweiten Schritt gewählt wird. Im zweiten Schritt wird außerdem versucht, den Linearisierungsfehler der dritten Gleichung (XSe=μe)(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
 
 

Wir Mathematiker sind die wahren Dichter, nur müssen wir das, was unsere Phantasie schafft, noch beweisen.

Leopold Kronecker

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Innere-Punkte-Verfahren aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
Datenschutzerklärung

 

Optimierung