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.
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 knifflig. 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.)
- Es seien
und
. Dann hat das Problem
eine globale Lösung.
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)
![{\displaystyle =q(\varrho _{k})+t\left[y^{T}Qx^{\varrho _{k}}+c^{T}y\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/43dcab89a402a7fb18f774445f53ce751cda113e)
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:
![{\displaystyle J:=\{j\in \{1,\ldots ,n\}{\big |}y_{j}=0\},\quad \xi :=\min _{j\notin J}y_{j}\in (0,1].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2ddf067c0cd81d9eb37ab532e17e78cbcbea99c0)
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:
![{\displaystyle q(x^{\varrho _{k}})\leq q(x^{\varrho _{k}}-ty)=q(x^{\varrho _{k}})-t\left[y^{T}Qx^{\varrho _{k}}+c^{T}y\right]\leq q(x^{\varrho _{k}}).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bdee0969b8ff8148a9fc1c3508965364ec331e1e)
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.
- 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).
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:
- (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.
- Das duale Problem zu
ist äquivalent mit
.
Ü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.
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.
- 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.
- (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.
(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.
- (i) Es sei
. Dann gilt

- (ii) Es sei
. Dann gilt

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.
- 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
.
Übung!
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.
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:
- Es sei
mit einem
und
. Dann gilt:
- (i)
, falls ein
mit
existiert.
- (ii)
, falls kein
mit
existiert.
Ü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.
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.
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
![{\displaystyle \inf _{x_{1},x_{2},x_{4},x_{5}}\sin(x_{1}+x_{2})+(-8x_{1}-9x_{4}-4x_{5}+6x_{2}+6)^{2}+{\frac {1}{3}}\left[x_{4}+x_{5}^{4}+\left(-{\frac {3}{8}}x_{1}+{\frac {1}{8}}x_{4}-{\frac {3}{4}}x_{5}-{\frac {1}{4}}x_{2}-{\frac {1}{2}}\right)\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/694bfacee05ea4c135b8c9fc0d0a38ff3fedcb86)
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
.
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)
![{\displaystyle x_{s}=Q_{1}R^{-T}b=(Y\overbrace {R)(R^{-1}} ^{=I}R^{-T})b=A^{T}R^{-T}R^{-T}b=A^{T}[(R^{T})\underbrace {\left(Y^{T}Y\right)} _{=I}(R)]^{-1}b=A^{T}\left(AA^{T}\right)b.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ca1a73469158e890cdef5260a6b5c638ee2c11e7)
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]
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:
- 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:
- (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.
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