Benutzer:Stepri2005/Kurs:Optimierung/Der primale Affine-Scaling-Algorithmus

Aus Wikiversity

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.

Beispiel 6.1[Bearbeiten]

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.

6.2 Definitionen[Bearbeiten]

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

Satz 6.2[Bearbeiten]

Es seien und Die Lösungsmenge von ist nichtleer und beschränkt.
(ii) ist nichtleer und beschränkt.

6.3 Existenz des zentralen Pfades[Bearbeiten]

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:

Bemerkung 6.3[Bearbeiten]

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:

Satz 6.4[Bearbeiten]

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.

Satz 6.5[Bearbeiten]

Die Probleme und und das System besitzen für jedes eindeutige Lösungen.

Beweis.[Bearbeiten]

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:

Für die Niveaumenge

können wir daher schließen:

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):

Satz 6.6[Bearbeiten]

Es sei beschränkt. Dann besitzt Problem (6.13) eine eindeutige Lösung.

Beweis.[Bearbeiten]

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.

Beispiel 6.7[Bearbeiten]

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)

Lemma 6.8[Bearbeiten]

Die Matrix in (6.26) ist für und nichtsingulär.

Beweis.[Bearbeiten]

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.

Modellalgorithmus 6.9[Bearbeiten]

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

Bemerkung 6.10[Bearbeiten]

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)

Lemma 6.11[Bearbeiten]

Die Lösung des linearen Gleichungssystems (6.31) besitzt die folgenden beiden Eigenschaften:
(i) ,
(ii) .

Beweis.[Bearbeiten]

(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

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 .

Satz 6.12[Bearbeiten]

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

Beweis.[Bearbeiten]

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.

6.5 Ein zulässiges Verfahren[Bearbeiten]

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.

Algorithmus 6.13[Bearbeiten]

(0) Wähle und mit und . Setze .
(1) Wähle ein und berechne sowie die Lösung des linearen Gleichungssystems
(6.37)
(2) Berechne
(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.

Lemma 6.14[Bearbeiten]

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.

Satz 6.15[Bearbeiten]

Seien die durch Algorithmus 6.13 erzeugten Iterierten. Dann gilt für eine von unabhängige Konstante

Beweis.[Bearbeiten]

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.

Bemerkung 6.16[Bearbeiten]

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:

Satz 6.17[Bearbeiten]

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

6.6 Ein nichtzulässiges Verfahren[Bearbeiten]

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:

Algorithmus 6.18[Bearbeiten]

(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)
(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]).

Satz 6.19[Bearbeiten]

Sei eine durch Algorithmus 6.18 erzeugte Folge. Dann gilt für eine von unabhängige Konstante :
(i)
(ii)

Bemerkung 6.20[Bearbeiten]

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 für die Residuen.

Darüber hinaus zeigt Satz 6.19, dass die Folge -linear und die Folgen und -linear gegen Null bzw. den Nullvektor konvergieren. Dabei heißt eine Nullfolge positiver reeller Zahlen -linear konvergent, wenn eine Konstante existiert, so dass für alle gilt und -linear konvergent, wenn sie durch eine -linear konvergente Folge majorisiert wird, d. h. wenn man für alle hat.

Für Algorithmus 6.18 kann man ohne großen Mehraufwand sogar polynomiale Komplexität beweisen, wobei man allerdings die Wahl des Startvektors einzuschränken hat (vgl. Satz 6.2 bei [Wri97]). Schließlich kann man unter den zusätzlichen Voraussetzungen und auch zeigen, dass die Folge einen Häufungspunkt besitzt und dass jeder solche Häufungspunkt ein strikt komplementäres Lösungspaar von und liefert (vgl. [Wri97], S. 121 ff.).