Zum Inhalt springen

Benutzer:Stepri2005/Kurs:Optimierung/Pfadverfolgungsmethoden für lineare Optimierungsprobleme

Aus Wikiversity

Eine von der Struktur her zumindest im konvexen Fall einfache Klasse nichtlinearer Optimierungsprobleme mit Nebenbedingungen ist die der linear restringierten Optimierungsprobleme mit einer quadratischen Zielfunktion. Wie wir bereits in Abschnitt 1.1 gesagt haben, bezeichnet man solche Probleme als quadratische Optimierungsprobleme. Die theoretische und numerische Beherrschung quadratischer Optimierungsprobleme ist nicht nur im Hinblick auf Anwendungen von Interesse, die direkt auf diesen Problemtypus führen (z.B. [Alt02], [NoWri06]), sondern auch im Hinblick auf wichtige Algorithmen der restringierten nichtlinearen Optimierung wie z.B. den Sequential-Quadratic-Programming-Verfahren, bei denen quadratische Optimierungsprobleme als Teilprobleme gelöst werden müssen. Die effiziente Lösung quadratischer Optimierungsprobleme ist also insbesondere auch ein Erfordernis für die Lösung allgemeiner nichtlinearer Optimierungsprobleme.

Im Hinblick auf die Untersuchung quadratischer Optimierungsprobleme ist es oft nützlich, von der folgenden Normalform eines quadratischen Optimierungsproblems auszugehen, für das eine symmetrische Matrix und Daten und gegeben sind:

Mit den in Bemerkung 2.32 und Abschnitt 4.1 beschriebenen Operationen lässt sich erforderlichenfalls jedes Problem mit einer quadratischen Zielfunktion und linearen Nebenbedingungen in diese Form transformieren. Im Fall allerdings, dass ein Problem nur Gleichungsnebenbedingungen aufweist, sollte man und werden wir diese numerisch direkt behandeln und werden wir also nicht die Schrankenbedingungen für die Variablen durch Einführung zusätzlicher Variablen erzwingen.

Zumeist setzt man im Zusammenhang mit der Einfachheit halber - zumindest für theoretische Zwecke - die Rangbedingung voraus, so dass insbesondere ist. In Abschnitt 4.2 war festgestellt worden, dass das System im Fall entweder keine Lösung besitzt und damit der zulässige Bereich von leer ist oder dass in diesem Fall überflüssige Gleichungen im System auftreten, welche gestrichen werden können. In letzterem Fall hat dann die Systemmatrix des resultierenden Gleichungssystems den gewünschten vollen Rang.

Den zulässigen Bereich von Problem bezeichnen wir mit

(7.1)

Im Fall eines konvexen quadratischen Optimierungsproblems, also im Fall, dass eine konvexe Funktion bzw. positiv semidefinit ist (s. Lemma 2.33), ist jede lokale Lösung des Problems auch eine globale, so dass wir in diesem Fall wie zuvor nur von Lösungen des Problems sprechen.

Im speziellen Fall handelt es sich bei dem Problem offenbar um ein lineares Optimierungsproblem in Normalform. Üblicherweise diskutiert man lineare Optimierungsprobleme gesondert, wie wir das auch hier getan haben, weil lineare Optimierungsprobleme im Vergleich zu nichtlinearen quadratischen Optimierungsproblemen zusätzliche Eigenschaften aufweisen, die sich auch numerisch nutzen lassen. Manche der in diesem Kapitel präsentierten Ergebnisse schließen aber den linearen Fall und bekannte Ergebnisse für diesen mit ein und zwar immer dann, wenn nicht die positive Definitheit von auf dem oder auf einem Teilraum des gefordert wird. So ist insbesondere der Existenzsatz 7.2 und die Dualitätstheorie in Abschnitt 7.2 auch auf lineare Probleme anwendbar.

Ist nicht positiv semidefinit, d. h., ist kein konvexes Optimierungsproblem, so kann lokale Minimierer besitzen, die nicht globale Minimierer des Problems sind. Es gibt inzwischen numerische Ansätze dafür, wie man auch in einem derartigen Fall einen globalen Minimalpunkt finden kann. Die Behandlung einer solchen Aufgabe der globalen Optimierung geht jedoch über den Rahmen dieses Kurses hinaus.

Zum Inhalt dieses Kapitels: In Abschnitt 7.1 werden wir einen zentralen Satz zur Existenz einer Lösung von Problem beweisen. Thema von Abschnitt 7.2 ist eine Dualitätstheorie für konvexe quadratische Optimierungsprobleme, die den (engen) Zusammenhang zwischen dem Problem und dem sog. dualen quadratischen Optimierungsproblem, das mit den Daten von gebildet wird, zum Inhalt hat. Die diesbezüglichen Resultate sind für die Praxis insofern von großer Bedeutung, als mit einer Lösung des dualen Problems auch eine Lösung von Problem gewonnen werden kann und als das duale Problem möglicherweise leichter oder schneller als numerisch zu lösen ist.

