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

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 $Q\in \mathbb {R} ^{n\times n}$ und Daten $A\in \mathbb {R} ^{m\times n},c\in \mathbb {R} ^{n}$ und $b\in \mathbb {R} ^{m}$ gegeben sind:

${\begin{array}{lll}(QP):&{\text{Minimiere}}&q(x):={\frac {1}{2}}x^{T}Qx+c^{T}x\\&{\text{u. d. N.}}&Ax=b,\\&&x\geq 0.\end{array}}$

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 $x\geq 0$ für die Variablen durch Einführung zusätzlicher Variablen erzwingen.

Zumeist setzt man im Zusammenhang mit $(QP)$ der Einfachheit halber - zumindest für theoretische Zwecke - die Rangbedingung $\operatorname {Rang} (A)=m$ voraus, so dass insbesondere $m\leq n$ ist. In Abschnitt 4.2 war festgestellt worden, dass das System $Ax=b$ im Fall $\operatorname {Rang} (A)\neq m$ entweder keine Lösung besitzt und damit der zulässige Bereich von $(QP)$ leer ist oder dass in diesem Fall überflüssige Gleichungen im System $Ax=b$ 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 $(QP)$ bezeichnen wir mit

(7.1) ${\mathcal {Z}}_{QP}:=\{x\in \mathbb {R} ^{n}{\big |}Ax=b,\quad x\geq 0\}.$

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

Im speziellen Fall $Q:=0$ handelt es sich bei dem Problem $(QP)$ 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 $Q$ auf dem $\mathbb {R} ^{n}$ oder auf einem Teilraum des $\mathbb {R} ^{n}$ gefordert wird. So ist insbesondere der Existenzsatz 7.2 und die Dualitätstheorie in Abschnitt 7.2 auch auf lineare Probleme anwendbar.

Ist $Q$ nicht positiv semidefinit, d. h., ist $(QP)$ kein konvexes Optimierungsproblem, so kann $(QP)$ 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 $(QP)$ beweisen. Thema von Abschnitt 7.2 ist eine Dualitätstheorie für konvexe quadratische Optimierungsprobleme, die den (engen) Zusammenhang zwischen dem Problem $(QP)$ und dem sog. dualen quadratischen Optimierungsproblem, das mit den Daten von $(QP)$ 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 $(QP)$ gewonnen werden kann und als das duale Problem möglicherweise leichter oder schneller als $(QP)$ 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

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

$\inf _{x\geq 0}e^{-x}=0.$

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 $-\infty$. 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

Es seien ${\mathcal {Z}}_{QP}\neq \emptyset$ und $\inf _{x\in {\mathcal {Z}}_{QP}}q(x)>-\infty$. Dann hat das Problem $(QP)$ eine globale Lösung.

Beweis.

Wegen ${\mathcal {Z}}_{QP}\neq \emptyset$ können wir ein $\varrho _{0}>0$ finden, so dass die Menge

${\mathcal {Z}}_{\varrho }:=\{x\in {\mathcal {Z}}_{QP}{\big |}\|x\|\leq \varrho \}$

für alle $\varrho \geq \varrho _{0}$ nichtleer ist. Da ${\mathcal {Z}}_{\varrho }$ kompakt und $q$ stetig ist, besitzt das Problem

${\begin{array}{ll}(P_{\varrho }):&\min \limits _{x\in {\mathcal {Z}}_{\varrho }}q(x)\end{array}}$

nach dem Satz 2.38 von Weierstraß für jedes $\varrho \geq \varrho _{0}$ eine Lösung. Wir nehmen nun im Folgenden an, dass $\varrho \geq \varrho _{0}$ ist und wir setzen

$\mu :=\inf _{x\in {\mathcal {Z}}_{QP}}q(x),\quad \mu _{\varrho }:=\min \limits _{x\in {\mathcal {Z}}_{\varrho }}q(x).$

Offenbar gilt aufgrund der Voraussetzung des Satzes und wegen ${\mathcal {Z}}_{\varrho }\subseteq {\mathcal {Z}}_{QP}$

(7.2) $-\infty <\mu \leq \mu _{\varrho }$

Die Lösungsmenge von $(P_{\varrho })$ ist, wie festgestellt wurde, nichtleer und sie ist als Teilmenge von ${\mathcal {Z}}_{\varrho }$ kompakt. Also nimmt die stetige Funktion $\|x\|^{2}=x^{T}x$ über der Lösungsmenge von $(P_{\varrho })$ ihr Infimum an und gibt es somit unter allen Lösungen von $(P_{\varrho })$ mindestens eine Lösung $x^{\varrho }\in {\mathcal {Z}}_{\varrho }$ mit minimaler $l_{2}$-Norm. Wir zeigen nun als nächstes:

(7.3) Es gibt ein $\varrho ^{*}\geq \varrho _{0}$, so dass $\|x^{\varrho }\|<\varrho$ für alle $\varrho \geq \varrho ^{*}$ gilt.

Wäre Letzteres nicht richtig, so gäbe es eine Folge $\{\varrho _{k}\}$ mit

$\varrho _{k}:=\|x^{\varrho _{k}}\|\to \infty \quad (k\to \infty ).$

Wir setzen nun

$y^{k}:={\frac {1}{\varrho _{k}}}x^{\varrho _{k}},\quad \left\|y^{k}\right\|=1$

und können ohne Beschränkung der Allgemeinheit annehmen, dass $y^{k}\to y$ $(k\to \infty )$ für ein $y\in \mathbb {R} ^{n}$ mit $\|y\|=1$ gilt. Weil nach unserer Konstruktion $x^{\varrho _{k}}\in {\mathcal {Z}}_{\varrho _{k}}$ ist und damit

$x^{\varrho _{k}}\geq 0,\quad A\left({\frac {1}{\varrho _{k}}}x^{\varrho _{k}}\right)={\frac {1}{\varrho _{k}}}b$

folgt, hat man für dieses $y$

(7.4) $y\geq 0,\quad Ay=0.$

Es ist ferner $x^{\varrho _{k}}\in {\mathcal {Z}}_{QP}$ und $x^{\varrho _{k}}$ für $(P_{\varrho _{k}})$ optimal. Wegen ${\mathcal {Z}}_{\varrho _{0}}\subseteq {\mathcal {Z}}_{\varrho _{k}}$ können wir daher mit (7.2) schließen:

(7.5) $-\infty <\mu \leq q(x^{\varrho _{k}})={\frac {1}{2}}\varrho _{k}^{2}(y^{k})^{T}Qy^{k}+\varrho _{k}c^{T}y^{k}\leq q(x^{\varrho _{0}})<+\infty .$

Diese Abschätzungen implizieren, dass $y^{T}Qy=0$ ist, denn für $y^{T}Qy\neq 0$ würde im Widerspruch zu (7.5) folgen:

$\left|\varrho _{k}(y^{k})^{T}Qy^{k}+c^{T}y^{k}\right|\geq \varrho _{k}\left|(y^{k})^{T}Qy^{k}\right\|-\|c\|\to +\infty \quad (k\to \infty ).$

Wegen (7.4) und $x^{\varrho _{k}}\in {\mathcal {Z}}_{QP}$ hat man als nächstes $x^{\varrho _{k}}+ty\in {\mathcal {Z}}_{QP}$ für $t\geq 0$. Also ergibt sich unter Verwendung der Beziehung $y^{T}Qy=0$ für $t\geq 0$

$-\infty <\mu \leq q(x^{\varrho _{k}}+ty)={\frac {1}{2}}(x^{\varrho _{k}}+ty)^{T}Q(x^{\varrho _{k}}+ty)+c^{T}(x^{\varrho _{k}}+ty)$

(7.6) $=q(\varrho _{k})+t\left[y^{T}Qx^{\varrho _{k}}+c^{T}y\right]$

Da der Ausdruck in (7.6) im Fall, dass $y^{T}Qx^{\varrho _{k}}+c^{T}y<0$ für ein $k$ gelten würde, für $t\to \infty$ gegen $-\infty$ strebte, folgt damit

(7.7) $y^{T}Qx^{\varrho _{k}}+c^{T}y\geq 0,\quad k\in \mathbb {N} .$

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

(7.8) $x^{\varrho _{k}}-ty\in {\mathcal {Z}}_{QP},\quad \|x^{\varrho _{k}}-ty\|<\|x^{\varrho _{k}}\|,\quad q(x^{\varrho _{k}}-ty)=q(x^{\varrho _{k}})$

für alle $t\in (0,t_{k}]$ und alle $k\geq k_{0}$ mit einem $t_{k}>0$ und ein $k_{0}\in \mathbb {N}$ gilt. Diese Beziehungen stehen im Widerspruch dazu, dass $x^{\varrho _{k}}$ eine Lösung von $(P_{\varrho _{k}})$ mit kleinster Euklidischer Norm ist, so dass (7.3) richtig sein muss.

Sei nun $t>0$. Gemäß (7.4) ist $y\geq 0$, so dass wir setzen können:

$J:=\{j\in \{1,\ldots ,n\}{\big |}y_{j}=0\},\quad \xi :=\min _{j\notin J}y_{j}\in (0,1].$

Wegen $y^{k}\to y$ $(k\to \infty )$ können wir also ein $k_{1}\in \mathbb {N}$ wählen, so dass $y_{j}^{k}\geq \xi /2$ $(j\notin J)$ für alle $k\geq k_{1}$ gilt. Weil $|y_{j}|\leq 1$ für alle $j$ ist, haben wir somit bei festem $k\geq k_{1}$ für alle $t\in (0,\tau _{k}]$ mit $\tau _{k}:=\varrho _{k}\xi /2$

$(x^{\varrho _{k}}-ty)_{j}=\varrho _{k}y_{j}^{k}-ty_{j}\geq \varrho _{k}{\frac {\xi }{2}}-t\geq 0\quad (j\notin J).$

Offenbar ist ferner wegen $x^{\varrho _{k}}\in {\mathcal {Z}}_{QP}$ und (7.4) auch $(x^{\varrho _{k}}-ty)_{j}\geq 0$ $(j\in J)$ sowie $A(x^{\varrho _{k}}-ty)=b$. Damit ist die erste Beziehung in (7.8) für alle genannten $t$ und $k$ gezeigt.

Wegen $\|y\|=1$ gibt es ein $k_{0}\geq k_{1}$, so dass $y^{T}y^{k}\geq 1/2$ für alle $k\geq k_{0}$ gilt. Demzufolge erhalten wir bei festem $k\geq k_{0}$ und fest gewähltem $t_{k}$ mit $0<t_{k}<\min\{\tau _{k},\varrho _{k}\}$ für alle $t\in (0,t_{k}]$

$\|x^{\varrho _{k}}-ty\|2=\|x^{\varrho _{k}}\|^{2}-2t\varrho _{k}y^{T}y^{k}+t^{2}\leq \|x^{\varrho _{k}}\|^{2}-t(\varrho _{k}-t)<\|x^{\varrho _{k}}\|^{2}.$

Damit ist für die genannten $t$ und $k$ auch die zweite Beziehung in (7.8) bewiesen. Für diese $tund<math>kfolgtaufgrunddererstenbeidenBeziehungenin(7.8)weiter<math>x^{\varrho _{k}}-ty\in {\mathcal {Z}}_{\varrho _{k}}$, so dass man analog zu (7.6) unter Verwendung von (7.7) erschließt:

$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}}).$

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

Gemäß der Definition eines Infimums existiert eine Folge $\{x^{k}\}$ mit

(7.9) $x^{k}\in {\mathcal {Z}}_{QP},\quad \lim _{k\to \infty }q(x^{k})=\mu .$

Im Fall, dass $\{x^{k}\}$ beschränkt ist, gibt es ferner eine Teilfolge $\{x^{k_{i}}\}$ von $\{x^{k}\}$ mit $\lim _{i\to \infty }x^{k_{i}}=x^{*}$, wobei $x^{*}\in {\mathcal {Z}}_{QP}$ wegen der Abgeschlossenheit von ${\mathcal {Z}}_{QP}$ geschlossen werden kann. Aufgrund der Stetigkeit von $q$ folgt außerdem $q(x^{k_{i}})\to q(x^{*})$ $(i\to \infty )$ und daher $q(x^{*})=\mu$. Somit ist für diesen Fall der Satz bewiesen und müssen wir abschließend noch den Fall betrachten, dass die Folge $\{x^{k}\}$ unbeschränkt ist.

Sei also $\{x^{k}\}$ eine unbeschränkte Folge mit (7.9) und sei ${\tilde {\varrho }}_{k}:=\left\|x^{k}\right\|$. Dann folgt $x^{k}\in {\mathcal {Z}}_{{\tilde {\varrho }}_{k}}$, und man erschließt daher mit (7.2)

$-\infty <\mu \leq \mu _{{\tilde {\varrho }}_{k}}\leq q(x^{k}).$

Letzteres impliziert wegen (7.9) die Konvergenz $\mu _{{\tilde {\varrho }}_{k}}\to \mu$ $(k\to \infty )$. Also existiert eine Folge $\{\varrho _{k}\}$ mit

(7.10) $\varrho ^{*}\leq \varrho _{k}\leq \varrho _{k+1},\quad \lim _{k\to \infty }\varrho _{k}=\infty ,\quad \lim _{k\to \infty }\mu _{\varrho _{k}}=\mu ,$

wobei $\varrho ^{*}$ durch (7.3) bestimmt ist. Wir wollen nun als Letztes zeigen, dass

(7.11) $\mu _{\varrho _{k}}=\mu ,\quad k\in \mathbb {N}$

gilt und demnach $x^{\varrho _{k}}$ für alle $k$ das Problem $(QP)$ löst. Wir nehmen dazu an, dass (7.11) nicht richtig ist.

Für $l\leq k$ bzw. für $\varrho ^{*}\leq \varrho _{l}\leq \varrho _{k}$ hat man offenbar $\mu \leq \mu _{\varrho _{k}}\leq \mu _{\varrho _{l}}$. Also konvergiert die Folge $\{\mu _{\varrho _{k}}\}$ monoton fallend gegen $\mu$. Wenn (7.11) nicht gilt, muss es weiter zwei Glieder $\varrho _{r}$ und $\varrho _{s}$ der Folge $\{\varrho _{k}\}gebenmit::(7.12)<math>\varrho ^{*}\leq \varrho _{r}<\varrho _{s},\quad -\infty <\mu \leq \mu _{\varrho _{s}}<\mu _{\varrho _{r}}$. Für $\varrho _{r}$ und $\varrho _{s}$ folgt dann mit (7.3)

$\varrho ^{*}\leq \varrho _{r}<\|x^{\varrho _{s}}\|<\varrho _{s}$

da die Annahme $\|x^{\varrho _{s}}\|\leq \varrho _{r}$ zunächst $x^{\varrho _{s}}\in {\mathcal {Z}}_{\varrho _{s}}$ und damit den Widerspruch $\mu _{\varrho _{r}}\leq q(x^{\varrho _{s}})=\mu _{\varrho _{s}}$ zu (7.12) nach sich ziehen würde.

Wir setzen nun ${\tilde {\varrho }}:=\|x^{\varrho _{s}}\|$, so dass ${\tilde {\varrho }}\in (\varrho _{r},\varrho _{s})$ gilt. Insbesondere ist dann mit (7.12) und (7.3) $\left\|x^{\tilde {\varrho }}\right\|<{\tilde {\varrho }}$ und $\mu _{\varrho _{s}}\leq \mu _{\tilde {\varrho }}$. Wäre nun $\mu _{\varrho _{s}}=\mu _{\tilde {\varrho }}$, dann wäre $x^{\tilde {\varrho }}$ wegen ${\mathcal {Z}}_{\tilde {\varrho }}\subseteq {\mathcal {Z}}_{\varrho _{s}}$ Element von ${\mathcal {Z}}_{\varrho _{s}}$ und damit Lösung von $(P_{\varrho _{s}})$. Dies ist jedoch wegen $\left\|x^{\tilde {\varrho }}\right\|<{\tilde {\varrho }}=\|x^{\varrho _{s}}\|$ und der Minimaleigenschaft von $x^{\varrho _{s}}$ bezüglich der Lösungsmenge von $(P_{\varrho _{s}})$ nicht möglich. Wegen ${\tilde {\varrho }}:=\|x^{\varrho _{s}}\|$ ist $x^{\varrho _{s}}\in {\mathcal {Z}}_{\tilde {\varrho }}$ und damit aber auch der Fall $\mu _{\varrho _{s}}<\mu _{\tilde {\varrho }}$ 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

Ist $Q$ positiv definit und ${\mathcal {Z}}_{QP}\neq \emptyset$, so besitzt das Problem $(QP)$ genau eine Lösung.

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

7.2 Dualitätstheorie

7.2.1 Das duale Problem zu einem Problem in Normalform

Wir nehmen in diesem Abschnitt grundsätzlich an

$Q$ ist positiv semidefinit

und wir betrachten das damit konvexe quadratische Optimierungsproblem in Normalform

${\begin{array}{lll}(QP):&{\text{Minimiere}}&q(x):={\frac {1}{2}}x^{T}Qx+c^{T}x\\&{\text{u. d. N.}}&Ax=b,\\&&x\geq 0.\end{array}}$

In dem hier diskutierten Zusammenhang nennen wir $(QP)$ das primale Problem. Den zulässigen Bereich von $(QP)$ bezeichnen wir wie zuvor in (7.1) mit ${\mathcal {Z}}_{QP}$.

Gemäß Beispiel 3.16 (1) ist $x^{*}$ genau dann eine Lösung des Problems $(QP)$, wenn $(x^{*},y^{*},s^{*})$ die nachstehenden KKT-Bedingungen erfüllt:

${\begin{array}{lrl}(S_{QP}):&Ax=b,&x\geq 0,\\&A^{T}y-Qx+s=c,&s\geq 0,\\&x^{T}s=0.\end{array}}$

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

${\begin{array}{lll}(QD):&{\text{Maximiere}}&r(x,y,s):=-{\frac {1}{2}}x^{T}Qx+b^{T}y\\&{\text{u. d. N.}}&A^{T}y-Qx+s=c,\\&&s\geq 0.\end{array}}$

Das Problem $(QD)$ nennt man in diesem Zusammenhang das zu $(QP)$ duale Problem. Seinen zulässigen Bereich bezeichnen wir mit

${\mathcal {Z}}_{QD}:=\left\{(x,y,s)\in \mathbb {R} ^{n+m+n}{\big |}A^{T}y-Qx+s=c,\quad s\geq 0\right\}.$

Das Problem $(QD)$ lässt sich offenbar auch äquivalent darstellen in der Form

(7.13) ${\begin{array}{ll}{\text{Maximiere}}&-{\frac {1}{2}}x^{T}Qx+b^{T}y\\{\text{u. d. N.}}&A^{T}y-Qx\leq c.\end{array}}$

Zur Herleitung der zugehörigen KKT-Bedingungen ersetzen wir das Maximierungsproblem $(QD)$ ä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 (Unbekannte Funktion „\begin{array}“): {\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 $I$ die $(n\times n)$-Einheitsmatrix. Die in der Zielfunktion von $(QD)'$ vorkommende Matrix ist wiederum eine symmetrische, positiv semidefinite Matrix, so dass es sich bei diesem Problem wie bei $(QP)$ um ein linear restringiertes, konvexes quadratisches Optimierungsproblem handelt.

Nach Korollar 3.14 ist somit $(x^{*},y^{*},s^{*})$ genau dann eine Lösung von $(QD)'$, wenn es Vektoren $u^{*}$ und $v^{*}$ gibt, so dass $(x^{*},y^{*},s^{*},u^{*},v^{*})$ das folgende System von Gleichungen und Ungleichungen löst (im Hinblick auf $v^{*}$ berücksichtige man dabei Bemerkung 3.6 (iii)):

(7.14) ${\begin{array}{r}A^{T}y-Qx+s=c,\quad s\geq 0,\\{\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}}+{\begin{pmatrix}-Q\\A\\I\end{pmatrix}}u-{\begin{pmatrix}0\\0\\I\end{pmatrix}}v={\begin{pmatrix}0\\0\\0\end{pmatrix}}\\v^{T}s=0,\quad v\geq 0.\end{array}}$

Unter Ausnutzung der darin enthaltenen Beziehungen $Qx=Qu$ und $v=u$ können wir dieses System wie folgt schreiben:

(7.15) ${\begin{array}{rr}Au=b,&u\geq 0,\\A^{T}y-Qu+s=c,&s\geq 0,\\u^{T}s=0,\\Qx=Qu,\\v=u.\end{array}}$

Berücksichtigt man nun, dass $(S_{QP})$ ein System in den Variablen $(x,y,s)$ und letzteres System eines in den Variablen $(x,y,s,u,v)$ ist, so können wir offenbar schließen:

(7.16) $(x^{*},y^{*},s^{*})$ löst $(QD)\Rightarrow (x^{*},y^{*},s^{*},u^{*},v^{*})$ löst (7.15) für gewisse $u^{*},v^{*}\Rightarrow (u^{*},y^{*},s^{*})$ löst $(S_{QP})\Rightarrow u^{*}$ löst $(QP)$

sowie

(7.17) $x^{*}$ löst $(QP)\Rightarrow (x^{*},y^{*},s^{*})$ löst $(S_{QP})$ für gewisse $y^{*},s^{*}\Rightarrow (x^{*},y^{*},s^{*},x^{*},x^{*})$ löst (7.15) $\Rightarrow (x^{*},y^{*},s^{*})$ löst $(QD)$.

