H. Th. Jongen und K. Meer

Die Innere-Punkte Methoden sind eine Klasse von Verfahren zur Lösung linearer und konvexer Optimierungsprobleme. Seit ihrer erstmaligen Verwendung für die lineare Programmierung 1984 durch Karmarkar [3] stellt ihre Untersuchung sicher einen der wesentlichen Forschungsbereiche innerhalb der mathematischen Optimierung der letzten 15 Jahre dar. Hinsichtlich der Bedeutung bei der Behandlung linearer Probleme sind sie mittlerweile konkurrenzfähig zur Simplexmethode.

Die Grundidee besteht darin, im Inneren der zulässigen Menge eines linearen Programmierungsproblems eine bestimmte Kurve zu definieren, die in eine optimale Ecke des Problems läuft. Dieser Kurve versucht man dann mittels numerischer Methoden (etwa mit dem Newtonverfahren) zu folgen. Es soll im folgenden ein Prototyp eines solchen Verfahrens zusammen mit den mathematischen Grundlagen dargestellt werden. Die einzelnen zitierten mathematischen Sätze finden sich z. B. in [7].

1. Grundlagen

Wir gehen von einem primalen Problem (P) der Gestalt min c^T · x unter den Nebenbedingungen A · x = b, x ≥ 0 aus. Das zugehörige duale Problem (D) ist durch max b^T · y unter den Nebenbedingungen A^T · y + s = c, s ≥ 0 gegeben. Dabei seien A ∈ ℝ^m×n vom Rang m, b, y ∈ ℝ^m und c, x, s ∈ ℝⁿ. Der Vektor s entspricht Schlupfvariablen. Die jeweils zulässigen Mengen bezeichnen wir mit \begin{eqnarray}M:=\{x\in {{\mathbb{R}}}^{n}|A\cdot x=b,x\ge 0\}\end{eqnarray} sowie \begin{eqnarray}N:=\{(y,s)\in {{\mathbb{R}}}^{m}\times {{\mathbb{R}}}^{n})|{A}^{T}\cdot y+s=c,s\ge 0\}.\end{eqnarray}

Zu beachten ist, daß die Rangbedingung an A eine eineindeutige Beziehung zwischen den y- und den s-Komponenten eines Punkts in N liefert; es gilt nämlich \begin{eqnarray}y={(A\cdot {A}^{T})}^{-1}\cdot A\cdot (c-s).\end{eqnarray}

Im folgenden sind Punkte in den beiden Mengen \(\begin{eqnarray}\tilde{M}:=\{x\in M|x\gt 0\}\end{eqnarray}\) und \(\begin{eqnarray}\tilde{N}:=\{s\in {{\mathbb{R}}}^{n}|\exists y\in {{\mathbb{R}}}^{m}\mathrm{mit}(y,s)\in N,s\gt 0\}\end{eqnarray}\) von wesentlicher Bedeutung. Eine vorläufige Generalvoraussetzung an das vorliegende Problem ist, daß es zulässige Punkte \(\begin{eqnarray}\bar{x}\in \tilde{M}\end{eqnarray}\) und \(\begin{eqnarray}(\bar{y},\bar{s})\in N\end{eqnarray}\) mit \(\begin{eqnarray}\bar{s}\in \tilde{N}\end{eqnarray}\). Diese Annahme ist äquivalent zur Beschränktheit der Mengen der optimalen Punkte von (P) und (D). Wir werden uns später wieder von ihr lösen.

Betrachtet werde die Abbildung \(\begin{eqnarray}\psi :\tilde{M}\times \tilde{N}\to {{\mathbb{R}}}_{+}^{n}\end{eqnarray}\), die durch komponentenweise Multiplikation definiert ist, d. h. ψ(x, s) ≔ (x₁ · s₁, …, x_n · s_n). Die grundlegende Eigenschaft von ψ liefert der folgende Satz:

Die Abbildung ψ ist eine Bijektion zwischen \(\begin{eqnarray}\tilde{M}\times \tilde{N}\end{eqnarray}\)und \(\begin{eqnarray}{{\mathbb{R}}}_{+}^{n}\end{eqnarray}\).

2. Der zentrale Pfad