In Abschnitt 7.4 diskutieren wir dann zunächst mehrere unterschiedliche Vorgehensweisen für die Lösung quadratischer Optimierungsprobleme, welche nur Gleichungsrestriktionen aufweisen. Anschließend werden wir in Abschnitt 7.5 ein oder zwei Verfahren für allgemeine quadratische Optimierungsprobleme diskutieren, und zwar ein Active-Set-Verfahren und wenn noch genügend Zeit dafür bleibt, ein modifiziertes Gradientenprojektionsverfahren.

7.1 Existenz einer Lösung

[Bearbeiten]

Für ein beliebiges nichtlineares Optimierungsproblem mit nichtleerem zulässigen Bereich ist es prinzipiell möglich, dass sein Minimalwert endlich ist, dass dieser aber für keinen zulässigen Punkt angenommen wird. Ein Beispiel dafür ist

Der folgende Satz impliziert, dass eine derartige Situation bei einem beliebigen quadratischen und damit, wie wir schon gesehen haben (s. Satz 4.13), auch bei einem linearen Optimierungsproblem nicht auftreten kann. Ein Problem dieses Typs mit nichtleerem zulässigen Bereich besitzt also entweder eine Lösung oder sein Minimalwert ist . Der Beweis dieser Aussage, auf die wir uns in diesem Kapitel mehrfach beziehen werden, ist erstaunlich kniffl­ig. Er mag beim ersten Lesen übersprungen werden. (Der folgende Satz schließt also die Aussage von Satz 4.13 für lineare Probleme mit ein, jedoch nicht die Aussage von Satz 4.14, weswegen wir den Existenzsatz für lineare Probleme gesondert bewiesen haben.)

Satz 7.1

[Bearbeiten]
Es seien und . Dann hat das Problem eine globale Lösung.

Beweis.

[Bearbeiten]

Wegen können wir ein finden, so dass die Menge

für alle nichtleer ist. Da kompakt und stetig ist, besitzt das Problem

nach dem Satz 2.38 von Weierstraß für jedes eine Lösung. Wir nehmen nun im Folgenden an, dass ist und wir setzen

Offenbar gilt aufgrund der Voraussetzung des Satzes und wegen

(7.2)

Die Lösungsmenge von ist, wie festgestellt wurde, nichtleer und sie ist als Teilmenge von kompakt. Also nimmt die stetige Funktion über der Lösungsmenge von ihr Infimum an und gibt es somit unter allen Lösungen von mindestens eine Lösung mit minimaler -Norm. Wir zeigen nun als nächstes:

(7.3) Es gibt ein , so dass für alle gilt.

Wäre Letzteres nicht richtig, so gäbe es eine Folge mit

Wir setzen nun

und können ohne Beschränkung der Allgemeinheit annehmen, dass für ein mit gilt. Weil nach unserer Konstruktion ist und damit

folgt, hat man für dieses

(7.4)

Es ist ferner und für optimal. Wegen können wir daher mit (7.2) schließen:

(7.5)

Diese Abschätzungen implizieren, dass ist, denn für würde im Widerspruch zu (7.5) folgen:

Wegen (7.4) und hat man als nächstes für . Also ergibt sich unter Verwendung der Beziehung für

(7.6)

Da der Ausdruck in (7.6) im Fall, dass für ein gelten würde, für gegen strebte, folgt damit

(7.7)

Wir wollen nun als nächstes zeigen, dass unter den gemachten Annahmen

(7.8)

für alle und alle mit einem und ein gilt. Diese Beziehungen stehen im Widerspruch dazu, dass eine Lösung von mit kleinster Euklidischer Norm ist, so dass (7.3) richtig sein muss.

Sei nun . Gemäß (7.4) ist , so dass wir setzen können:

Wegen können wir also ein wählen, so dass für alle gilt. Weil für alle ist, haben wir somit bei festem für alle mit

Offenbar ist ferner wegen und (7.4) auch sowie . Damit ist die erste Beziehung in (7.8) für alle genannten und gezeigt.

Wegen gibt es ein , so dass für alle gilt. Demzufolge erhalten wir bei festem und fest gewähltem mit für alle

Damit ist für die genannten und auch die zweite Beziehung in (7.8) bewiesen. Für diese , so dass man analog zu (7.6) unter Verwendung von (7.7) erschließt:

Somit ist die Gültigkeit von (7.8) und weiter die von (7.3) bewiesen.

Gemäß der Definition eines Infimums existiert eine Folge mit

(7.9)

Im Fall, dass beschränkt ist, gibt es ferner eine Teilfolge von mit , wobei wegen der Abgeschlossenheit von geschlossen werden kann. Aufgrund der Stetigkeit von folgt außerdem und daher . Somit ist für diesen Fall der Satz bewiesen und müssen wir abschließend noch den Fall betrachten, dass die Folge unbeschränkt ist.

Sei also eine unbeschränkte Folge mit (7.9) und sei . Dann folgt , und man erschließt daher mit (7.2)

Letzteres impliziert wegen (7.9) die Konvergenz . Also existiert eine Folge mit