Ist $(x^{*},y^{*},s^{*})$ eine Lösung von $(QD)$ und $u^{*}$ der zu der Gleichungsnebenbedingung in $(QD)$ gehörende Multiplikator, so ist $u^{*}$ gemäß (7.16) eine Lösung von $(QP)$. (Viele Verfahren der nichtlinearen Optimierung zur Lösung eines Problems erzeugen zugehörige Multiplikatoren gleich mit.) Dabei unterscheiden sich $u^{*}$ und $x^{*}$ wegen $Q(x^{*}-u^{*})=0$ nur durch eine Lösung $h^{*}$ von $Qh=0$.

Weiter können wir festhalten: Besitzt das Problem $(QD)$ eine Lösung, so besitzt es auch eine Lösung $(x^{*},y^{*},s^{*})$ derart, dass $x^{*}$ das Problem $(QP)$ löst. Dies folgt aus (7.17), da mit $(QD)$ nach (7.16) auch $(QP)$ lösbar ist. Im Fall, dass $Q$ positiv definit ist, liefert sogar der $x$-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 $x=u=v$ gilt und damit $u^{*}$ und $v^{*}$ in den Implikationen (7.16) durch $x^{*}$ ersetzt werden können. Wenn $Q$ positiv definit ist sowie im Fall $Q:=0$ sind also die KKT-Bedingungen für $(QD)$ mit denen für $(QP)$ identisch.

Wir haben damit unter anderem den folgenden Satz bewiesen:

Satz 7.3

(i) Es gilt:

$(QP)$ ist lösbar $\Leftrightarrow (S_{QP})$ ist lösbar $\Leftrightarrow (QD)$ ist lösbar.

(ii) Ist $(x^{*},y^{*},s^{*})$ eine Lösung von $(S_{QP})$, so löst $x^{*}$ das Problem $(QP)$ und $(x^{*},y^{*},s^{*})$ das Problem $(QD)$.

(iii) Besitzt das Problem $(QD)$ eine Lösung, so besitzt es auch eine Lösung $(x^{*},y^{*},s^{*})$ derart, dass $x^{*}\geq 0$ ist und $x^{*}$ das Problem $(QP)$ löst. Ist $Q$ positiv definit, so hat jede Lösung von $(QD)$ die letztere Eigenschaft.

Die drei Zeilen im System $(S_{QP})$ 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 $(S_{QP})$ eine Lösung des anderen Problems gewinnen. Wenn $Q$ positiv definit ist, liefert eine Lösung von $(QD)$ gemäß Satz 7.3 sogar direkt eine Lösung von $(QP)$ mit. Das duale Problem zu lösen kann also dann nützlich sein, wenn dieses schneller als $(QP)$ zu lösen oder für den gerade verfügbaren Algorithmus günstiger als $(QP)$ 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 $(QD)$ unter Einführung zusätzlicher Variablen in ein Problem des Typs $(QP)$ und stellt man anschließend das dazu duale Problem auf, so gelangt man ferner zu der folgenden Aussage.

Satz 7.4

Das duale Problem zu $(QD)$ ist äquivalent mit $(QP)$.

Beweis.

Übung!

Es sei abschließend gesagt, dass man im linearen Fall, d. h. im Fall $Q:=0$, 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

Als nächstes wollen wir weitere Beziehungen zwischen dem primalen Problem $(QP)$ und dem dualen Problem $(QD)$ herleiten. Offenbar erhält man für ein Punktepaar zulässiger Punkte $x\in {\mathcal {Z}}_{QP}$ und $(z,y,s)\in {\mathcal {Z}}_{QD}$ unter Verwendung der Nebenbedingungen und der Zielfunktionen beider Probleme

$0\leq x^{T}s=x^{T}\left(c-A^{T}y+Qz\right)=c^{T}x-b^{T}y+x^{T}Qz$

$=\left(c^{T}x+{\frac {1}{2}}x^{T}Qx\right)-\left(-{\frac {1}{2}}z^{T}Qz+b^{T}y\right)-\left({\frac {1}{2}}x^{T}Qx-x^{T}Qz+{\frac {1}{2}}z^{T}Qz\right)$

(7.18) $=q(x)-r(z,y,s)-{\frac {1}{2}}(x-z)^{T}Q(x-z).$

Da man $(x-z)^{T}Q(x-z)\geq 0$ hat, führt diese Beobachtung zu der folgenden Aussage.

Satz 7.7 (Schwacher Dualitätssatz)

Für ein Paar zulässiger Punkte $x\in {\mathcal {Z}}_{QP}$ und $(z,y,s)\in {\mathcal {Z}}_{QD}$ der Probleme $(QP)$ und $(QD)$ gilt

$0\leq x^{T}s\leq q(x)-r(z,y,s).$

Für $x\in {\mathcal {Z}}_{QP}$ und $(x,y,s)\in {\mathcal {Z}}_{QP}$ folgt insbesondere

$0\leq x^{T}s=q(x)-r(x,y,s).$

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

Korollar 7.8 (Schwacher Dualitätssatz)

Für ein Paar zulässiger Punkte $x\in {\mathcal {Z}}_{LP}$ und $(y,s)\in {\mathcal {Z}}_{LD}$ der Probleme $(LP)$ und $(LD)$ gilt

$0\leq x^{T}s=c^{T}x-b^{T}y.$

Für ein Punktepaar $x\in {\mathcal {Z}}_{QP}$ und $(z,y,s)\in {\mathcal {Z}}_{QD}$ bezeichnet man den Abstand $q(x)-r(z,y,s)\geq 0$ der Zielfunktionswerte des primalen und dualen Problems als Dualitätslücke. Im linearen Fall entspricht sie nach Korollar (7.8) der Zahl $x^{T}s$. 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)

(i) Gilt ${\mathcal {Z}}_{QP}\neq \emptyset$ und ${\mathcal {Z}}_{QD}\neq \emptyset$, so besitzen die beiden Probleme $(QP)$ und $(QD)$ eine Lösung.

(ii) $x^{*}$ und $(z^{*},y^{*},s^{*})$ sind genau dann Lösungen von $(QP)$ und $(QD)$, wenn $x^{*}$ und $(z^{*},y^{*},s^{*})$ für $(QP)$ und $(QD)$ zulässig sind und wenn $q(x^{*})=r(z^{*},y^{*},s^{*})$ bzw. wenn äquivalent dazu $x^{*T}s^{*}=0$ gilt.

Beweis.

(i) Seien ${\mathcal {Z}}_{QP}\neq \emptyset$ und ${\mathcal {Z}}_{QD}\neq \emptyset$. Für ein $(z,y,s)\in {\mathcal {Z}}_{QD}$ bekommt man dann aus Satz 7.7

$-\infty <r(z,y,s)\leq q(x),\quad x\in {\mathcal {Z}}_{QP}.$

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

(ii) Gilt $q(x^{*})-r(z^{*},y^{*},s^{*})=0$, so folgt offenbar aus Satz 7.7 $x^{*T}{\tilde {s}}=0$. Seien jetzt zunächst $x^{*}$ und $(z^{*},y^{*},s^{*})$ Lösungen von $(QP)$ und $(QD)$. Nach (7.17) existieren dann Vektoren ${\tilde {y}}$ und ${\tilde {s}}$, so dass $(x^{*},{\tilde {y}},{\tilde {s}})$ sowohl das System $(S_{QP})$ als auch das Problem $(QD)$ löst. Insbesondere ist damit $x^{*T}{\tilde {y}}=0$. Mit Satz 7.7 schließt man daher

$0=x^{*T}{\tilde {y}}=q(x^{*})-r(x^{*},{\tilde {y}},{\tilde {s}})=q(x^{*})-r(z^{*},y^{*},s^{*}).$

Nun seien umgekehrt $x^{*}$ und $(z^{*},y^{*},s^{*})$ zulässige Punkte von $(QP)$ und $(QD)$ mit $q(x^{*})=r(z^{*},y^{*},s^{*})$. Nach Aussage (i) besitzt dann das Problem $(QP)$ eine Lösung ${\tilde {x}}$ und nach (7.17) das Problem $(QD)$ eine Lösung $({\tilde {x}},{\tilde {y}},{\tilde {s}})$. Anwendung des ersten Teil des Beweises und von Satz 7.7 liefert schließlich

$q(x^{*})=r(z^{*},y^{*},s^{*})\leq r({\tilde {z}},{\tilde {y}},{\tilde {s}})=q({\tilde {x}})\leq q(x*).$

Also sind auch $x^{*}$ und $(z^{*},y^{*},s^{*})$ Lösungen von $(QP)$ und $(QD)$.

q.e.d.

Eine weitere wichtige Folgerung aus dem Vorangegangenen ist die folgende.

Korollar 7.10

(i) Es sei ${\mathcal {Z}}_{QP}\neq \emptyset$. Dann gilt

$\inf _{x\in {\mathcal {Z}}_{QP}}q(x)=-\infty \Leftrightarrow {\mathcal {Z}}_{QD}=\emptyset .$

(ii) Es sei ${\mathcal {Z}}_{QD}\neq \emptyset$. Dann gilt

$\sup _{(z,y,s)\in {\mathcal {Z}}_{QD}}r(z,y,s)=+\infty \Leftrightarrow {\mathcal {Z}}_{QP}=\emptyset .$

Aufgabe 7.11

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 $x$- bzw. $z$-Anteile für Punkte des dualen Problems streicht.

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

Satz 7.12

Man beweise:

(i) Besitzt das Problem $(QD)$ eine Lösung, so tut dies auch das Problem $(QDM)$ und die optimalen Zielfunktionswerte beider Probleme sind identisch.

(ii) Jede Lösung von $(QD)$ mit nichtnegativem $x$-Anteil löst $(QDM)$ und jede Lösung von $(QDM)$ löst $(QD)$.

Beweis.

Übung!

7.2.4 Ein weiterer Spezialfall

Ein anderer relevanter Spezialfall des Problempaares $({\mathcal {QP}})$ und $({\mathcal {QD}})$ ist das Problempaar

${\begin{array}{lll}({\overline {QP}}):&{\text{Minimiere}}&{\frac {1}{2}}x^{T}Qx+c^{T}x\\&{\text{u. d. N.}}&Ax\geq b\end{array}}$

und

${\begin{array}{lll}({\overline {QD}}):&{\text{Maximiere}}&-{\frac {1}{2}}x^{T}Qx+b^{T}y\\&{\text{u. d. N.}}&A^{T}y-Qx=c,\\&&y\geq 0.\end{array}}$

Im Fall, dass $Q$ positiv definit ist, lässt sich die Gleichungsnebenbedingung in $({\overline {QD}})$ nach $x$ auflösen, was

(7.19) $x=Q^{-1}\left(A^{T}y-c\right)$

ergibt. Setzt man letzteren Ausdruck in die Zielfunktion von $({\overline {QD}})$ ein, so erhält man

$-{\frac {1}{2}}x^{T}Qx+b^{T}y=-{\frac {1}{2}}\left(y^{T}A-c^{T}\right)Q^{-1}QQ^{-1}\left(A^{T}y-c\right)+b^{T}y$

$=-{\frac {1}{2}}y^{T}\left(AQ^{-1}A^{T}\right)y+\left(AQ^{-1}c+b\right)^{T}y-{\frac {1}{2}}c^{T}Q^{-1}c.$

Folglich kann man das duale Problem $({\overline {QD}})$ für positiv definites $Q$ durch das folgende äquivalente Problem ersetzen:

${\begin{array}{lll}({\overline {QD}})':&{\text{Maximiere}}&-{\frac {1}{2}}y^{T}\left(AQ^{-1}A^{T}\right)y+\left(AQ^{-1}c+b\right)^{T}y-{\frac {1}{2}}c^{T}Q^{-1}c\\&{\text{u. d. N.}}&y\geq 0.\end{array}}$

Die Matrix $AQ^{-1}A^{T}$ darin ist symmetrisch und positiv semidefinit und im Fall $\operatorname {Rang} (A)=m$ sogar positiv definit (s. Lemma 2.21). Insbesondere ist also das Problem $({\overline {QD}})'$, wenn man es äquivalent als ein Minimierungsproblem formuliert, wiederum ein konvexes quadratisches Optimierungsproblem.

Hat man eine Lösung $y^{*}$ von $({\overline {QD}})'$ gefunden (im Fall $\operatorname {Rang} (A)=m$ ist diese eindeutig), so lässt sich der zugehörige $x$-Anteil $x^{*}$ der Lösung von $({\overline {QD}})$ gemäß (7.19) als eindeutige Lösung des linearen Gleichungssystems

$Qx=A^{T}y^{*}-c$

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

Eine Lösung von $({\overline {QD}})'$ liefert also gleichzeitig eine Lösung von $({\overline {QP}})$ mit. Da das Problem $({\overline {QD}})'$ nur einfache Schrankenbedingungen als Nebenbedingungen enthält, kann es wesentlich einfacher als Problem $({\overline {QP}})$ zu lösen sein. Allerdings benötigt man bei dieser Vorgehensweise die Matrix $AQ^{-1}A^{T}$, so dass diese ohne allzu großen Aufwand zu berechnen sein sollte.

7.3 Elimination bei linearen Gleichungsrestriktionen

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

Wir betrachten für eine Funktion $f\in C(\mathbb {R} ^{n})$ und Daten $A\in \mathbb {R} ^{m\times n}$ und $b\in \mathbb {R} ^{m}$ das durch lineare Gleichungen restringierte Problem

${\begin{array}{lll}({\mathcal {P}}_{GN}):&{\text{Minimiere}}&f(x)\\&{\text{u. d. N.}}&Ax=b.\end{array}}$

Den zulässigen Bereich von $({\mathcal {P}}_{GN})$ bezeichnen wir mit

$Z_{GN}:=\{x\in \mathbb {R} ^{n}{\big |}Ax=b\}.$

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

Satz 7.13

Es sei $f(x):=c^{T}x$ mit einem $c\in \mathbb {R} ^{n}$ und $Z_{GN}\neq \emptyset$. Dann gilt:

(i) $f(x)=y^{*T}b,x\in Z_{GN}$, falls ein $y^{*}\in \mathbb {R} ^{m}$ mit $A^{T}y^{*}=c$ existiert.

(ii) $\inf _{x\in Z_{GN}}f(x)=-\infty$, falls kein $y^{*}\in \mathbb {R} ^{m}$ mit $A^{T}y^{*}=c$ existiert.

Beweis.

Übung!

Der Fall, dass das Problem $({\mathcal {P}}_{GN})$ 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 $f$ in Problem $({\mathcal {P}}_{GN})$ eine nichtlineare Funktion ist.

Wir nehmen nun wieder $\operatorname {Rang} (A)=m$ und damit insbesondere $m\leq n$ an. Dabei ist der Fall $m=n$ nicht von Interesse, weil dann das System $Ax=b$ genau eine Lösung besitzt, welche die eindeutige Lösung von Problem $({\mathcal {P}}_{GN})$ ist. Für die folgenden beiden Unterabschnitte setzen wir daher

(7.20) $\operatorname {Rang} (A)=m,\quad m<n$

voraus. In diesem Fall lassen sich einige der Variablen $x_{i}$ durch die anderen ausdrücken und kann man somit zu einer Formulierung des Problems gelangen, welche weniger Variable als $({\mathcal {P}}_{GN})$ aufweist und überdies keine Restriktionen enthält. Wir beschreiben in diesem Zusammenhang zunächst die sog. einfache Elimination.

7.3.2 Einfache Elimination

Nach der Voraussetzung in (7.20) sind $m$ Spalten von $A$ linear unabhängig. Wir können annehmen, dass dies die ersten $m$ Spalten von $A$ sind. (Anderenfalls vertausche man die Spalten und die Variablen im System $Ax=b$ entsprechend.) Bezeichnen wir die nichtsinguläre Matrix, welche aus diesen Spalten von $A$ gebildet wird, mit $B\in \mathbb {R} ^{m\times m}$, so können wir die Matrix $A$ blockweise in der Form

$A={\begin{pmatrix}B&N\end{pmatrix}}$

darstellen, wobei $N\in \mathbb {R} ^{m\times (n-m)}$ die aus den verbleibenden Spalten von $A$ bestehende Matrix ist. Dabei steht „$B$“ hier für „Basis“ und „$N$“ für „Nichtbasis“. Entsprechend schreiben wir den Variablenvektor $x$ mit Vektoren $x_{B}\in \mathbb {R} ^{m}$ und $x_{N}\in \mathbb {R} ^{n-m}$ in der Form

$x={\begin{pmatrix}x_{B}\\x_{N}\end{pmatrix}}.$

Für jedes $x\in Z_{GN}$ können wir somit die Darstellung

$b=Ax={\begin{pmatrix}B&N\end{pmatrix}}{\begin{pmatrix}x_{B}\\x_{N}\end{pmatrix}}=Bx_{B}+Nx_{N}$

erhalten, welche für $x_{B}$ die explizite Darstellung

(7.21) $x_{B}=B^{-1}b-B^{-1}Nx_{N}$

impliziert (vgl. dazu die Darstellung (5.3)). Wählt man umgekehrt einen beliebigen Vektor $x_{N}$ und berechnet man anschließend $x_{B}$ nach (7.21), so ist $x:=(x_{B},x_{N})^{T}$ eine Lösung des Systems $Ax=b$ und folglich ein zulässiger Punkt für das Problem $({\mathcal {P}}_{GN})$.

Weiter bekommt man für die Zielfunktion von Problem $({\mathcal {P}}_{GN})$ die Darstellung

$f(x)=f(x_{B},x_{N})=f\left(B^{-1}b-B^{-1}Nx_{N},x_{N}\right)$

und damit für $({\mathcal {P}}_{GN})$ die alternative Formulierung

(7.22) $\inf _{x\in Z_{GN}}f(x)=\inf _{x_{N}\in \mathbb {R} ^{n-m}}f\left(B^{-1}b-B^{-1}Nx_{N},x_{N}\right).$

Besitzt das rechte der beiden Probleme eine Lösung $x_{N}^{*}$, so rechnet man $x_{B}^{*}$ nach (7.21) aus. Der Vektor $x^{*}=(x_{B}^{*},x_{N}^{*})^{T}$ ist dann Lösung von $({\mathcal {P}}_{GN})$. Unsere Herleitung zeigt insbesondere, dass das gleichungsrestringierte Problem $({\mathcal {P}}_{GN})$ mathematisch mit einem unrestringierten Problem äquivalent ist, welches überdies $m$ Variable weniger als $({\mathcal {P}}_{GN})$ aufweist. Den Vektor $x_{N}\in \mathbb {R} ^{n-m}$ bezeichnet man in diesem Zusammenhang auch als Vektor der reduzierten Variablen.

Sind $m$ linear unabhängige Spalten von $A$ nicht wie in dem folgenden Beispiel unmittelbar identifizierbar, dann könnte man z. B. durch Gauß-Elimination mittels Spalten- und Zeilenpivotsuche feststellen, ob $\operatorname {Rang} (A)=m$ ist und könnte man in diesem Fall die Matrix $B$ aus den Spalten von $A$ bilden, die im letzten Gauß-Tableau an den ersten $m$ 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 $B^{-1}$ von $B$ benötigt wird, so dass $B$ idealerweise leicht zu invertieren und gut konditioniert sein sollte. Wir geben dazu ein Beispiel.

Beispiel 7.14

Wir betrachten das Problem

${\begin{array}{ll}{\text{Minimiere}}&\sin(x_{1}+x_{2})+x_{3}^{2}+{\frac {1}{3}}\left(x_{4}+x_{5}^{4}+{\frac {1}{2}}x_{6}\right)\\{\text{u. d. N.}}&8x_{1}-6x_{2}+x_{3}+9x_{4}+4x_{5}=6,\\&3x_{1}+2x_{2}-x_{4}+6x_{5}+4x_{6}=-4\end{array}}$

und wir setzen $x:=(x_{1},x_{2},x_{3},x_{4},x_{5},x_{6})^{T}$ sowie

$A:={\begin{pmatrix}8&-6&1&9&4&0\\3&2&0&-1&6&4\end{pmatrix}},\quad b:={\begin{pmatrix}6\\-4\end{pmatrix}}.$

Offenbar sind die 3. und die 6. Spalte von $A$ 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 $A$ und entsprechend die Variablen im System $Ax=b$. Mit

$B:={\begin{pmatrix}1&0\\0&4\end{pmatrix}},\quad N:={\begin{pmatrix}8&9&4&6\\3&-1&6&2\end{pmatrix}}$

und

$x_{B}:=(x_{3},x_{6})^{T},\quad x_{N}:=(x_{1},x_{4},x_{5},x_{2})^{T}$

schreiben wir dann das System $Ax=b$ in der Form $Bx_{B}+Nx_{N}=b$.

Als nächstes berechnen wir

$B^{-1}={\begin{pmatrix}1&0\\0&1/4\end{pmatrix}},\quad B^{-1}N={\begin{pmatrix}8&9&4&-6\\3/4&-1/4&3/2&1/2\end{pmatrix}}$

und damit unter Verwendung von (7.21)

$x_{B}={\begin{pmatrix}x_{3}\\x_{6}\end{pmatrix}}={\begin{pmatrix}8&9&4&6\\3/4&-1/4&3/2&1/2\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{4}\\x_{5}\\x_{2}\end{pmatrix}}+{\begin{pmatrix}6\\-1\end{pmatrix}}.$

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

$\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]$

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

---

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

(7.23) $Y:={\begin{pmatrix}B^{-1}\\0\end{pmatrix}}\in \mathbb {R} ^{n\times m},\quad Z:={\begin{pmatrix}-B^{-1}N\\I\end{pmatrix}}\in \mathbb {R} ^{n\times (n-m)}$