Der vorangehende Satz bildet die Grundlage für die Definition der eingangs erwähnten Kurve, des sogenannten zentralen Pfades (wobei man prinzipiell auch andere Kurven untersuchen kann). Dazu betrachtet man im Bildbereich \(\begin{eqnarray}{{\mathbb{R}}}_{+}^{n}\end{eqnarray}\) der Abbildung ψ eine spezielle Kurve, nämlich μ → μ · e, wobei e ≔ (1, …, 1)^T und μ > 0 seien. Die Bijektivität von ψ liefert zu jedem μ > 0 eine eindeutige Lösung \(\begin{eqnarray}(x(\mu ),s(\mu ))\in \tilde{M}\times \tilde{N}\end{eqnarray}\). Der zentrale Pfad zu (P) und (D) ist die Menge {(x(μ), s(μ))| μ > 0} dieser Urbilder. Man beachte, daß zu s(μ) ein eindeutiges y(μ) mit (y(μ), s(μ)) ∈ N gehört.

Es sei noch eine weitere gebräuchliche Art erwähnt, wie man den zentralen Pfad auch definieren kann. Dazu betrachtet man eine logarithmische Barrierefunktion und verändert das primale Problem (P) zu \begin{eqnarray}\min \{{c}^{T}\cdot x-\mu \cdot \displaystyle \sum _{i=1}^{n}\mathrm{ln}({x}_{i}),A\cdot x=b,x\ge 0\}\end{eqnarray} mit einem festen Parameter μ > 0. Unter der Generalvoraussetzung \(\begin{eqnarray}\tilde{M}\ne 0\end{eqnarray}\) existiert zu jedem μ > 0 ein eindeutiger Minimalpunkt x(μ) des obigen Problems. Die sich aus den Optimalitätsbedingungen erster Ordnung ergebenden Lagrangeparameter y(μ) zusammen mit den zugehörigen Schlupfvariablen s(μ) liefern dann wiederum den zentralen Pfad. Die obige Formulierung zeigt zudem, daß der Wert der Zielfunktion x → c^T · x entlang des zentralen Pfades für μ → 0 monoton abnimmt.

Die Bedeutung des zentralen Pfades wird natürlich durch seine Eigenschaften bestimmt. Ist (x(μ), s(μ)) ein Punkt darauf mit zugehöriger dualer Lösung y(μ), so ergibt sich als Dualitätslücke \begin{eqnarray}{c}^{T}\cdot x(\mu )-{b}^{T}\cdot y(\mu )={x}^{T}(\mu )\cdot s(\mu )=n\cdot \mu .\end{eqnarray}

Da Extremalpunkte von (P) und (D) durch eine verschwindende Dualitätslücke gekennzeichnet sind, interessiert nun insbesondere, wie sich (x(μ), s(μ)) beim Grenzübergang μ → 0, μ > 0 verhält. Es gilt:

Unter den obigen Voraussetzungen konvergiert der zentrale Pfad fürμ → 0 gegen eine optimale Lösung (x*, s*) des linearen Programmierungsproblems. Diese ist strikt komplementär, d. h. es giltx* + s* > 0 (komponentenweise).

Dieses Ergebnis ist der Ausgangspunkt der innere-Punkte Methoden.

Zunächst sei noch kurz erwähnt, wie man sich von der Voraussetzung der Existenz innerer Punkte befreien kann. Dies geschieht i. allg. durch eine Einbettung des ursprünglichen Problems in ein neues derart, daß

1. (x*, s*) liegt in \(\begin{eqnarray}\tilde{M}\times \tilde{N}\end{eqnarray}\), d. h. ist zulässig;
2. der Vektor w* ≔ ψ(x*, s*) liegt wiederum nahe genug an \(\begin{eqnarray}\tilde{w}\end{eqnarray}\);
3. es ist \(\begin{eqnarray}{(x* )}^{T}\cdot s* ={e}^{T}\cdot \tilde{w}\end{eqnarray}\), d. h. die Dualitätslücke des neuen Punkts ist bereits so klein wie diejenige von \(\begin{eqnarray}(\tilde{x},\tilde{s})\end{eqnarray}\).

