6.1 Zur Geschichte der linearen Optimierung
[Bearbeiten]
Der einzig relevante Algorithmus zur Lösung linearer Optimierungsprobleme war 40 Jahre lang der Mitte der 40er Jahre von Dantzig entwickelte und oben vorgestellte Simplexalgorithmus. Dieser Algorithmus macht sich zunutze, dass der Rand des Polyeders
endliche viele Ecken hat und dass ein lineares Optimierungsproblem der Form

sofern es überhaupt lösbar ist, auch eine solche Ecke als Lösung besitzt. Ausgehend von einer Startecke durchläuft der Simplexalgorithmus eine gewisse Anzahl von jeweils benachbarten Ecken so, dass der Zielfunktionswert von einer Ecke zur nächsten zumindest nicht größer wird und daher nach endlich vielen Schritten eine optimale Ecke erreicht wird.
Nun gibt es Polyeder, welche eine bezüglich
exponentielle Anzahl von Ecken haben. Ein solches Polyeder ist der durch
Ungleichungen beschreibbare Einheitskubus

der offenbar
Ecken besitzt, die nacheinander ohne Mehrfachkontakt durchlaufen werden können. Im Jahr 1972 zeigten Klee und Minty, dass der Simplexalgorithmus zur Lösung eines gewissen Problems, welches darin besteht, die Funktion
über einem „etwas verbeulten“ Einheitskubus zu minimieren, bei Wahl einer bestimmten Startecke alle Ecken des zulässigen Gebietes dieses Problems abwandert und folglich
Iterationen benötigt (siehe z. B. [BerTsi97]). Damit war bewiesen, dass der Simplexalgorithmus im ungünstigsten Fall eine in Bezug auf die Zahl der Variablen exponentielle Anzahl von Iterationen zur Lösung eines linearen Optimierungsproblems aufwenden muss.
Es stellte sich nun die Frage, ob ein derartiges „Worst-Case-Verhalten“ ein Charakteristikum des Simplexalgorithmus ist oder ob es eine Eigenschaft ist, die dem Problem der linearen Optimierung selbst innewohnt und damit für jeden anderen Algorithmus für lineare Optimierungsprobleme auch nachgewiesen werden kann. Die Beantwortung einer solchen Frage, d. h. die Erfassung des Aufwands, der benötigt wird, um ein Problem einer gegebenen Problemklasse mit vorgegebener Genauigkeit zu lösen, fällt in das Gebiet der in den 70er Jahren begründeten Komplexitätstheorie.
In der Komplexitätstheorie unterscheidet man die Worst Case Analysis, bei der es darum geht, den Aufwand zu bemessen, der zur Lösung des schwierigsten Problems vorgegebener Größe einer Problemklasse erforderlich ist, von der Average Case Analysis, die sich mit dem durchschnittlichen Aufwand zur Lösung eines Problems fester Größe bezüglich einer Problemklasse beschäftigt. Für die Praxis sind Ergebnisse einer Average Case Analysis sicher die aussagefähigeren. Sie sind aber auch sehr viel schwieriger zu gewinnen, weswegen meistens auch nur eine Worst Case Analysis betrieben wird.
Grob gesprochen sagt man, dass eine Problemklasse polynomiale Komplexität besitzt, wenn jedes Problem der Größe „
“ (z. B. der Variablenzahl
bei einem Optimierungsproblem) durch einen Algorithmus in höchstens
„elementaren Rechenoperationen“ im Rahmen einer gewissen Genauigkeit gelöst werden kann, wobei
ein Polynom ist. Verfügt insbesondere ein spezieller Algorithmus über diese Lösungseigenschaft, so sagt man, dass er eine polynomiale Laufzeit hat. Die polynomiale Komplexität einer Problemklasse folgt natürlich, wenn für sie ein Algorithmus mit polynomialer Laufzeit gefunden wurde.
Für die lineare Optimierung war durch das Beispiel von Klee und Minty nachgewiesen worden, dass der Simplexalgorithmus keine polynomiale, sondern nur eine exponentielle Laufzeit besitzt. (Ob dies für jede denkbare Pivotregel gilt, ist noch ungeklärt. Für die wichtigsten Pivotregeln ist dies aber gezeigt worden.) Die viele Jahre offene Frage im Rahmen der Komplexitätstheorie war also, ob das lineare Optimierungsproblem polynomiale oder exponentielle Komplexität hat oder, anders ausgedrückt, ob es Algorithmen zur Lösung linearer Optimierungsaufgaben mit polynomialer Laufzeit gibt. Dass die Beantwortung dieser Frage grundsätzlich von Interesse ist, zeigt das folgende Beispiel.
Angenommen, man hat die Wahl zwischen zwei Algorithmen, von denen der erste
(exponentielle Laufzeit) und der zweite
(polynomiale Laufzeit) Rechenoperationen benötigt, um ein Problem in
Variablen einer bestimmten Problemklasse zu lösen. Hat man einen Computer zur Verfügung, der
Rechenoperationen pro Sekunde durchführen kann, und ist man bereit, diesen
Sekunden für die Lösung eines Problems arbeiten zu lassen, so errechnet man