können wir jeden Vektor $x\in Z_{GN}$ gemäß (7.21) darstellen in der Form

(7.24) $x={\begin{pmatrix}x_{B}\\x_{N}\end{pmatrix}}={\begin{pmatrix}B^{-1}b-B^{-1}Nx_{N}\\x_{N}\end{pmatrix}}=Yb+Zx_{N}.$

Dabei enthält die Matrix $Z$ die $((n-m)\times (n-m))$-Einheitsmatrix und sind somit ihre $n-m$ Spalten linear unabhängig. Außerdem gilt

$AZ={\begin{pmatrix}B&N\end{pmatrix}}{\begin{pmatrix}-B^{-1}N\\I\end{pmatrix}}=-BB^{-1}N+N=0.$

Demnach bilden die $n-m$ Spalten von $Z$ eines Basis des Nullraums von $A$

${\mathcal {N}}(A):=\{p\in \mathbb {R} ^{n}{\big |}Ap=0\}.$

Wir stellen weiter mit Lemma 3.12 fest, dass $p$ für jedes $x\in Z_{GN}$ genau dann eine zulässige Richtung für $Z_{GN}$ ist, wenn $p\in {\mathcal {N}}(A)$ gilt.

Ferner hat man

$AYb={\begin{pmatrix}B&N\end{pmatrix}}{\begin{pmatrix}B^{-1}\\0\end{pmatrix}}b=BB^{-1}b=b,\quad AZx_{N}=0.$

Wie ein Vergleich mit (7.24) zeigt, drückt also die einfache Eliminationstechnik zulässige Punkte von $({\mathcal {P}}_{GN})$ als Summe der speziellen Lösung $Yb$ von $Ax=b$ und der zulässigen Richtung $Zx_{N}$ für $Z_{GN}$ aus. Insbesondere erhält man die spezielle Lösung $Yb$, indem man $n-m$ Variable, d. h. $x_{N}$ 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 $Ax=b$ fast parallel zur $x_{1}$-Achse und ist $x$ eine Lösung von $Ax=b$, die fast in Richtung der positiven $x_{2}$-Achse zeigt, dann ist $\|x\|$ sehr klein und sind $\|Yb\|$ sowie $\|Zx_{N}\|$ sehr groß, so dass $x$ 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 $Yb$ - in Richtung der $x_{2}$-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 $B$ auftreten, wenn $B$ schlecht konditioniert ist. Daher wollen wir im nächsten Unterabschnitt noch andere Reduktionstechniken betrachten.

Im Hinblick darauf bemerken wir noch, dass offenbar die $m$ Spalten von $Y$ und die $n-m$ von $Z$ zusammen genommen linear unabhängig sind und folglich den $\mathbb {R} ^{n}$ aufspannen. Nun ist aus der Linearen Algebra bekannt, dass für $A\in \mathbb {R} ^{m\times n}$

$\mathbb {R} ^{n}={\mathcal {N}}(A)\oplus R(A^{T})$

gilt, wobei $R(A^{T})$ der Bildraum von $A^{T}$ ist und „$\oplus$“ die direkte Summe zweier Halbräume des $\mathbb {R} ^{n}$ bezeichnet. Da die Spalten von $Z$ eine Basis von ${\mathcal {N}}(A)$ bilden, generieren die Spalten von $Y$ daher eine Basis von $R(A^{T})$.

7.3.3 Allgemeine Elimination

In Anlehnung an den vorangehenden Unterabschnitt seien $Y\in \mathbb {R} ^{n\times m}$ und $Z\in \mathbb {R} ^{n\times (n-m)}$ Matrizen, für die gilt:

(7.25) $AY\in \mathbb {R} ^{m\times m}{\mbox{ ist nichtsingulär}},\quad AZ=0,\quad \operatorname {Rang} (Z)=n-m.$

Wie bei der einfachen Elimination bilden demnach die Spalten von $Z$ eine Basis des Nullraumes ${\mathcal {N}}(A)$ von $A$. Dagegen ist $Y$ hier nur durch die erste Bedingung in (7.25) spezifiziert. Für die bei der einfachen Elimination verwendete Matrix $Y:={\begin{pmatrix}B^{-1}\\0\end{pmatrix}}$ ist diese Bedingung wegen

$AY={\begin{pmatrix}B&N\end{pmatrix}}{\begin{pmatrix}B^{-1}\\0\end{pmatrix}}=I$

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

Bekanntlich lässt sich jede Lösung $x$ des inhomogenen Gleichungssystems $Ax=b$ als Summe einer beliebigen speziellen Lösung des Systems und einer Lösung des homogenen Systems $Ax=0$, also jedes $x\in Z_{GN}$ durch ein beliebiges $x^{*}\in Z_{GN}$ und ein $p\in {\mathcal {N}}(A)$ in der Form $x=x^{*}+p$ beschreiben. Da die Spalten von $Z$ nach Voraussetzung eine Basis des Nullraumes ${\mathcal {N}}(A)$ bilden, gibt es zu jedem solchen $p$ ein $x_{Z}\in \mathbb {R} ^{n-m}$ mit $p=Zx_{Z}$.

Weiter ist $Yx_{Y}$ mit einem Vektor $x_{Y}\in \mathbb {R} ^{m}$ eine spezielle Lösung von $Ax=b$, wenn

$b=AYx_{Y}$

bzw. wenn wegen der vorausgesetzten Invertierbarkeit von $AY$

$x_{Y}=(AY)^{-1}b$

gilt. Folglich erlaubt eine wie in (7.25) vorausgesetzte Wahl von $Y$ und $Z$, dass jedes $x\in Z_{GN}$ mittels Vektoren $x_{Y}\in \mathbb {R} ^{m}$ und $x_{Z}\in \mathbb {R} ^{n-m}$ in der Form

(7.26) $x=Yx_{Y}+Zx_{Z}$

bzw. mit einem Vektor $x_{Z}\in \mathbb {R} ^{n-m}$ in der Form

(7.27) $x=Y(AY)^{-1}b+Zx_{Z}$

geschrieben werden kann. Umgekehrt erhält man für jedes $x_{Z}$ mittels (7.27) einen für $Ax=b$ zulässigen Punkt $x$. Insbesondere liefert $x_{Z}=0$ den Vektor $Y(AY)^{-1}b\in Z_{GN}$ und ist das Problem $({\mathcal {P}}_{GN})$ aufgrund von (7.27) mit folgendem unrestringierten Problem äquivalent:

$\inf _{x_{Z}\in \mathbb {R} ^{n-m}}f\left(Y(AY)^{-1}b+Zx_{Z}\right).$

Die Matrix $Y$ wird idealerweise so gewählt, dass die Kondition der Matrix $AY$ so klein wie möglich ist, weil zur Berechnung des Vektors $(AY)^{-1}b$ das lineare Gleichungssystem $(AY)x=b$ gelöst werden muss. Wie wir zeigen wollen, ist es darum günstig, z. B. mit dem Householder-Verfahren eine $QS$-Zerlegung von $A^{T}$ der Art

$A^{T}=QS={\begin{pmatrix}Q_{1}&Q_{2}\end{pmatrix}}{\begin{pmatrix}R\\0\end{pmatrix}}$

zu berechnen, wie sie aus der Numerischen Mathematik bekannt ist. Dabei ist $Q:={\begin{pmatrix}Q_{1}&Q_{2}\end{pmatrix}}\in \mathbb {R} ^{n\times n}$ eine orthogonale Matrix und $R\in \mathbb {R} ^{m\times m}$ eine nichtsinguläre obere Dreiecksmatrix. Insbesondere haben somit die Untermatrizen $Q_{1}\in \mathbb {R} ^{n\times m}$ und $Q_{2}\in \mathbb {R} ^{n\times (n-m)}$ orthonormale Spalten.

Man definiert nun

$Y:=Q_{1},\quad Z:=Q_{2},$

d. h. ${\begin{pmatrix}Y&Z\end{pmatrix}}:={\begin{pmatrix}Q_{1}&Q_{2}\end{pmatrix}}$, so dass die Spalten von $Y$ und $Z$ gemeinsam eine Orthonormalbasis des $\mathbb {R} ^{n}$ bilden. (Bei der einfachen Eliminationstechnik ist dies typischerweise nicht der Fall.) Wie man sich leicht klarmacht, gilt damit insbesondere $Y^{T}Y=I$ und $Y^{T}Z=0$, so dass man aus

(7.28) $A={\begin{pmatrix}R^{T}&0\end{pmatrix}}{\begin{pmatrix}Y^{T}\\Z^{T}\end{pmatrix}}=R^{T}Y^{T}$

die Beziehungen

(7.29) $AY=R^{T},\quad AZ=0$

schließen kann.

Letzteres zeigt, dass die Matrizen $Y$ und $Z$ 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 $AY,R,R^{T}$ und $A$ im Fall $m=n$ dieselben Konditionen bezüglich der Spektralnorm besitzen. Schließlich folgt mit (7.27), dass jedes $x\in Z_{LC}$ mit einem $x_{Z}$ dargestellt werden kann als

(7.30) $x=YR^{-T}b+Zx_{Z}=Q_{1}R^{-T}b+Q_{2}x_{Z},$

wobei $x_{s}:=Q_{1}R^{-T}b\in Z_{GN}$ ist. Dabei muss man für die Bestimmung des Vektors $u:=R^{-T}b$ nur das lineare Gleichungssystem $R^{T}u=b$ mit der unteren Dreiecksmatrix $R^{T}\in \mathbb {R} ^{m\times m}$ auflösen, wobei $R^{T}$, wie oben festgestellt wurde, im Fall $m=n$ dieselbe Kondition wie $A$ hat.

Für die in (7.30) auftretende spezielle Lösung $x_{s}=Q_{1}R^{-T}b$ von $Ax=b$ folgert man unter Verwendung von (7.29) und der Identität $Y^{T}Y=I$

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

Also ist $x_{s}$ gerade die bezüglich der $l_{2}$-Norm kleinste aller Lösungen des Systems $Ax=b$ (vgl. Beispiel 3.16 (3)). Wie die letzte Identität in (7.31) weiter zeigt, ist $x_{s}$ Element von $R(A^{T})={\mathcal {N}}(A)^{\perp }$ und somit orthogonal zu ${\mathcal {N}}(A)$. Wenn $Y$ und $Z$ mittels einer $QS$-Zerlegung von $A^{T}$ bestimmt werden, wird folglich jedes Element $x\in Z_{LC}$ durch (7.30) als Summe bzw. Differenz von $x_{s}$ und einem dazu orthogonalen Vektor $Q_{2}x_{Z}=Zx_{Z}$ aus ${\mathcal {N}}(A)$ berechnet.

Vom Standpunkt der numerischen Stabilität her ist eine solche Wahl von $Y$ und $Z$ also ideal. Allerdings ist der für die Berechnung einer $QS$-Zerlegung von $A^{T}$ 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

7.4.1 Einleitung

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

${\begin{array}{lll}(QP_{GN}):&{\text{Minimiere}}&q(x):={\frac {1}{2}}x^{T}Qx+c^{T}x\\&{\text{u. d. N.}}&Ax=b.\end{array}}$

Dabei seien $Q\in \mathbb {R} ^{n\times n}$ eine symmetrische Matrix, $c\in \mathbb {R} ^{n},b\in \mathbb {R} ^{m}$ und $A\in \mathbb {R} ^{m\times n}$ eine Matrix mit

(7.32) $\operatorname {Rang} (A)=m.$

Die Rangbedingung (7.32) stellt zumindest für die Theorie keine Einschränkung dar, wie bereits mehrfach bemerkt wurde. Sie impliziert bekanntlich, dass $m\leq n$ ist und dass das inhomogene Gleichungssystem $Ax=b$ eine Lösung besitzt. Bezeichnen wir den zulässigen Bereich von $(QP_{GN})$ mit

${\mathcal {Z}}_{GN}:=\{x\in \mathbb {R} ^{n}{\big |}Ax=b\},$

so ist also hier ${\mathcal {Z}}_{GN}\neq \emptyset$.

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

(7.33) ${\begin{pmatrix}Q&-A^{T}\\-A&0\end{pmatrix}}{\begin{pmatrix}x\\y\end{pmatrix}}=-{\begin{pmatrix}c\\b\end{pmatrix}}$

darstellen. Die $((n+m)\times (n+m))$-Systemmatrix

(7.34) $K:={\begin{pmatrix}Q&-A^{T}\\-A&0\end{pmatrix}}$

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

Wir gehen nun wie in Abschnitt 7.3.3 davon aus, dass Matrizen $Y\in \mathbb {R} ^{n\times m}$ und $Z\in \mathbb {R} ^{n\times (n-m)}$ bekannt sind mit den Eigenschaften

(7.35) $AY\in \mathbb {R} ^{m\times m}{\mbox{ ist nichtsingulär}},\quad AZ=0,\quad \operatorname {Rang} (Z)=n-m.$

Wie wir dort gezeigt haben, lässt sich in diesem Fall jeder Vektor $x\in {\mathcal {Z}}_{GN}$ mit einem sog. Vektor der reduzierten Variablen $x_{Z}\in \mathbb {R} ^{n-m}$ und einem Vektor $x_{Y}\in \mathbb {R} ^{m}$ in der Form

(7.36) $x=Yx_{Y}+Zx_{Z}=x_{s}+Zx_{Z}$

darstellen, wobei

(7.37) $x_{s}:=Y(AY)^{-1}b$

eine spezielle Lösung von $Ax=b$ ist. Beispiele für Matrizen $Y$ und $Z$, welche die Bedingungen in (7.35) erfüllen, ergaben sich aus der einfachen Elimination und aus einer $QS$-Zerlegung von $A^{T}$.

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

$q(x)={\frac {1}{2}}x^{T}Qx+c^{T}x={\frac {1}{2}}(x_{s}+Zx_{Z})^{T}Q(x_{s}+Zx_{Z})+c^{T}(x_{s}+Zx_{Z})=:{\hat {q}}(x_{Z}),$

wobei wir ${\hat {q}}$ schreiben in der Form

(7.38) ${\hat {q}}(x_{Z})={\frac {1}{2}}x_{Z}^{T}(Z^{T}QZ)x_{Z}+(Qx_{s}+c)^{T}Zx_{Z}+\left({\frac {1}{2}}x_{s}^{T}Qx_{s}+c^{T}x_{s}\right).$

Gilt nun für die symmetrische Matrix $Z^{T}QZ\in \mathbb {R} ^{(n-m)\times (n-m)}$ in (7.38)

$Z^{T}QZ$ ist positiv definit,

so minimiert offenbar ein Vektor $x_{Z}^{*}$ die Funktion ${\hat {q}}$ genau dann, wenn $x_{Z}^{*}$ das System $\nabla {\hat {q}}(x_{Z})=0$ löst, welches ausgeschrieben lautet:

(7.39) $\left(Z^{T}QZ\right)x_{Z}=-Z^{T}(Qx_{s}+c).$

Die Matrix $Z^{T}QZ$ und der Vektor

$Z^{T}(Qx_{s}+c)=Z^{T}\nabla q(x_{s})$

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

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

Wenn $Z^{T}QZ$ positiv definit ist, hat das System (7.39) eine eindeutige Lösung $x_{Z}^{*}$ und ist damit

(7.40) $x^{*}=x_{s}+x_{Z}^{*}=Y(AY)^{-1}b+x_{Z}^{*}$

die eindeutige Lösung von Problem $(QP_{GN})$. Speziell für $c:=0$ und $b:=0$ ergibt sich in diesem Fall aus (7.37) und (7.39) $x_{s}=0$ sowie $x_{Z}^{*}=0$ und ist demzufolge $x^{*}=0$. Wegen $\operatorname {Rang} (A)=m$ folgt dann weiter aus der ersten Zeile des Systems in (7.33), dass $y^{*}=0$ ist. Wenn $Z^{T}QZ$ positiv definit ist, besitzt das zu (7.33) gehörende homogene System also nur die Nulllösung, was gleichbedeutend damit ist, dass die Matrix $K$ in (7.34) nichtsingulär ist. Zusammengefasst haben wir also gezeigt:

Satz 7.13

Die Matrix $Z^{T}QZ$ sei positiv definit. Dann folgt:

(i) Das Problem $(QP_{GN})$ besitzt eine eindeutige Lösung.

(ii) Die KKT-Matrix $K$ in (7.34) ist nichtsingulär.

In diesem Zusammenhang kann man darüber hinaus beweisen:

Satz 7.14

(i) Ist die Matrix $Z^{T}QZ$ nicht positiv semidefinit, dann gilt

$\inf _{x\in {\mathcal {Z}}_{GN}}q(x)=-\infty .$

(ii) Ist die Matrix $Z^{T}QZ$ positiv semidefinit, aber nicht positiv definit und besitzt Problem $(QP_{GN})$ eine Lösung $x^{*}$, so ist auch jeder Vektor $x^{*}+tZu$ mit $t>0$ Lösung von $(QP_{GN})$, wobei $u$ Eigenvektor zum Eigenwert 0 von $Z^{T}QZ$ ist.

Beweis.

Wegen $\operatorname {Rang} (A)=m$ ist ${\mathcal {Z}}_{GN}\neq \emptyset$. Wir nehmen nun $\inf _{x\in {\mathcal {Z}}_{GN}}q(x)>-\infty$ an, so dass das Problem $(QP_{GN})$ gemäß Satz 7.1 eine Lösung $x^{*}$ und somit das KKT-System (7.33) gemäß Satz 3.13 eine Lösung $(x^{*},y^{*})$ besitzt. Sei nun $\lambda$ ein negativer Eigenwert von $Z^{T}QZ$ und $u$ zugehöriger Eigenvektor, d. h. sei $Z^{T}QZu=\lambda u$ mit $\lambda <0$ und $u\neq 0$. Dann ist

$u^{T}Z^{T}QZu=u^{T}\lambda u<0$

und ergibt sich für $p:=Zu$ somit $p^{T}Qp<0$.

Weil $AZ=0$ gilt, folgt als nächstes $Ap=0$ und demnach

(7.41) $A(x^{*}+tp)=Ax^{*}=b,\quad t>0.$

Aus den KKT-Bedingungen für $(QP_{GN})$ in (7.33) erhält man weiter $Qx^{*}+c=A^{T}y^{*}$ und dies impliziert wiederum wegen $Ap=0$

$p^{T}(Qx^{*}+c)=p^{T}A^{T}y^{*}=(Ap)^{T}y^{*}=0.$

Demnach gilt

$q(x^{*}+tp)={\frac {1}{2}}(x^{*}+tp)^{T}Q(x^{*}+tp)+c^{T}(x^{*}+tp)=q(x^{*})+tp^{T}(Qx^{*}+c)+{\frac {1}{2}}t^{2}p^{T}Qp$

(7.42) $=q(x^{*})+{\frac {1}{2}}t^{2}p^{T}Qp<q(x^{*}),\quad t>0.$

In Verbindung mit (7.41) widerspricht dies aber der Optimalität von $x^{*}$. Also ist die Aussage (i) des Satzes richtig.

Ist weiter die Matrix $Z^{T}QZ$ positiv semidefinit und nicht positiv definit, so ist mindestens einer ihrer Eigenwerte identisch 0. Für den Nachweis von (ii) folge man nun dem Beweis von (i) für $\lambda =0$. Man erhält dann $p^{T}Qp=0$ für $p:=Zu$ und daher (vgl. (7.42))

$q(x^{*}+tp)=q(x^{*}),\quad t>0.$

q.e.d.

Umgekehrt kann man im Fall der Lösbarkeit des Problems $(QP_{GN})$ aus Satz 7.14 schließen:

Korollar 7.15

(i) Hat das Problem $(QP_{GN})$ eine Lösung, so ist die Matrix $Z^{T}QZ$ positiv semidefinit.

(ii) Hat das Problem $(QP_{GN})$ eine eindeutige Lösung, so ist $Z^{T}QZ$ positiv definit.

Wenn $Z^{T}QZ$ positiv semidefinit, aber nicht positiv definit ist, was z. B. für $Q=0$ der Fall ist, besitzt also das gleichungsrestringierte quadratische Optimierungsproblem $(QP_{GN})$ entweder eine Lösung (Satz 7.14 (ii)), oder es gilt $\inf _{x\in {\mathcal {Z}}_{GN}}q(x)=-\infty$ (Satz 7.11). Ist andererseits $Z^{T}QZ$ positiv definit, so hat $(QP_{GN})$ gemäß Satz 7.13 eine eindeutige Lösung.

Darüber hinaus zeigen die Herleitungen in diesem Unterabschnitt einen Weg auf, wie diese Lösung und zugehörige Multiplikatoren, sofern solche benötigt werden, bestimmt werden können. Diesen Lösungsweg für $(QP_{GN})$ werden wir im folgenden Unterabschnitt 7.4.2 nochmals zusammenfassen und kommentieren. Anschließend werden wir im Unterabschnitt 7.4.3 diskutieren, wie man vorgehen kann, wenn man eine Lösung von $(QP_{GN})$ über die direkte Lösung des KKT-Systems (7.33) anstrebt. Letzterer Lösungsweg hat den Vorteil, dass man dafür nur die Nichtsingularität der KKT-Matrix $K$ benötigt.

7.4.2 Die Nullraum-Methode