(7.10)

wobei durch (7.3) bestimmt ist. Wir wollen nun als Letztes zeigen, dass

(7.11)

gilt und demnach für alle das Problem löst. Wir nehmen dazu an, dass (7.11) nicht richtig ist.

Für bzw. für hat man offenbar . Also konvergiert die Folge monoton fallend gegen . Wenn (7.11) nicht gilt, muss es weiter zwei Glieder und der Folge . Für und folgt dann mit (7.3)

da die Annahme zunächst und damit den Widerspruch zu (7.12) nach sich ziehen würde.

Wir setzen nun , so dass gilt. Insbesondere ist dann mit (7.12) und (7.3) und . Wäre nun , dann wäre wegen Element von und damit Lösung von . Dies ist jedoch wegen und der Minimaleigenschaft von bezüglich der Lösungsmenge von nicht möglich. Wegen ist und damit aber auch der Fall ausgeschlossen. Also ist die Implikation (7.11) gültig und der Satz damit bewiesen.

q.e.d.

Aus Satz 2.41 in Verbindung mit Lemma 2.33 können wir ferner direkt den folgenden Existenzsatz für konvexe quadratische Optimierungsprobleme ableiten.

Satz 7.2

[Bearbeiten]
Ist positiv definit und , so besitzt das Problem genau eine Lösung.

Die Voraussetzung der positiven Definitheit von im letzten Satz garantiert, dass die Zielfunktion von auf dem ganzen Raum gleichmäßig konvex ist, was die Existenz einer Lösung für sicherstellt. Wenn Gleichungsnebenbedingungen in vorliegen, muss die gleichmäßige Konvexität von für eine solche Existenzaussage jedoch nur auf einem geeigneten Teilraum des gegeben sein, da ja Gleichungsnebenbedingungen die Dimension des Suchraumes reduzieren (s. dazu Abschnitt 7.4).

7.2 Dualitätstheorie

[Bearbeiten]

7.2.1 Das duale Problem zu einem Problem in Normalform

[Bearbeiten]

Wir nehmen in diesem Abschnitt grundsätzlich an

ist positiv semidefinit

und wir betrachten das damit konvexe quadratische Optimierungsproblem in Normalform

In dem hier diskutierten Zusammenhang nennen wir das primale Problem. Den zulässigen Bereich von bezeichnen wir wie zuvor in (7.1) mit .

Gemäß Beispiel 3.16 (1) ist genau dann eine Lösung des Problems , wenn die nachstehenden KKT-Bedingungen erfüllt:

Wir wollen nun als erstes zeigen, dass aus einer Lösung des KKT-Systems für das Minimierungsproblem eine Lösung des KKT-Systems für das folgende, mit den Daten von erzeugte Maximierungsproblem gewonnen werden kann und umgekehrt und dass somit zwischen diesen beiden Problemen enge Beziehungen bestehen:

Das Problem nennt man in diesem Zusammenhang das zu duale Problem. Seinen zulässigen Bereich bezeichnen wir mit

Das Problem lässt sich offenbar auch äquivalent darstellen in der Form

(7.13)