Das bedeutet, dass der erste Algorithmus in dieser Zeit Probleme bis
und der zweite Probleme bis
lösen kann.
Im Jahr 1979 veröffentlichte Khachian einen neuen Algorithmus zur Lösung linearer Optimierungsprobleme, die sog. Ellipsoidmethode, welche eine polynomiale Laufzeit besitzt. Damit war geklärt, dass das Problem der linearen Optimierung polynomiale Komplexität hat. Leider stellte sich sehr schnell heraus, dass die auch im SPIEGEL im Dezember 1979 verbreitete Vermutung „Wahrscheinlich wird sich durch Khachian’s Erkenntnis die dagegen doch recht umständliche Simplexmethode weithin ersetzen lassen“ unzutreffend war und die Ellipsoidmethode dem Simplexalgorithmus in der Praxis fast immer deutlich unterlegen ist. Dies hängt unter Anderem damit zusammen, dass das Beispiel von Klee und Minty nicht das typische, sondern nur das in Extremfällen mögliche Verhalten des Simplexverfahrens aufzeigt.
Inzwischen vorliegende Untersuchungen über durchschnittliche Laufzeiten des Simplexalgorithmus für gewisse Problemklassen geben ein sehr viel günstigeres Bild dieses Verfahrens. Dieses Bild spiegelt die auf 50-jährigem Umgang mit dem Simplexalgorithmus beruhende Erfahrung wider, dass dieser im Schnitt nur
Iterationen zur Lösung des anfangs beschriebenen linearen Optimierungsproblems benötigt, wobei
eine relativ kleine Konstante ist. (Es werden unterschiedliche Werte zwischen 1 und 6 angegeben. Dantzig vermutete 1979 in einer Arbeit über den Khachian-Algorithmus, dass der Simplexalgorithmus nach durchschnittlich höchstens
Iterationen eine Lösung von
findet.) Derartige Ergebnisse bzw. Beobachtungen zur durchschnittlichen Iterationszahl eines Verfahrens sind z. B. auch für die Entscheidung darüber wichtig, ob man bei großen Problemen das ursprüngliche primale Problem oder das dazu gehörige duale Problem lösen sollte.
Nachdem durch Khachian geklärt worden war, dass das Problem der linearen Optimierung polynomiale Komplexität besitzt, wuchs die Hoffnung, dass man eines Tages auch effizientere Algorithmen als den Simplexalgorithmus zu seiner Lösung finden würde. Aufgrund der Eigenschaften des Simplexalgorithmus war zu erwarten, dass ein solches Verfahren Iterierte erzeugen muss, welche im Inneren der zulässigen Menge liegen. Die wesentliche Frage, die es in diesem Zusammenhang zu lösen galt, war dann die nach einer geeigneten Richtung, die von einem gegebenen Punkt im Inneren des Gebietes zu einem inneren Punkt zeigt, der eine „wesentlich bessere“ Näherung in Bezug auf eine Lösung des Problems darstellt.
Im Jahr 1984 schlug Karmarkar auf einer Tagung ein neues Verfahren vor, welches eine polynomiale Laufzeit mit einem günstigeren Worst-Case-Verhalten als das von Khachian besitzt. Diesem Verfahren liegt die folgende Beobachtung zugrunde: Angenommen das zulässige Gebiet eines LOPs ist ein beschränktes Polyeder, d. h. ein Polytop und man befindet sich in einem Punkt nahe dem Zentrum dieses Polytops, dann ermöglicht die zulässige Richtung steilsten Abstiegs einen relativ großen Schritt in Richtung einer Lösung des Problems, während sie für nicht zentral liegende Punkte schnell in die Nähe des Randes des Polytops führen und daher ungünstig sein kann. Denn kann man dem Rand nicht mehr entkommen und folgt man diesem bzw. muss man diesem aufgrund der festgelegten Richtungswahl (im Inneren des Polytops) in Richtung einer Lösung folgen, so kann dies im ungünstigsten Fall zu einem ähnlichen Verhalten führen, wie es Klee und Minty für den Simplexalgorithmus gezeigt hatten.
Karmarkar hatte deshalb die Idee, in jedem Schritt eine projektive Transformation zu verwenden, die das Polytop so auf sich selbst abbildet, dass die aktuelle (transformierte) Iterierte zentral bezüglich des durch die Transformation erzeugten Polytops liegt. Er schlug dann weiter vor, für das mittels dieser Transformation erzeugte Problem bzw., da dieses nichtlinear ist, für ein dazu äquivalentes lineares Problem die zulässige Richtung steilsten Abstiegs zu bestimmen und damit für dieses Problem eine neue Näherung zu erzeugen, die wiederum im Inneren des Polytops liegt. Diese mit der inversen Transformation in den Ursprungsraum zurück transformierte Näherung dient dann als nächste Iterierte für das ursprüngliche Problem. Karmarkar konnte Konvergenz und polynomiale Laufzeit für sein Verfahren beweisen.
Im Unterschied zum Simplexalgorithmus arbeitet das Verfahren von Karmarkar also mit inneren Punkten des zulässigen Gebietes. Karmarkar’s Behauptung, dass sein Verfahren, welches ja eine polynomiale Laufzeit aufweist, überdies bei den größten von ihm gerechneten Problemen bis zu 50 mal schneller sei als der Simplexalgorithmus, löste große Erwartungen aus. Die Tatsache, dass er - vermutlich aus vertraglichen Gründen gegenüber seinem Arbeitgeber, den AT&T Bell Laboratories - nicht bereit war (s. Combinatorica 5, 1984), rechnerische Details anzugeben (ein guter Code zur Lösung linearer Optimierungsprobleme bringt heute sehr viel Geld ein), verursachte jedoch gleichzeitig große Verärgerung und Diskussionen bis hinein in die Tagespresse (wie z.B. Schrijver im CWI Newsletter 8, 1985, beschreibt). Mit der Zeit wurden aber die Details des Karmarkar-Verfahrens bekannt und stellte es sich heraus, dass es im Einzelfall zwar erheblich schneller als der Simplexalgorithmus sein, ein solches Verhalten aber nicht allgemein angenommen werden kann.
Karmarkar geht für seinen Algorithmus von einer speziellen Gestalt eines linearen Optimierungsproblems aus. Die Überführung eines gegebenen LOPs in diese Gestalt kann ein Problem erheblich vergrößern. Außerdem ist die von Karmarkar - im Rahmen der linearen Optimierung verwendete - projektive Transformation eine nichtlineare Abbildung, und hat diese Nachteile. Das Karmarkar-Verfahren selbst hat heute keine praktische Bedeutung mehr. Wesentlich war jedoch, wie Karmarkar die polynomiale Komplexität seines Verfahrens bewiesen hatte. Er hatte nämlich eine sog. Potentialfunktion verwendet und gezeigt, dass die polynomiale Komplexität seines Verfahrens folgt, wenn der Wert dieser Funktion in jeder Iteration um den gleichen Wert abnimmt (und damit gegen
strebt). Also lag es nahe, direkt oder indirekt eine solche Potentialfunktion zu verwenden und Verfahren zu konstruieren, deren Iterierte die entsprechende Funktion in jeder Iteration um denselben Wert reduzieren.
Die Auseinandersetzungen mit dem Karmarkar-Verfahren erwiesen sich für die Optimierung als äußerst fruchtbar. Sie lösten eine wahre Flut von Publikationen aus und führten schließlich zu einer großen Zahl neuer Verfahren zur Lösung linearer und konvexer Optimierungsprobleme, den sog. Innere-Punkte-Verfahren (interior-point methods). Dabei haben sich inzwischen einige unterschiedliche Verfahrensklassen herausgebildet, wobei sich jede dieser Klassen wiederum in primale, duale und primal-duale Verfahren untergliedert, in Bezug darauf, ob diese primal, dual oder primal und dual zulässige Iterierte erzeugen.
Zunächst einmal gibt es die Klasse der Affine-Scaling-Verfahren, die wie das Karmarkar-Verfahren auf einer Transformation beruhen, welche aber im Vergleich zu diesem linear ist. Überdies geht beispielsweise ein primaler Affine-Scaling-Algorithmus direkt von der Standard-Normalform eines LOPs aus. Ein erster solcher primaler Affine-Scaling-Algorithmus wurde 1986 unabhängig voneinander von Barnes und von Vanderbei, Meketon und Freedman entwickelt und stellt wohl die einfachste Innere-Punkte-Methode überhaupt dar. (Wie man später feststellte, war dieser Algorithmus bereits 1967 von Dikin vorgeschlagen worden). Leider zeigten aber Experimente (ein theoretischer Beweis steht noch aus), dass der Algorithmus, wenn er auf das Problem
angewandt und in der Nähe einer Ecke von
gestartet wird, dem Rand von
im Inneren von
folgen und somit im Extremfall wie der Simplexalgorithmus eine exponentielle Anzahl von Iterationen zur Lösung von
benötigen kann.
Die Potentialreduktionsverfahren (potential reduction methods) verwenden direkt eine Potentialfunktion für ein LOP und vermindern deren Wert in jedem Schritt wenigstens um eine feste Größe. Diese Verfahren gehen auf Ye, 1988, zurück. Für sie kann üblicherweise polynomiale Laufzeit nachgewiesen werden.
Es wurde erkannt, dass die Funktionswerte einer Potentialfunktion in jeder Iteration am ehesten dann um dieselbe Größe verringert werden können, wenn die Iterierten des zugehörigen Verfahrens in gewissem Sinne zentral bezüglich des Inneren des jeweiligen zulässigen Gebietes liegen. Diese Beobachtung hat zu einer weiteren, der wohl wichtigsten Klasse von Innere-Punkte-Verfahren geführt, den Pfadverfolgungsmethoden (path following methods). Solche Methoden (die erste geht auf Meggido, 1989, zurück) erzeugen Iterierte, welche näherungsweise dem sog. zentralen Pfad im Inneren des betreffenden zulässigen Gebietes folgen. Bei den wichtigen primal-dualen Pfadverfolgungsmethoden ist ein Punkt auf dem zugehörigen Pfad als eindeutige Lösung eines schwach nichtlinearen Gleichungssystems gegeben, so dass bei diesen Verfahren das Newton-Verfahren zur Lösung nichtlinearer Gleichungssysteme eine entscheidende Rolle spielt.
Pfadverfolgungsverfahren vereinigen ein ausgezeichnetes theoretisches und praktisches Verhalten und sind daher gegenwärtig wohl die Verfahren, welche man insbesondere zur Lösung sehr großer linearer Optimierungsprobleme verwenden sollte. Ihre Grundlagen gehen auf Arbeiten von Frisch, 1956, und Fiacco und McCormick ([FiMcCo68]) zurück.
Innere-Punkte-Verfahren können also dem Simplexalgorithmus bei großen linearen Problemen deutlich überlegen sein. Solche Verfahren wurden inzwischen auch für die Lösung konvexer Optimierungsprobleme entwickelt, und es gibt bereits zahlreiche Vorschläge, wie die ihnen zugrunde liegenden Ideen für die Lösung nichtlinearer Probleme genutzt werden können. Man kann jetzt schon sagen, dass diese Entwicklung auch das Gebiet der numerischen nichtlinearen Optimierung, welches schon weitgehend abgeschlossen zu sein schien, erheblich bereichert hat und möglicherweise auch noch weiter bereichern wird.
Das Karmarkar-Verfahren, ein primaler Affine-Scaling-Algorithmus und ein Potentialreduktionsverfahren werden ausführlicher z. B. in [Ree01] diskutiert. Im Folgenden wollen wir hier nur auf die wichtigen primal-dualen Pfadverfolgungsmethoden näher eingehen.
Wir gehen im Folgenden aus von dem linearen Optimierungsproblem in Normalform