Wie im vorangegangenen Unterabschnitt sei insbesondere $A\in \mathbb {R} ^{m\times n}$ eine Matrix mit $\operatorname {Rang} (A)=m$ und seien Matrizen $Y\in \mathbb {R} ^{n\times m}$ und $Z\in \mathbb {R} ^{n\times (n-m)}$ bekannt, für die gilt:

(7.43) $AY\in \mathbb {R} ^{m\times m}{\mbox{ ist nichtsingulär}},\quad AZ=0,\quad \operatorname {Rang} (Z)=n-m.$

Darüber hinaus gelte:

(7.44) $Z^{T}QZ$ ist positiv definit.

Nach Satz 7.13 besitzt dann das Problem $(QP_{GN})$ eine eindeutige Lösung $x^{*}$ und einen eindeutigen zugehörigen Multiplikator $y^{*}$.

Wie aus Abschnitt 7.3.3 hervorgeht, lässt sich eine Lösung $x^{*}\in {\mathcal {Z}}_{GN}$ von Problem $(QP_{GN})$ unter diesen Voraussetzungen mit einer speziellen Lösung $x_{s}$ des Systems $Ax=b$ und mit einem Vektor $x_{Z}^{*}\in \mathbb {R} ^{n-m}$ in der Form

(7.45) $x^{*}=x_{s}+Zx_{Z}^{*}$

aufspalten. Insbesondere gilt

(7.46) $x_{s}:=Yx_{Y}^{*},\quad x_{Y}^{*}:=(AY)^{-1}b.$

Wegen der in (7.43) vorausgesetzten Nichtsingularität von $AY$ kann dabei $x_{Y}^{*}$ als eindeutige Lösung des linearen Gleichungssystems

(7.47) $(AY)x_{Y}=b$

berechnet werden. Wie im Unterabschnitt 7.4.1 gezeigt wurde, ergibt sich ferner $x_{Z}^{*}$ als eindeutige Lösung des linearen Gleichungssystems

(7.48) $\left(Z^{T}QZ\right)x_{Z}=-Z^{T}(c+Qx_{s}).$

Da die Matrix $Z^{T}QZ$ in diesem System nach Voraussetzung positiv definit ist, sollte man für die Lösung von (7.48) eine Cholesky-Zerlegung verwenden. Zusammengefasst gewinnt man also die Lösung $x^{*}$ von $(QP_{GN})$ bei einer solchen Vorgehensweise folgendermaßen:

• Man berechne Matrizen $Y$ und $Z$, welche den Bedingungen in (7.43) genügen.
• Man bestimme die eindeutigen Lösungen $x_{Y}^{*}$ und $x_{Z}^{*}$ der linearen Gleichungssysteme (7.47) und (7.48).
• Man berechne $x^{*}:=Yx_{Y}^{*}+Zx_{Z}^{*}$.

Vergleicht man diese Vorgehensweise mit den Ergebnissen aus dem Unterabschnitt 7.4.1, so stellt man fest, dass sie sich genau dann ergibt, wenn man das Problem $(QP_{GN})$ über die unrestringierte Minimierung von ${\hat {q}}$ aus (7.38) löst.

Für manche Zwecke, wie z. B. für die wichtigen SQP-Verfahren der nichtlinearen Optimierung, wird neben $x^{*}$ auch ein zu $x^{*}$ gehörender Vektor $y^{*}$ von Multiplikatoren benötigt. Unter der Voraussetzung (7.44) ist dieser Vektor eindeutig bestimmt (s. Satz 7.13). In diesem Zusammenhang beachte man, dass Multiplikation der ersten Gleichung in (7.33) von links mit $Y^{T}$ die Beziehung

$Y^{T}A^{T}y=Y^{T}(Qx+c)$

liefert und dass mit $AY$ auch $(AY)^{T}$ invertierbar ist. Also kann $y^{*}$ folgendermaßen berechnet werden:

• Man bestimme die eindeutige Lösung $y^{*}$ des linearen Gleichungssystems

(7.49) $(AY)^{T}y=Y^{T}(Qx^{*}+c).$

Die beschriebene Vorgehensweise zur Lösung von $(QP_{GN})$ bezeichnet man als Nullraum-Methode, da sie vorrangig von der Matrix $Z$, d. h. von einer Basis des Nullraumes von $A$ Gebrauch macht. Denn die Matrix $AY$ kann ja im Prinzip als Einheitsmatrix gewählt werden (siehe die einfache Elimination in Abschnitt 7.3.2). Verschiedene Nullraum-Methoden unterscheiden sich im wesentlichen durch die Wahl von $Y$ und $Z$.

Die Bestimmung einer Basis des Nullraumes von $A$ kann zumindest bei großen Problemen numerisch sehr teuer sein. Deshalb bietet sich die Nullraum-Methode insbesondere dann zur Lösung von $(QP_{GN})$ an, wenn die Dimension des Nullraums von $A$, d. h. wenn die Zahl $n-m$ relativ klein ist. Die Basis des Nullraums von $A$ ist außerdem nicht eindeutig definiert, so dass das lineare Gleichungssystem in (7.48), wenn diese ungünstig gewählt wird, schlecht konditioniert sein kann. Normalerweise wählt man die Matrix $Z$ für kleine und mittelgroße Probleme so, dass die Spalten von $Z$ orthonormal sind. Die Kondition der Matrix $Z^{T}QZ$ ist dann, wie man zeigen kann, höchstens so groß wie die von $Q$. Für große, dünn besetzte Matrizen $A$ ist eine solche Wahl von $Z$ aber numerisch zu teuer, so dass man oft gezwungen wird, $Z$ in ungünstigerer Weise festzulegen.

Die Durchführung der Nullraum-Methode an einem Beispiel stellen wir als Aufgabe:

Aufgabe 7.16

Man betrachte das Problem

${\begin{array}{ll}{\text{Minimiere}}&q(x):={\frac {1}{2}}x^{T}Qx+c^{T}x\\{\text{u. d. N.}}&Ax=b\end{array}}$

mit $x:=(x_{1},x_{2},x_{3})^{T}$ und

$Q:={\begin{pmatrix}6&2&1\\2&5&2\\1&2&4\end{pmatrix}},\quad c:={\begin{pmatrix}-8\\-3\\-3\end{pmatrix}},\quad A:={\begin{pmatrix}1&0&1\\0&1&1\end{pmatrix}},\quad b:={\begin{pmatrix}3\\0\end{pmatrix}}.$

(a) Man bestimme mittels der einfachen Elimination Matrizen $Y$ und $Z$ mit den Eigenschaften in (7.43).

(b) Man weise nach, dass auch die folgenden Matrizen die in (7.43) geforderten Eigenschaften besitzen:

(7.50) $Y:={\begin{pmatrix}2/3&-1/3\\-1/3&2/3\\1/3&1/3\end{pmatrix}},\quad Z:={\begin{pmatrix}-1\\-1\\1\end{pmatrix}}.$

(c) Man verwende die Nullraum-Methode mit $Y$ und $Z$ aus (7.50) zur Bestimmung der Lösung und des zugehörigen Multiplikators des gegebenen Problems. (Die Rechnungen mit $Y$ und $Z$ aus (7.50) sind etwas einfacher als entsprechende Rechnungen mit den Matrizen, die sich in Teil (a) anbieten.)

7.4.3 Direkte Lösung des KKT-Systems

Eine Lösung des Problems $(QP_{GN})$ lässt sich auch dadurch bestimmen, dass man das zugehörige KKT-System (7.33) direkt löst. Wir betrachten in diesem Zusammenhang zunächst den Fall

$Q$ ist positiv definit.

Das KKT-System für $(QP_{GN})$, welches durch

(7.51) ${\begin{array}{r}Qx+c-A^{T}y=0,\\Ax=b\end{array}}$

gegeben ist, besitzt dann eine eindeutige Lösung $(x^{*},y^{*})$ (vgl. Beispiel 3.16 (2)). Insbesondere lässt sich in diesem Fall der zu $x^{*}$ gehörende Multiplikator $y^{*}$ gemäß (3.41) als Lösung des linearen Gleichungssystems

(7.52) $\left(AQ^{-1}A^{T}\right)y=b+AQ^{-1}c$

berechnen. Da wir für das Problem $(QP_{GN})$ grundsätzlich die Rangbedingung $\operatorname {Rang} (A)=m$ vorausgesetzt haben, ist die Matrix $AQ^{-1}A^{T}$ in diesem System symmetrisch und positiv definit (s. Lemma 2.21). Ihre Aufstellung erfordert die Kenntnis der Inversen von $Q$, so dass man $Q^{-1}$ auch dazu verwenden kann, anschließend $x^{*}$ gemäß der Formel (3.40) zu berechnen:

(7.53) $x^{*}=Q^{-1}\left(A^{T}y^{*}-c\right).$

Wenn $Q^{-1}$ bekannt ist, besteht die Hauptarbeit bei einer solchen Vorgehensweise darin, das Gleichungssystem in (7.52) zu lösen. Dieses hat nur $m$ Gleichungen in $m$ Veränderlichen. Demgegenüber ist das KKT-System (7.51) selbst, dessen direkte Lösung wir anschließend diskutieren werden, ein System von $n+m$ Gleichungen mit $n+m$ Unbekannten.

Bei dem beschriebenen Vorgehen benötigt man aber neben der Inversen $Q^{-1}$ von $Q$ eine Zerlegung der symmetrischen, positiv definiten Matrix $AQ^{-1}A^{T}$. Daher ist die beschriebene Methode zur Lösung von $(QP_{GN})$ nur dann sinnvoll, wenn $Q$ leicht zu invertieren, d. h., wenn $Q$ z. B. eine Diagonal- oder Blockdiagonalmatrix ist oder wenn $Q^{-1}$ z. B. aufgrund der Verwendung einer Quasi-Newton-Update-Formel für $Q$ explizit bekannt ist. (Letzteres ist für die sog. SQP-Verfahren für allgemeine nichtlineare Optimierungsprobleme der Fall.)

Für die eindeutige Lösbarkeit des KKT-Systems in (7.51) bzw. des Systems

$Ku=d$

mit

(7.54) $K:={\begin{pmatrix}Q&-A^{T}\\-A&0\end{pmatrix}},\quad u:={\begin{pmatrix}x\\y\end{pmatrix}},\quad d:=-{\begin{pmatrix}c\\b\end{pmatrix}}$

muss $Q$ jedoch nicht positiv definit und nicht einmal regulär sein, sondern genügt es, dass die Systemmatrix $K$ in (7.54) nichtsingulär ist. Gemäß Satz 7.13 ist dies insbesondere der Fall, wenn eine Matrix $Z\in \mathbb {R} ^{n\times (n-m)}$ existiert, für die $AZ=0$ gilt und für die die Matrix $Z^{T}QZ$ positiv definit ist. Es sei in diesem Zusammenhang bemerkt, dass die symmetrische KKT-Matrix $K$ immer indefinit ist, selbst dann, wenn $Q$ positiv definit ist (s. [NoWri06, S. 454]):

Satz 7.17

Die Matrix $Z^{T}QZ$ sei positiv definit. Dann hat die KKT-Matrix $K\in \mathbb {R} ^{(n+m)\times (n+m)}$ in (7.54) $n$ positive und $m$ negative Eigenwerte und keiner ihrer Eigenwerte ist Null.

Wir setzen nun für die KKT-Matrix $K$ nur voraus, dass sie nichtsingulär ist, so dass sich die im Folgenden beschriebene Vorgehensweise auch zur Bestimmung von KKT-Punkten für nichtkonvexe Probleme eignet. Im Prinzip könnte man in einem solchen Fall die Lösung des linearen Gleichungssystems in (7.54) mittels Gauß-Elimination oder gegebenenfalls mit einer ihrer Varianten für dünn besetzte Matrizen ermitteln. Jedoch lässt sich bei solchen Methoden nicht die Symmetrie der Matrix $K$ ausnutzen. Daher ist es in diesem Zusammenhang am effektivsten, eine sog. symmetrische indefinite Faktorisierung von $K$ zu berechnen und damit das System in (7.54) zu lösen.

Ist $K\in \mathbb {R} ^{p\times p}$ eine beliebige symmetrische nichtsinguläre (und nicht notwendig positiv definite) Matrix, so besitzt $K$ eine symmetrische indefinite Zerlegung der Gestalt

(7.55) $P^{T}KP=LBL^{T},$

wobei $P\in \mathbb {R} ^{p\times p}$ eine Permutationsmatrix, $L\in \mathbb {R} ^{p\times p}$ eine untere Dreiecksmatrix mit Einsen in der Diagonale und $B\in \mathbb {R} ^{p\times p}$ eine Blockdiagonalmatrix mit Blöcken der Dimension 1 oder 2 ist. Insbesondere hat $B$ dieselbe Anzahl von negativen und positiven Eigenwerten wie $K$ und haben die $(2\times 2)$-Blockmatrizen in $B$ jeweils einen positiven und negativen Eigenwert (s. [GiMuWr91], [GolLoa96], [NoWri06]).

Beispiel 7.18

Die Matrix

$K:={\begin{pmatrix}0&1&2&3\\1&2&2&2\\2&2&2&3\\3&2&3&4\end{pmatrix}}$

hat, wie man z. B. mit MATLAB ermittelt, die Eigenwerte

$-1.6881,\quad -0.3386,\quad 0.9655,\quad 9.0611.$

Man prüft leicht nach, dass $K$ mit $P:=<math>(e^{1},e^{4},e^{3},e^{2})$, wobei $e^{i}$ die $i$-te Spalte der Einheitsmatrix $I\in \mathbb {R} ^{4\times 4}$ ist und mit den folgenden Matrizen in der Form (7.55) geschrieben werden kann:

$L:={\begin{pmatrix}1&0&0&0\\0&1&0&0\\1/9&2/3&1&0\\2/9&1/3&0&1\end{pmatrix}},\quad B:={\begin{pmatrix}0&3&0&0\\3&4&0&0\\0&0&-2/9&5/9\\0&0&5/9&10/9\end{pmatrix}}.$

Man beachte, dass beide Diagonalblockmatrizen in $B$ $(2\times 2)$-Matrizen sind, wobei die obere die Eigenwerte $-1.6056$ und $5.6056$ und die untere die Eigenwerte $-0.4234$ und $1.3122$ besitzt.

---

Auf die Berechnung einer solchen Zerlegung von $K$ können wir hier nicht eingehen. Wir verweisen dafür auf die oben angegebene Literatur. Hat man speziell für $K$ aus (7.54) eine Zerlegung wie in (7.55) berechnet (dies ist numerisch die wesentliche Arbeit), so folgt wegen $P^{T}P=PP^{T}=I$

$K=PLBL^{T}P^{T}.$

Das lineare Gleichungssystem $Ku=d$ entspricht in diesem Fall also dem System

(7.56) $LBL^{T}P^{T}u=P^{T}d.$

Wie man den obigen Angaben zu den darin vorkommenden Matrizen $L$ und $B$ entnehmen kann, sind diese Matrizen nichtsingulär. Daher kann man die eindeutige Lösung $u^{*}$ des Systems (7.56) auf folgende effiziente Weise berechnen, bei der man die Struktur der in der Zerlegung vorkommenden Matrizen ausnutzt (man setze dazu zunächst $v:=BL^{T}P^{T}u$ und fahre in ähnlicher Weise mit $L^{T}P^{T}u$, usw. fort):

1. Man bestimme eine Lösung $v_{1}$ von $Lv=P^{T}d$.
2. Man bestimme eine Lösung $v_{2}$ von $Bv=v_{1}$.
3. Man bestimme eine Lösung $v_{3}$ von $L^{T}v=v_{2}$.
4. Man setze $u^{*}=Pv_{3}$.

Die Lösung des Gleichungssystems unter 2. lässt sich aufgrund der speziellen Blockstruktur von $B$ auf die Lösung von $(1\times 1)$- bzw. $(2\times 2)$-Systemen reduzieren. Ferner müssen in 1. und 3. nur gestaffelte Gleichungssysteme mit einer Dreiecksmatrix aufgelöst werden. Schließlich beachte man, dass Multiplikation eines Vektors von links mit $P^{T}$ bzw. $P$ nur eine Umstellung seiner Komponenten bedeutet, also numerisch billig ist.

Eine solche Vorgehensweise ist für viele Probleme recht effektiv. Ungünstig kann sie für große Probleme werden, bei denen die Matrix $L$ sehr viel dichter besetzt ist als die Ausgangsmatrix $K$. Es sei abschließend hierzu noch ohne weitere Erläuterung erwähnt, dass die anfänglich beschriebene Vorgehensweise für den Fall, dass $Q$ positiv definit ist, als ein Spezialfall der Lösung des Systems (7.54) mittels einer symmetrischen indefiniten Faktorisierung von $K$ interpretiert werden kann.

7.5 Probleme mit Ungleichungsnebenbedingungen

7.5.1 Einleitung

Als nächstes wenden wir uns der Lösung quadratischer Optimierungsprobleme mit linearen Gleichungs- und Ungleichungsrestriktionen zu. Wir gehen dazu von der folgenden Gestalt eines solchen Problems aus, weil diese für die Darstellung der Methoden, die wir vorstellen möchten, zweckmäßiger als die Normalform eines quadratischen Optimierungsproblems ist:

${\begin{array}{lll}(QP):&{\text{Minimiere}}&q(x):={\frac {1}{2}}x^{T}Qx+c^{T}x\\&{\text{u. d. N.}}&(a^{i})^{T}x-b_{i}=0\quad (i\in {\mathcal {E}}),\\&&(a^{i})^{T}x-b_{i}\leq 0\quad (i\in {\mathcal {I}}).\end{array}}$

Dabei seien $Q\in \mathbb {R} ^{n\times n}$ eine symmetrische Matrix, $c,a^{i}\in \mathbb {R} ^{n},b_{i}\in \mathbb {R}$ und

${\mathcal {E}}:=\{1,\ldots ,m\},\quad {\mathcal {I}}:=\{m+1,\ldots ,m+l\}.$

Die Gleichungs- und Ungleichungsnebenbedingungen sind hier also von 1 bis $m+l$ durchnummeriert.

Wir bezeichnen dieses allgemeine quadratische Optimierungsproblem wiederum mit $(QP)$ (es ließe sich ja äquivalent in eines in Normalform umschreiben). Der zulässige Bereich von $(QP)$ ist dann hier durch

${\mathcal {Z}}_{QP}:=\left\{x\in \mathbb {R} ^{n}{\big |}(a^{i})^{T}x-b_{i}=0\quad (i\in {\mathcal {E}}),\quad (a^{i})^{T}x-b_{i}\leq 0\quad (i\in {\mathcal {I}})\right\}$

gegeben. Weiter definieren wir

${\mathcal {A}}(x):=\left\{i\in ({\mathcal {E}}\cup {\mathcal {I}}){\big |}(a^{i})^{T}x-b_{i}=0,x\in {\mathcal {Z}}_{QP}\right\}$

Der Einfachheit halber bezeichnen wir ${\mathcal {A}}(x)$ als Menge der aktiven Indizes. (In Abschnitt 3.2 hatten wir diese Bezeichnung ja nur für Ungleichungsnebenbedingungen eingeführt.)

Jeder lokale Minimalpunkt von Problem $(QP)$ ist nach Satz 3.13 ein KKT-Punkt des Problems. Im Fall, dass $Q$ positiv semidefinit und damit $(QP)$ ein konvexes Problem ist, ist ferner nach Satz 3.7 jeder KKT-Punkt von $(QP)$ ein globaler Minimalpunkt von $(QP)$. Im konvexen Fall ist also die Existenz eines KKT-Punktes $x^{*}$ notwendig und hinreichend dafür, dass $x^{*}$ das Problem $(QP)$ löst.

In diesem Zusammenhang seien zwei Phänomene erwähnt, die für einen KKT-Punkt $x^{*}$ von $(QP)$ auftreten können und die bei der Durchführung einiger Algorithmen Schwierigkeiten bereiten können. In beiden Fällen bezeichnet man $(QP)$ als in $x^{*}$ degeneriert. (Der Begriff der Degeneriertheit wird in der Literatur leider nicht einheitlich verwendet.)

Und zwar liegt eine Art von Degeneriertheit bei $x^{*}$ vor, wenn die Gradienten $a^{i}$ $(i\in {\mathcal {A}}(x^{*}))$ aller in $x^{*}$ aktiven Restriktionen linear abhängig sind. (In der Sprache der nichtlinearen Optimierung, ist in diesem Fall die „Linear Independence Constraint Qualification (LICQ)“ in $x^{*}$ nicht erfüllt.) Eine solche Situation tritt z. B. auf, wenn mehr als $n$ Restriktionen in $x^{*}$ aktiv sind.

Beispiel 7.19

Die Aufgabe

${\begin{array}{ll}{\text{Minimiere}}&q(x):=x_{1}^{2}+x_{2}^{2}\\{\text{u. d. N.}}&x_{1}\geq 0,\\&x_{2}\geq 0,\\&x_{1}-x_{2}\geq 0\end{array}}$

hat offenkundig die Lösung $x^{*}:=(0,0)^{T}$. Die drei Restriktionen des Problems sind in $x^{*}$ aktiv, so dass die zugehörigen Gradienten linear abhängig sind.

---