Sofern man also nahe genug am zentralen Pfad startet, kann man diesem folgen. Bei der Reduzierung des Wertes μ – und das heißt: bei der Auswahl des neuen Zielpunkts \(\begin{eqnarray}\tilde{w}\end{eqnarray}\) – muß dann darauf geachtet werden, daß er nicht zu weit vom aktuellen Iterationspunkt entfernt liegt. Eine genauere Analyse obigen Satzes zeigt zudem, daß die Konvergenz des Newtonverfahrens gegen \(\begin{eqnarray}\tilde{w}\end{eqnarray}\) lokal quadratisch ist.

Eine Familie von Verfahren, die auf obige Weise vorgehen, sind sogenannte short-step Methoden (vgl. [6]). Hier berechnet man, ausgehend von einem Startwert (x₀, s₀) nahe einem w₀ ≔ μ₀ · e, eine Folge von Punkten (x_k, s_k) nahe einem w_k = μ_k · e. Dabei ist μ_k gemäß der Vorschrift \begin{eqnarray}{\mu }_{k}:=(1-{\rm{\Theta }})\cdot {\mu }_{k-1}\end{eqnarray} mit fester Konstante Θ ∈ (0, 1) gewählt. Eine übliche Festlegung für Θ ist beispielsweise \(\begin{eqnarray}{\rm{\Theta }}:=\frac{1}{\sqrt{n}}\end{eqnarray}\) (n ≥ 4 sei die Variablenzahl des Problems). Sind die (x_k, s_k) gemäß des Newtonverfahrens bezüglich w_k mit Startpunkt (x_k−1, s_k−1) berechnet, dann gilt:

Bei vorgegebener oberer Schranke ϵ > 0 für die Dualitätslücke einer näherungsweise optimalen Lösung genügen\begin{eqnarray}K:=O(\sqrt{n}\cdot {ln}(\frac{{x}^{T}\cdot {s}_{0}}{\varepsilon }))\end{eqnarray}viele Iterationen, um einen zulässigen Punkt (x_k, s_k) zu erreichen, dessen Dualitätslücke das vorgegebene E unterschreitet.

4. Rationale Eingabedaten

Sind alle Eingaben eines linearen Programmierungsproblems rational, so gilt dasselbe auch für die Komponenten einer optimalen Ecke. Diese kann dann exakt berechnet werden. Dazu folgt man zunächst wie oben beschrieben dem zentralen Pfad, bis man nahe genug an einer optimalen Ecke angelangt ist. Kriterium dafür ist der Wert der aktuellen Dualitätslücke. Ist diese genügend klein, dann kann man mit einem zusätzlichen Verfahren vom aktuellen Iterationspunkt aus zu einer optimalen Ecke springen. Genauer läßt sich beweisen:

a) Sei \(\begin{eqnarray}\bar{x}\end{eqnarray}\)ein zulässiger Punkt für das primale Problem \(\begin{eqnarray}\bar{x}\end{eqnarray}\) (P). Ist \(\begin{eqnarray}\bar{x}\end{eqnarray}\)keine zulässige Basislösung, so läßt sich entweder aus \(\begin{eqnarray}\bar{x}\end{eqnarray}\)eine solche, etwa x*, mit \(\begin{eqnarray}{c}^{T}\cdot x* \le {c}^{T}\cdot \bar{x}\end{eqnarray}\)algorithmisch konstruieren, oder aber man kann folgern, daß die primale Zielfunktion x → c^T · xauf M nach unten unbeschränkt ist.

b) Ist das gegebene lineare Optimierungsproblem ganzzahlig mit Bitgröße L, und hat ein zulässiger primal-dualer Punkt (x, y, s) eine Dualitätslücke ≤ 2^−const.L (mit fester Konstante const ≤ 5), dann ist die aus (x, y, s) in a) konstruierte zulässige Basislösung optimal.

Die oben beschriebenen Ergebnisse liefern im Falle rationaler Eingabedaten eine polynomiale Laufzeit der innere-Punkte Methoden im Modell der Turingmaschine (d. h. unter der Verwendung der Bitgröße als Eingabegröße der einzelnen linearen Optimierungsprobleme). Damit sind diese Methoden in ihrem worst case-Verhalten theoretisch besser als das Simplexverfahren. Im Gegensatz zu den Ellipsoidverfahren zeigen die innere-Punkte Methoden aber auch in der Praxis ein effizientes Verhalten.