Den zulässigen Bereich von Problem
bezeichnen wir wieder mit

und sein Inneres (vgl. Abschnitt 4.4) mit

Das zu
duale Problem lautet

Es besitzt den zulässigen Bereich

mit Innerem

Für
definieren wir durch

eine Diagonalmatrix, welche für
positiv definit ist und die positiv definite Inverse

besitzt. Entsprechend sind
und
die durch
erzeugten Diagonalmatrizen.
Schließlich machen wir grundsätzlich die für primal-duale Innere-Punkte-Verfahren typischen Annahmen
- (A1)
,
- (A2)
,
- (A3)
.
Die Annahmen (A2) und (A3) implizieren nach dem starken Dualitätssatz insbesondere die Lösbarkeit von
und
. In diesem Zusammenhang ist auch folgendes Resultat interessant (s. [Wri97], S. 26 ff.):
- Es seien
und
Die Lösungsmenge von
ist nichtleer und beschränkt.
- (ii)
ist nichtleer und beschränkt.
Da bekannt ist, wie lineare Gleichungssystem zu lösen sind, verursacht die Ungleichungsnebenbedingung
die Hauptschwierigkeit bei der Lösung des LOPs
. Eine Idee ist es daher zu versuchen, diese Bedingung als Nebenbedingung zu entfernen und sie in einer geeigneten Form wenigstens näherungsweise in der Zielfunktion mit zu berücksichtigen. Ähnlich kann man mit der Bedingung
in dem dualen Problem
verfahren.
Man betrachtet dazu die von einem Parameter
abhängenden Hilfsprobleme

und

Die Bedingungen
und
müssen wir in die Problemformulierungen mit aufnehmen, da die jeweilige Zielfunktion für andere Werte nicht definiert ist. Sie sind aber im Rahmen von Innere-Punkte-Verfahren einfach zu behandeln. Die Probleme
und
besitzen also gerade
und
als zulässige Gebiete, welche nach unseren Annahmen (A2) und (A3) nichtleer sind.
Die Zielfunktion von
gewinnt man dabei aus der Zielfunktion
von
, indem man zu letzterer die logarithmische Barrierefunktion

mit Barriereparameter
hinzu addiert. Für
erzeugt diese im Inneren des zulässigen Gebietes
von
eine Barriere, welche verhindert, dass man bei der Lösung von
dem Rand von
zu nahe kommt. Denn für
hat man
, so dass eine Lösung
von
, sofern eine solche existiert, nicht „zu nahe“ am Rand von
liegen wird. Dabei ist zu vermuten, dass der Barriereterm bei der Lösung von
für
eine immer kleinere Rolle spielt und eine Folge
, sofern eine solche definiert ist, für
gegen eine Lösung von
konvergiert. Analoges lässt sich für das Problem
sagen.
Es gilt nun