Die lineare Abhängigkeit der $a^{i}$ $(i\in {\mathcal {A}}(x^{*}))$ kann beispielsweise Schwierigkeiten bei dem im Unterabschnitt 7.5.2 beschriebenen Active-Set-Verfahren verursachen, bei dem in jeder Iteration ein gleichungsrestringiertes Problem bezüglich der für die aktuelle Iterierte aktiven Restriktionen gelöst werden muss. Ist dann nämlich $A$ diejenige Matrix, welche die zu den aktiven Restriktionen gehörenden Vektoren $(a^{i})^{T}$ als Zeilen hat und sind die entsprechenden $a^{i}$ linear abhängig, so kann die Berechnung der Nullraummatrix $Z$ zu $A$ Schwierigkeiten bereiten. Auch Matrizen in anderen Verfahren, die für deren Durchführung invertierbar sein müssen, sind in diesem Fall singulär. Dies trifft z. B. auf die Matrix $AQ^{-1}A^{T}$ zu, die bei der ersten im Unterabschnitt 7.4.3 beschriebenen Methode zur direkten Lösung des KKT-Systems benötigt wird.

Eine zweite Art von Degeneriertheit liegt vor, wenn die strikte Komplementaritätsbedingung

$\lambda _{i}^{*}>0,\quad i\in ({\mathcal {I}}\cap {\mathcal {A}}(x^{*}))$

für die zu $x^{*}$ gehörenden Multiplikatoren $\lambda _{i}^{*}$ verletzt ist, d. h., wenn $\lambda _{i}^{*}=0$ für mindestens einen zu einer aktiven Ungleichungsrestriktion gehörenden Index $i$ gilt.

Beispiel 7.20

Man betrachte das Problem

${\begin{array}{ll}{\text{Minimiere}}&q(x):=(x_{1}-1)^{2}+(x_{2}-1)^{2}\\{\text{u. d. N.}}&x_{1}\geq 1,\\&x_{2}\geq 2.\end{array}}$

Es besitzt offenbar die Lösung $x^{*}:=(1,2)^{T}$ und beide Restriktionen sind in $x^{*}$ aktiv. Die Bedingung (3.15) der KKT-Bedingungen lautet hier in $(x^{*},\lambda ^{*})$

(7.57) $2{\begin{pmatrix}x_{1}^{*}-1\\x_{2}^{*}-1\end{pmatrix}}+\lambda _{1}^{*}{\begin{pmatrix}-1\\0\end{pmatrix}}+\lambda _{2}^{*}{\begin{pmatrix}0\\-1\end{pmatrix}}={\begin{pmatrix}0\\0\end{pmatrix}}.$

Also ergibt sich $\lambda _{1}^{*}=0$ und $\lambda _{2}^{*}=2$.

Offenbar ist hier die $x_{1}$-Komponente von $x^{*}$ identisch mit der des (unrestringierten) Minimalpunktes ${\hat {x}}:=(1,1)^{T}$ von $q$. Die erste Komponente $2(x_{1}^{*}-1)$ des ersten Vektors in (7.57) entspricht also gerade ${\frac {\partial }{\partial x_{1}}}q({\hat {x}})$, so dass die ersten Komponenten der beiden anderen Summanden auf der linken Seite von (7.57) wegen ${\frac {\partial }{\partial x_{1}}}q({\hat {x}})=0$ in der Summe keinen Beitrag mehr leisten dürfen.

---

Ist die strikte Komplementaritätsbedingung in $(x^{*},\lambda ^{*})$ verletzt und gilt für eine durch ein numerisches Verfahren erzeugte Näherung $(x^{k},\lambda ^{k})$ von $(x^{*},\lambda ^{*})$, dass $\lambda _{j}^{k}\approx 0$ für ein $j$ ist, so ist es zumeist schwierig zu entscheiden, ob die zugehörige Restriktion im Grenzwert $x^{*}$ aktiv ist oder nicht. Insbesondere Active-Set- und Gradientenprojektionsverfahren, die wir im Folgenden vorstellen wollen, neigen dann zu einem Zick-Zack-Verhalten, wenn eine solche Restriktion mal in das zu lösende Unterproblem mit aufgenommen wird und mal nicht. Es sollten daher erforderlichenfalls Maßnahmen in Algorithmen vorgesehen werden, die ein derartiges Verhalten verhindern.

In den folgenden beiden Unterabschnitten wollen wir nun ein Active-Set- und ein modifiziertes Gradientenprojektionsverfahren für die Lösung quadratischer Optimierungsprobleme vom Typ $(QP)$ diskutieren. Die Beschreibung weiterer Methoden für solche Probleme, wie die von Pfadverfolgungsmethoden (z. B. [NoWri06], [Wri97]) oder die des Goldfarb-Idnani-Verfahrens (z. B. [GeiKa02], [Spe93], [SuYu06]), wäre wünschenswert, aber übersteigt den begrenzten Rahmen dieses Kurses.

7.5.2 Ein Active-Set-Verfahren

In diesem Unterabschnitt beschreiben wir ein primales Active-Set-Verfahren zur Lösung konvexer quadratischer Optimierungsprobleme, d. h. für Probleme der Gestalt $(QP)$ mit der Eigenschaft

$Q$ ist positiv semidefinit.

„Primales Verfahren“ bedeutet hier, dass bei diesem Verfahren Näherungen einer Lösung des primalen Problems erzeugt werden. (Es gibt auch duale und primal-duale Active-Set-Verfahren.)

Einführung: Wir stellen zunächst die folgende, in der Optimierung häufig verwendete und geometrisch einleuchtende Aussage bereit:

Lemma 7.21

Seien $f,g_{i},h_{j}\in C(\mathbb {R} ^{n})$ und sei $({\mathcal {P}})$ das Problem

${\begin{array}{lll}({\mathcal {P}}):&Minimiere&f(x)\\&u.~d.~N.&h_{j}(x)=0\quad (j=1,\ldots ,m),\\&&g_{i}(x)\leq 0\quad (i=1,\ldots ,l).\end{array}}$

Ist $x^{*}$ ein lokaler Minimalpunkt von $({\mathcal {P}})$, so ist $x^{*}$ auch ein lokaler Minimalpunkt von

$({\mathcal {P}}):$ Minimiere $f(x)$ über alle $x\in Z^{*}$

für

$Z^{*}:={\Big \{}x\in \mathbb {R} ^{n}{\big |}h_{j}(x)=0\quad (j=1,\ldots ,m),\quad g_{i}(x)=0\quad (i\in I(x^{*})){\Big \}}$

mit

$I(x^{*}):=\{i\in \{1,\ldots ,l\}{\big |}g_{i}(x^{*})=0\}.$

Beweis.

Übung!

Man betrachte zunächst für ein $x^{*}\in {\mathcal {Z}}_{QP}$ und für die damit festliegende Menge ${\mathcal {A}}(x^{*})$ der aktiven Indizes das folgende gleichungsrestringierte quadratische Optimierungsproblem:

(7.58) ${\begin{array}{ll}{\text{Minimiere}}&q(x):={\frac {1}{2}}x^{T}Qx+c^{T}x\\{\text{u. d. N.}}&(a^{i})^{T}x-b_{i}=0\quad (i\in {\mathcal {A}}(x^{*})).\end{array}}$

Ist $x^{*}$ eine Lösung des Problems $(QP)$, so ist offenbar $x^{*}\in {\mathcal {Z}}_{QP}$ und löst $x^{*}$ gemäß Lemma 7.21 auch das Problem (7.58). Ist umgekehrt $x^{*}\in {\mathcal {Z}}_{QP}$ und ist $x^{*}$ selbst auch Lösung von (7.58), so gibt es Multiplikatoren $\lambda _{i}^{*}$ $(i\in {\mathcal {A}}(x^{*}))$, so dass die folgenden KKT-Bedingungen für das Problem (7.58) erfüllt sind:

$Qx^{*}+c+\sum _{i\in {\mathcal {A}}(x^{*})}\lambda _{i}^{*}a^{i}=0,$

$(a^{i})^{T}x^{*}-b_{i}=0\quad (i\in {\mathcal {A}}(x^{*})).$

Gilt in diesem Fall zusätzlich

(7.59) $\lambda _{i}^{*}\geq 0,\quad i\in ({\mathcal {I}}\cap {\mathcal {A}}(x^{*})),$

so erfüllt $x^{*}\in {\mathcal {Z}}_{QP}$ offenbar auch die KKT-Bedingungen für das Problem $(QP)$ und ist $x^{*}$ damit eine Lösung von $(QP)$.

Ziel der im Folgenden beschriebenen Methode ist es, ausgehend von einem für das Problem $(QP)$ zulässigen Punkt $x^{0}$, zulässige Punkte $x^{k}$ für $(QP)$ zu erzeugen, so dass $x^{*}:=x^{\ell }$ für ein $\ell$ das Problem (7.58) löst und die zugehörigen Multiplikatoren die Bedingung in (7.59) erfüllen. Nach dem Gesagten ist $x^{*}$ dann auch eine Lösung des Ausgangsproblems $(QP)$. Auf Methoden zur Auffindung eines Startpunktes $x^{0}\in {\mathcal {Z}}_{QP}$ werden wir weiter unten eingehen.

Ein primales Active-Set-Verfahren geht im $k$-ten Schritt von einem Punkt $x^{k}$ und einer Arbeitsmenge (working set) ${\mathcal {W}}_{k}$ von Indizes aus, wobei

(7.60) $x^{k}\in {\mathcal {Z}}_{QP},\quad {\mathcal {E}}\subseteq {\mathcal {W}}_{k}\subseteq {\mathcal {A}}(x^{k})$

und demnach insbesondere

(7.61) $(a^{i})^{T}x^{k}-b_{i}=0\quad (i\in {\mathcal {W}}_{k})$

gilt. Die Indexmenge ${\mathcal {W}}_{k}$ muss also alle Indizes der Gleichungsrestriktionen und kann einige oder alle Indizes von Ungleichungsrestriktionen enthalten, welche in $x^{k}$ aktiv sind. In der $k$-ten Iteration ist dann ein quadratisches Optimierungsproblem mit linearen Gleichungsnebenbedingungen für Indizes $i\in {\mathcal {W}}_{k}$ zu lösen. Anschließend werden unter Verwendung von Informationen, die man aus der Lösung dieses Unterproblems gewinnt, ein neuer Vektor $x^{k+1}$ und eine neue Arbeitsmenge ${\mathcal {W}}_{k+1}$ gebildet.

Für jedes $k$ muss dabei ${\mathcal {W}}_{k}$ derart sein, dass für die Gradienten $a^{i}$ der im Unterproblem auftretenden Restriktionen gilt:

(7.62) $a^{i}~(i\in {\mathcal {W}}_{k}){\mbox{ sind linear unabhängig}}.$

Die letztere Bedingung muss auch dann erfüllt sein, wenn die Vektoren $a^{i}$ $(i\in {\mathcal {A}}(x^{k}))$ linear abhängig sein sollten.

Auf diese Weise wird sukzessive eine Folge zulässiger Punkte für $(QP)$ erzeugt, für welche die Zielfunktion $q$ von $(QP)$ von einem Schritt zum nächsten zumindest nicht zunimmt. Darüber hinaus wird sukzessive die Bestimmung der Menge ${\mathcal {A}}(x^{*})$ der in einer Lösung $x^{*}$ von $(QP)$ aktiven Indizes sowie die Erzeugung nichtnegativer Multiplikatoren zu den Ungleichungsnebenbedingungen von $(QP)$ angestrebt.

Herleitung der einzelnen Verfahrensschritte: Wir wollen jetzt die einzelnen Schritte, die in der $k$-ten Iteration des Verfahrens zu durchlaufen sind, im Detail herleiten. Dazu setzen wir die Bedingungen in (7.60) und (7.62) voraus und definieren wir

$g^{k}:=\nabla q(x^{k})=Qx^{k}+c.$

Ein beliebiger Vektor $x$ kann mit einem $p$ in der Form $x:=x^{k}+p$ dargestellt werden. Mittels einer Taylor-Entwicklung erhält man daher

(7.63) $q(x)=q(x^{k}+p)=q(x^{k})+(g^{k})^{T}p+{\frac {1}{2}}p^{T}Qp.$

Folglich kann man $q(x)$ minimieren, indem man das Funktional auf der rechten Seite von (7.63) bezüglich $p$ minimiert. Die Konstante $q(x^{k})$ kann dabei fortgelassen werden.

Weiter soll zunächst gesichert werden, dass mit $x^{k}$ auch $x^{k+1}$ für die zur Arbeitsmenge ${\mathcal {W}}_{k}$ gehörenden Restriktionen von $(QP)$ zulässig ist. Die gesuchte Richtung sollte also eine hinsichtlich der Gleichungsnebenbedingungen in (7.61) zulässige Richtung sein. Gemäß Lemma 3.12 führen diese Überlegungen zu dem folgenden Unterproblem, das in der $k$-ten Iteration zu lösen ist:

${\begin{array}{lll}(WP)_{k}:&{\text{Minimiere}}&{\frac {1}{2}}p^{T}Qp+(g^{k})^{T}p\\&{\text{u. d. N.}}&(a^{i})^{T}p=0\quad (i\in {\mathcal {W}}_{k}).\end{array}}$

Besitzt das Problem $(WP)_{k}$ eine Lösung $p^{k}$, so erfüllt mit $x^{k}$ offenbar auch $x^{k+1}:=x^{k}+\alpha p^{k}$ für jedes $\alpha \geq 0$ die Bedingungen in (7.61). Dabei ist $p^{k}$ genau dann eine Lösung von $(WP)_{k}$, wie wir mehrfach ausnutzen werden, wenn Multiplikatoren $\lambda _{i}^{k}$ existieren, so dass gilt (vgl. Korollar 3.14):

(7.64) ${\begin{matrix}Qp^{k}+g^{k}+\sum \limits _{i\in {\mathcal {W}}_{k}}\lambda _{i}^{k}a^{i}=0,\\(a^{i})^{T}p^{k}=0(i\in {\mathcal {W}}_{k}).\end{matrix}}$

Aufgrund der Voraussetzung in (7.62) hat die Systemmatrix zu den Gleichungsnebenbedingungen von Problem $(WP)_{k}$ vollen Rang und ist damit die Voraussetzung (7.32) im Abschnitt 7.4 über gleichungsrestringierte quadratische Probleme für $(WP)_{k}$ erfüllt. Die Existenz einer eindeutigen Lösung des Unterproblems $(WP)_{k}$ ist gewährleistet, wenn die Matrix $Z_{k}^{T}QZ_{k}$ für eine Nullraummatrix $Z_{k}$ zu dieser Systemmatrix positiv definit ist (Satz 7.13). Die positive Definitheit von $Z_{k}^{T}QZ_{k}$ ist insbesondere dann gesichert, wenn $Q$ positiv definit ist. Eine Lösung des Unterproblems $(WP)_{k}$ kann dann mit einer der Methoden aus Abschnitt 7.4 gewonnen werden.

Wir definieren nun

(7.65) $\lambda _{r}^{k}:=\min _{i\in ({\mathcal {W}}_{k}\cap {\mathcal {I}})}\lambda _{i}^{k}{\text{ (d. h. }}\lambda _{r}^{k}=+\infty {\text{ im Fall }}{\mathcal {W}}_{k}\cap {\mathcal {I}}=\emptyset ),$

wobei $r$ von $k$ abhängt. Als nächstes analysieren wir die folgenden drei Fälle:

Fall 1: $p^{k}\neq 0$.

Fall 2: $p^{k}=0$ und $\lambda _{r}^{k}\geq 0$.

Fall 3: $p^{k}=0$ und $\lambda _{r}^{k}<0$.

Wir beginnen mit einem Ergebnis für den Fall 1, wobei $q$ die Zielfunktion des Problems $(QP)$ ist.

Lemma 7.22

Es sei $p^{k}$ eindeutige Lösung des Unterproblems $(WP)_{k}$. Ist $p^{k}\neq 0$, so ist $p^{k}$ Abstiegsrichtung für $q$ in $x^{k}$.

Beweis.

Da $p:=0$ für das Problem $(WP)_{k}$ zulässig und $p^{k}\neq 0$ die nach Voraussetzung eindeutige Lösung dieses Problems ist, erhält man

${\frac {1}{2}}(p^{k})^{T}Qp^{k}+(g^{k})^{T}p^{k}<0.$

Weil $Q$ generell als positiv semidefinit vorausgesetzt wurde, ist weiter $(p^{k})^{T}Qp^{k}\geq 0$ und daher $(g^{k})^{T}p^{k}<0$. Damit folgt die Behauptung aus Lemma 3.9.

q.e.d.

Zu $p^{k}\neq 0$ sei nun $\alpha _{k}$ die maximale Schrittweite im Intervall $[0,1]$, so dass mit $x^{k}\in {\mathcal {Z}}_{QP}$ auch $x^{k+1}:=x^{k}+\alpha _{k}p^{k}$ noch in ${\mathcal {Z}}_{QP}$ liegt. Diese Schrittweite lässt sich leicht berechnen:

Lemma 7.23

Es sei $p^{k}\neq 0$ Lösung des Unterproblems $(WP)_{k}$ und

(7.66) $\alpha _{k}:=\min\{1,\beta _{k}\}$ mit $\beta _{k}:=\min _{i\notin {\mathcal {W}}_{k},(a^{i})^{T}p^{k}>0}{\frac {b_{i}-(a^{i})^{T}x^{k}}{(a^{i})^{T}x^{k}}}.$

Dann ist $\alpha :=\alpha _{k}$ das größte $\alpha \in [0,1]$, so dass $x^{k+1}:=x^{k}+\alpha p^{k}$ in ${\mathcal {Z}}_{QP}$ liegt.

Beweis.

Wegen $x^{k}\in {\mathcal {Z}}_{QP}$ und $(a^{i})^{T}p^{k}=0$ $(i\in {\mathcal {W}}_{k})$ gilt für alle $\alpha \geq 0$

$(a^{i})^{T}\left(x^{k}+\alpha p^{k}\right)-b_{i}=(a^{i})^{T}x^{k}-b_{i}=0\quad (i\in {\mathcal {W}}_{k}).$

Sei nun $i\notin {\mathcal {W}}_{k}$, also insbesondere $i\in {\mathcal {I}}$. Ist dann $(a^{i})^{T}p^{k}\leq 0$, so hat man für alle $\alpha \geq 0$

$(a^{i})^{T}\left(x^{k}+\alpha p^{k}\right)-b_{i}=(a^{i})^{T}x^{k}+\alpha (a^{i})^{T}p^{k}-b_{i}\leq (a^{i})^{T}x^{k}-b_{i}\leq 0.$

Ist schließlich $i\notin {\mathcal {W}}_{k}$ und $(a^{i})^{T}p^{k}>0$, so folgert man

$(a^{i})^{T}\left(x^{k}+\alpha p^{k}\right)-b_{i}\leq 0\Leftrightarrow \alpha (a^{i})^{T}p^{k}\leq b_{i}-(a^{i})^{T}x^{k}\Leftrightarrow \alpha \leq {\frac {b_{i}-(a^{i})^{T}x^{k}}{(a^{i})^{T}p^{k}}}.$

Zusammen genommen erschließt man die Behauptung.

q.e.d.

Im Fall $\beta _{k}\leq 1$ bezeichnen wir eine Restriktion mit Index $i$, für welche das Minimum in (7.66) angenommen wird, als blockierende Restriktion. Man beachte in diesem Zusammenhang, dass sich $\beta _{k}=\alpha _{k}=0$ ergibt, wenn für einen Index $i\notin {\mathcal {W}}_{k}$ mit $(a^{i})^{T}p^{k}>0$ gleichzeitig $i\in \left({\mathcal {I}}\cap {\mathcal {A}}(x^{k})\right)$ und damit $b_{i}-(a^{i})^{T}x^{k}=0$ gilt (siehe die Bemerkungen dazu im Anschluss an den Konvergenzsatz 7.28).

Ist die in der Definition von $\beta _{k}$ in (7.66) vorkommende Indexmenge leer und somit $\beta _{k}=\infty$ oder ist $\beta _{k}>1$, also keine Restriktion blockierend, so ist $\alpha _{k}=1$ und offenbar keine neue Restriktion in $x^{k+1}:=x^{k}+\alpha _{k}p^{k}$ aktiv. Ist andererseits $\beta _{k}\leq 1$, dann wurde der Schritt der Länge $\alpha _{k}=\beta _{k}$ von $x^{k}$ in Richtung $p^{k}$ durch eine Restriktion mit Index $i\notin {\mathcal {W}}_{k}$ blockiert. Wie man aus der Definition von $\beta _{k}$ erschließt, ist dann die Restriktion mit diesem Index $i$ in $x^{k+1}$ aktiv, d. h. ist $i\in \left({\mathcal {I}}\cap {\mathcal {A}}(x^{k+1})\right)$. In diesem Fall wählt man einen Index $i$ zu einer blockierenden Restriktion aus und bildet man eine neue Arbeitsmenge ${\mathcal {W}}_{k+1}$, indem man $i$ zu ${\mathcal {W}}_{k}$ hinzufügt.

Wenn das Problem $(WP)_{k}$ eine Lösung $p^{k}\neq 0$ besitzt, ist also gesichert, dass $x^{k+1}$ wieder zulässig für $(QP)$ ist. In der beschriebenen Weise fährt man dann so lange fort, bis das aktuelle Unterproblem die Lösung $p^{k}=0$ besitzt, bis also einer der Fälle 2 und 3 oben eintritt. Im Hinblick auf diese Fälle beweisen wir als nächstes:

Lemma 7.24

Ist $p^{k}=0$ Lösung des Unterproblems $(WP)_{k}$, dann ist $x^{k}$ Lösung des Problems

(7.67) ${\begin{array}{ll}Minimiere&q(x)={\frac {1}{2}}x^{T}Qx+c^{T}x\\u.~d.~N.&(a^{i})^{T}x-b_{i}=0\quad (i\in {\mathcal {W}}_{k}).\end{array}}$