Der erste innere-Punkte Algorithmus zur Lösung linearer Programmierungsaufgaben wurde 1984 von Karmarkar ([3]) vorgestellt. Sein Zugang war eine sogenannte Potential-Reduktionsmethode (potential-reduction method), bei der man schrittweise versucht, den Wert einer Potentialfunktion \begin{eqnarray}f(x,y,s):=q\cdot \mathrm{ln}({c}^{T}\cdot x-{b}^{T}\cdot y)-\displaystyle \sum _{j=1}^{n}\mathrm{ln}({x}_{j})\end{eqnarray}<?PageNum _494unter den Nebenbedingungen \(\begin{eqnarray}x\in \tilde{M}\end{eqnarray}\), (y, s) ∈ N zu verringern. Dabei ist q ein geeignet gewählter Parameter. Eine Übersicht über derartige Ansätze liefert zum Beispiel [1].

Eine weitere Klasse von Verfahren bilden die affinen Skalierungsmethoden. Dort beschreibt man um einen inneren Punkt \(\begin{eqnarray}\bar{x}\end{eqnarray}\) ein „einfaches“ Ellipsoid \(\begin{eqnarray}E(\bar{x})\end{eqnarray}\), das ganz in M liegt, und minimiert c^T · x auf \(\begin{eqnarray}E(\bar{x})\end{eqnarray}\). In Richtung des Minimums wählt man den neuen Iterationspunkt. Einzelheiten findet man etwa in [8].

Schließlich erwähnt seien noch Ansätze, bei denen man die Komplexitätsuntersuchungen von anderen Daten als der Bitgröße oder der algebraischen Größe eines Problems abhängig macht. In [9] werden innere-Punkte Methoden angewandt, um einen Algorithmus zur Lösung linearer Optimierungsprobleme zu entwerfen, dessen Laufzeit polynomial in der Variablenzahl n sowie einer gewissen, der Systemmatrix A zugeordneten Konditionszahl ist.

Dies mag als Beschreibung innerer-Punkte Methode genügen. In den letzten 15 Jahren sind über 1500 Arbeiten zu diesem Themenkreis publiziert worden, und entsprechend groß ist die Anzahl weiterer Ansätze und Varianten. Allgemeine Darstellungen finden sich in [2], [10], [11] einen Übersichtsartikel stellt [7] dar. Eine umfangreiche Literaturliste im Internet über innere-Punkte Methoden findet man unter [4].

In [5] werden ebenfalls Verallgemeinerungen auf konvexe Programmierungsprobleme behandelt. Theoretisch bedeutsam ist dabei die Frage, für welche Art von Problemen und Barrierefunktionen man noch einen zentralen Pfad geeignet definieren kann. Speziell wichtig sind hier die Eigenschaften der Selbstkonkordanz und der Selbstbeschränktheit von Barrierefunktionen.

[4] Kranich, E.: Bibliography on interior point methods for mathematical programming. http://liinwww.ira.uka.de/ bibliography/Math/intbib.html, 1999.

[5] Nemirovskii, A.S.; Nesterov, Y.: Interior-point polynomial algorithms in convex programming. SIAM Publications, Philadelphia, 1994.

[6] Renegar, J.: A polynomial-time algorithm, based on Newton’s method, for linear programming. Mathematical Programming, 40, 1988.

[7] Roos, C; Vial, J.P.: Interior point methods. Beasley, J.E. (Hrg.): Advances in linear and integer programming; Oxford Science Publication, 1996.

[8] Saigal, R.: Linear Programming: A modern integrated analysis. Kluwer Academic Publishers, Boston, 1995.

[9] Vavasis, S; Ye, Y.: A primal-dual interior point method whose running time depends only on the constraint matrix. Mathematical Programming 74, 1996.

[10] Wright, S.: Primal-Dual Interior Point Algorithms. SIAM Publications, Philadelphia, 1997.

[11] Ye, Y.: Interior Pont Algorithms: Theory and Analysis. John Wiley and Sons, New York, 1997.

[12] Ye, Y.; Todd, M.; Mizuno, S.: An \(\begin{eqnarray}O(\sqrt{n}\cdot L)\end{eqnarray}\)-iteration homogeneous and self-dual linear programming algorithm. Mathematics of Operations Research 19, 1994.