Für
ist die Matrix
eine positiv definite und für
die Matrix
eine negativ semidefinite Diagonalmatrix. Also ist
strikt konvex auf
und
konkav auf
. Insbesondere hat daher Problem
nach Satz 2.37 höchstens eine Lösung
.
Die Probleme
und
besitzen beide das System
aus Abschnitt 4.6.1 als notwendige und hinreichende Optimalitätsbedingungen (siehe auch das System
in Abschnitt 4.6.3). Wir wollen als nächstes zeigen, dass auch
und
durch ein gemeinsames System von Optimalitätsbedingungen charakterisierbar sind. Dazu überlege man sich zunächst:
Man überlegt sich leicht: Enthält das Problem
aus Abschnitt 3.2 zusätzlich die Nebenbedingung
, wobei
eine offene Menge ist, so bleibt die Aussage des Korollars 3.14 gültig, wenn man diese Nebenbedingung mit in die KKT-Bedingungen aufnimmt.
Unter Verwendung von Bemerkung 6.3 schließen wir für
, dass
genau dann Lösung von
ist, wenn
für ein
das folgende System löst:
- (6.2)

- (6.3)

- (6.4)

Wir setzen nun
und
, wobei wir für letztere Beziehung mehrere äquivalente Schreibweisen angeben können:
- (6.5)

Offenbar gilt somit
genau dann, wenn
ist, so dass wir die (redundante) Bedingung
auch noch mit in das obige System aufnehmen können. Das System (6.2)–(6.4) besitzt also genau dann eine Lösung
, wenn das System

eine Lösung
hat.
Problem
können wir in ein konvexes Minimierungsproblem mit konvexer Zielfunktion
umschreiben. Gemäß Bemerkung 6.3 löst demnach
das Problem
genau dann, wenn
für ein
den folgenden Bedingungen genügt:
- (6.6)

- (6.7)

- (6.8)

- (6.9)

Fassen wir (6.6) und (6.7) zu
- (6.10)

zusammen, setzen wir
, was mit
auch
impliziert und nutzen wir (6.5) aus, so geht das System (6.8)–(6.10) ebenfalls in das System
über.
Insbesondere existiert also zu einer Lösung
von
, sofern es ein solches
gibt, eine Lösung
von
, so dass
eine Lösung von
ist. Wir werden mit Satz 6.5 zeigen, dass
und
eindeutige Lösungen haben und dass somit gilt:
- (6.11)
löst
löst
löst
.
Satz 6.5 im voraus verwendend können wir also unsere Überlegungen zu folgendem Ergebnis zusammenfassen:
- Sei
.
- (i) Es gilt:
ist lösbar
ist lösbar
ist lösbar.
- (ii)
und
sind genau dann Lösungen von
und
, wenn
eine Lösung von
ist.
Das System
ähnelt offenbar dem System
aus Abschnitt 4.6.3. Während
und
keine eindeutigen Lösungen haben müssen, können wir beweisen, dass
und
unter den Voraussetzungen (A1)–(A3) eindeutig lösbar sind. Insbesondere hat man dann damit, dass
und
Lösungen besitzen.
- Die Probleme
und
und das System
besitzen für jedes
eindeutige Lösungen.
Wir zeigen zunächst, dass
eine Lösung hat. Dazu sei
fest gewählt. Für
gilt dann nach dem schwachen Dualitätssatz

Damit schließen wir
- (6.12)


Sei nun

Dann folgt

Also ist
strikt konvex für
und besitzt
den eindeutigen Minimalpunkt
mit
, was
für alle
impliziert. Schließlich hat man
oder
.
Für ein
definieren wir jetzt