Sind ferner $\lambda _{i}^{k}$ die zur Lösung $p^{k}$ von $(WP)_{k}$ gehörenden Multiplikatoren und gilt $\lambda _{r}^{k}\geq 0$ für $\lambda _{r}^{k}$ aus (7.65), so löst $x^{k}$ auch das Problem $(QP)$.

Beweis.

Für $p^{k}$ sind mit Multiplikatoren $\lambda _{i}^{k}$ die KKT-Bedingungen für $(WP)_{k}$ in (7.64) erfüllt. Wegen $p^{k}=0$ und $g^{k}=Qx^{k}+c$ folgt aus diesen

(7.68) $Qx^{k}+c+\sum _{i\in {\mathcal {W}}_{k}}^{}\lambda _{i}^{k}a^{i}=0.$

Aufgrund der generellen Voraussetzung in (7.60) hat man weiter

(7.69) $(a^{i})^{T}x^{k}-b_{i}=0\quad (i\in {\mathcal {W}}_{k}).$

Die Bedingungen (7.68) und (7.69) zusammen implizieren, dass $x^{k}$ das Problem (7.67) löst. Gilt ferner

$\lambda _{r}^{k}=\min _{i\in ({\mathcal {W}}_{k}\cap {\mathcal {I}})}\lambda _{i}^{k}\geq 0$

und setzt man $\lambda _{i}^{k}:=0$ $(i\notin {\mathcal {W}}_{k})$, so erfüllt $x^{k}\in {\mathcal {Z}}_{QP}$ mit den $\lambda _{i}^{k}$ $(i\in ({\mathcal {E}}\cup {\mathcal {I}}))$ offenbar auch die KKT-Bedingungen für Problem $(QP)$ und ist $x^{k}$ daher eine Lösung von $(QP)$.

q.e.d.

Im Fall ${\mathcal {W}}_{k}\cap {\mathcal {I}}=\emptyset$ hat man insbesondere $\lambda _{r}^{k}=+\infty$, so dass man aus Lemma 7.24 folgern kann:

Korollar 7.25

Ist $p^{k}=0$ Lösung des Unterproblems $(WP)_{k}$ und ist ${\mathcal {W}}_{k}\cap {\mathcal {I}}=\emptyset$, so löst $x^{k}$ das Problem $(QP)$.

Es sei nun $p^{k}=0$ Lösung von Problem $(WP)_{k}$. Ist $\lambda _{r}^{k}\geq 0$, so ist eine Lösung des Ausgangsproblems $(QP)$ gefunden. Also müssen wir noch den Fall 3 betrachten, dass $\lambda _{r}^{k}<0$ ist.

Es gibt verschiedene Möglichkeiten, in diesem Fall zu einer Abstiegsrichtung in $x^{k}$ zu kommen, die für alle zu ${\mathcal {W}}_{k}$ gehörenden Restriktionen zulässig bleibt. Das folgende Lemma gibt an, dass eine Lösung des Problems

(7.70) ${\begin{array}{ll}{\text{Minimiere}}&{\frac {1}{2}}p^{T}Qp+(g^{k})^{T}p\\{\text{u. d. N.}}&(a^{i})^{T}p=0\quad (i\in {\mathcal {W}}_{k}\setminus \{r\})\end{array}}$

eine solche liefert, zumindest wenn diese Lösung eindeutig ist (vgl. Lemma 3.12). Diese Vorgehensweise hat gegenüber anderen den Vorteil, dass das zu lösende Unterproblem (7.70) von demselben Typ wie das Unterproblem $(WP)_{k}$ ist.

Lemma 7.26

Es sei $p^{k}=0$ Lösung des Unterproblems $(WP)_{k}$ mit Multiplikatoren $\lambda _{i}^{k}$ und es sei $\lambda _{r}^{k}<0$ für $\lambda _{r}^{k}$ aus (7.65). Ist ${\hat {p}}^{k}$ Lösung des Problems (7.70), dann gilt $(a^{r})^{T}{\hat {p}}^{k}\leq 0$. Ist ${\hat {p}}^{k}$ die einzige Lösung von (7.70), so folgt

(7.71) $(a^{r})^{T}{\hat {p}}^{k}<0,\quad (g^{k})^{T}{\hat {p}}^{k}<0.$

Beweis.

Die Lösung ${\hat {p}}^{k}$ des Problems (7.70) erfüllt mit Multiplikatoren ${\hat {\lambda }}_{i}^{k}$ die zu diesem Problem gehörenden KKT-Bedingungen, d. h., es gilt

(7.72) $Q{\hat {p}}^{k}+g^{k}+\sum _{i\in {\mathcal {W}}_{k}\setminus \{r\}}{\hat {\lambda }}_{i}^{k}a^{i}=0,\quad (a^{i})^{T}{\hat {p}}^{k}=0\quad (i\in {\mathcal {W}}_{k}\setminus \{r\}).$

Ist nun $A_{k}$ die Matrix mit den gemäß (7.62) linear unabhängigen Spalten $a^{i}$ $(i\in {\mathcal {W}}_{k}\setminus \{r\})$ und ist ${\hat {Z}}_{k}$ eine Matrix, deren Spalten eine Basis des Nullraums ${\mathcal {N}}(A_{k})$ von $A_{k}$ bilden, so können wir weiter mit Korollar 7.15 schließen, dass die Matrix ${\hat {Z}}_{k}^{T}Q{\hat {Z}}_{k}$ positiv semidefinit ist. Wegen ${\hat {p}}^{k}\in {\mathcal {N}}(A_{k})$ gibt es ferner ein $p_{Z}$ mit ${\hat {Z}}_{k}p_{Z}={\hat {p}}^{k}$, so dass folgt:

(7.73) $0\leq (p_{Z})^{T}({\hat {Z}}_{k}^{T}Q{\hat {Z}}_{k})p_{Z}=({\hat {p}}^{k})^{T}Q{\hat {p}}^{k}.$

Da $p^{k}=0$ Problem $(WP)_{k}$ löst, folgt aus den Optimalitätsbedingungen (7.64) für $(WP)_{k}$ in Verbindung mit der ersten Gleichung in (7.72)

(7.74) $Q{\hat {p}}^{k}=\sum _{i\in {\mathcal {W}}_{k}\setminus \{r\}}\left(\lambda _{i}^{k}-{\hat {\lambda }}_{i}^{k}\right)a^{i}+\lambda _{r}^{k}a^{r}.$

Multipliziert man diese Gleichung mit ${\hat {p}}^{k}$ und verwendet man die zweite Gleichung in (7.72), so gelangt man zu

(7.75) $({\hat {p}}^{k})^{T}Q{\hat {p}}^{k}=\lambda _{r}^{k}(a^{r})^{T}{\hat {p}}^{k}.$

Aus $\lambda _{r}^{k}<0$ und $({\hat {p}}^{k})^{T}Q{\hat {p}}^{k}\geq 0$ folgt somit $(a^{r})^{T}{\hat {p}}^{k}\leq 0$.

Es sei ${\hat {p}}^{k}$ jetzt die einzige Lösung des Problems (7.70). Nach Korollar 7.15 ist dann die Matrix ${\hat {Z}}_{k}^{T}Q{\hat {Z}}_{k}$ positiv definit. Wäre nun $(a^{r})^{T}{\hat {p}}^{k}=0$, so wäre wegen (7.75) $({\hat {p}}^{k})^{T}Q{\hat {p}}^{k}=0$ und wegen (7.73) $p_{Z}=0$. Aufgrund der linearen Unabhängigkeit der Spalten von ${\hat {Z}}_{k}$ folgte daher ${\hat {p}}^{k}=0$. Letzteres würde jedoch wegen der linearen Unabhängigkeit der $a^{i}$ $(i\in {\mathcal {W}}_{k})$ mit (7.74) $\lambda _{r}^{k}=0$ implizieren, was der Voraussetzung $\lambda _{r}^{k}<0$ widerspricht. Demnach ist

$(a^{r})^{T}{\hat {p}}^{k}<0,\quad ({\hat {p}}^{k})^{T}Q{\hat {p}}^{k}>0.$

Damit liefert schließlich Multiplikation der ersten Gleichung in (7.72) mit ${\hat {p}}^{k}$ und anschließende Verwendung der zweiten Gleichung aus (7.72)

$0<({\hat {p}}^{k})^{T}Q{\hat {p}}^{k}=-(g^{k})^{T}{\hat {p}}^{k}.$

q.e.d.

Setzt man also im Fall 3

$x^{k+1}:=x^{k},\quad {\mathcal {W}}_{k+1}:={\mathcal {W}}_{k}\setminus \{r\},$

so gilt trivialerweise $x^{k+1}\in {\mathcal {Z}}_{QP}$ und ist zumindest dann, wenn $(WP)_{k+1}$ eine eindeutige Lösung $p^{k+1}$ besitzt, gesichert, dass $p^{k+1}$ eine Abstiegsrichtung für $q$ in $x^{k+1}$ ist. Insbesondere ist in diesem Fall also $p^{k+1}\neq 0$ und liegt damit in der $(k+1)$-Iteration wieder der Fall 1 vor.

Das letzte Lemma bleibt richtig, wie dessen Beweis zeigt, wenn der Multiplikator $\lambda _{r}^{k}$ dort ein beliebiger negativer Multiplikator zu $p^{k}$ ist. Die Wahl eines kleinsten Multiplikators ist aber dadurch gerechtfertigt, dass man sich mittels einer Sensitivitätsanalyse klarmachen kann, dass sie zumindest lokal den größten Abstieg des Zielfunktionswertes von $(QP)$ im Verfahren bewirkt. Allerdings kann man für jede Restriktion in $(WP)_{k}$ mit Index $i\in ({\mathcal {W}}_{k}\cap {\mathcal {I}})$ und Multiplikator $\lambda _{i}^{k}<0$ durch eine geeignete Skalierung erreichen, dass zu ihr der kleinste negative Multiplikator gehört. (Es gilt ja $\lambda _{i}^{k}a^{i}=\left(\lambda _{i}^{k}/\beta \right)(\beta a^{i})$ für $\beta \neq 0$.) Deshalb verwendet man in der Praxis manchmal eine kompliziertere Regel zur Auswahl des Multiplikators.

Beschreibung des Verfahrens und Konvergenzsatz: Mit den gewonnenen Ergebnissen können wir das Active-Set-Verfahren vollständig beschreiben:

Algorithmus 7.27 (Active-Set-Verfahren)

(0) Wähle $x^{0}\in {\mathcal {Z}}_{QP}$ und eine Menge ${\mathcal {W}}_{0}$ mit ${\mathcal {E}}\subseteq {\mathcal {W}}_{0}\subseteq {\mathcal {A}}(x^{0})$. Setze $k:=0$.

(1) Berechne eine Lösung $p^{k}$ des Problems

${\begin{array}{lll}(WP)_{k}:&{\text{Minimiere}}&{\frac {1}{2}}p^{T}Qp+(g^{k})^{T}p\\&{\text{u. d. N.}}&(a^{i})^{T}p=0\quad (i\in {\mathcal {W}}_{k}).\end{array}}$

(2) Falls $p^{k}\neq 0$ ist, gehe nach (3).

Falls $p^{k}=0$ und ${\mathcal {W}}_{k}\cap {\mathcal {I}}=\emptyset$ ist, stop! ($x^{k}$ löst Problem $(QP)$.)

Falls $p^{k}=0$ und ${\mathcal {W}}_{k}\cap {\mathcal {I}}\neq \emptyset$ ist, berechne zugehörige Lagrange-Multiplikatoren, d. h., berechne eine Lösung $\lambda _{i}^{k}$ $(i\in {\mathcal {W}}_{k})$ von

(7.76) $\sum _{i\in {\mathcal {W}}_{k}}\lambda _{i}a^{i}=-g^{k}$

und bestimme

$\lambda _{r}^{k}:=\min _{i\in ({\mathcal {W}}_{k}\cap {\mathcal {I}})}\lambda _{i}^{k}.$

Falls $\lambda _{r}^{k}\geq 0$ ist, stop! ($x^{k}$ löst Problem $(QP)$.)

Falls $\lambda _{r}^{k}<0$ ist, setze

${\mathcal {W}}_{k+1}:={\mathcal {W}}_{k}\setminus \{r\},\quad x^{k+1}:=x^{k}$

und gehe nach (4).

(3) Berechne

(7.77) $\beta _{k}:=\min _{i\notin {\mathcal {W}}_{k},(a^{i})^{T}p^{k}>0}{\frac {b_{i}-(a^{i})^{T}x^{k}}{(a^{i})^{T}p^{k}}},\quad \alpha _{k}:=\min\{1,\beta _{k}\}$

und definiere

$x^{k+1}:=x^{k}+\alpha _{k}p^{k}.$

Falls $\beta _{k}>1$ ist, setze ${\mathcal {W}}_{k+1}:={\mathcal {W}}_{k}$.

Falls $\beta _{k}\leq 1$ ist, setze ${\mathcal {W}}_{k+1}:={\mathcal {W}}_{k}\cup \{s\}$ mit einem Index $s$, für den der Minimalwert $\beta _{k}$ in (7.77) angenommen wird.

(4) Setze $k:=k+1$ und gehe nach (1).

Wir beweisen die Konvergenz dieses Verfahrens unter etwas vereinfachenden Voraussetzungen.

Satz 7.28

Es sei $Q$ positiv definit und ${\mathcal {Z}}_{QP}\neq \emptyset$. Weiter seien in Algorithmus 7.27 für alle $k$ die Vektoren $a^{i}$ $(i\in {\mathcal {W}}_{k})$ linear unabhängig und gelte $\alpha _{k}>0$. Dann bricht Algorithmus 7.27 nach endlich vielen Iterationen mit der eindeutigen Lösung von $(QP)$ ab.

Beweis.

Ist $p^{k}=0$ für ein $k$, dann ist $x^{k}$ nach Lemma 7.24 Lösung und wegen der vorausgesetzten positiven Definitheit von $Q$ eindeutige Lösung des Problems (7.67). Wenn $x^{k}$ nicht die Lösung von $(QP)$ ist und damit das Verfahren abbricht, gilt $\lambda _{r}^{k}<0$ und damit ${\mathcal {W}}_{k+1}:={\mathcal {W}}_{k}\setminus \{r\}$ sowie $x^{k+1}:=x^{k}$. Nach Lemma 7.26 ist dann $p^{k+1}:={\hat {p}}^{k}$ Abstiegsrichtung für $q$ und somit insbesondere $p^{k+1}\neq 0$. Da man weiter nach Voraussetzung $\alpha _{k+1}>0$ hat, gilt als Folge der Lemmata 7.22 und 7.26

$q(x^{\ell })\leq q(x^{k+2})<q(x^{k+1})=q(x^{k})$ für alle $\ell \geq k+2$.

Somit kann, wie Lemma 7.24 anzeigt, der Fall $p^{\ell }=0$ mit ${\mathcal {W}}_{\ell }={\mathcal {W}}_{k}$ für $\ell >k$ nicht mehr auftreten, da dann $q(x^{\ell })=q(x^{k})$ wäre.

Wir zeigen als nächstes, dass das Unterproblem $(WP)_{k}$ im Algorithmus spätestens für jede $n$-te Iteration die Lösung 0 haben muss. Wir nehmen dazu $p^{k}\neq 0$ für ein $k$ an. Im Fall $\beta _{k}>1$ ist insbesondere $\alpha _{k}=1$ und damit $x^{k+1}:=x^{k}+p^{k}$ und ${\mathcal {W}}_{k+1}:={\mathcal {W}}_{k}$. Aufgrund der Identität in (7.63) und der Äquivalenz

(7.78) $(a^{i})^{T}p^{k}=0\quad (i\in {\mathcal {W}}_{k})\Leftrightarrow (a^{i})^{T}\left(x^{k}+p^{k}\right)-b_{i}=0\quad (i\in {\mathcal {W}}_{k})$

ist $x^{k+1}$ die eindeutige Lösung des Problems

(7.79) ${\begin{array}{ll}{\text{Minimiere}}&q(x)={\frac {1}{2}}x^{T}Qx+c^{T}x\\{\text{u. d. N.}}&(a^{i})^{T}x-b_{i}=0\quad (i\in {\mathcal {W}}_{k}).\end{array}}$

Wegen ${\mathcal {W}}_{k+1}:={\mathcal {W}}_{k}$ kann man für die Lösung $p^{k+1}$ des Problems $(WP)_{k+1}$ analog schließen, dass $z^{k+1}:=x^{k+1}+p^{k+1}$ ebenfalls eine Lösung von (7.79) und damit $p^{k+1}=0$ ist.

Der Fall $p^{k}\neq 0$ und $\beta _{k}\leq 1$ kann höchstens $n$-mal hintereinander eintreten. Denn in diesem Fall wird die Arbeitsmenge um jeweils einen Index erweitert. Aufgrund der vorausgesetzten linearen Unabhängigkeit der $a^{i}$ $(i\in {\mathcal {W}}_{k})$ besitzt daher das Gleichungssystem $(a^{i})^{T}p=0$ $(i\in {\mathcal {W}}_{k})$ und demzufolge das Unterproblem $(WP)_{k}$ die eindeutige Lösung $p^{k}=0$, sobald ${\mathcal {W}}_{k}$ aus $n$ Elementen besteht.

Also ist nach jeweils spätestens $n$ Schritten $p^{k}=0$. Da weiter anfangs gezeigt wurde, dass der Fall $p^{k}=0$ nur für unterschiedliche Arbeitsmengen möglich ist und da es nur endlich viele solcher Mengen gibt, bricht Algorithmus 7.27 entweder in Schritt (2) des Verfahrens mit der Lösung $x^{k}$ von $(QP)$ ab, bevor auf allen möglichen Arbeitsmengen die Nulllösung erreicht wurde oder es wird nach insgesamt endlich vielen Schritten die Lösung $p^{\ell }=0$ auf der letzten, zuvor noch nicht durchlaufenen Menge ${\mathcal {W}}_{\ell }$ erzielt. Es muss dann $\lambda _{r}^{\ell }\geq 0$ gelten, so dass $x^{\ell }$ die Lösung von $(QP)$ ist (Lemma 7.24). Denn anderenfalls käme man nach spätestens $n$ Schritten zu einer Nulllösung auf einer früheren Arbeitsmenge, was aber, wie bereits gesagt wurde, ausgeschlossen ist.

q.e.d.

Wie im Anschluss an Lemma 7.23 erläutert wurde, kann im Algorithmus 7.27 auch der Fall $\alpha _{k}=0$ auftreten. Es ist daher möglich, dass über mehrere Iterationen hinweg aus der Arbeitsmenge Indizes entfernt und hinzu gefügt werden, ohne dass sich die Iterierte $x^{k}$ verändert. Kehrt dann Algorithmus 7.27 nach endlich vielen Schritten zu derselben Arbeitsmenge zurück, so tritt, ähnlich wie es auch beim Simplexalgorithmus der linearen Optimierung geschehen kann, ein Zyklus auf, aus dem der Algorithmus nicht mehr herauskommt. Letzteres wurde in Satz 7.28 durch die Annahme $\alpha _{k}>0$ für alle $k$ ausgeschlossen. Wie beim Simplexalgorithmus könnte man aber auch eine Strategie in den Algorithmus einbauen, die das Auftreten von Zyklen verhindert. In den meisten Implementierungen wird Letzteres jedoch nicht getan, da unvermeidliche Rundungsfehler auf einem Computer solche Zyklen sehr unwahrscheinlich machen.

Die Durchführung des Verfahrens an einem Beispiel wird als eine Aufgabe gestellt.

Berechnung eines Startpunktes: Ein für das Problem $(QP)$ zulässiger Punkt, welcher als Startpunkt für Algorithmus 7.27 benötigt wird, lässt sich in vielen konkreten Fällen direkt angeben. Wenn dies nicht möglich ist, kann man einen solchen Punkt auf verschiedene Weisen berechnen. So kann man die Phase I des Simplexalgorithmus verwenden, welche für lineare Restriktionen entweder einen zulässigen Punkt liefert oder feststellt, dass es keinen solchen Punkt gibt. In diesem Zusammenhang sei erwähnt, dass die Phase II des Simplexalgorithmus, sofern dieser dem Leser bekannt sein sollte, als ein Active-Set-Verfahren aufgefasst werden kann. Im Unterschied zum Simplexverfahren erzeugen Active-Set-Verfahren für quadratische Optimierungsprobleme aber nicht notwendig Iterierte, die auf dem Rand des zulässigen Gebietes liegen oder Ecken von diesem sind. (Es kann ja sogar der Fall ${\mathcal {W}}_{k}=\emptyset$ eintreten.)

Zur Bestimmung eines Punktes, der für das Problem $(QP)$ zulässig ist, kann man auch das folgende Hilfsproblemin den Variablen $(x,t)\in \mathbb {R} ^{n+1}$ lösen (die Vorgehensweise lässt sich auf allgemeine nichtlineare Optimierungsprobleme ausdehnen):

(7.80) ${\begin{array}{ll}{\text{Minimiere}}&t\\{\text{u. d. N.}}&+\left[(a^{i})^{T}x-b_{i}\right]\leq t\quad (i\in {\mathcal {E}}),\\&-\left[(a^{i})^{T}x-b_{i}\right]\leq t\quad (i\in {\mathcal {E}}),\\&(a^{i})^{T}x-b_{i}\leq t\quad (i\in {\mathcal {I}}),\\&t\geq 0.\end{array}}$