Zur Herleitung der zugehörigen KKT-Bedingungen ersetzen wir das Maximierungsproblem äquivalent durch das folgende Minimierungsproblem (der Vorzeichenwechsel bezüglich des optimalen Zielfunktionswertes kann dabei vernachlässigt werden, da er für diesen Zweck keine Rolle spielt):

Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikiversity.org/v1/“:): {\displaystyle \begin{array}{lll} (QD)': & \text{Minimiere} & \frac 12 \begin{pmatrix} x \\ y \\ s \end{pmatrix}^T \begin{pmatrix} Q & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix} \begin{pmatrix} x \\ y \\ s \end{pmatrix} - \begin{pmatrix} 0 \\ b \\ 0 \end{pmatrix}^T \begin{pmatrix} x \\ y \\ s \end{pmatrix} \\ & \text{u. d. N.} & \begin{pmatrix} - Q \\ A \\ I \end{pmatrix}^T \begin{pmatrix} x \\ y \\ s \end{pmatrix} = c, \quad \begin{pmatrix} 0 \\ 0 \\ -I \end{pmatrix}^T \begin{pmatrix} x \\ y \\ s \ge 0 \end{pmatrix}.}

Dabei ist die -Einheitsmatrix. Die in der Zielfunktion von vorkommende Matrix ist wiederum eine symmetrische, positiv semidefinite Matrix, so dass es sich bei diesem Problem wie bei um ein linear restringiertes, konvexes quadratisches Optimierungsproblem handelt.

Nach Korollar 3.14 ist somit genau dann eine Lösung von , wenn es Vektoren und gibt, so dass das folgende System von Gleichungen und Ungleichungen löst (im Hinblick auf berücksichtige man dabei Bemerkung 3.6 (iii)):

(7.14)

Unter Ausnutzung der darin enthaltenen Beziehungen und können wir dieses System wie folgt schreiben:

(7.15)

Berücksichtigt man nun, dass ein System in den Variablen und letzteres System eines in den Variablen ist, so können wir offenbar schließen:

(7.16) löst löst (7.15) für gewisse löst löst

sowie

(7.17) löst löst für gewisse löst (7.15) löst .

Ist eine Lösung von und der zu der Gleichungsnebenbedingung in gehörende Multiplikator, so ist gemäß (7.16) eine Lösung von . (Viele Verfahren der nichtlinearen Optimierung zur Lösung eines Problems erzeugen zugehörige Multiplikatoren gleich mit.) Dabei unterscheiden sich und wegen nur durch eine Lösung von .

Weiter können wir festhalten: Besitzt das Problem eine Lösung, so besitzt es auch eine Lösung derart, dass das Problem löst. Dies folgt aus (7.17), da mit nach (7.16) auch lösbar ist. Im Fall, dass positiv definit ist, liefert sogar der -Anteil jeder Lösung des dualen Problems eine Lösung des primalen Problems, da in diesem Fall die beiden letzten Gleichungen in (7.15) bedeuten, dass gilt und damit und in den Implikationen (7.16) durch ersetzt werden können. Wenn positiv definit ist sowie im Fall sind also die KKT-Bedingungen für mit denen für identisch.

Wir haben damit unter anderem den folgenden Satz bewiesen:

Satz 7.3

[Bearbeiten]
(i) Es gilt:
ist lösbar ist lösbar ist lösbar.
(ii) Ist eine Lösung von , so löst das Problem und das Problem .
(iii) Besitzt das Problem eine Lösung, so besitzt es auch eine Lösung derart, dass ist und das Problem löst. Ist positiv definit, so hat jede Lösung von die letztere Eigenschaft.

Die drei Zeilen im System drücken offenbar die primale Zulässigkeit, die duale Zulässigkeit und die Komplementarität aus. Eine Lösung dieses Systems liefert nach Satz 7.3 Lösungen des primalen und dualen quadratischen Optimierungsproblems. Ist eine Lösung von einem der beiden Probleme bekannt, so lässt sich ferner über eine Lösung des anderen Problems gewinnen. Wenn positiv definit ist, liefert eine Lösung von gemäß Satz 7.3 sogar direkt eine Lösung von mit. Das duale Problem zu lösen kann also dann nützlich sein, wenn dieses schneller als zu lösen oder für den gerade verfügbaren Algorithmus günstiger als formuliert ist. Algorithmen gehen nämlich typischerweise von einer bestimmten Gestalt eines Problems aus, und die Überführung eines gegebenen Problems in diese Gestalt kann ja die Einführung vieler neuer Variablen bedeuten (vgl. Beispiel 4.2).

Überführt man das Problem unter Einführung zusätzlicher Variablen in ein Problem des Typs und stellt man anschließend das dazu duale Problem auf, so gelangt man ferner zu der folgenden Aussage.

Satz 7.4

[Bearbeiten]
Das duale Problem zu ist äquivalent mit .

Beweis.

[Bearbeiten]

Übung!

Es sei abschließend gesagt, dass man im linearen Fall, d. h. im Fall , mit Hilfe von (7.16) und (7.17) gerade Satz 4.17 erhält und Satz 7.4 in Satz 4.15 übergeht.

7.2.2 Dualitätssätze

[Bearbeiten]

Als nächstes wollen wir weitere Beziehungen zwischen dem primalen Problem und dem dualen Problem herleiten. Offenbar erhält man für ein Punktepaar zulässiger Punkte und unter Verwendung der Nebenbedingungen und der Zielfunktionen beider Probleme

(7.18)

Da man hat, führt diese Beobachtung zu der folgenden Aussage.

Satz 7.7 (Schwacher Dualitätssatz)

[Bearbeiten]
Für ein Paar zulässiger Punkte und der Probleme und gilt
Für und folgt insbesondere

Speziell für den linearen Fall gewinnt man unter Verwendung von (7.18) die nachstehende Folgerung.

Korollar 7.8 (Schwacher Dualitätssatz)

[Bearbeiten]
Für ein Paar zulässiger Punkte und der Probleme und gilt

Für ein Punktepaar und bezeichnet man den Abstand der Zielfunktionswerte des primalen und dualen Problems als Dualitätslücke. Im linearen Fall entspricht sie nach Korollar (7.8) der Zahl . Der folgende Satz besagt unter anderem, dass die Dualitätslücke für ein Paar von Lösungen des primalen und dualen Problems identisch 0 ist.

Satz 7.9 (Starker Dualitätssatz)

[Bearbeiten]
(i) Gilt und , so besitzen die beiden Probleme und eine Lösung.
(ii) und sind genau dann Lösungen von und , wenn und für und zulässig sind und wenn bzw. wenn äquivalent dazu gilt.

Beweis.

[Bearbeiten]

(i) Seien und . Für ein bekommt man dann aus Satz 7.7

Gemäß Satz 7.1 ist damit lösbar. Die Lösbarkeit von folgt nun aus Satz 7.3 (i).

(ii) Gilt , so folgt offenbar aus Satz 7.7 . Seien jetzt zunächst und Lösungen von und . Nach (7.17) existieren dann Vektoren und , so dass sowohl das System als auch das Problem löst. Insbesondere ist damit . Mit Satz 7.7 schließt man daher

Nun seien umgekehrt und zulässige Punkte von und mit . Nach Aussage (i) besitzt dann das Problem eine Lösung und nach (7.17) das Problem eine Lösung . Anwendung des ersten Teil des Beweises und von Satz 7.7 liefert schließlich

Also sind auch und Lösungen von und .

q.e.d.

Eine weitere wichtige Folgerung aus dem Vorangegangenen ist die folgende.

Korollar 7.10

[Bearbeiten]
(i) Es sei . Dann gilt
(ii) Es sei . Dann gilt

Aufgabe 7.11

[Bearbeiten]

Man beweise die Gültigkeit von Korollar 7.10.

Die Einschränkung von Satz 4.18 und Korollar 7.10 auf den linearen Fall erhält man, indem man die - bzw. -Anteile für Punkte des dualen Problems streicht.

Über und lässt sich für ein gegebenes quadratisches Optimierungsproblem beliebiger Gestalt das zugehörige duale Problem sofort ableiten. Insbesondere stellen offenbar und einen Spezialfall dieses allgemeinen Problempaares dar. Es können ferner alle Aussagen für und direkt auf und übertragen werden, da letztere Probleme ja gemäß ihrer Herleitung äquivalent mit Problemen der Gestalt von und sind. Wir fassen diese Aussagen nochmals zusammen, wobei und die zulässigen Gebiete von und seien.

Satz 7.12

[Bearbeiten]
Man beweise:
(i) Besitzt das Problem eine Lösung, so tut dies auch das Problem und die optimalen Zielfunktionswerte beider Probleme sind identisch.
(ii) Jede Lösung von mit nichtnegativem -Anteil löst und jede Lösung von löst .

Beweis.

[Bearbeiten]

Übung!

7.2.4 Ein weiterer Spezialfall

[Bearbeiten]

Ein anderer relevanter Spezialfall des Problempaares und ist das Problempaar

und

Im Fall, dass positiv definit ist, lässt sich die Gleichungsnebenbedingung in nach auflösen, was

(7.19)

ergibt. Setzt man letzteren Ausdruck in die Zielfunktion von ein, so erhält man

Folglich kann man das duale Problem für positiv definites durch das folgende äquivalente Problem ersetzen:

Die Matrix darin ist symmetrisch und positiv semidefinit und im Fall sogar positiv definit (s. Lemma 2.21). Insbesondere ist also das Problem , wenn man es äquivalent als ein Minimierungsproblem formuliert, wiederum ein konvexes quadratisches Optimierungsproblem.

Hat man eine Lösung von gefunden (im Fall ist diese eindeutig), so lässt sich der zugehörige -Anteil der Lösung von gemäß (7.19) als eindeutige Lösung des linearen Gleichungssystems

berechnen. Weiter besitzt offenbar für positiv definites eine eindeutige Lösung und ist gerade diese Lösung. (Man stelle z.B. für und die KKT-Bedingungen auf und schließe analog wie in (7.17), wobei man die Eindeutigkeit von für und berücksichtige.)

Eine Lösung von liefert also gleichzeitig eine Lösung von mit. Da das Problem nur einfache Schrankenbedingungen als Nebenbedingungen enthält, kann es wesentlich einfacher als Problem zu lösen sein. Allerdings benötigt man bei dieser Vorgehensweise die Matrix , so dass diese ohne allzu großen Aufwand zu berechnen sein sollte.

7.3 Elimination bei linearen Gleichungsrestriktionen

[Bearbeiten]

Bevor wir uns speziell mit nur gleichungsrestringierten quadratischen Optimierungsproblemen beschäftigen, wollen wir allgemein die Möglichkeit der Variablenelemination bei nichtlinearen Optimierungsproblemen mit linearen Gleichungsnebenbedingungen untersuchen.

7.3.1 Einleitung

[Bearbeiten]

Wir betrachten für eine Funktion und Daten und das durch lineare Gleichungen restringierte Problem

Den zulässigen Bereich von bezeichnen wir mit

(„GN“ steht für „Gleichungsnebenbedingungen“.) Falls linear ist, hat man die folgende Aussage:

Satz 7.13

[Bearbeiten]
Es sei mit einem und . Dann gilt:
(i) , falls ein mit existiert.
(ii) , falls kein mit existiert.

Beweis.

[Bearbeiten]

Übung!

Der Fall, dass das Problem eine lineare Zielfunktion hat, ist folglich uninteressant, da diese dann auf dem zulässigen Bereich entweder konstant oder nach unten unbeschränkt ist. Im Folgenden werden wir daher implizit davon ausgehen, dass in Problem eine nichtlineare Funktion ist.

Wir nehmen nun wieder und damit insbesondere an. Dabei ist der Fall nicht von Interesse, weil dann das System genau eine Lösung besitzt, welche die eindeutige Lösung von Problem ist. Für die folgenden beiden Unterabschnitte setzen wir daher

(7.20)

voraus. In diesem Fall lassen sich einige der Variablen durch die anderen ausdrücken und kann man somit zu einer Formulierung des Problems gelangen, welche weniger Variable als aufweist und überdies keine Restriktionen enthält. Wir beschreiben in diesem Zusammenhang zunächst die sog. einfache Elimination.

7.3.2 Einfache Elimination

[Bearbeiten]

Nach der Voraussetzung in (7.20) sind Spalten von linear unabhängig. Wir können annehmen, dass dies die ersten Spalten von sind. (Anderenfalls vertausche man die Spalten und die Variablen im System entsprechend.) Bezeichnen wir die nichtsinguläre Matrix, welche aus diesen Spalten von gebildet wird, mit , so können wir die Matrix blockweise in der Form

darstellen, wobei die aus den verbleibenden Spalten von bestehende Matrix ist. Dabei steht „“ hier für „Basis“ und „“ für „Nichtbasis“. Entsprechend schreiben wir den Variablenvektor mit Vektoren und in der Form

Für jedes können wir somit die Darstellung

erhalten, welche für die explizite Darstellung

(7.21)

impliziert (vgl. dazu die Darstellung (5.3)). Wählt man umgekehrt einen beliebigen Vektor und berechnet man anschließend nach (7.21), so ist eine Lösung des Systems und folglich ein zulässiger Punkt für das Problem .

Weiter bekommt man für die Zielfunktion von Problem die Darstellung

und damit für die alternative Formulierung

(7.22)

Besitzt das rechte der beiden Probleme eine Lösung , so rechnet man nach (7.21) aus. Der Vektor ist dann Lösung von . Unsere Herleitung zeigt insbesondere, dass das gleichungsrestringierte Problem mathematisch mit einem unrestringierten Problem äquivalent ist, welches überdies Variable weniger als aufweist. Den Vektor bezeichnet man in diesem Zusammenhang auch als Vektor der reduzierten Variablen.

Sind linear unabhängige Spalten von nicht wie in dem folgenden Beispiel unmittelbar identifizierbar, dann könnte man z. B. durch Gauß-Elimination mittels Spalten- und Zeilenpivotsuche feststellen, ob ist und könnte man in diesem Fall die Matrix aus den Spalten von bilden, die im letzten Gauß-Tableau an den ersten Positionen stehen, da diese linear unabhängig sein müssen. Man beachte aber, dass für die Aufstellung von Problem (7.22) eine explizite Darstellung der Inversen von benötigt wird, so dass idealerweise leicht zu invertieren und gut konditioniert sein sollte. Wir geben dazu ein Beispiel.

Beispiel 7.14

[Bearbeiten]

Wir betrachten das Problem

und wir setzen sowie

Offenbar sind die 3. und die 6. Spalte von linear unabhängig und bilden diese eine einfach zu invertierende Matrix. Wir vertauschen daher die 3. mit der 1. sowie die 6. mit der 2. Spalte von und entsprechend die Variablen im System . Mit

und

schreiben wir dann das System in der Form .

Als nächstes berechnen wir

und damit unter Verwendung von (7.21)

Einsetzen dieser Beziehung in die Zielfunktion des Problems führt auf das unrestringierte Optimierungsproblem

Man hätte die Matrix natürlich auch mit zwei anderen linear unabhängigen Spalten von bilden können, aber für diese wäre dann die Berechnung der Inversen und des Produktes aufwändiger gewesen.


Wir machen weiter die folgende Beobachtung (Im Zusammenhang mit Eliminationstechniken verwenden wir den Buchstaben für eine Matrix. Eine Verwechslung mit dem zulässigen Gebiet (3.12) des allgemeinen nichtlinearen Optimierungsproblems sollte ausgeschlossen sein.): Mit den Blockmatrizen

(7.23)

können wir jeden Vektor gemäß (7.21) darstellen in der Form

(7.24)

Dabei enthält die Matrix die -Einheitsmatrix und sind somit ihre Spalten linear unabhängig. Außerdem gilt

Demnach bilden die Spalten von eines Basis des Nullraums von

Wir stellen weiter mit Lemma 3.12 fest, dass für jedes genau dann eine zulässige Richtung für ist, wenn gilt.

Ferner hat man

Wie ein Vergleich mit (7.24) zeigt, drückt also die einfache Eliminationstechnik zulässige Punkte von als Summe der speziellen Lösung von und der zulässigen Richtung für aus. Insbesondere erhält man die spezielle Lösung , indem man Variable, d. h. gleich 0 setzt.

Einfache Elimination ist numerisch relativ „billig“, kann aber zu numerischen Instabilitäten führen, wie man sich im Fall eines Beispiels in zwei Veränderlichen geometrisch klarmacht. Verläuft nämlich die Lösungsmenge von fast parallel zur -Achse und ist eine Lösung von , die fast in Richtung der positiven -Achse zeigt, dann ist sehr klein und sind sowie sehr groß, so dass als Differenz zweier sehr großer Vektoren berechnet werden muss. Letzteres führt typischerweise zu numerischer Auslöschung. In einer solchen Situation sollte man die spezielle Lösung des Systems - hier ist dies - in Richtung der -Achse, d. h. sollte man eine andere Basis wählen. Eine geeignete Basis zu finden ist in der Praxis aber häufig eine nichttriviale Aufgabe. Weitere numerische Schwierigkeiten können bei der Invertierung der Basis auftreten, wenn schlecht konditioniert ist. Daher wollen wir im nächsten Unterabschnitt noch andere Reduktionstechniken betrachten.

Im Hinblick darauf bemerken wir noch, dass offenbar die Spalten von und die von zusammen genommen linear unabhängig sind und folglich den aufspannen. Nun ist aus der Linearen Algebra bekannt, dass für

gilt, wobei der Bildraum von ist und „“ die direkte Summe zweier Halbräume des bezeichnet. Da die Spalten von eine Basis von bilden, generieren die Spalten von daher eine Basis von .

7.3.3 Allgemeine Elimination

[Bearbeiten]

In Anlehnung an den vorangehenden Unterabschnitt seien und Matrizen, für die gilt:

(7.25)

Wie bei der einfachen Elimination bilden demnach die Spalten von eine Basis des Nullraumes von . Dagegen ist hier nur durch die erste Bedingung in (7.25) spezifiziert. Für die bei der einfachen Elimination verwendete Matrix ist diese Bedingung wegen

erfüllt, so dass die einfache Elimination einen Spezialfall der hier betrachteten Situation darstellt.

Bekanntlich lässt sich jede Lösung des inhomogenen Gleichungssystems als Summe einer beliebigen speziellen Lösung des Systems und einer Lösung des homogenen Systems , also jedes durch ein beliebiges und ein in der Form beschreiben. Da die Spalten von nach Voraussetzung eine Basis des Nullraumes bilden, gibt es zu jedem solchen ein mit .

Weiter ist mit einem Vektor eine spezielle Lösung von , wenn

bzw. wenn wegen der vorausgesetzten Invertierbarkeit von

gilt. Folglich erlaubt eine wie in (7.25) vorausgesetzte Wahl von und , dass jedes mittels Vektoren und in der Form

(7.26)

bzw. mit einem Vektor in der Form

(7.27)

geschrieben werden kann. Umgekehrt erhält man für jedes mittels (7.27) einen für zulässigen Punkt . Insbesondere liefert den Vektor und ist das Problem aufgrund von (7.27) mit folgendem unrestringierten Problem äquivalent:

Die Matrix wird idealerweise so gewählt, dass die Kondition der Matrix so klein wie möglich ist, weil zur Berechnung des Vektors das lineare Gleichungssystem gelöst werden muss. Wie wir zeigen wollen, ist es darum günstig, z. B. mit dem Householder-Verfahren eine -Zerlegung von der Art

zu berechnen, wie sie aus der Numerischen Mathematik bekannt ist. Dabei ist eine orthogonale Matrix und eine nichtsinguläre obere Dreiecksmatrix. Insbesondere haben somit die Untermatrizen und orthonormale Spalten.

Man definiert nun

d. h. , so dass die Spalten von und gemeinsam eine Orthonormalbasis des bilden. (Bei der einfachen Eliminationstechnik ist dies typischerweise nicht der Fall.) Wie man sich leicht klarmacht, gilt damit insbesondere und , so dass man aus

(7.28)

die Beziehungen

(7.29)

schließen kann.

Letzteres zeigt, dass die Matrizen und alle in (7.25) geforderten Bedingungen erfüllen. Mit den Eigenschaften der verwendeten Matrizen kann man ferner leicht zeigen (was wir hier nicht tun wollen), dass die Matrizen und im Fall dieselben Konditionen bezüglich der Spektralnorm besitzen. Schließlich folgt mit (7.27), dass jedes mit einem dargestellt werden kann als

(7.30)

wobei ist. Dabei muss man für die Bestimmung des Vektors nur das lineare Gleichungssystem mit der unteren Dreiecksmatrix auflösen, wobei , wie oben festgestellt wurde, im Fall dieselbe Kondition wie hat.

Für die in (7.30) auftretende spezielle Lösung von folgert man unter Verwendung von (7.29) und der Identität

(7.31)

Also ist gerade die bezüglich der -Norm kleinste aller Lösungen des Systems (vgl. Beispiel 3.16 (3)). Wie die letzte Identität in (7.31) weiter zeigt, ist Element von und somit orthogonal zu . Wenn und mittels einer -Zerlegung von bestimmt werden, wird folglich jedes Element durch (7.30) als Summe bzw. Differenz von und einem dazu orthogonalen Vektor aus berechnet.

Vom Standpunkt der numerischen Stabilität her ist eine solche Wahl von und also ideal. Allerdings ist der für die Berechnung einer -Zerlegung von erforderliche numerische Aufwand bei voll besetzten Matrizen etwa doppelt so groß wie für die Gauß-Elimination, die bei der einfachen Eliminationstechnik verwendet wird. Aus letzterem Grund wurden auch noch andere Eliminationsstrategien vorgeschlagen, die versuchen, einen Kompromiss zwischen numerischer Stabilität und numerischem Aufwand zu erreichen (siehe z. B. [NoWri06]).

7.4 Probleme mit Gleichungsnebenbedingungen

[Bearbeiten]

7.4.1 Einleitung

[Bearbeiten]

Wir wollen nun quadratische Optimierungsprobleme genauer betrachten, welche nur Gleichungsnebenbedingungen aufweisen, welche also Probleme des folgenden Typs sind:

Dabei seien eine symmetrische Matrix, und eine Matrix mit

(7.32)

Die Rangbedingung (7.32) stellt zumindest für die Theorie keine Einschränkung dar, wie bereits mehrfach bemerkt wurde. Sie impliziert bekanntlich, dass ist und dass das inhomogene Gleichungssystem eine Lösung besitzt. Bezeichnen wir den zulässigen Bereich von mit

so ist also hier .

Nach Beispiel 3.16 (2) lassen sich die KKT-Bedingungen für als lineares Gleichungssystem der Gestalt

(7.33)

darstellen. Die -Systemmatrix

(7.34)

in (7.33) bezeichnen wir als KKT-Matrix. Offenbar ist eine symmetrische Matrix.

Wir gehen nun wie in Abschnitt 7.3.3 davon aus, dass Matrizen und bekannt sind mit den Eigenschaften

(7.35)

Wie wir dort gezeigt haben, lässt sich in diesem Fall jeder Vektor mit einem sog. Vektor der reduzierten Variablen und einem Vektor in der Form

(7.36)

darstellen, wobei

(7.37)

eine spezielle Lösung von ist. Beispiele für Matrizen und , welche die Bedingungen in (7.35) erfüllen, ergaben sich aus der einfachen Elimination und aus einer -Zerlegung von .

Zur Reduktion der Variablen ersetzen wir nun in der Zielfunktion des Problems durch die rechte Seite von (7.36). Auf diese Weise erhalten wir

wobei wir schreiben in der Form

(7.38)

Gilt nun für die symmetrische Matrix in (7.38)

ist positiv definit,

so minimiert offenbar ein Vektor die Funktion genau dann, wenn das System löst, welches ausgeschrieben lautet:

(7.39)

Die Matrix und der Vektor

in diesem System werden häufig als reduzierte Hesse-Matrix und als reduzierter Gradient bezeichnet.

Aufgrund der Rangvoraussetzung für in (7.35) ist die positive Definitheit von insbesondere dann gegeben, wenn positiv definit ist (vgl. Lemma 2.21). Man beachte aber, dass die Matrix im Einzelfall selbst dann positiv definit sein kann, wenn indefinit oder singulär ist. Die Voraussetzung der positiven Definitheit von stellt also im Allgemeinen eine viel schwächere Voraussetzung als die der positiven Definitheit von dar.

Wenn positiv definit ist, hat das System (7.39) eine eindeutige Lösung und ist damit

(7.40)

die eindeutige Lösung von Problem . Speziell für und ergibt sich in diesem Fall aus (7.37) und (7.39) sowie und ist demzufolge . Wegen folgt dann weiter aus der ersten Zeile des Systems in (7.33), dass ist. Wenn positiv definit ist, besitzt das zu (7.33) gehörende homogene System also nur die Nulllösung, was gleichbedeutend damit ist, dass die Matrix in (7.34) nichtsingulär ist. Zusammengefasst haben wir also gezeigt:

Satz 7.13

[Bearbeiten]
Die Matrix sei positiv definit. Dann folgt:
(i) Das Problem besitzt eine eindeutige Lösung.
(ii) Die KKT-Matrix in (7.34) ist nichtsingulär.

In diesem Zusammenhang kann man darüber hinaus beweisen:

Satz 7.14

[Bearbeiten]
(i) Ist die Matrix nicht positiv semidefinit, dann gilt
(ii) Ist die Matrix positiv semidefinit, aber nicht positiv definit und besitzt Problem eine Lösung , so ist auch jeder Vektor mit Lösung von , wobei Eigenvektor zum Eigenwert 0 von ist.

Beweis.

[Bearbeiten]

Wegen ist . Wir nehmen nun an, so dass das Problem gemäß Satz 7.1 eine Lösung und somit das KKT-System (7.33) gemäß Satz 3.13 eine Lösung besitzt. Sei nun ein negativer Eigenwert von und zugehöriger Eigenvektor, d. h. sei mit und . Dann ist

und ergibt sich für somit .

Weil gilt, folgt als nächstes und demnach

(7.41)

Aus den KKT-Bedingungen für in (7.33) erhält man weiter und dies impliziert wiederum wegen

Demnach gilt