Aus den Eigenschaften von
folgt die Existenz von
, so dass gilt:
![{\displaystyle \{t>0{\big |}g_{i}(t)\leq \gamma _{0}\}=[\alpha _{i},\beta _{i}].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/55477ef116817ba17e8e4fe7ac50b921c44bab48)
Für die Niveaumenge

können wir daher schließen:
![{\displaystyle N_{\tau }(x^{0})\subseteq \{x\in Z_{P}^{o}{\big |}g_{i}(x_{i})\leq \gamma _{0}~(i=1,\ldots ,n)\}\subseteq [\alpha _{1},\beta _{1}]\times \ldots \times [\alpha _{n},\beta _{n}].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4dd943e9218a225a4ac24e3e58e1224811167739)
Letzteres zeigt, dass
beschränkt ist.
Für den Nachweis der Abgeschlossenheit von
gehen wir von einer Folge
mit
und
aus. Offenbar ist dann
. Es ist sogar
. Denn wäre
für ein
, so hätte man
und damit den Widerspruch

Stetigkeit von
auf
impliziert schließlich
. Aus den Sätzen 2.37 und 2.40 kann man daher folgern, dass das Problem
genau eine Lösung besitzt.
Da
lösbar ist, folgt nun nach dem vor Satz 6.4 Gezeigten die Existenz einer Lösung
von
, wobei
die eindeutige Lösung von
ist. Die Bedingung
legt
als
mit

auf eindeutige Weise fest. Weiter ist
Lösung der Gleichung
und damit der Gleichung
, welche wegen (A1) (vgl. Lemma 2.21) eindeutig lösbar ist mit

Also hat
genau eine Lösung.
Schließlich gilt nach dem vor Satz 6.4 Gezeigten, weil
eine Lösung hat, dass dies auch
tut. Wie wir dort hergeleitet haben, gibt es insbesondere zu Lösungen
und
von
Punkte
, so dass
und
das System
lösen. Die eindeutige Lösbarkeit von
impliziert also die von
.
q.e.d.
Die somit wohldefinierte Menge

nennt man den primal-dualen zentralen Pfad (primal-dual central path). Entsprechend bezeichnet man die Menge

als den primalen zentralen Pfad (primal central path).
Wenn für den primalen oder primal-dualen zentralen Pfad Konvergenz

gezeigt werden kann, so muss der Grenzwert
, wie man sofort durch Grenzwertbildung in
erkennt, Lösung des Systems

sein und müssen damit
und
das Problem
bzw.
lösen. Wir können also
als Grenzwertproblem zur Folge der Probleme
für
ansehen. Es deutet sich damit an, dass Lösungen von
für
zu Lösungen von
und
führen.
Wie man durch Betrachtung der jeweiligen Optimalitätsbedingungen erkennt, ist das Problem
äquivalent mit dem Problem, das man erhält, wenn man die Zielfunktion
von
durch
dividiert. Diesem äquivalenten Problem kann man für
formal das Problem
- (6.13)

zuordnen, das in der Theorie der Inneren-Punkte-Verfahren eine besondere Bedeutung hat. Im Fall, dass Problem (6.13) einen eindeutigen Minimalpunkt besitzt, bezeichnet man diesen als das analytische Zentrum (analytic center) von
. Es gilt z. B. (man beachte, dass wir Satz 6.5 unter den Voraussetzungen (A1), (A2) und (A3) für ein gegebenes
bewiesen hatten):
- Es sei
beschränkt. Dann besitzt Problem (6.13) eine eindeutige Lösung.
Um Satz 6.5 für
und
anwenden zu können, müssen wir das Erfülltsein von (A3) für
zeigen. Wir bezeichnen die Probleme
und
für den Fall
mit
und
und ihre zulässigen Bereiche und deren Innere mit
sowie
. Da die Lösungsmenge von
nichtleer, gleich
und beschränkt ist, hat man nach den Sätzen 4.17 und 6.2, dass auch
eine Lösung besitzt und auch
gilt.
q.e.d.
Wir geben dazu ein Beispiel.
Wir betrachten das folgende Problem:
- (6.14)

und dazu das
entsprechende KKT-System





Auflösung der dritten Zeile nach den
und Einsetzung in die zweite Zeile führt auf das System
- (6.15)

- (6.16)

- (6.17)

Aus der ersten und dritten Zeile von (6.16) erhält man
, also wegen
insbesondere
. Gleichung (6.15) nach
aufgelöst und in die zweite Zeile von (6.16) eingesetzt ergibt dann
. Es folgt

Wegen
gelangt man mit letzterer Gleichung zu:

Die Folge
konvergiert für
gegen den Vektor
, der nach den obigen Überlegungen Lösung von
ist.
Ersetzt man den Vektor
auf der rechten Seite in (6.16) durch den Nullvektor und setzt man
, so erhält man aus (6.15)–(6.17) im Hinblick auf das hier (6.13) entsprechende Problem das KKT-System



Dieses hat die Lösung
und
. Der Vektor
ist also das analytische Zentrum des zulässigen Bereichs von Problem (6.14). Man kann zeigen, dass
gilt. (Letzteres ist allgemein richtig, wenn
beschränkt ist; vgl. [Sai97], S. 225.)
Die Lösungsmenge von Problem (6.14) ist offenbar gegeben durch

Das analytische Zentrum von
errechnet sich aus dem System



welches
mit
als einzige Lösung besitzt. Also ist die Lösung
von Problem (6.14), die man erhält, wenn man dem primalen Pfad folgt, das analytische Zentrum der Lösungsmenge des Problems. (Letzteres Resultat lässt sich allgemein beweisen; siehe [Sai97], S. 225.) Ferner ist offenbar

ein strikt komplementäres Lösungspaar für das Problem (6.14) und das dazu duale Problem, wie man durch Einsetzen von
und
in das oben aufgeführte, dem System
entsprechende KKT-System mit
erkennt.
Analog kann man auch für
ein analytisches Zentrum definieren.
6.4 Ein allgemeiner Rahmen für primal-duale Verfahren
[Bearbeiten]
Der an Beispiel 6.7 gezeigte, aber hier nicht allgemein bewiesene Umstand, dass
für
gegen eine Lösung von
konvergiert (und zwar gegen das analytische Zentrum der Lösungsmenge von
, welche nach Satz 6.2 beschränkt ist), liefert die Motivation für eine auf Gonzaga ([Gon89]) zurückgehende primale Pfadverfolgungsmethode. Die Idee dabei ist es, ausgehend von Punkten
und
und einem
in der
-ten Iteration einen Newton-Schritt für das Problem
durchzuführen und anschließend
zu verkleinern. Ziel ist es, auf diese Weise dem primalen zentralen Pfad wenigstens näherungsweise zu folgen (daher: Pfadverfolgungsmethode).
Offenbar macht es keinen Sinn,
im
-ten Schritt bei einer solchen Vorgehensweise festzuhalten und das Newton-Verfahren fortzuführen, da man ja an einer genauen Lösung von
für ein
gar nicht interessiert ist. Bei dem beschriebenen Vorgehen ignoriert man die Nebenbedingungen
und
und sichert man deren Erfülltsein für
und
dadurch, dass man sich von
und
nur einen hinreichend kleinen Schritt weg bewegt. Auf diese primale Pfadverfolgungsmethode wollen wir hier aber nicht näher eingehen, sondern wir wollen uns gleich den effizienteren primal-dualen Methoden zuwenden.
In Abschnitt 6.3 haben wir gesehen, dass das System

für festes
eine eindeutige Lösung
besitzt und dass
und
die Probleme
und
lösen. Die Menge aller solcher Lösungen für
definiert den (primal-dualen) zentralen Pfad. Ferner haben wir festgestellt, dass im Fall der Konvergenz
- (6.18)

der Grenzwert
Lösung von
ist und damit
und
Lösungen von
bzw.
sind. Also liegt es nahe, Verfahren zu konstruieren, die für eine Nullfolge
Näherungen
von
erzeugen, so dass
- (6.19)

und damit
für
gilt.
Im Hinblick auf die Lösung des Systems
für gegebenes
betrachten wir das Gleichungssystem
- (6.20)

- (6.21)

- (6.22)

In diesem sind die Gleichungen (6.20) und (6.21) linear und ist die Gleichung (6.22) schwach nichtlinear. Addiert man die einzelnen Zeilen der Gleichung (6.22), so folgt daraus für
die Beziehung

Das System (6.20)–(6.22) schreiben wir jetzt in der Form
- (6.23)

so dass
für
und
durch

gegeben ist. Die Jacobi-Matrix zu
lautet

und ist offenbar von
und
unabhängig.
Das System
lässt sich für gegebenes
im allgemeinen nicht exakt lösen und eine exakte Lösung von
wird ja auch, wie oben für ein primales Verfahren erläutert wurde, gar nicht benötigt. Die Idee bei den primal-dualen Pfadverfolgungsmethoden ist es, für gegebenes
und einer durch
und
gegebenen Näherung
mit einer geeigneten Schrittweite einen Newton-Schritt in Richtung des auf dem zentralen Pfad liegenden Punktes
durchzuführen. Dabei soll
gegen Null konvergieren und insbesondere durch die Schrittweitenwahl garantiert sein, dass die Glieder der Folge
in einer geeignet gewählten Umgebung des zentralen Pfades bleiben und die Konvergenz (6.19) folgt.
Das Newton-Verfahren wird bekanntlich zur Bestimmung einer Nullstelle einer einmal stetig differenzierbaren Funktion
, also eines
mit
, verwendet. Die Iterationsvorschrift des Newton-Verfahrens lautet
- (6.24)

wobei

die als nichtsingulär angenommene Jacobi-Matrix von
in
sei. Die in (6.24) vorkommende sog. Newton-Richtung

gewinnt man sinnvollerweise als Lösung des linearen Gleichungssystems
- (6.25)

Denn die Berechnung der Inversen einer
-Matrix, wie hier die der Matrix
, erfordert bekanntlich mehr Rechenoperationen.
Für
und
mit
ergibt sich die Newton-Richtung für das System (6.23) als Lösung des linearen Gleichungssystems (vgl. (6.25))

welches ausgeschrieben lautet:
- (6.26)

- Die Matrix
in (6.26) ist für
und
nichtsingulär.
Mit
lautet das System
ausgeschrieben
- (6.27)

- (6.28)

- (6.29)

Gleichung (6.28) liefert mit (6.27)

und Gleichung (6.29) impliziert
- (6.30)

Also hat man

woraus
wegen der positiven Definitheit von
folgt. Nach (6.30) ist damit
. Schließlich folgt mit (6.28) unter Verwendung unserer Standardvoraussetzung
, dass
ist.
q.e.d.
Das System (6.26) besitzt also eine eindeutige Lösung
. Geeigneterweise wird
als Produkt der Form
gewählt, wobei

ein Dualitätsmaß, nämlich der arithmetische Mittelwert der Produkte
und
ein Zentrierungsparameter ist. Für
macht man offenbar einen Newton-Schritt in Richtung der Lösung des Systems
, also in Richtung des zentralen Pfades, auf dem alle Produkte
denselben Wert
haben. Man nennt daher eine solche Richtung auch zentrierende Richtung (centering direction). Eine solche Richtung bringt typischerweise nur wenig oder keinen Fortschritt bezüglich der Verkleinerung von
, lässt aber erwarten, dass man in der nächsten Iteration einen größeren Schritt bezüglich einer wohldefinierten Umgebung des zentralen Pfades gehen kann. Im anderen Extremfall
macht man einen Newton-Schritt in Richtung einer Lösung des Systems (6.20)–(6.22) für
, was zwar im allgemeinen eine Verkleinerung von
zur Folge hat, aber auch bedeuten kann, dass in der nächsten Iteration nur ein kleiner Schritt innerhalb der gewählten Umgebung des zentralen Pfades möglich ist. Die meisten Algorithmen verwenden daher Werte
, um einerseits Nähe zum zentralen Pfad zu erzwingen und andererseits
zu verkleinern.
Diese Überlegungen führen nun zu folgendem Modellalgorithmus, durch den sich eine Reihe von primal-dualen Pfadverfolgungsmethoden mittels spezieller Parameterwahl beschreiben lassen.
- (0) Wähle
und
. Setze
.
- (1) Berechne
und bestimme die Lösung
des linearen Gleichungssystems
- (6.31)

- (2) Bestimme eine geeignete Schrittweite
und ein
.
- (3) Setze

- (4) Setze
und gehe nach (1).
In der angegebenen Weise erzeugt der Modellalgorithmus 6.9 unendliche Folgen
und
, was im Hinblick auf die folgenden Untersuchungen angenehmer ist. Für die Implementierung eines speziellen Verfahrens hat man zwischen Schritt (0) und (1) folgende Abbruchbedingung einzuführen:
- Falls
ist, stop!
Im Schritt (0) ist dann außerdem noch

zu berechnen und
vorzugeben. Falls
bzw.
für alle
mit einem
gezeigt werden kann, bricht dann das Verfahren nach endlich vielen Iterationen mit einem
-optimalen Lösungspaar
und
von
und
ab (vgl. Korollar 4.19).
Man beachte, dass die Konvergenz von
gegen 0 nicht die Konvergenz der Folgen
und
impliziert. Da man
und
für alle
hat, können wir jedoch ähnlich wie (6.18) schließen: Gilt
, so ist jeder Häufungspunkt
der Folge
eine Lösung des Systems
und sind damit
und
Lösungen von
und
. Die Existenz von Häufungspunkten ist im Einzelfall zu beweisen.
Wir zeigen nun als erstes, dass die gewichtete Dualitätslücke
bei geeigneter Wahl der Schrittweite und der Konstanten
in jedem Schritt verkleinert werden kann. Dazu machen wir von folgenden Notationen Gebrauch, wobei
eine beliebige Schrittweite ist:
- (6.32)

- (6.33)

- Die Lösung
des linearen Gleichungssystems (6.31) besitzt die folgenden beiden Eigenschaften:
- (i)
,
- (ii)
.
(i) Die eindeutige Lösung
des Gleichungssystems (6.31) genügt offenbar den Gleichungen

Multiplikation der zweiten Gleichung von links mit
und Anwendung der ersten Gleichung impliziert

(ii) Die dritte Blockzeile des Gleichungssystems (6.31) führt zu

Summation der
Komponenten dieser Gleichung liefert unter Verwendung der Definition von

Zusammen mit Aussage (i) ergibt sich daraus

![{\displaystyle =(x^{k})^{T}s^{k}+\alpha \left((s^{k})^{T}\Delta x^{k}+(x^{k})^{T}\Delta s^{k}\right)+\alpha ^{2}(\Delta x^{k})^{T}\Delta s^{k}=(x^{k})^{T}s^{k}[1-\alpha (1-\sigma _{k})].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f456ad37c541e679ede5f7a7c4eea57ce9dc6252)
q.e.d.
Der folgende Satz besagt nun, dass der Modellalgorithmus 6.9 eine polynomiale Laufzeit hat, wenn die Abnahme des Dualitätsmaßes in jedem Schritt in gewissem Sinne gleichmäßig ist und dieses Maß im Startpunkt nicht zu groß ist. Dabei bedeutet
kleinste ganze Zahl größer oder gleich
.
- Es sei
beliebig gegeben und die Startvektoren
und
mögen mit einem
die Bedingung
- (6.34)

- erfüllen. Genügen die durch die Iterierten
des Modellalgorithmus 6.9 erzeugten
für gewisse Konstanten
und
mit
der Ungleichung
- (6.35)

- so gilt

- für

Aus (6.35) folgt für

Mehrfache Anwendung dieser Formel liefert zusammen mit (6.34)

Verwenden wir weiter die Abschätzung
bzw.
für
, so bekommen wir

Das Konvergenzkriterium
ist also dann erfüllt, wenn

gilt bzw., nach
aufgelöst,

Daraus folgt die Behauptung.
q.e.d.
Die Hauptmühe im Zusammenhang mit Innere-Punkte-Verfahren macht der Nachweis des Erfülltseins der Bedingung (6.35). Wir werden im nächsten Abschnitt ein Verfahren vorstellen, für das man diese Bedingung verifizieren kann.
Wir beschreiben nun hintereinander zwei konkrete primal-duale Innere-Punkte-Verfahren zur Lösung linearer Optimierungsaufgaben. Die Idee dieser Verfahren besteht darin, dem primal-dualen zentralen Pfad in Richtung einer Lösung des Problems zu folgen. Bei den zulässigen Verfahren (feasible methods) müssen dafür der primale und duale Startvektor zulässig sein und sind damit alle Iterierten primal und dual zulässig. Bei den nichtzulässigen Verfahren (infeasible methods) kann man dagegen mit primal und dual nichtzulässigen Punkten starten, was diese besonders attraktiv macht. Im Folgenden werden wir zunächst ein zulässiges Verfahren untersuchen, welches sich dem Modellalgorithmus 6.9 unterordnet. Anschließend werden wir dieses zu einem nichtzulässigen Verfahren verallgemeinern.
Da jeder Punkt des zentralen Pfades Lösung eines nichtlinearen Gleichungssystems ist, kann man im allgemeinen dem zentralen Pfad nur approximativ folgen. Man definiert sich daher eine geeignete (und bisweilen recht großzügig angelegte) Umgebung des zentralen Pfades, aus der Iterierte noch akzeptiert werden. Insbesondere wird so erzwungen, dass die Iterierten dem Rand des nichtnegativen Orthanten nicht „zu nahe“ zu kommen.
Eine in diesem Zusammenhang verwendete Umgebung des zentralen Pfades ist die 2-Norm-Umgebung

mit einem
und

Ein typischer Wert für
in der Praxis ist
.
Im Fall
stimmt die Umgebung
offenbar mit dem zentralen Pfad überein. Aber auch für
erlaubt die Wahl von
keine großen Abweichungen vom zentralen Pfad bzw. nur relativ kleine Schrittweiten
. Aus praktischer Sicht sind daher Verfahren, welche eine 2-Norm-Umgebung verwenden, weniger empfehlenswert. Sie besitzen aber häufig schöne theoretische Konvergenzeigenschaften (s. [Wri97]).
Eine gebräuchliche und hier verwendete Umgebung des zentralen Pfades ist die einseitige
-Norm-Umgebung
- (6.36)

mit einem
. Ihr Name resultiert aus den Implikationen

Mit diesen Implikationen kann man auch die Beziehung
für
schließen. Insbesondere stimmt
für
mit dem Inneren
des primal-dual zulässigen Bereichs überein. Ein typischer, in der Praxis verwendeter Wert für
ist
. Allgemein kann man sagen, dass Verfahren, die eine
-Norm-Umgebung des zentralen Pfades verwenden, meist größere Schrittweiten ermöglichen und daher in der Praxis schneller konvergieren als Verfahren mit einer 2-Norm-Umgebung. Jedoch sind ihre theoretisch nachgewiesenen Konvergenzeigenschaften häufig etwas schlechter als die letzterer.
Das folgende zulässige Verfahren erzeugt Iterierte in
für ein vorgegebenes
und ist aufgrund der Schrittweitenwahl ein sog. Long-Step-Verfahren. Wir verweisen in diesem Zusammenhang auf die in (6.32) und (6.33) eingeführten Notationen und auf Bemerkung 6.10.
- (0) Wähle
und
mit
und
. Setze
.
- (1) Wähle ein
und berechne
sowie die Lösung
des linearen Gleichungssystems
- (6.37)

- (2) Berechne
![{\displaystyle \alpha _{k}:=\max \left\{\alpha \in [0,1]{\big |}\left(x^{k}(\alpha ),y^{k}(\alpha ),s^{k}(\alpha )\right)\in {\mathcal {U}}_{-\infty }(\gamma )\right\}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bb2c4010774e5246a26e6a9954e0e759a5b264ec)
- (3) Setze

- (4) Setze
und gehe nach (1).
Algorithmus 6.13 ist offenbar vom Typ des Modellalgorithmus 6.9, wobei aber durch die spezielle Wahl des Zentrierungsparameters
insbesondere die beiden Extremfälle
und
ausgeschlossen sind. Die Berechnung der Schrittweite
im Schritt (2) ist zwar prinzipiell möglich (der Leser möge dies verifizieren), sie erfordert jedoch einen gewissen numerischen Aufwand, so dass man meist eine kleinere, aber einfach zu bestimmende Schrittweite verwendet, für welche sich die Konvergenzeigenschaften des Verfahrens nicht ändern (s. hierzu Bemerkung 6.16).
Die Konvergenz von Algorithmus 6.13 wollen wir hier nicht im Detail beweisen (wir verweisen dafür auf [Wri97] und [Ree01]). Man kann insbesondere zeigen, dass die Schrittweiten
nach unten von Null weg beschränkt sind.
- Sei
. Dann hat man

- für alle
mit
- (6.38)

- wobei
für jedes
ist.
Mit letzterem Ergebnis können wir nun die gewünschte Ungleichung vom Typ (6.35) beweisen.
- Seien
die durch Algorithmus 6.13 erzeugten Iterierten. Dann gilt für eine von
unabhängige Konstante

Für
schließt man aus Lemma 6.14
, so dass mit Lemma 6.11 (ii) folgt:
- (6.39)

Da die quadratische Funktion
konkav ist, nimmt sie ihr Minimum auf dem Intervall
in einem der Randpunkte an. Daher gilt für alle

Mit

folgt demnach die Behauptung.
q.e.d.
Wählt man
aus (6.38) anstelle von
als Schrittweite in Algorithmus 6.13, so gilt die Aussage von Satz 6.15 für das selbe
, wie man leicht aus dem Beweis des Satzes ersieht.
Verbindung der Sätze 6.15 und 6.12 liefert das entscheidende Konvergenzresultat für Algorithmus 6.13:
- Seien
die durch Algorithmus 6.13 erzeugten Iterierten, wobei der Startvektor
der Bedingung
- (6.40)

- für ein
genüge. Dann hat man

- für

Aufgrund von Bemerkung 6.16 erhält man das Konvergenzresultat von Satz 6.17 auch dann, wenn man in Algorithmus 2 in jeder Iteration anstelle von
die leicht berechenbare Konstante
als Schrittweite verwendet. Weiter kann man zeigen (vgl. Bemerkung 6.10), dass die Folge
einen Häufungspunkt
besitzt und dass für jeden solchen Häufungspunkt die Vektoren
und
ein strikt komplementäres Lösungspaar von
und
bilden (s. [Wri97], S. 100 ff., und beachte, dass man
hat und daher mit
auch
einen Häufungspunkt besitzt).
Für weitere Verfahren vom Typ des Modellalgorithmus 6.9 verweisen wir auf [Wri97].
Wir beschreiben nun abschließend eine nichtzulässige Pfadverfolgungsmethode (infeasible path following method), welche man als eine Modifikation des Algorithmus 6.13 auffassen kann. Dieses Verfahren lässt also primale und duale Startpunkte zu, die nicht im Inneren der jeweiligen zulässigen Gebieten liegen müssen. Solche Methoden gelten heute als die effizientesten und besten Innere-Punkte-Verfahren.
Wir definieren dazu die Residuen

wobei wir aus praktischen Gründen deren Abhängigkeit von
bzw.
nicht kennzeichnen, und wir bezeichnen weiter mit
und
die Residuen in Iterierten
und
. Für Algorithmus 6.13 galt
und
für alle
, weshalb wir auch von einem zulässigen Verfahren sprachen. Jedoch ist für jenes Verfahren die Bestimmung eines Startvektors
, der in
liegt und zusätzlich der Bedingung (6.40) genügt, nicht unproblematisch.
Bei dem in diesem Abschnitt vorgestellten Verfahren müssen der Startpunkt und die Iterierten
und
nicht mehr innere Punkte des primalen bzw. dualen zulässigen Bereichs sein. Folglich werden hier die Voraussetzungen (A2) und (A3) aus Abschnitt 6.2 nicht benötigt. Statt dessen setzen wir neben der Rangbedingung (A1) in diesem Abschnitt nur voraus:
- (A4) Das Problem
besitzt eine Lösung.
Nach Satz 4.17 impliziert (A4), dass auch das Problem
und das System
lösbar sind.
Um für nichtzulässige Punkte, also Punkte mit
und
, eine Umgebung des zentralen Pfades zu definieren, müssen wir die im vorigen Unterabschnitt eingeführte Menge
geeignet erweitern. Wir definieren daher
- (6.41)

wobei
und
gegebene Konstanten sind und sich
und
aus dem gewählten Startpunkt
ergeben. Die Forderung
ist hierbei nötig, damit der Startvektor
die in
gegenüber
zusätzlich auftretende Bedingung

erfüllt und demnach in
liegt. Mit dieser Bedingung wird gemessen, inwieweit die linearen Gleichungen
und
in
bzw.
verletzt sind.
Die Definition (6.41) einer Umgebung des zentralen Pfades garantiert für jede Folge
von Iterierten aus
, dass mit
auch
und
für
folgt und damit, ähnlich wie für zulässige Verfahren (vgl. Bemerkung 6.10), jeder Häufungspunkt der Folge
das System
erfüllt bzw. Lösungen der Probleme
und
liefert. Also ist für ein Verfahren, welches die Umgebung
verwendet, das Hauptziel, die Konvergenz
für
zu zeigen. Als Abbruchbedingung für ein solches Verfahren kann man dann wieder die Abfrage
für ein vorgegebenes
verwenden. Das zugehörige Iteriertenpaar
und
wird jedoch im allgemeinen nicht
-optimal für
und
im Sinne von Korollar 4.19 sein, da
und
die Gleichungssysteme
und
nicht exakt erfüllen müssen.
Der Algorithmus, den wir nun betrachten wollen, lautet unter Verwendung der Definitionen (6.32) und (6.33) folgendermaßen:
- (0) Wähle
und
mit
sowie
und
mit
, so dass
und
gelten. Setze
.
- (1) Für ein
und
bestimme die Lösung
des linearen Gleichungssystems
- (6.42)

- (2) Berechne
- (6.43)
![{\displaystyle \alpha _{k}:=\max \left\{\alpha \in [0,1]{\big |}\left(x^{k}(\alpha ),y^{k}(\alpha ),s^{k}(\alpha )\right)\in {\mathcal {U}}_{-\infty }(\gamma ,\beta ),{\frac {(x^{k}(\alpha ))^{T}s^{k}(\alpha )}{n}}\leq (1-0.01\alpha )\mu _{k}\right\}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/51db48288e95e2b42e548402d83c129448dcdcf6)
- (3) Setze

- (4) Setze
und gehe nach (1).
Algorithmus 6.18 ähnelt offenbar dem Algorithmus 6.13 weitgehend. Die Voraussetzung
ist im Folgenden formal notwendig. Wäre sie nicht erfüllt, d. h. wäre
, dann wären die Umgebungen
und
in (6.36) bzw. (6.41) identisch und wäre Algorithmus 6.18 aufgrund der Schrittweitenwahl nur eine Variante von Algorithmus 6.13.
Die Bedingung
an den Startpunkt ist für genügend kleines
immer erfüllbar und stellt sicher, dass
gilt. Da die Residuen
und
, anders als bei dem Modellalgorithmus 6.9 und Algorithmus 6.13, nicht mehr notwendig gleich Null sind, ergibt sich hier das lineare Gleichungssystem (6.42) aus der Anwendung des Newton-Verfahrens auf das ursprüngliche System (6.23).
Aufgrund der Wahl des Startpunktes
(es ist
) und der Wahl der Schrittweite in Schritt (2) des Verfahrens liegen alle durch Algorithmus 6.18 erzeugten Iterierten
in der Umgebung
des zentralen Pfades. Weiter impliziert die zweite Bedingung in (6.43) an die Wahl der Schrittweite
eine Abnahme des Dualitätsmaßes
.
Für Algorithmus 6.18 hat man nun das folgende Konvergenzresultat (s. [Wri97], [Ree01]).
- Sei
eine durch Algorithmus 6.18 erzeugte Folge. Dann gilt für eine von
unabhängige Konstante
:
- (i)

- (ii)

Bestimmt man die Schrittweite
von Algorithmus 6.18 nicht als den maximalen Wert aus der Menge
, sondern für ein vorgegebenes
als den maximalen Wert aus der Menge
, so dass die beiden Bedingungen in (6.43) erfüllt sind (letztere Zahl lässt sich leicht bestimmen), so gilt Satz 6.19 analog mit dem Wert
anstelle von
(vgl. [Ree01]).
Offenbar impliziert Aussage (i) von Satz 6.19 die Konvergenz
. Aussage (ii) garantiert damit die Konvergenzen