Im Fall ${\mathcal {E}}\neq \emptyset$ kann die Nebenbedingung $t\geq 0$ in diesem Problem gestrichen werden, da dann für jeden Punkt $(x,t)$, der für (7.80) zulässig ist, automatisch $t\geq 0$ gilt. Gibt man sich nun irgendein ${\tilde {x}}$ vor und berechnet man dazu den maximalen Wert $\sigma$ aller Funktionen auf den linken Seiten der Restriktionen, so erhält man offenbar einen für dieses Problem zulässigen Punkt $({\tilde {x}},{\tilde {t}})$, indem man ${\tilde {t}}\geq \max\{0,\sigma \}$ wählt. Insbesondere ist also der zulässige Bereich dieses Problems nichtleer. Da seine Zielfunktion außerdem nach unten durch 0 beschränkt ist, besitzt das Problem (7.80) gemäß Satz 7.1 eine Lösung $({\hat {x}},{\hat {t}})$.

Ist dann weiter ${\hat {t}}>0$, so ist der zulässige Bereich von $(QP)$ offenbar leer. Im Fall ${\hat {t}}=0$ dagegen ist ${\hat {x}}$ ein zulässiger Punkt für $(QP)$. Für ${\mathcal {E}}=\emptyset$ könnte man alternativ auch die Nebenbedingung $t\geq 0$ weglassen und nur so lange mit einem Verfahren iterieren, bis man ein $({\hat {x}},{\hat {t}})$ mit ${\hat {t}}\leq 0$ gefunden hat (oder bis man zu einer Lösung $({\hat {x}},{\hat {t}})$ des Problems mit ${\hat {t}}>0$ gelangt).

Da ja für Problem (7.80) ein zulässiger Punkt $({\tilde {x}},{\tilde {t}})$ sofort angegeben werden kann, kann eine Lösung dieses Problems im Prinzip mit Algorithmus 7.27 bestimmt werden. (Satz 7.28 sichert in diesem Fall aber nicht die Konvergenz des Verfahrens.) Diese Vorgehensweise sowie die Verwendung des Simplexalgorithmus haben aber den Nachteil, dass man zusätzlich ein lineares Problem von derselben Größenordnung wie der des gegebenen Problems $(QP)$ selbst zu lösen hat, ohne dass man dabei dessen Zielfunktion berücksichtigt. Außerdem ist es auch nicht erstrebenswert, das Problem $(QP)$ mit zwei unterschiedlichen Verfahren zu lösen. Aus diesen Gründen ist die im folgenden beschriebene Methode attraktiv, welche man als Modifikation des zuletzt beschriebenen Vorgehens ansehen kann.

Bei der sog. Big-M-Methode löst man für ein hinreichend großes, vorab gewähltes $M$ das folgende Problem in den Variablen $(x,t)$:

${\begin{array}{lll}(QP_{M}):&{\text{Minimiere}}&q_{M}(x,t):={\frac {1}{2}}x^{T}Qx+c^{T}x+Mt\\&{\text{u. d. N.}}&+\left[(a^{i})^{T}x-b_{i}\right]\leq t\quad (i\in {\mathcal {E}}),\\&&-\left[(a^{i})^{T}x-b_{i}\right]\leq t\quad (i\in {\mathcal {E}}),\\&&(a^{i})^{T}x-b_{i}\leq t\quad (i\in {\mathcal {I}}),\\&&t\geq 0.\end{array}}$

Man kann nun zeigen, was als zu bearbeitende Übungsaufgabe gestellt ist: Ist $Q$ positiv semidefinit und besitzt das Problem $(QP)$ eine Lösung $x^{*}$, so gibt es ein $M_{0}\geq 0$, so dass $(x^{*},t^{*})$ mit $t^{*}=0$ für jedes $M\geq M_{0}$ eine Lösung von Problem $(QP_{M})$ ist. Ist weiter $(x^{*},t^{*})$ eine Lösung von Problem $(QP_{M})$ mit $t^{*}=0$, so ist $x^{*}$ eine Lösung von Problem $(QP)$.

Bemerkung 7.29

Setzt man zusätzlich z. B. voraus, dass $Q$ positiv definit und für jede Lösung von $(QP_{M})$ mit $M\geq M_{0}$ die Gradienten der aktiven Nebenbedingungen von $(QP_{M})$ linear unabhängig sind, d. h. dass für jede solche Lösung die LICQ erfüllt ist (siehe den Absatz vor Beispiel 7.19), so besitzt $(QP_{M})$ für alle hinreichend großen $M$ keine Lösung $(x^{*},t^{*})$ mit $t^{*}>0$. (Man hat dafür zu beweisen, dass dann die $x$-Anteile aller Lösungen von $(QP_{M}),M\geq M_{0}$ und damit alle zu diesen Lösungen gehörenden Multiplikatoren für die „$\leq$“-Restriktionen von $(QP_{M})$ beschränkt sind. Wählt man dann $M$ groß genug, so muss der zur Ungleichung $t\geq 0$ gehörende Multiplikator positiv sein und folgt damit aus der Komplementaritätsbedingung $t^{*}=0$.)

Für das Problem $(QP_{M})$ kann man wie für Problem (7.80) einen zulässigen Punkt direkt angeben, so dass Algorithmus 7.27 zu seiner Lösung verwendet werden kann. In der Praxis wird dabei die Konstante $M$ zumeist mittels einer Heuristik gewählt. Man beginnt mit einem beliebigem $M>0$. Hat dann die Variable $t$ in der berechneten Lösung des Problems einen positiven Wert, so löst man das Problemmit einem vergrößerten $M$ erneut, wobei man die zuletzt erzielte Lösung als Startlösung wählen kann. Diese Prozedur setzt man so lange fort, bis $t$ in der Lösung des aktuellen Problems den Wert 0 annimmt.

Bemerkungen und Hinweise: Die durch Algorithmus 7.27 erzeugten Arbeitsmengen und folglich auch die Anzahl der von ihm zur Lösung des Problems benötigten Iterationen können in Abhängigkeit von der Wahl der Startmenge ${\mathcal {W}}_{0}$ zu $x^{0}$ sehr variieren. Sind die $a^{i}$ $(i\in {\mathcal {A}}(x^{0}))$ linear unabhängig, so kann man insbesondere ${\mathcal {W}}_{0}:={\mathcal {A}}(x^{0})$ setzen. Aber selbst in diesem Fall muss die Folge der erzeugten Arbeitsmengen nicht eindeutig sein, da die im Verfahren auftretenden Indizes $r$ und $s$ nicht eindeutig bestimmt sind.

Weiter sei bemerkt: Startet man mit einer Menge ${\mathcal {W}}_{0}$, für welche die Vektoren $a^{i}$ $(i\in {\mathcal {W}}_{0})$, wie im Konvergenzsatz gefordert, linear unabhängig sind, so sind die Vektoren $a^{i}$ $(i\in {\mathcal {W}}_{k})$ für alle $k$ linear unabhängig, wie man sich leicht überlegt:

Aufgabe 7.30

Man zeige für Algorithmus 7.27: Sind die Vektoren $a^{i}$ $(i\in {\mathcal {W}}_{k})$ linear unabhängig, so sind dies auch die Vektoren $a^{i}$ $(i\in {\mathcal {W}}_{k+1})$.

In jeder Iteration des Verfahrens muss ein gleichungsrestringiertes konvexes quadratisches Optimierungsproblem gelöst werden, wobei sich die Anzahl der Nebenbedingungen von einer Iteration zur nächsten höchstens um eine Nebenbedingung verringert oder vergrößert. Ist $A_{k}$ die Matrix, welche die Vektoren $(a^{i})^{T}$ $(i\in {\mathcal {W}}_{k})$ als Zeilen hat, so geht also $A_{k+1}$ aus $A_{k}$ hervor, indem höchstens eine Zeile aus $A_{k}$ gestrichen oder zu $A_{k}$ mit hinzu genommen wird. Folglich ändert sich die KKT-Matrix für das quadratische Unterproblem von einem Schritt zum nächsten maximal nur in einer Zeile und Spalte. Diese Tatsache kann man für die effiziente Lösung der Unterprobleme ausnutzen. Für diesbezügliche Details verweisen wir auf [NoWri06].

Eine schlechte Eigenschaft des Verfahrens ist es, dass in jeder Iteration nur höchstens ein Index neu in die Arbeitsmenge mit aufgenommen wird. Startet man nun mit einem Punkt $x^{0}$, für den keine der Ungleichungsrestriktionen aktiv ist und sind in jeder Lösung des Problems $m$ von diesen aktiv, so benötigt Algorithmus 7.27 mindestens $m$ Iterationen. Diese Zahl erhöht sich noch, wenn im Verlauf des Verfahrens Indizes wieder aus den Arbeitsmengen entfernt werden. Deshalb sollte man Active-Set-Verfahren nur für Probleme kleiner und mittlerer Größe verwenden. Für solche Probleme sind sie laut [NoWri06] im Allgemeinen die effizientesten Verfahren.

Active-Set-Verfahren wurden für die Bestimmung lokaler Minima nichtkonvexer quadratischer Optimierungsprobleme modifiziert (z. B. [NoWri06]). Ferner wurden sie auch auf nichtquadratische Probleme mit linearen Restriktionen übertragen (z.B. [Fle91]). Die zu lösenden Unterprobleme sind dann allerdings ebenfalls linear restringierte Probleme mit einer nichtquadratischen Zielfunktion.

7.5.3 Ein modifiziertes Gradientenprojektionsverfahren

Einführung: Wir wollen ein weiteres Verfahren, ein modifiziertes Gradientenprojektionsverfahren, für die Lösung des allgemeinen quadratischen Optimierungsproblems

${\begin{array}{lll}(QP):&{\text{Minimiere}}&q(x):={\frac {1}{2}}x^{T}Qx+c^{T}x\\&{\text{u. d. N.}}&(a^{i})^{T}x-b_{i}=0\quad (i\in {\mathcal {E}}),\\&&(a^{i})^{T}x-b_{i}=0\quad (i\in {\mathcal {I}})\end{array}}$

diskutieren. Den zulässigen Bereich von $(QP)$ bezeichnen wir wieder mit ${\mathcal {Z}}_{QP}$, wobei wir ${\mathcal {Z}}_{QP}\neq \emptyset$ annehmen. Das Verfahren verlangt abgesehen von der Symmetrie keine weitere Voraussetzung an $Q$ und ist somit auch für nichtkonvexe quadratische Optimierungsprobleme einsetzbar. Die Durchführung des Verfahrens ist allerdings für Probleme mit allgemeinen linearen Restriktionen nicht sinnvoll, weswegen wir es unten nur für einen in der Praxis häufig vorkommenden, speziellen Typ linearer Nebenbedingungen, den von Schrankenbedingungen an die Variablen, vorstellen werden.

Ein bekanntes, im Kurs „Optimierung II“ genauer betrachtetes Verfahren zur unrestringierten Minimierung einer Funktion $f\in C^{1}(\mathbb {R} ^{n})$ ist das Gradientenverfahren. Bei diesem wählt man in einer Iterierten $x^{k}$ mit $\nabla f(x^{k})\neq 0$ die Richtung des steilsten Abstiegs $p^{k}:=-\nabla f(x^{k})$ als Abstiegsrichtung (vgl. Bemerkung 3.10), bestimmt man anschließend eine geeignete Schrittweite $t_{k}$ und setzt man dann $x^{k+1}:=x^{k}+t_{k}p^{k}$. Als zunächst nahe liegende Schrittweite bietet sich dabei die Minimumschrittweite, d. h. die folgende Wahl von $t_{k}$ an:

(7.81) $f(x^{k}+t_{k}p^{k})=\min _{t\geq 0}f(x^{k}+tp^{k}).$

(Wir werden in der „Optimierung II“ zeigen, dass ein solches $t_{k}>0$ existiert.) Das Verfahren bricht man z. B. ab, wenn $\nabla f(x^{k})\neq 0$ bzw. wenn $\left|\nabla f(x^{k})\right|\leq \varepsilon$ für ein vorgegebenes $\varepsilon >0$ ist. Da die Schrittweitenwahl in (7.81) die Bestimmung eines globalen Minimierers einer Funktion in einer Veränderlichen bedeutet, hat man alternativ eine ganze Reihe anderer Schrittweitenstrategien entwickelt. Einige davon sind ebenfalls ein Thema der „Optimierung II“. Das Gradientenverfahren macht in der Praxis häufig über einige Iterationen hinweg ganz gute Fortschritte, kann dann aber unerträglich langsam werden, so dass es in der Praxis heute kaum noch eine Rolle spielt.

Das klassische Gradientenprojektionsverfahren stellt nun eine Verallgemeinerung des Gradientenverfahrens auf linear restringierte Optimierungsprobleme und insbesondere auf Probleme des Typs $(QP)$ dar. Wie beim Active-Set-Verfahren startet man mit einem für das Problem $(QP)$ zulässigen Punkt. In der $k$-ten Iteration liegt dann eine Näherung $x^{k}\in {\mathcal {Z}}_{QP}$ vor, von der aus man in Richtung des steilsten Abstiegs $-\nabla q(x^{k})$ fortschreitet, sofern $x^{k}$ nicht bereits ein KKT-Punkt von $(QP)$ ist. Um Zulässigkeit der Iterierten zu bewahren, „projiziert“ man als nächstes den Strahl $x^{k}-t\nabla q(x^{k}),t\geq 0$ auf die zulässige Menge ${\mathcal {Z}}_{QP}$. Bezüglich dieses auf ${\mathcal {Z}}_{QP}$ projizierten Strahls sucht man nun den kleinsten positiven lokalen Minimierer $x_{c}^{k}$ von $q$, den sog. Cauchy-Punkt.

Zur Berechnung dieses Punktes hat man die kleinste positive lokale Lösung eines eindimensionalen quadratischen Optimierungsproblems in der Variablen $t$ zu bestimmen. Wir werden zeigen, dass man diese Lösung für Schrankennebenbedingungen mit wenig Aufwand explizit ausrechnen kann. Beim klassischen Gradientenprojektionsverfahren setzt man anschließend $x^{k+1}:=x_{c}^{k}$ (z. B. [Ber95], [Gei-Ka02]). Da dieses Verfahren im unrestringierten Fall genau dem Gradientenverfahren mit der Minimumschrittweitenregel (7.81) entspricht, kann es aber ein ähnlich schlechtes Konvergenzverhalten wie dieses aufweisen.

Daher variiert man das klassische Verfahren, indem man den Cauchy-Punkt nur insoweit verwendet, als man mit den für ihn aktiven Indizes, ähnlich wie beim Active-Set-Verfahren, eine aktuelle Arbeitsmenge von Indizes festlegt. Anders als beim Active-Set-Verfahren muss man nun aber das zugehörige gleichungsrestringierte quadratische Optimierungsproblem nicht vollständig lösen. Da die Konvergenz des klassischen Gradientenprojektionsverfahrens, also des Verfahrens für die Wahl $x^{k+1}:=x_{c}^{k}$, unter relativ schwachen Voraussetzungen gesichert ist, genügt es, als nächste Iterierte einen für $(QP)$ zulässigen Punkt zu bestimmen, in dem der Funktionswert von $q$ zumindest nicht größer als der im Cauchy-Punkt ist. Für die Bestimmung eines solchen Punktes gibt es verschiedene Möglichkeiten, die wir hier nur andeuten und nicht ausformulieren können.

Die durch ein derartiges modifiziertes Gradientenprojektionsverfahren erzeugten Arbeitsmengen streben im Allgemeinen sehr viel schneller gegen die Menge der aktiven Indizes in einer Lösung des Problems als es die Arbeitsmengen bei einem Active-Set-Verfahren tun. Solche Projektionsverfahren haben sich daher als sehr effiziente Verfahren für die Lösung großer quadratischer Optimierungsprobleme insbesondere mit Schrankennebenbedingungen erwiesen.

Berechnung der Projektion: Für einen gegebenen Vektor $z\in \mathbb {R} ^{n}$ und eine nichtleere, abgeschlossene konvexe Menge $M\subseteq \mathbb {R} ^{n}$ bezeichnet man die nach Satz 2.41 existierende eindeutige Lösung ${\hat {x}}\in M$ des quadratischen Optimierungsproblems

(7.82) $\min _{x\in M}\|z-x\|^{2}$

als Projektion von $z$ auf $M$. Die Projektion von $z$ auf $M$ ist also derjenige Vektor ${\hat {x}}\in M$, der $z$ in der Menge $M$ am nächsten liegt.

Insbesondere ist der zulässige Bereich $M:={\mathcal {Z}}_{QP}$ von $(QP)$ eine abgeschlossene, konvexe und nach Voraussetzung auch nichtleere Menge. Der numerische Aufwand zur Lösung des Problems (7.82) für die Menge $M:={\mathcal {Z}}_{QP}$ kann aber bei allgemeinen linearen Nebenbedingungen so groß wie der zur Lösung von $(QP)$ selbst sein. Deshalb sollte man Projektionsverfahren nur auf solche Probleme anwenden, für welche die benötigte Projektion einfach zu berechnen ist. Dies ist hier z. B. der Fall, wenn das quadratische Problem nur Schrankenrestriktionen des Typs

$\ell _{i}\leq x_{i}\leq u_{i}\quad (i=1,\ldots ,n)$

aufweist („box constraints“). Dabei sind $\ell _{i}$ und $u_{i}$ reelle Zahlen mit $\ell _{i}\leq u_{i}$ und sind $\ell _{i}:=-\infty$ und $u_{i}:=+\infty$ zugelassen.

Wir betrachten daher ab jetzt nur das quadratische Optimierungsproblem mit Schrankennebenbedingungen

${\begin{array}{lll}(QP_{SN}):&{\text{Minimiere}}&q(x):={\frac {1}{2}}x^{T}Qx+c^{T}x\\&{\text{u. d. N.}}&\ell _{i}\leq x_{i}\leq u_{i}\quad (i=1,\ldots ,n).\end{array}}$

Seinen zulässigen Bereich bezeichnen wir mit

${\mathcal {Z}}_{SN}:=\{x\in \mathbb {R} ^{n}{\big |}\ell \leq x\leq u\},$

wobei $\ell ,u\in \mathbb {R} ^{n}$ die Vektoren sind, welche die Komponenten $\ell _{i}$ und $u_{i}$ haben. Da $\ell _{i}\leq u_{i}$ für alle $i$ vorausgesetzt wurde, gilt ${\mathcal {Z}}_{SN}\neq \emptyset$.

Probleme des Typs $(QP_{SN})$ muss man z. B. als Unterprobleme bei einem sog. Trust-Region-Verfahren lösen, wie es in der Vorlesung „Optimierung II“ vorgestellt werden wird. Weiter beachte man, dass jedes linear restringierte, quadratische Optimierungsproblem als ein Problem formuliert werden kann, das nur lineare Ungleichungen als Nebenbedingungen hat und dass sich ein solches Problem, wenn $Q$ positiv definit ist, lösen lässt, indem man eine Lösung des zugehörigen dualen Problems, das vom Typ $(QP_{SN})$ ist, bestimmt (vgl. die Probleme $({\overline {QP}})$ und $({\overline {QD}})'$ in Abschnitt 7.2.4). Im Prinzip lässt sich also jedes quadratische Optimierungsproblem mit gleichmäßig konvexer Zielfunktion dadurch lösen, dass man eine Lösung eines schrankenrestringierten quadratischen Optimierungsproblems berechnet. Allerdings macht eine solche Vorgehensweise nur dann Sinn, wenn die Berechnung der Matrizen $Q^{-1}$ und $AQ^{-1}A^{T}$ nicht zu viele Rechenoperationen erfordert (siehe Abschnitt 7.2.4 für die Details).

Das Problem (7.82) lautet nun für $M:={\mathcal {Z}}_{SN}$

(7.83) ${\begin{array}{ll}{\text{Minimiere}}&\sum \limits _{i=1}^{n}(z_{i}-x_{i})^{2}\\{\text{u. d. N.}}&\ell _{i}\leq x_{i}\leq u_{i}\quad (i=1,\ldots ,n).\end{array}}$

Seine eindeutige Lösung, die Projektion von $z$ auf ${\mathcal {Z}}_{SN}$, bezeichnen wir mit $P(z)$. Die Zielfunktion von (7.83) ist offenbar separierbar, d. h. sie wird minimal, wenn jeder ihrer Summanden minimal wird. Somit ergibt sich sofort

(7.84) $P(z)_{i}={\begin{cases}\ell _{i},&{\text{falls }}z_{i}<\ell _{i},\\z_{i},&{\text{falls }}\ell _{i}\leq z_{i}\leq u_{i},\\u_{i},&{\text{falls }}u_{i}<z_{i}.\end{cases}}$

Es sei nun $z$ ein für $(QP_{SN})$ zulässiger Punkt, d. h. $z\in {\mathcal {Z}}_{SN}$ und es sei

$g:=\nabla q(z).$

(Im Verfahren unten ist $z:=x^{k}$ die aktuelle Iterierte.) Im Hinblick auf die Minimierung von $q$ bietet es sich an, wie beim Gradientenverfahren den von $z$ ausgehenden Strahl in Richtung des steilsten Abstiegs, d. h. $z-tg$ für $t\geq 0$ zu betrachten und dann auf diesem Strahl einen Punkt $z-t^{*}g$ mit einer geeigneten Schrittweite $t^{*}$ zu bestimmen, für den $q(z-t^{*}g)\leq q(z)$ gilt und der wieder zulässig für das Problem $(QP_{SN})$ ist.

Es liegt somit nahe, für $t\geq 0$ zunächst die Projektion

$x(t):=P(z-tg)$

von $z-tg$ auf den zulässigen Bereich ${\mathcal {Z}}_{SN}$ von $(QP_{SN})$ zu bestimmen. Gemäß (7.84) ist diese gegeben durch

(7.85) $x(t)_{i}=P(z-tg)_{i}={\begin{cases}\ell _{i},&{\text{falls }}z_{i}-tg_{i}<\ell _{i},\\z_{i}-tg_{i},&{\text{falls }}\ell _{i}\leq z_{i}-tg_{i}\leq u_{i},\\u_{i},&{\text{falls }}u_{i}<z_{i}-tg_{i}.\end{cases}}$

Wie deutlich werden wird, beschreibt $x(t)$ für $t\geq 0$ einen stückweise linearen Pfad in ${\mathcal {Z}}_{SN}$. Zur Bestimmung einer geeigneten Schrittweite berechnet man anschließend eine Lösung des einparametrischen, stückweise quadratischen Optimierungsproblems

(7.86) $\inf _{t\geq 0}^{}q(x(t)).$

Den kleinsten lokalen Minimierer $t^{*}$ dieses Problems bezeichnet man als Cauchy-Punkt. Diesen Punkt kann man leicht berechnen, wie wir als nächstes zeigen werden.

Man beachte in diesem Zusammenhang, dass für $t>0$

$\|z-tg-x\|=\|-tg-(x-z)\|$

gilt. Die Bestimmung der Projektion von $z-tg$ auf ${\mathcal {Z}}_{SN}$ entspricht somit der Bestimmung der Projektion des skalierten Gradienten $-tg$ auf die Menge

$-z+{\mathcal {Z}}_{SN}=\{x\in \mathbb {R} ^{n}{\big |}\ell -z\leq x\leq u-z\}.$

Dies erklärt den Namen „Gradientenprojektionsverfahren“ für das hier beschriebene Verfahren.

Berechnung des Cauchy-Punktes: Es sei nun $z\in {\mathcal {Z}}_{SN}$ und damit $\ell _{i}\leq z_{i}\leq u_{i}$ für alle $i$. Zunächst wollen die Projektion $x(t)$ von $z-tg$ auf die Menge ${\mathcal {Z}}_{SN}$ für $t\geq 0$ genauer analysieren.

Die Komponente $z_{i}-tg_{i}$ des Vektors $z-tg$ erreicht offenbar mit wachsendem $t\geq 0$ für ein ${\tilde {t}}_{i}\geq 0$ den Rand von ${\mathcal {Z}}_{SN}$. Und zwar erreicht $z_{i}-tg_{i}$ für ${\tilde {t}}_{i}$ die untere Schranke $\ell _{i}$, wenn $g_{i}>0$ ist und die obere Schranke $u_{i}$, wenn $g_{i}<0$ ist. Dabei gilt ${\tilde {t}}_{i}=+\infty$, wenn $\ell _{i}=-\infty$ oder $u_{i}=+\infty$ oder wenn $g_{i}=0$ ist. Dieses ${\tilde {t}}_{i}$ ist somit gegeben durch

(7.87) ${\tilde {t}}_{i}={\begin{cases}(u_{i}-z_{i})/(-g_{i}),&{\text{falls }}g_{i}<0{\text{ und }}u_{i}<\infty {\text{ ist}},\\(z_{i}-\ell _{i})/g_{i},&{\text{falls }}g_{i}>0{\text{ und }}\ell _{i}>-\infty {\text{ ist}},\\+\infty &{\text{sonst}}.\end{cases}}$

Je nachdem, ob für ${\tilde {t}}_{i}$ die Schranke $\ell _{i}$ oder $u_{i}$ erreicht wird, ob also

$z_{i}-{\tilde {t}}_{i}g_{i}=\ell _{i}$ oder $z_{i}-{\tilde {t}}_{i}g_{i}=u_{i}$

gilt, ist dann gemäß (7.85) für alle $t>{\tilde {t}}_{i}$ entweder

$x(t)_{i}=\ell _{i}$ oder $x(t)_{i}=u_{i}$.

Zusammengefasst folgt also und zwar auch im Fall ${\tilde {t}}_{i}=+\infty$,

(7.88) $x(t)_{i}={\begin{cases}z_{i}-tg_{i},&{\text{falls }}t\leq {\tilde {t}}_{i},\\z_{i}-{\tilde {t}}_{i}g_{i},&{\text{falls }}t\geq {\tilde {t}}_{i}.\end{cases}}$

Dieses Ergebnis ist anschaulich klar: eine Komponente $x(t)_{i}$ von $x(t)$ bewegt sich mit wachsendem $t$ von $z$ aus in Richtung des steilsten Abstiegs auf die Schranken $\ell _{i}$ und $u_{i}$ zu und sie bleibt konstant, sobald sie diese Schranke erreicht hat.

Die in ${\mathcal {Z}}_{SN}$ liegende Kurve $x(t),t\geq 0$ ist somit stückweise linear. Denn folgt man dem Strahl $z-tg$ für wachsendes $t\geq 0$, so liegt $z-tg$ zum „ersten Mal“ auf dem Rand von ${\mathcal {Z}}_{SN}$, wenn $t$ den Wert

${\tilde {t}}:=\inf _{i=1,\ldots ,n}{\tilde {t}}_{i}$

annimmt. Dabei ist ${\tilde {t}}=+\infty$, wenn ${\tilde {t}}_{i}=+\infty$ für alle $i$ gilt, und ist ${\tilde {t}}=0$, wenn $z$ selbst sich schon auf dem Rand von ${\mathcal {Z}}_{SN}$ befindet.

Ist ${\tilde {t}}<+\infty$, so werden dann für alle $t\geq {\tilde {t}}$ die Komponenten $z_{i}-tg_{i}$ von $z-tg$, für die ${\tilde {t}}_{i}={\tilde {t}}$ ist, entsprechend der erreichten Schranke konstant gehalten. (Es können ja mehrere solcher Komponenten den Rand von ${\mathcal {Z}}_{SN}$ gleichzeitig erreichen.) Dem so „geknickten Strahl“ $z-tg$ folgt man nun von ${\tilde {t}}$ aus mit wachsendem $t$ bis zu dem nächst größeren ${\tilde {t}}_{i}$, für welches eine oder mehrere weitere Komponenten von $z-tg$ auf den Rand von ${\mathcal {Z}}_{SN}$ stoßen, usw. Die Kurve $x(t),t\geq 0$, welche durch die Projektion des Strahls $z-tg,t\geq 0$ auf ${\mathcal {Z}}_{SN}$ entsteht, ist somit eine stückweise lineare Kurve.

Es gibt also ein Intervall oder mehrere Intervalle $[t_{j-1},t_{j}]$, so dass $x(\cdot )$ in dem Intervall $[t_{j-1},t_{j}]$ eine lineare Funktion ist. Dabei gewinnt man diese $t_{j}$ von den $n$ in (7.87) definierten ${\tilde {t}}_{i}$ so, dass man diejenigen der ${\tilde {t}}_{i}$ entfernt, welche identisch 0 sind oder denselben Wert wie ein ${\tilde {t}}_{i}$ mit kleinerem Index haben und indem man die $\nu \leq n$ verbleibenden Werte der ${\tilde {t}}_{i}$ der Größe nach sortiert. Auf diese Weise erhält man dann

$0=:t_{0}<t_{1}<t_{2}<\ldots <t_{\nu },$

wobei $t_{\nu }=\infty$ möglich ist. Den Fall ${\tilde {t}}_{i}=0$ für alle $i$ können wir ignorieren, da dann Multiplikatoren existieren, so dass $z$ mit diesen Multiplikatoren die KKT-Bedingungen von $(QP_{SN})$ erfüllt:

Aufgabe 7.31

Man zeige: Ist ${\tilde {t}}_{i}=0$ $(i=1,\ldots ,n)$ für ${\tilde {t}}_{i}$ aus (7.87), so ist $z\in {\mathcal {Z}}_{SN}$ ein KKT-Punkt des Problems $(QP_{SN})$.

Um den Cauchy-Punkt zu ermitteln (vgl. (7.86)), untersuchen wir nun $q(x(\cdot ))$ der Reihe nach auf den Intervallen $[0,t_{1}],[t_{1},t_{2}],\ldots ,[t_{\nu -1},t_{\nu }]$, auf denen $x(\cdot )$ eine lineare Funktion ist. Es sei dazu angenommen, dass wir dies bereits bis zum Intervall $[t_{j-2},t_{j-1}]$ getan und dabei festgestellt hätten, dass der Cauchy-Punkt für einen Wert $t\geq t_{j-1}$ angenommen wird. Da der Cauchy-Punkt per Definition der kleinste lokale Minimierer von $q(x(\cdot ))$ ist, muss demzufolge $q(x(\cdot ))$ auf dem gesamten Intervall $[0,t_{j-1}]$ streng monoton fallend sein.

Für alle $t\in [t_{j-1},t_{j}]$ wollen wir zunächst $x(t)$ als Summe von $x(t_{j-1})$ und einem Korrekturvektor ausdrücken. Gemäß (7.88) gilt offenbar

$x(t_{j-1})_{i}={\begin{cases}z_{i}-t_{j-1}g_{i},&{\text{falls }}t_{j-1}\leq {\tilde {t}}_{i},\\z_{i}-{\tilde {t}}_{i}g_{i},&{\text{falls }}t_{j-1}\geq {\tilde {t}}_{i}\end{cases}}$

sowie

$x(t)_{i}={\begin{cases}z_{i}-t_{j-1}g_{i}+(t-t_{j-1})(-g_{i}),&{\text{falls }}t\leq {\tilde {t}}_{i},\\z_{i}-{\tilde {t}}_{i}g_{i},&{\text{falls }}t\geq {\tilde {t}}_{i}.\end{cases}}$

Man berücksichtige nun, dass der Fall „$t_{j-1}<{\tilde {t}}_{i}$“ aufgrund der Definition der $t_{j}$ mittels der ${\tilde {t}}_{i}$ zunächst $t_{j}\leq {\tilde {t}}_{i}$ und somit für $t\in [t_{j-1},t_{j}]$ auch $t\leq {\tilde {t}}_{i}$ nach sich zieht. Ähnlich können wir im Fall „$t_{j-1}\geq {\tilde {t}}_{i}$“ schließen, dass für alle $t\in [t_{j-1},t_{j}]$ die Beziehung $t\geq {\tilde {t}}_{i}$ gilt. So können wir $x(\cdot )$ auf dem Intervall $[t_{j-1},t_{j}]$ mit

$\Delta t:=t-t_{j-1},\quad \Delta t\in [0,t_{j}-t_{j-1}]$

und

(7.89) $p_{i}^{j-1}:={\begin{cases}-g_{i},&{\text{falls }}t_{j-1}<{\tilde {t}}_{i},\\0,&{\text{falls }}t_{j-1}\geq {\tilde {t}}_{i}\end{cases}}$

in der Form schreiben:

$x(t)=x(t_{j-1})+\Delta t\cdot p^{j-1},\quad t\in [t_{j-1},t_{j}].$

Damit erhalten wir weiter für $q(x(\cdot ))$ auf $[t_{j-1},t_{j}]$ die Darstellung

$q(x(t))={\frac {1}{2}}[x(t_{j-1})+\Delta t\cdot p^{j-1}]^{T}Q[x(t_{j-1})+\Delta t\cdot p^{j-1}]+c^{T}[x(t_{j-1})+\Delta t\cdot p^{j-1}]={\frac {1}{2}}\alpha _{j-1}(\Delta t)^{2}+\beta _{j-1}\Delta t+\gamma _{j-1}=:{\hat {q}}_{j}(\Delta t)$

mit $\Delta t\in [0,t_{j}-t_{j-1}]$ und

$\alpha _{j-1}:=(p^{j-1})^{T}Qp^{j-1},\quad \beta _{j-1}:=x(t_{j-1})^{T}Qp^{j-1}+c^{T}p^{j-1},$

$\gamma _{j-1}:={\frac {1}{2}}x(t_{j-1})^{T}Qx(t_{j-1})+c^{T}x(t_{j-1}).$

Differentiation von ${\hat {q}}_{j}(\Delta t)$ nach $\Delta t$ und anschließende Nullsetzung liefert weiter im Fall $\alpha _{j-1}\neq 0::<math>\alpha _{j-1}\Delta t^{*}+\beta _{j-1}=0\Leftrightarrow \Delta t^{*}=-{\frac {\beta _{j-1}}{\alpha _{j-1}}}.$

Ist $\Delta t^{*}\in [0,t_{j}-t_{j-1}]$ und $\alpha _{j-1}>0$, so können wir schließen, dass $q(x(\cdot ))$ ein lokales Minimum bei $t^{*}:=t_{j-1}+\Delta t^{*}$ annimmt. Ist ${\hat {q}}'(0)=\beta _{j-1}>0$, dann ändert die Ableitung von $q(x(\cdot ))$ bei $t_{j-1}$ ihr Vorzeichen und hat $q(x(\cdot ))$ somit einen lokalen Minimalpunkt bei $t^{*}:=t_{j-1}$. In den anderen Fällen ist $q(x(\cdot ))$ auf $[t_{j-1},t_{j}]$ und demzufolge auf $[0,t_{j}]$ streng monoton fallend.

Ist dann $j=\nu$ und $t_{j}=t_{\nu }=+\infty$, so ist $q(x(\cdot ))$ demnach auf $[0,\infty )$ streng monoton fallend. Ist andererseits $t_{j}$ endlich, was für jeden Index $j<\nu$ immer gegeben ist, so hat dann $q(x(\cdot ))$ bei $t^{*}:=t_{j}$ einen lokalen Minimalpunkt und geht man im Fall $j<\nu$ zum nächsten Intervall $[t_{j},t_{j+1}]$ über. Insbesondere muss in letzterer Situation die neue Richtung $p^{j}$ mittels (7.89) bestimmt werden. Da sich $p^{j}$ von $p^{j-1}$ häufig nur in einer Komponente unterscheidet, kann man manchmal Rechenzeit sparen, wenn man die Koeffizienten des neuen Polynoms ${\hat {q}}_{j+1}$ durch eine geeignete Aufdatierung aus denen für ${\hat {q}}_{j}$ gewinnt.

Die beschriebene Vorgehensweise liefert also entweder ein (endliches) $t^{*}$ und damit den gesuchten Cauchy-Punkt oder sie ergibt, dass $q$ auf der zulässigen Menge von $(QP_{SN})$ nach unten unbeschränkt ist und das Problem $(QP_{SN})$ somit keine Lösung besitzt.

Das Verfahren: Es sei nun $x_{c}:=x(t^{*})$ der berechnete Cauchy-Punkt von $q$. Beim (klassischen) Gradientenprojektionsverfahren wählt man nun $x^{k+1}:=x_{c}$ und verfährt man weiter mit $x^{k+1}$ in derselben Weise wie mit $x^{k}$. Dieses Verfahren stimmt im unrestringierten Fall genau mit dem Gradientenverfahren überein, wenn dieses mit der entsprechenden Minimumschrittweitenregel versehen wird. Deshalb ist es nicht überraschend, dass für das Gradientenprojektionsverfahren, ähnlich wie für das Gradientenverfahren, unter schwachen Voraussetzungen globale Konvergenz bewiesen werden kann (siehe z. B. [Ber95] und [GeiKa02], wo eine sog. Armijo-Schrittweitenregel für $q(x(\cdot ))$ benutzt wird und beachte, dass alle $x^{k}$ z. B. dann in einer kompakten Menge liegen, wenn ${\mathcal {Z}}_{SN}$ beschränkt ist). Ferner kann damit natürlich das Gradientenprojektionsverfahren wie das Gradientenverfahren im Einzelfall extrem langsam konvergieren.

Aus letzterem Grund modifiziert man die klassische Vorgehensweise wie folgt, wobei

${\mathcal {A}}(x_{c}):=\{i\in \{1,\ldots ,n\}{\big |}(x_{c})_{i}=\ell _{i}{\text{ oder }}(x_{c})_{i}=u_{i}\}$

die Menge der in $x_{c}$ aktiven Indizes für $(QP_{SN})$ sei. Um zu einer neuen Iterierten zu gelangen, betrachtet man das quadratische Optimierungsproblem

(7.90) ${\begin{array}{ll}{\text{Minimiere}}&q(x):={\frac {1}{2}}x^{T}Qx+c^{T}x\\{\text{u. d. N.}}&x_{i}=(x_{c})_{i}\quad (i\in {\mathcal {A}}(x_{c})),\\&\ell _{i}\leq x_{i}\leq u_{i}\quad (i\notin {\mathcal {A}}(x_{c})).\end{array}}$

Die Lösung dieses Problems kann genauso schwierig sein wie die des Ausgangsproblems $(QP_{SN})$, so dass es nicht sinnvoll ist, dieses Problem vollständig zu lösen. Eine „exakte“ Lösung ist auch gar nicht erforderlich. Wie man aufgrund der für das klassische Gradientenprojektionsverfahren garantierten Konvergenz vermuten kann, genügt es im Hinblick auf die Sicherstellung der globalen Konvergenz, einen Punkt $x^{+}$ zu finden, welcher die Nebenbedingungen in (7.90) und damit auch die in $(QP_{SN})$ erfüllt und für den $q(x^{+})\leq q(x_{c})$ gilt.

Eine Strategie, die man als einen Kompromiss zwischen der Wahl $x^{+}:=x_{c}$ und einer vollständigen Lösung von Problem (7.90) interpretieren kann, ist es, die Ungleichungen in (7.90) zunächst zu ignorieren und das verbleibende gleichungsrestringierte Problem wenigstens teilweise zu lösen. Da die zu den Gleichungsrestriktionen gehörende Matrix die Zeilen $(e^{i})^{T}$ $(i\in {\mathcal {A}}(x_{c}))$ hat und somit zu ihr sofort eine Nullraummatrix $Z$ angegeben werden kann, bietet es sich an, für die Minimierung der zugehörigen reduzierten quadratischen Funktion ${\hat {q}}$ aus (7.38) ein sog. CG-Verfahren mit Startpunkt $x_{c}$ anzuwenden („CG“ steht für „Conjugate Gradient“, siehe „Optimierung II“). Im Fall, dass $Z^{T}QZ$ positiv definit ist, entspricht dieses Vorgehen für das gleichungsrestringierte Problem der Nullraum-Methode aus Abschnitt 7.4.2. Zur gleichzeitigen Einhaltung der Ungleichungsrestriktionen in (7.90) hat man nun weiter CG-Verfahren so variiert, dass man damit zwar das Problem (7.90) im Allgemeinen nicht löst, aber zumindest einen Punkt $x^{+}$ erhält, der die gewünschten Eigenschaften besitzt. Ein solches modifiziertes CG-Verfahren ist das Verfahren von Steihaug, für dessen Details wir z. B. auf [NoWri06] oder [SuYu06] verweisen.

Zusammengefasst erhalten wir also den folgenden, im Detail nicht ausformulierten Algorithmus. Da wir für die Zielfunktion $q$ des Problems $(QP_{SN})$ keine Konvexität vorausgesetzt haben, kann dieser nur einen Punkt finden, in dem die notwendigen Optimalitätsbedingungen erster Ordnung für $(QP_{SN})$ erfüllt sind.

Algorithmus 7.32 (Modifiziertes Gradientenprojektionsverfahren)

(0) Wähle $x^{0}\in {\mathcal {Z}}_{SN}$. Setze $k:=0$.

(1) Falls $x^{k}$ ein KKT-Punkt für $(QP_{SN})$ ist, stop!

(2) Zu $z:=x^{k}$ bestimme den Cauchy-Punkt $x_{c}^{k}$ gemäß der oben beschriebenen Vorgehensweise.

(3) Bestimme mit $x_{c}^{k}$ als Startpunkt einen Punkt $x^{k+1}\in {\mathcal {Z}}_{SN}$, für den

$q(x^{k+1})\leq q(x_{c}^{k})$

gilt. Tue dies z. B. mit dem Steihaug-Verfahren für das gleichungsrestringierte quadratische Optimierungsproblem

(7.91) ${\begin{array}{ll}{\text{Minimiere}}&q(x):={\frac {1}{2}}x^{T}Qx+c^{T}x\\{\text{u. d. N.}}&x_{i}=(x_{c}^{k})_{i}\quad (i\in {\mathcal {A}}(x_{c})).\end{array}}$

(4) Setze $k:=k+1$ und gehe nach (1).

Für Aussagen zur Konvergenz dieses Verfahrens verweisen wir auf die Arbeit [CGT88b], welche sich auf die allgemeine Theorie in [CGT88a] bezieht (setze dort $f(x):=q(x)$ und $\Delta _{k}:=+\infty$ und beachte, dass in diesem Fall $\rho _{k}=1$ ist). Für den Fall, dass die strikte Komplementaritätsbedingung in KKT-Punkten von $(QP_{SN})$ erfüllt ist, kann man zeigen, dass sich die Arbeitsmenge ${\mathcal {A}}(x_{c}^{k})$ nach endlich vielen Schritten nicht mehr ändert und dass dann das Problem $(QP_{SN})$ wie ein unrestringiertes Problem behandelt werden kann. Im degenerierten Fall können Zyklen bezüglich der aktiven Mengen ${\mathcal {A}}(x_{c}^{k})$ auftreten. In der Literatur findet man aber verschiedene Vorgehensweisen, wie man solche vermeiden kann.