Benutzer:Stepri2005/Kurs:Optimierung/Grundlagen

In den Abschnitten 2.1-2.4 werden grundlegende Aussagen über Vektor- und Matrixnormen zusammengestellt, wie sie z. B. auch in der Numerischen Mathematik 1 vermittelt werden. Matrixnormen werden in diesem Manuskript zur Optimierung 1 aber nur am Rande benötigt. So wird der Einfluss der Größe der Konditionen der in einem Problem vorkommenden Matrizen auf dessen numerische Lösung nur am Rande angesprochen (s. Abschnitt 7.3).

2.1 Normen

Die Größe einer reellen Zahl und damit den Abstand zweier reeller Zahlen misst man bekanntlich mit dem Betrag. In der Mathematik ist es häufig auch erforderlich, den „Abstand“ zweier Vektoren, Matrizen, Funktionen, usw. zu beschreiben. Welchen „Abstand“ hat aber beispielsweise eine gegebene Matrix von einer Matrix, die in Bezug auf diese leicht gestört ist?

Man benötigt also einen geeigneten Abstandsbegriff auf dem entsprechenden Vektorraum, der bestimmten Grundregeln genügen sollte, wie man sie vom Rechnen mit dem Betrag reeller Zahlen her kennt. Einen solchen Abstandsbegriff für einen beliebigen Vektorraum ${\mathcal {V}}$ über $\mathbb {R}$ liefert die folgende, bereits aus der Numerischen Mathematik bekannte Definition einer Norm. Es sei dabei

$\mathbb {R} _{+}:=\{x\in \mathbb {R} |x\geq 0\}.$

Definition 2.1

Eine Abbildung $\|\cdot \|:{\mathcal {V}}\to \mathbb {R} _{+}$ heißt Norm (auf ${\mathcal {V}}$), falls Folgendes gilt:

(i) $\|x\|=0\Leftrightarrow x=0,\quad x\in {\mathcal {V}},$

(ii) $\|\alpha x\|=|\alpha |\|x\|,\quad x\in {\mathcal {V}},\quad \alpha \in \mathbb {R}$ (Positive Homogenität),

(iii) $\|x+y\|\leq \|x\|+\|y\|,\quad x,y\in {\mathcal {V}}$ (Dreiecksungleichung).

Aus den Normgesetzen leitet man die Beziehung

(2.1) $|\|x\|-\|y\||\leq \|x-y\|,\quad x,y\in {\mathcal {V}}$

ab. Einen Vektorraum ${\mathcal {V}}$, auf dem eine Norm $\|\cdot \|$ definiert ist, bezeichnet man als einen normierten Vektorraum. Die Konvergenz einer Folge von Vektoren in einem solchen Raum wird folgendermaßen definiert. (Vektoren einer Folge indizieren wir mit einem hochgestellten und Zahlen einer Folge mit einem tiefgestellten Index. Es heißt also z. B. $x^{k}\in \mathbb {R} ^{n}$ und $t_{k}\in \mathbb {R}$.)

Definition 2.2

Es sei $\|\cdot \|$ eine Norm auf ${\mathcal {V}}$. Eine Folge $\left\{x^{k}\right\}$ von Vektoren $x^{k}\in {\mathcal {V}}$ konvergiert gegen $x\in {\mathcal {V}}$, kurz

$\lim _{k\to \infty }x^{k}=x,$

wenn gilt:

$\lim _{k\to \infty }\left\|x^{k}-x\right\|=0.$

Unter Verwendung der Ungleichung in (2.1) schließt man damit:

Korollar 2.3

Eine Norm $\|\cdot \|:{\mathcal {V}}\to \mathbb {R} _{+}$ ist eine stetige Abbildung, d. h., es gilt

$\lim _{k\to \infty }x^{k}=x\Rightarrow \lim _{k\to \infty }\left\|x^{k}\right\|=\|x\|,\quad x,x^{k}\in {\mathcal {V}}.$

Eine auf ${\mathcal {V}}:=\mathbb {R} ^{n}$ definierte Norm bezeichnet man als Vektornorm und eine auf dem Raum ${\mathcal {V}}:=\mathbb {R} ^{n\times n}$ aller reellen $(n\times n)$-Matrizen definierte Norm als Matrixnorm. In der Praxis können je nach Zusammenhang unterschiedliche Normen für einen Vektorraum sinnvoll oder praktisch leichter handhabbar sein. Die drei gebräuchlichsten Vektornormen sind die Euklidische oder $l_{2}$-Norm

(2.2) $\|x\|_{2}:=\left(\sum _{j=1}^{n}|x_{j}|^{2}\right)^{1/2},$

die Summen- oder $l_{1}$-Norm

(2.3) $\|x\|_{1}:=\sum _{j=1}^{n}|x_{j}|$

und die Maximum- oder $l_{\infty }$-Norm

(2.4) $\|x\|_{\infty }:=\max _{j=1,\ldots ,n}|x_{j}|,$

wobei jeweils $x\in \mathbb {R} ^{n}$ ist. Dass es sich dabei tatsächlich um Normen im Sinne von Definition 2.2 handelt, wurde bereits in der Numerischen Mathematik gezeigt. Dort findet man auch den Hinweis, dass dies gerade die sog. $l_{p}$-Normen für $p=2,p=1$ und $p=\infty$ sind.

Ein wichtiges Ergebnis in diesem Zusammenhang, das insbesondere für die Räume $\mathbb {R} ^{n}$ und $\mathbb {R} ^{n\times n}$ relevant ist, lautet:

Satz 2.4

Ist ${\mathcal {V}}$ ein endlich-dimensionaler Vektorraum und sind $\|\cdot \|_{a}$ und $\|\cdot \|_{b}$ zwei beliebige Normen auf ${\mathcal {V}}$, so sind diese „äquivalent“, d. h., es gibt Konstanten $c_{1},c_{2}>0$, so dass gilt:

(2.5) $c_{1}\|x\|_{a}\leq \|x\|_{b}\leq c_{2}\|x\|_{a},\quad x\in {\mathcal {V}}.$

Demnach ist jede Folge im $\mathbb {R} ^{n}$, die bezüglich irgendeiner Norm konvergiert, auch bezüglich jeder anderen Norm auf dem $\mathbb {R} ^{n}$ konvergent. Der Beweis des Satzes kann hier nicht gegeben werden (siehe dafür z. B. [Heu92, S. 103]). Der Nachweis der Äquivalenz speziell der $l_{p}$-Normen auf dem $\mathbb {R} ^{n}$ ist eine Aufgabe in der Numerischen Mathematik.

Als nächstes gehen wir auf Matrixnormen ein. Spezielle Matrixnormen für Matrizen $A:=(a_{kj})\in \mathbb {R} ^{n\times n}$ sind die Zeilensummennorm

(2.6) $\|A\|_{\infty }:=\max _{k=1,\ldots ,n}\sum _{j=1}^{n}|a_{kj}|$

und die Spaltensummennorm

(2.7) $\|A\|_{1}:=\max _{j=1,\ldots ,n}\sum _{k=1}^{n}|a_{kj}|.$

Die Normeigenschaften wurden für die Zeilensummennorm in Analysis 2 nachgewiesen. Der Beweis für die Spaltensummennorm verläuft ganz analog. Für die Normen in (2.6) und (2.7) geben wir ein Beispiel.

Beispiel 2.5

Man betrachte die Matrix

$A:={\begin{pmatrix}-1&6&-3&10\\2&0&4&-7\\0&2&3&8\\4&-2&0&1\end{pmatrix}}.$

Bildung der Summen der Beträge der Koeffizienten in jeder Zeile von $A$ liefert

$\|A\|_{\infty }=\max\{20,13,13,7\}=20.$

Bildung der Summen der Beträge der Koeffizienten in jeder Spalte von $A$ ergibt

$\|A\|_{1}=\max\{7,10,10,26\}=26.$

---

2.2 Induzierte Matrixnormen

Im Folgenden sei $\|\cdot \|$ entweder eine Vektornorm auf dem $\mathbb {R} ^{n}$ oder eine Matrixnorm auf dem Raum $\mathbb {R} ^{n\times n}$, wobei durch den Inhalt „$\cdot$“ von $\|\cdot \|$ klar ist, um was es sich jeweils handelt. (Vektoren bezeichnen wir, wie üblich, mit kleinen und Matrizen mit großen Buchstaben.) Jeder gegebenen Vektornorm wird nun in der nächsten Definition eine spezielle Matrixnorm zugeordnet, wobei anschließend zu zeigen ist, dass es sich dabei tatsächlich um eine Norm handelt und dass diese Norm von praktischem Interesse ist.

Definition 2.6

Sei $\|\cdot \|$ eine Norm auf dem $\mathbb {R} ^{n}$. Dann heißt die durch

(2.8) $\|A\|:=\max _{\|x\|=1}\|Ax\|$

für $A\in \mathbb {R} ^{n\times n}$ definierte Norm die durch die Vektornorm $\|\cdot \|$ induzierte Matrixnorm.

Man beachte, dass in der Definition (2.8) von $\|A\|$ nur die Vektornorm verwendet wird. Wegen der Kompaktheit der Menge

$\{x\in \mathbb {R} ^{n}|\|x\|=1\}$

und der Stetigkeit der Norm wird nach dem Satz von Weierstraß (vgl. Satz 2.38) das Maximum in (2.8) tatsächlich angenommen, so dass die Verwendung von „$\max$“ korrekt ist. Offenbar gilt für die Norm in (2.8)

(2.9) $\|A\|=\max _{y\in \mathbb {R} ^{n}\setminus \{0\}}\left\|A{\frac {y}{\|y\|}}\right\|=\max _{y\in \mathbb {R} ^{n}\setminus \{0\}}{\frac {\|Ay\|}{\|y\|}}.$

Speziell für die Einheitsmatrix $I\in \mathbb {R} ^{n\times n}$ erhält man bei beliebiger Wahl der Vektornorm für die durch diese Norm induzierte Matrixnorm

$\|I\|=\max _{\|x\|=1}\|Ix\|=\max _{\|x\|=1}\|x\|=1.$

Lemma 2.7

Die in (2.8) eingeführte „induzierte Matrixnorm“ ist eine Norm im Sinne von Definition 2.1.

Beweis.

Für $A:=(a_{ij})\in \mathbb {R} ^{n\times n}$ sei

(2.10) $\|A\|:=\max _{y\in \mathbb {R} ^{n}\setminus \{0\}}{\frac {\|Ay\|}{\|y\|}}=\max _{\|x\|=1}\|Ax\|.$

Weiter sei zunächst $\|A\|=\max _{\|x\|=1}\|Ax\|=0$. Dann schließt man für jedes $x$ mit $\|x\|=1$, dass $\|Ax\|\leq 0$ und damit $\|Ax\|=0$ ist. Aus den Axiomen für die Vektornorm folgt daher $Ax=0$ für jedes $x$ mit $\|x\|=1$. Dies ist nur für $A=0$ möglich, da im Fall, dass $a_{ij}\neq 0$ für mindestens ein $i$ und $j$ ist, für den Einheitsvektor $x:=e^{j}$ folgen würde: $(Ax)_{i}=a_{ij}\neq 0$. Ist umgekehrt $A=0$, so ergibt sich mit (2.10)

$\|A\|=\max _{\|x\|=1}\|Ax\|=\max _{\|x\|=1}\|0x\|=0.$

Weiter erschließt man unter Verwendung der Normaxiome für die Vektornorm mit $\alpha \in \mathbb {R}$

$\|\alpha A\|=\max _{\|x\|=1}\|\alpha Ax\|=\max _{\|x\|=1}|\alpha |\|Ax\|=|\alpha |\|A\|$

und für $A,B\in \mathbb {R} ^{n\times n}$

$\|(A+B)x\|=\|Ax+Bx\|\leq \|Ax\|+\|Bx\|.$

Damit erhält man für ein geeignetes ${\bar {x}}$ mit $\|{\bar {x}}\|=1$

$\|A+B\|=\max _{\|x\|=1}\|(A+B)x\|\leq \max _{\|x\|=1}(\|Ax\|+\|Bx\|)=\|A{\bar {x}}\|+\|B{\bar {x}}\|$

$\leq \max _{\|x\|=1}\|Ax\|+\max _{\|x\|=1}\|Bx\|=\|A\|+\|B\|.$

q.e.d.

Induzierte Matrixnormen, wie wir sie von nun an nur noch betrachten werden, sind deshalb von besonderem Interesse, weil sie neben den allgemeinen Normeigenschaften die sehr nützlichen, zusätzlichen Eigenschaften besitzen, welche in dem folgenden Satz angegeben werden.

Satz 2.8

Für die in Definition 2.6 eingeführte Matrixnorm gilt

(2.11) $\|Ax\|\leq \|A\|\|x\|,\quad A\in \mathbb {R} ^{n\times n},\quad x\in R^{n}$

sowie

(2.12) $\|AB\|\leq \|A\|\|B\|,\quad A,B\in \mathbb {R} ^{n\times n}.$

Beweis.

Für $x=0$ ist die Ungleichung in (2.11) trivialerweise erfüllt. Für $x\neq 0$ ergibt sie sich aus den Abschätzungen

$\|Ax\|={\frac {\|Ax\|}{\|x\|}}\|x\|\leq \left(\max _{x\in \mathbb {R} ^{n}\setminus \{0\}}{\frac {\|Ax\|}{\|x\|}}\right)\|x\|=\|A\|\|x\|.$

Weiter gilt für $Bx\neq 0$ und damit $x\neq 0$

${\frac {\|ABx\|}{\|x\|}}={\frac {\|A(Bx)\|}{\|Bx\|}}{\frac {\|Bx\|}{\|x\|}}\leq \|A\|\|B\|.$

Im Fall $Bx=0$ und $x\neq 0$ hat man trivialerweise

${\frac {\|ABx\|}{\|x\|}}=0\leq \|A\|\|B\|.$

Somit folgt für alle $x\neq 0$

${\frac {\|ABx\|}{\|x\|}}\leq \|A\|\|B\|$

und damit

$\|AB\|=\max _{x\in \mathbb {R} ^{n}\setminus \{0\}}{\frac {\|ABx\|}{\|x\|}}\leq \|A\|\|B\|.$

q.e.d.

Der folgende Satz besagt nun, dass die in (2.6) und (2.7) eingeführte Zeilen- und Spaltensummennorm gerade die durch die Vektornormen $\|\cdot \|_{\infty }$ und $\|\cdot \|_{1}$ induzierten Matrixnormen sind.

Satz 2.9

Sei $A:=(a_{kj})\in \mathbb {R} ^{n\times n}$. Für die durch die Vektornormen $\|\cdot \|_{\infty }$ und $\|\cdot \|_{1}$ induzierte Matrixnorm $\|A\|_{\infty }$ bzw. $\|A\|_{1}$ gilt

$\|A\|_{\infty }=\max _{k=1,\ldots ,n}\sum _{j=1}^{n}|a_{kj}|$ (Zeilensummennorm),

$\|A\|_{1}=\max _{j=1,\ldots ,n}\sum _{k=1}^{n}|a_{kj}|$ (Spaltensummennorm).

Beweis.

Wir weisen die Behauptung für die Zeilensummennorm nach. Für jedes $x\in \mathbb {R} ^{n}$ gilt

$\|A\|_{\infty }=\max _{k=1,\ldots ,n}\left|\sum _{j=1}^{n}a_{kj}x_{j}\right|\leq \max _{k=1,\ldots ,n}\sum _{j=1}^{n}|a_{kj}||x_{j}|\leq \left(\max _{k=1,\ldots ,n}\sum _{j=1}^{n}|a_{kj}|\right)\|x\|_{\infty }.$

Somit ergibt sich für $x\neq 0$

${\frac {\|Ax\|_{\infty }}{\|x\|_{\infty }}}\leq \max _{k=1,\ldots ,n}\sum _{j=1}^{n}|a_{kj}|$

und demzufolge gemäß (2.9)

$\|A\|_{\infty }\leq \max _{k=1,\ldots ,n}\sum _{j=1}^{n}|a_{kj}|.$

Zum Beweis der umgekehrten Abschätzung sei $k\in \{1,\ldots ,n\}$ beliebig, aber fest gewählt und $x:=(x_{j})$ der Vektor mit Koeffizienten

$x_{j}:={\begin{cases}|a_{kj}|/a_{kj},&{\text{falls }}a_{kj}\neq 0,\\1,&{\text{sonst}}.\end{cases}}$

Offenbar ist $\|x\|_{\infty }=1$. Somit schließt man

(2.13) $\|A\|_{\infty }=\max _{\|y\|_{\infty }=1}\|Ay\|_{\infty }\geq \|Ax\|_{\infty }\geq \left|\sum _{j=1}^{n}a_{kj}x_{j}\right|=\sum _{j=1}^{n}|akj|.$

Da $k$ beliebig gewählt war, folgt die behauptete Darstellung für $\|A\|_{\infty }$. Der Beweis für die Spaltensummennorm verläuft ganz ähnlich.

q.e.d.

Die wichtige Matrixnorm, welche durch die Euklidische Vektornorm induziert wird, ist leider nicht so einfach zu berechnen wie die Zeilen- oder Spaltensummennorm. Auf sie gehen wir im folgenden Abschnitt ein.

2.3 Die Spektralnorm

Eine symmetrische Matrix $A\in R^{n\times n}$ heißt positiv semidefinit, wenn

$x^{T}Ax\geq 0,\quad x\in \mathbb {R} ^{n}$

gilt und positiv definit im Fall

$x^{T}Ax>0,\quad x\in \mathbb {R} ^{n}\setminus \{0\}.$

Bezeichnen wir die Eigenwerte von $A$ mit $\lambda _{i}(A)$ und insbesondere den größten Eigenwert von $A$ mit $\lambda _{\max(}A)$, so ist aus der Linearen Algebra folgende Aussage bekannt:

Satz 2.10

Eine symmetrische Matrix $A\in \mathbb {R} ^{n\times n}$ ist genau dann positiv semidefinit, wenn

$\lambda _{i}(A)\geq 0\quad (i=1,\ldots ,n)$

ist und genau dann positiv definit, wenn gilt:

$\lambda _{i}(A)>0\quad (i=1,\ldots ,n).$

Über die Eigenwerte einer Matrix definieren wir weiter:

Definition 2.11

Für eine Matrix $B\in \mathbb {R} ^{n\times n}$ heißt

$\sigma (B):=\{\lambda \in \mathbb {C} {\big |}\lambda :=\lambda (B)\ ist\ Eigenwert\ von\ B\}$

das Spektrum und

$\varrho (B):=\max\{|\lambda |{\big |}\lambda \in \sigma (B)\}$

der Spektralradius von $B$.

Die durch die Euklidische Vektornorm induzierte Matrixnorm einer Matrix $A$ kann mit dem Spektralradius, d. h. dem größten Eigenwert von $A^{T}A$ dargestellt werden.

Satz 2.12

Sei $A\in \mathbb {R} ^{n\times n}$. Für die durch die Euklidische Vektornorm $\|\cdot \|_{2}$ induzierte Matrixnorm $\|\cdot \|_{2}$ gilt

$\|A\|_{2}={\sqrt {\varrho (A^{T}A)}}={\sqrt {\lambda _{\max(}A^{T}A)}}.$

Beweis.

Die Matrix $A^{T}A$ ist wegen $\left(A^{T}A\right)^{T}=A^{T}A$ symmetrisch und wegen

$x^{T}(A^{T}A)x=(Ax)^{T}(Ax)=\|Ax\|_{2}^{2}\geq 0,\quad x\in \mathbb {R} ^{n}$

positiv semidefinit. Somit besitzt $A^{T}A$ Eigenwerte $\lambda _{k}\geq 0$ $(k=1,\ldots ,n)$ und gibt es zu $A^{T}A$ ein System $u^{1},\ldots ,u^{n}\in \mathbb {R} ^{n}$ von orthonormalen Eigenvektoren, d. h., es ist

$A^{T}Au^{k}=\lambda _{k}u^{k},\quad k=1,\ldots ,n$

und

(2.15) $(u^{i})^{T}u^{k}=\delta _{ki}:={\begin{cases}0,&{\text{falls }}k\neq i,\\1,&{\text{falls }}k=i.\end{cases}}$

Für $x\in \mathbb {R} ^{n}$ gibt es daher mit Koeffizienten $c_{i}$ eine Darstellung $x=\sum _{i=1}^{n}c_{i}u^{i}$. Damit folgt

$\|x\|_{2}^{2}=x^{T}x=\left(\sum _{i=1}^{n}c_{i}(u^{i})^{T}\right)\left(\sum _{k=1}^{n}c_{k}u^{k}\right)=\sum _{i=1}^{n}c_{i}^{2}$

sowie

(2.16) $\|Ax\|_{2}^{2}=x^{T}A^{T}Ax=\left(\sum _{i=1}^{n}c_{i}u^{i}\right)^{T}\left(\sum _{k=1}^{n}c_{k}\left(A^{T}A\right)u^{k}\right)=\left(\sum _{i=1}^{n}c_{i}u^{i}\right)^{T}\left(\sum _{k=1}^{n}\lambda _{k}c_{k}u^{k}\right)$

$=\sum _{i=1}^{n}\lambda _{i}c_{i}^{2}\leq \left(\max _{i=1,\ldots ,n}\lambda _{i}\right)\cdot \sum _{i=1}^{n}c_{i}^{2}=\lambda _{\max(}A^{T}A)\|x\|_{2}^{2}.$

Somit hat man

(2.17) $\|A\|_{2}=\max _{x\in \mathbb {R} ^{n}\setminus \{0\}}{\frac {\|Ax\|_{2}}{\|x\|_{2}}}\leq {\sqrt {\lambda _{\max(}A^{T}A)}}.$

Für einen Eigenvektor ${\tilde {x}}$ zu einem maximalen Eigenwert $\lambda _{\max(}A^{T}A)$ gilt

$\|A{\tilde {x}}\|_{2}^{2}={\tilde {x}}^{T}A^{T}A{\tilde {x}}=\lambda _{\max(}A^{T}A){\tilde {x}}^{T}{\tilde {x}}=\lambda _{\max(}A^{T}A)\|{\tilde {x}}\|_{2}^{2}.$

Folglich wird das Maximum in (2.17) für ${\tilde {x}}$ angenommen und kann das „$\leq$“ dort durch „$=$“ ersetzt werden.

q.e.d.

Die Matrixnorm $\|\cdot \|_{2}$ bezeichnet man auch als Spektralnorm. Dieser Name begründet sich durch den letzten Satz bzw. durch die in folgendem Satz angegebene Identität für symmetrische Matrizen.

Satz 2.13

Sei $A\in \mathbb {R} ^{n\times n}$ eine symmetrische Matrix, d. h. $A=A^{T}$. Dann gilt

(2.18) $\|A\|_{2}=\varrho (A)=|\lambda _{\max(}A)|.$

Für jede andere durch eine Vektornorm induzierte Matrixnorm $\|\cdot \|$ folgt

(2.19) $\|A\|_{2}\leq \|A\|.$

Beweis.

Aufgrund der vorausgesetzten Symmetrie von $A$ gilt $A^{T}A=A^{2}$ und

$0\leq \lambda _{\max(}A^{T}A)=\lambda _{\max(}A^{2})=[\lambda _{\max(}A)]^{2},$

da $A^{2}$ die quadrierten Eigenwerte von $A$ als Eigenwerte hat. Daher schließt man

$\|A\|_{2}={\sqrt {\lambda _{\max(}A^{T}A)}}={\sqrt {\lambda _{\max(}A^{2})}}=|\lambda _{\max(}A)|.$

Da $A$ symmetrisch ist, sind ferner alle Eigenwerte von $A$ reell. Ist ${\tilde {x}}\neq 0$ ein Eigenvektor zum Eigenwert $\lambda _{\max(}A)$ und somit $A{\tilde {x}}=\lambda _{\max(}A){\tilde {x}}$, dann folgt für eine beliebige durch die Vektornorm $\|\cdot \|$ induzierte Matrixnorm $\|\cdot \|$

$\|A\|\geq {\frac {\|A{\tilde {x}}\|}{\|{\tilde {x}}\|}}={\frac {\|\lambda _{\max(}A){\tilde {x}}\|}{\|{\tilde {x}}\|}}={\frac {|\lambda _{\max(}A)|\|{\tilde {x}}\|}{\|{\tilde {x}}\|}}=|\lambda _{\max(}A)|.$

Damit ist alles gezeigt.

q.e.d.

Für eine reelle symmetrische Matrix ist also gemäß (2.19) der Wert der Spektralnorm unter allen Werten für induzierte Matrixnormen der kleinste. Die Spektralnorm wäre deshalb stets die favorisierte Norm für Matrizen, wenn ihre Berechnung im Allgemeinen nicht unvergleichlich aufwändiger wäre als die der Zeilen- oder Spaltensummennorm.

Beispiel 2.14

(1) Für die symmetrische Matrix

$A={\begin{pmatrix}1&3\\3&2\end{pmatrix}}$

berechnet man die Eigenwerte $\lambda _{1,2}=(3\pm {\sqrt {37}})/2$, so dass mit (2.18) folgt:

$\|A\|_{2}=(3+{\sqrt {37}})/2\approx 4.541.$

Weiter ergibt sich $\|A\|_{1}=\|A\|_{\infty }=5$. Man vergleiche hierzu (2.19).

(2) Für die nicht symmetrische Matrix

$A={\begin{pmatrix}0&1\\0&1\end{pmatrix}}\quad \left[\Rightarrow A^{T}A={\begin{pmatrix}0&0\\0&2\end{pmatrix}}\right]$

berechnet man unter Verwendung von Satz 2.12

$\|A\|_{2}={\sqrt {\lambda _{\max(}A^{T}A)}}={\sqrt {2}}.$

Demgegenüber erhält man für die Zeilen- und Spaltensummennorm

$\|A\|_{\infty }=1=\lambda _{\max(}A),\quad \|A\|_{1}=2.$

In diesem Fall ist also $\|A\|_{\infty }\leq \|A\|_{2}$. Letzteres zeigt, dass auf die Voraussetzung der Symmetrie der Matrix in Satz 2.13 nicht verzichtet werden kann.

---

2.4 Die Kondition einer Matrix

In der Numerischen Mathematik spielen Konditionszahlen im Zusammenhang mit der Stabilität eines numerischen Verfahrens eine große Rolle. Die in der folgenden Definition eingeführte Konditionszahl für Matrizen ist insbesondere im Zusammenhang mit der numerischen Lösung von linearen Gleichungssystemen relevant. Dies wird mit Satz 2.17 deutlich werden. Es bezeichne hierbei $\|\cdot \|$ generell wieder eine Vektornorm oder die durch sie induzierte Matrixnorm.

Definition 2.15

Sei $A\in \mathbb {R} ^{n\times n}$ eine reguläre Matrix. Die Zahl

$\operatorname {cond} (A):=\|A\|\left\|A^{-1}\right\|$

heißt Kondition oder Konditionszahl der Matrix $A$ (bezüglich der Norm $\|\cdot \|$).

Man beachte, dass die Größe der Konditionszahl einer Matrix im Allgemeinen von der gewählten Matrixnorm abhängig ist. Für symmetrische Matrizen liefert offenbar die Spektralnorm gemäß (2.19) die kleinste Konditionszahl für alle induzierten Matrixnormen:

$\operatorname {cond} _{2}(A):=\|A\|_{2}\left\|A^{-1}\right\|_{2}.$

Satz 2.16

Sei $A\in \mathbb {R} ^{n\times n}$ eine reguläre Matrix. Für die Kondition von $A$ bezüglich der Matrixnorm $\|\cdot \|$ folgt

(2.20) $\operatorname {cond} (A)=\left(\max _{\|x\|=1}\|Ax\|\right)/\left(\min _{\|x\|=1}\|Ax\|\right).$

Beweis.

Die Beziehung (2.20) ergibt sich aus

$\left\|A^{-1}\right\|=\max _{y\in \mathbb {R} ^{n}\setminus \{0\}}{\frac {\left\|A^{-1}y\right\|}{\|y\|}}{\stackrel {y=Ax}{=}}\max _{x\in \mathbb {R} ^{n}\setminus \{0\}}{\frac {\|x\|}{\|Ax\|}}=\max _{\|x\|=1}{\frac {1}{\|Ax\|}}=\left(\min _{\|x\|=1}\|Ax\|\right)^{-1}.$

q.e.d.

Die Konditionszahl $\operatorname {cond} (A)$ gibt also die Bandbreite an, um die sich die Vektorlänge eines Vektors $x$ bei Multiplikation mit $A$ ändern kann. Aus (2.20) ergibt sich zudem

$\operatorname {cond} (I)=1,\quad \operatorname {cond} (A)\geq 1,$

wobei $I\in \mathbb {R} ^{n\times n}$ wieder die Einheitsmatrix ist.

Wir betrachten nun den folgenden Satz im Hinblick auf die Lösung linearer Gleichungssysteme. In diesem Satz wird die Lösung $x$ eines Systems $Ax=b$ mit der Lösung ${\tilde {x}}$ eines gestörten Systems mit Matrix $A+\Delta A$ und rechter Seite $b+\Delta b$ verglichen, wobei die Größe der Störung, d. h. $\|\Delta A\|$ nicht zu groß sein darf. (Einen Beweis des Satzes findet man in [Pla00].)

Satz 2.17

Sei $A\in \mathbb {R} ^{n\times n}$ eine reguläre Matrix und $\Delta A\in \mathbb {R} ^{n\times n}$ eine Matrix mit $\|\Delta A\|<1/\left\|A^{-1}\right\|$. Gilt für Vektoren $b,x,\Delta b,{\tilde {x}}\in \mathbb {R} ^{n}$

$Ax=b,\quad (A+\Delta A){\tilde {x}}=b+\Delta b,$

so folgt für den relativen Fehler von ${\tilde {x}}$ bezüglich $x$ die Abschätzung

(2.21) ${\frac {\|x-{\tilde {x}}\|}{\|x\|}}\leq {\frac {\operatorname {cond} (A)}{1-\operatorname {cond} (A){\|\Delta A\|/\|A\|}}}\left({\frac {\|\Delta A\|}{\|A\|}}+{\frac {\|\Delta b\|}{\|b\|}}\right).$

Die Konstanten $\|\Delta A\|/\|A\|$ und \|\Delta b\| / \|b\|</math> sind offenbar gerade die relativen Fehler bezüglich $A$ und $b$, die durch die Störungen $\Delta A$ und $\Delta b$ verursacht werden. Deren Summe wird in (2.21) verstärkt durch den Faktor

${\frac {\operatorname {cond} (A)}{1-\operatorname {cond} (A){\frac {\|\Delta A\|}{\|A\|}}}}={\frac {\operatorname {cond} (A)}{1-\underbrace {\|\Delta A\|\left\|A^{-1}\right\|} _{<1}}}\geq 1.$

Dieser Faktor ist offenbar um so größer je größer die Kondition $\operatorname {cond} (A)$ von $A$ ist. Im Fall $\operatorname {cond} (A)\gg 1$ spricht man daher von einem schlecht konditionierten Gleichungssystem. (Dabei steht „$\gg$“ für „viel größer als“.)

Für ein schlecht konditioniertes lineares Gleichungssystem können sich also kleine Eingabefehler in den „Daten“ $A$ und $b$ sehr stark auf die Lösung des Systems $Ax=b$ auswirken, und sie tun dies normalerweise auch. Solche Eingabefehler macht man z. B. natürlicherweise, wenn man irrationale Zahlen wie ${\sqrt {2}}$ oder $\pi$ in einen Computer eingibt. Rundungsfehler, wie sie aufgrund der endlichen Zahlendarstellung beim Rechnen auf einem Computer nicht zu vermeiden sind, sind dabei noch gar nicht mit berücksichtigt. Bei Problemen, von denen man weiß, dass die Kondition der Matrix sehr groß ist, ist also Vorsicht im Hinblick auf die Interpretation der Genauigkeit der erzielten Lösung geboten. Wir geben im folgenden Abschnitt ein Beispiel für eine solche Matrix.

2.5 Positiv definite Matrizen

Wenn nichts anderes gesagt ist, meinen wir von nun an mit $\|\cdot \|$ der Einfachheit halber immer die Euklidische Vektornorm bzw. die durch sie induzierte Matrixnorm, die Spektralnorm. Folglich bedeutet $\operatorname {cond} (\cdot )$ die durch die Spektralnorm definierte Konditionszahl einer Matrix.

In diesem Kurs spielen symmetrische, positiv definite Matrizen eine große Rolle. Solche Matrizen sind insbesondere nichtsingulär. Ist $\lambda _{\min(}A)>0$ der kleinste und $\lambda _{\max(}A)$ der größte Eigenwert der symmetrischen, positiv definiten Matrix $A\in \mathbb {R} ^{n\times n}$, so ist offenbar $1/\lambda _{\max(}A)$ der kleinste und $1/\lambda _{\min(}A)$ der größte Eigenwert von $A^{-1}$. Demnach ist auch $A^{-1}$ eine symmetrische, positiv definite Matrix. Damit ergibt sich weiter für die Kondition einer solchen Matrix hinsichtlich der Spektralnorm:

(2.22) $\operatorname {cond} (A)=\|A\|\left\|A^{-1}\right\|={\frac {\lambda _{\max(}A)}{\lambda _{\min(}A)}}.$

Beispiel 2.18

Sei $A$ mit $\varepsilon >0$ gegeben durch

$A:={\begin{pmatrix}1&{\frac {1}{2}}\\{\frac {1}{2}}&{\frac {1}{4}}+\varepsilon \end{pmatrix}}.$

Für kleines $\varepsilon$ ist diese Matrix nahezu singulär. Insbesondere errechnet man für $A$ im Fall $\varepsilon =0.000\ 01$ die Eigenwerte

$\lambda _{1}=0.000\ 008,\quad \lambda _{2}=1.250\ 002.$

Also ist $A$ symmetrisch und positiv definit und erhält man gemäß (2.22) für die Kondition von $A$ bezüglich der Spektralnorm

$cond(A)={\frac {\lambda _{\max(}A)}{\lambda _{\min(}A)}}={\frac {1.250\ 002}{0.000\ 008}}\approx 156\ 250.$

Ein lineares Gleichungssystem mit $A$ als Systemmatrix ist demnach ein schlecht konditioniertes Gleichungssystem.

---

Wir benötigen ferner folgendes Resultat:

Lemma 2.19

Für eine symmetrische, positiv definite Matrix $A\in \mathbb {R} ^{n\times n}$ gilt

(2.23) $\lambda _{\min(}A)\|x\|^{2}\leq x^{T}Ax\leq \lambda _{\max(}A)\|x\|^{2},\quad x\in \mathbb {R} ^{n}$

sowie

(2.24) ${\frac {1}{\lambda _{\max(}A)}}\|x\|^{2}\leq x^{T}A^{-1}x\leq {\frac {1}{\lambda _{\min(}A)}}\|x\|^{2},\quad x\in \mathbb {R} ^{n}.$

Beweis.

Da die Matrix $A$ symmetrisch ist, existiert zu ihren Eigenwerten $\lambda _{i}$ eine Orthonormalbasis $\left\{u^{1},\ldots ,u^{n}\right\}$ von Eigenvektoren. Somit kann jedes $x$ mit Koeffizienten $c_{i}$ in der Form $x=\sum _{i=1}^{n}c_{i}u^{i}$ dargestellt werden. Nun gilt

$Au^{i}=\lambda _{i}u^{i},\quad i=1,\ldots ,n,$

so dass man analog zu (2.16) erhält:

$x^{T}Ax=\sum _{i=1}^{n}\lambda _{i}c_{i}^{2}.$

Letzteres impliziert wegen $\lambda _{i}>0$ und

$\|x\|^{2}=x^{T}x=\sum _{i=1}^{n}c_{i}^{2}$

die Ungleichungen in (2.23). Die Ungleichungen in (2.24) ergeben sich durch Anwendung von (2.23) auf $A^{-1}$.

Bemerkung 2.20

Wählt man $x$ in (2.23) als einen zu $\lambda _{\min(}A)$ bzw. $\lambda _{\max(}A)$ gehörenden Eigenvektor, so ergibt sich offenbar Gleichheit in der jeweiligen Ungleichung. Entsprechend schließt man für (2.24). Die Ungleichungen in (2.23) und (2.24) sind somit „scharf“.

Ferner werden wir uns auf die folgende Aussage beziehen.

Lemma 2.21

Ist $A\in \mathbb {R} ^{n\times n}$ eine symmetrische, positiv semidefinite Matrix und $C\in \mathbb {R} ^{m\times n}$, dann ist die Matrix $CAC^{T}$ symmetrisch und positiv semidefinit. Ist überdies $A$ positiv definit und $\operatorname {Rang} (C)=m$, dann ist auch $CAC^{T}$ positiv definit.

Beweis.

Die Matrix $CAC^{T}$ ist wegen

$\left[CAC^{T}\right]^{T}=\left[C(CA)^{T}\right]^{T}=CAC^{T}$

symmetrisch und wegen

(2.25) $x^{T}CAC^{T}x=\left(C^{T}x\right)^{T}A\left(C^{T}x\right)\geq 0,\quad x\in \mathbb {R} ^{n}$

positiv semidefinit. Die Rangbedingung an $C$ impliziert, dass $C^{T}x=0$ genau dann gilt, wenn $x=0$ ist. Für $x\neq 0$ hat man daher in (2.25) „$>0$“, wenn $A$ positiv definit ist.

q.e.d.

2.6 Konvexe Mengen und Funktionen

Besonders einfach geformte Mengen im $\mathbb {R} ^{n}$ sind konvexe Mengen. Dies sind Mengen, bei denen für zwei beliebige Punkte aus der Menge auch die gesamte Strecke, die sie verbindet, wieder in der Menge liegt. Mathematisch lässt sich dies folgendermaßen ausdrücken:

Definition 2.22

Eine Menge $K\subseteq \mathbb {R} ^{n}$ heißt konvex, wenn gilt:

$x,y\in K,\quad t\in [0,1]\Rightarrow tx+(1-t)y\in K.$

Man macht sich leicht klar, dass der Durchschnitt einer beliebigen Anzahl konvexer Mengen ebenfalls konvex ist, dass aber die Vereinigung konvexer Mengen nicht notwendig wieder eine konvexe Menge ergibt.

Definition 2.23

Hat $x\in \mathbb {R} ^{n}$ mit $x^{i}\in \mathbb {R} ^{n}$ $(i=1,\ldots ,l)$ die Gestalt

$x=\sum _{i=1}^{l}t_{i}x^{i},\qquad t_{i}\geq 0\quad (i=1,\ldots ,l),\qquad \sum _{i=1}^{l}t_{i}=1,$

so sagt man, $x$ ist eine Konvexkombination der $x^{i}$ $(i=1,\ldots ,l)$.

Das folgende Lemma lässt sich mittels vollständiger Induktion beweisen.

Lemma 2.24

Jede Konvexkombination von endlich vielen Elementen einer konvexen Menge $K$ ist wieder Element von $K$.

In Abschnitt 1.1 hatten wir bereits lineare und quadratische Funktionen eingeführt. Jede Funktion $f:D\subseteq \mathbb {R} ^{n}\to \mathbb {R}$, die auf $D$ nicht identisch mit einer affin-linearen Funktion ist, bezeichnet man als nichtlinear. Unter den nichtlinearen Funktionen interessieren im Hinblick auf Minimierungsprobleme besonders die konvexen Funktionen.

Anschaulich ist eine reellwertige Funktion $f$ in $n$ Veränderlichen konvex, wenn der Graph von $f$ zwischen zwei beliebigen Punkten $x$ und $y$ unterhalb der Sekante liegt, welche die beiden Punkte $(x,f(x))$ und $(y,f(y))$ auf dem Graphen verbindet oder wenn er mit dieser Sekante zusammenfällt. Befindet sich der Graph von $f$, abgesehen von den beiden Punkten $(x,f(x))$ und $(y,f(y))$, strikt unterhalb dieser Sekante, so bezeichnet man $f$ als strikt konvex.

Konvexe und strikt konvexe Funktionen können, aber müssen nicht so gekrümmt sein, dass sie Minimalpunkte besitzen. So hat die strikt konvexe Funktion $f(x):=x^{2}$ auf $\mathbb {R}$ genau einen Minimalpunkt, während die strikt konvexe Funktion $f(x):=1/x$ für $x>0$ ihr Minimum nicht annimmt. Im Hinblick auf die Existenz von Minima spielen daher gleichmäßig konvexe Funktionen in der Optimierung eine große Rolle (vgl. Satz 2.42). Wir wollen die diskutierten Begriffe nun mathematisch fassen:

Definition 2.25

Sei $f:D\subseteq \mathbb {R} ^{n}\to \mathbb {R}$ eine Funktion und $K\subseteq D$ eine konvexe Menge.

(i) $f$ heißt konvex auf $K$, falls gilt:

(2.26) $x,y\in K,\quad t\in [0,1]\Rightarrow f(tx+(1-t)y)\leq tf(x)+(1-t)f(y).$

(ii) $f$ heißt strikt konvex auf $K$, falls gilt:

$x,y\in K,\quad x\neq y,\quad t\in (0,1)\Rightarrow f(tx+(1-t)y)<tf(x)+(1-t)f(y).$

(iii) $f$ heißt gleichmäßig konvex auf $K$, falls eine Konstante $\beta >0$, genannt (gleichmäßige) Konvexitätskonstante, existiert, so dass gilt:

(2.27) $x,y\in K,\quad t\in [0,1]\Rightarrow {\frac {\beta }{2}}t(1-t)\|x-y\|^{2}+f(tx+(1-t)y)\leq tf(x)+(1-t)f(y).$

(iv) $f$ heißt konkav (strikt konkav, gleichmäßig konkav) auf $K$, wenn $-f$ konvex (strikt konvex, gleichmäßig konvex) auf $K$ ist.

Falls $D=K$ ist, kann in (i) - (iv) der Zusatz „auf $K$“ fortgelassen werden.

Ist $f$ eine affin-lineare Funktion der Gestalt

$f(x):=c^{T}x+\alpha ,\quad x\in \mathbb {R} ^{n},$

so gilt für alle $x,y$ und $t\in [0,1]$

$f(tx+(1-t)y)=c^{T}[tx+(1-t)y]+\alpha =t\left[c^{T}x+\alpha \right]+(1-t)\left[c^{T}y+\alpha \right]=tf(x)+(1-t)f(y).$

Wie auch schon anschaulich klar ist, sind also affin-lineare Funktionen sowohl konvexe als auch konkave Funktionen.

Es gibt nun eine ganze Reihe nützlicher Bedingungen, mit welchen man die Konvexität gewisser Funktionenklassen erschließen kann. Das folgende, leicht zu beweisende Lemma gibt ein Beispiel dafür an.

Lemma 2.26

Für $i=1,\ldots ,r$ seien $a_{i}>0$ und seien $f_{i}:D\subseteq \mathbb {R} ^{n}\to \mathbb {R}$ konvexe Funktionen auf einer konvexen Menge $K\subseteq D$. Dann ist auch die Funktion

(2.28) $f(x):=\sum _{i=1}^{r}a_{i}f_{i}(x),\quad x\in D$

auf </math>K</math> konvex.

Wie man unmittelbar aus den Definitionen erschließt, ist jede gleichmäßig konvexe Funktion strikt konvex und jede strikt konvexe Funktion auch konvex. Die Umkehrungen dieser Implikationen müssen aber nicht gelten. So ist eine affin-lineare Funktion konvex, aber nicht strikt konvex und ist die Funktion $f(x):=1/x$ für $x>0$ strikt konvex, aber nicht gleichmäßig konvex. Denn wäre sie gleichmäßig konvex, so erhielte man gemäß (2.26) für $t:=1/2,x>1,y:=x-1$ und ein $\beta >0$

$0<{\frac {\beta }{8}}\leq {\frac {\beta }{8}}+{\frac {1}{{\frac {1}{2}}x+{\frac {1}{2}}(x-1)}}\leq {\frac {1}{2x}}+{\frac {1}{2(x-1)}}.$

Dies kann jedoch für hinreichend große $x$ nicht richtig sein, da der rechte Ausdruck für $x\to \infty$ gegen 0 strebt.

Es ist zumeist sehr mühsam, eine Konvexitätseigenschaft für eine gegebene Funktion mittels der obigen Definitionen nachzuweisen. Deshalb sind, wie oft in der Mathematik, Bedingungen von Interesse, mit denen sich ein solcher Nachweis möglicherweise leichter führen lässt. Derartige Bedingungen werden wir im folgenden Abschnitt herleiten, so dass wir erst danach weitere Beispiele konvexer Funktionen betrachten wollen. Zuvor sei im Hinblick auf restringierte Optimierungsprobleme aber noch das folgende Ergebnis festgehalten.

Lemma 2.27

Seien $g_{i},h_{j}:\mathbb {R} ^{n}\to \mathbb {R}$ Funktionen und sei $Z$ die Menge

(2.29) $Z:=\{x\in \mathbb {R} ^{n}{\big |}h_{j}(x)=0\quad (j=1,\ldots ,m),\quad g_{i}(x)\leq 0\quad (i=1,\ldots ,l)\}.$

(i) Sind die $g_{i}$ und $h_{j}$ stetig, so ist $Z$ abgeschlossen.

(ii) Sind die $g_{i}$ konvex und die $h_{j}$ affin-linear, so ist $Z$ konvex.

Beweis.

Um die Abgeschlossenheit von $Z$ zu beweisen, zeigen wir, dass der Grenzwert jeder konvergenten Folge aus $Z$ wieder in $Z$ liegt. Sei also $\left\{x^{k}\right\}$ eine Folge mit $x^{k}\in Z$ und $\lim _{k\to \infty }x^{k}={\hat {x}}$. Dann folgt für alle $i$ und $j$

$g_{i}(x^{k})\leq 0,\quad h_{j}(x^{k})=0.$

Es kann weder $g_{i}({\hat {x}})>0$ noch $h_{j}({\hat {x}})\neq 0$ gelten, da dann auch $g_{i}(x^{k})>0$ bzw. $h_{j}(x^{k})\neq 0$ für alle hinreichend großen $k$ folgen würde. Also ist ${\hat {x}}\in Z$.

Für den Nachweis der Konvexität von $Z$ seien $x,y\in Z,t\in [0,1]$ und

$z:=tx+(1-t)y.$

Da die $g_{i}$ konvex und die $h_{j}$ affin-linear sind, folgt dann

$g_{i}(z)=g_{i}(tx+(1-t)y)\leq t\underbrace {g_{i}(x)} _{\leq 0}+(1-t)\underbrace {g_{i}(y)} _{\leq 0}\leq 0,$

$h_{j}(z)=h_{j}(tx+(1-t)y)=t\underbrace {h_{j}(x)} _{=0}+(1-t)\underbrace {h_{j}(y)} _{=0}=0.$

Also hat man $z\in Z$, womit die Konvexität von $Z$ bewiesen ist.

q.e.d.

Man beachte, dass in Aussage (ii) von Lemma 2.27 für die $g_{i}$ Konvexität, aber für die $h_{j}$ affine Linearität gefordert ist. Denn während eine Ungleichungsnebenbedingung $g_{i}(x)\leq 0$ mit einer konvexen Funktion $g_{i}$ einen konvexen Bereich definiert, tut dies eine Gleichungsrestriktion $h_{j}(x)=0$ mit einer nichtlinear-konvexen Funktion $h_{j}$ nicht.

2.7 Charakterisierungen konvexer Funktionen

Einmal bzw. zweimal stetig differenzierbare, konvexe Funktionen lassen sich durch Bedingungen erster und zweiter Ordnung charakterisieren. So ist eine einmal stetig differenzierbare Funktion in einer Veränderlichen offenbar genau dann konvex gekrümmt, wenn jede Tangente an ihren Graphen unterhalb des Graphen liegt bzw. mit diesem zusammenfällt. Dies ist im eindimensionalen Fall die Interpretation von Teil (i) des folgenden Satzes. Ähnlich kann man für eine strikt oder gleichmäßig konvexe Funktion argumentieren.

Satz 2.28

Sei $K\subseteq \mathbb {R} ^{n}$ konvex und $f\in C^{1}(K)$. (Mit $C^{k}(\Omega )$ bezeichnen wir die Menge aller auf einer offenen Obermenge ${\tilde {\Omega }}$ von $\Omega \subseteq \mathbb {R} ^{n}$ $k$-mal stetig differenzierbaren Funktionen $f:{\tilde {\Omega }}\to \mathbb {R}$, wobei ${\tilde {\Omega }}$ von $f$ abhängen darf.) Dann gilt:

(i) $f$ ist auf $K$ genau dann konvex, wenn gilt:

(2.30) $f(y)+\nabla f(y)^{T}(x-y)\leq f(x),\quad x,y\in K.$

(ii) $f$ ist auf $K$ genau dann strikt konvex, wenn gilt:

$f(y)+\nabla f(y)^{T}(x-y)<f(x),\quad x,y\in K,\quad x\neq y.$

(iii) $f$ ist auf $K$ genau dann gleichmäßig konvex mit Konstante $\beta >0$, wenn gilt:

${\frac {\beta }{2}}\|x-y\|^{2}+f(y)+\nabla f(y)^{T}(x-y)\leq f(x),\quad x,y\in K.$

Beweis.

„$\Rightarrow$ für (i), (iii)“: $f$ sei konvex bzw. gleichmäßig konvex auf $K$. Dann gilt mit $\beta =0$ bzw. $\beta >0$ für alle $x,y\in K$ und $t\in [0,1]$:

${\frac {\beta }{2}}t(1-t)\|x-y\|^{2}+f(tx+(1-t)y))\leq tf(x)+(1-t)f(y).$

Für $t\in (0,1]$ impliziert dies

(2.31) ${\frac {\beta }{2}}(1-t)\|x-y\|^{2}+{\frac {1}{t}}[f(y+t(x-y))-f(y)]\leq f(x)-f(y).$

Nach Definition der Richtungsableitung von $f$ bei $x$ in Richtung $p$ hat man

$\lim _{t\to 0+}{\frac {f(x+tp)-f(x)}{t}}=\nabla f(x)^{T}p,$

so dass Grenzwertbildung für $t\to 0+$ in (2.31) das gewünschte Ergebnis liefert:

(2.32) ${\frac {\beta }{2}}\|x-y\|^{2}+\nabla f(y)^{T}(x-y)\leq f(x)-f(y).$

„$\Rightarrow$ für (ii)“: Ist $f$ strikt konvex, dann ist $f$ auch konvex, so dass für $\beta =0$ gemäß (2.32) gilt:

(2.33) $\nabla f(y)^{T}(x-y)\leq f(x)-f(y),\quad x,y\in K.$

Für alle $x,y\in K$ mit $x\neq y$ und $z:={\frac {1}{2}}(x+y)$ folgt daher unter Ausnutzung von (2.33) und der strikten Konvexität von $f$

$\nabla f(y)^{T}(x-y)=\nabla f(y)^{T}(2z-y-y)=2\nabla f(y)^{T}(z-y)\leq 2[f(z)-f(y)]$

$=2\left[f\left({\frac {1}{2}}(x+y)\right)-f(y)\right]<f(x)-f(y).$

„$\Leftarrow$ für (i), (iii)“: Mit $\beta =0$ bzw. $\beta >0$ sei

(2.34) ${\frac {\beta }{2}}\|x-y\|^{2}+\nabla f(y)^{T}(x-y)\leq f(x)-f(y),\quad x,y\in K.$

Da $K$ eine konvexe Menge ist, liegt für $x,y\in K$ und jedes $t\in [0,1]$ auch $z:=tx+(1-t)y$ in $K$. Somit liefert (2.34), angewandt auf $x$ und $z$ bzw. $y$ und $z$,

${\frac {\beta }{2}}\|x-z\|^{2}+\nabla f(z)^{T}(x-z)\leq f(x)-f(z),$

${\frac {\beta }{2}}\|y-z\|^{2}+\nabla f(z)^{T}(y-z)\leq f(y)-f(z).$

Multipliziert man die erste dieser Ungleichungen mit $t$ und die zweite mit $1-t$ und addiert man anschließend beide Ungleichungen, so erhält man

${\frac {\beta }{2}}\left[t\|x-z\|^{2}+(1-t)\|y-z\|^{2}\right]+\nabla f(z)^{T}[t(x-z)+(1-t)(y-z)]$

$\leq t[f(x)-f(z)]+(1-t)[f(y)-f(z)]=tf(x)+(1-t)f(y)-f(tx+(1-t)y).$

Wegen der Definition von $z$ ist dabei

${\frac {\beta }{2}}\left[t\|x-z\|^{2}+(1-t)\|y-z\|^{2}\right]={\frac {\beta }{2}}\left[t(1-t)^{2}+(1-t)t^{2}\right]\|x-y\|^{2}={\frac {\beta }{2}}t(1-t)\|x-y\|^{2},$

womit das gewünschte Ergebnis folgt. Der Beweis der Richtung „$\Leftarrow$“ für (ii) erfolgt analog, indem man $\beta =0$ setzt und überall „$\leq$“ gegen „$<$“ austauscht.

q.e.d.

Der nächste Satz charakterisiert die unterschiedlichen Konvexitätseigenschaften durch zweite Ableitungen.

Satz 2.29

Sei $K\subseteq \mathbb {R} ^{n}$ konvex und $f\in C^{2}(K)$. Dann gilt:

(i) Ist $\nabla ^{2}f(x)$ für alle $x\in K$ positiv semidefinit, so ist $f$ konvex auf $K$.

(ii) Ist $\nabla ^{2}f(x)$ für alle $x\in K$ positiv definit, so ist $f$ strikt konvex auf $K$.

(iii) Gibt es eine Konstante $\beta >0$, so dass

(2.35) $h^{T}\nabla ^{2}f(x)h\geq \beta \|h\|^{2},\quad h\in \mathbb {R} ^{n},\quad x\in K$

gilt, so ist $f$ gleichmäßig konvex auf $K$ mit Konstante $\beta$.

(iv) Ist $K$ offen, so gelten auch die Umkehrungen von (i) und (iii).

Beweis.

(i)-(iii): Seien $x,y\in K$ und $x\neq y$. Weiter sei

$\varphi (t):=f(y+t(x-y)),\quad t\in [0,1].$

Dann gilt nach dem Satz von Taylor mit einem $t_{0}\in (0,1)$

$\varphi (1)-\varphi (0)-\varphi '(0)={\frac {1}{2}}\varphi ''(t_{0})$

bzw.

$f(x)-f(y)-\nabla f(y)^{T}(x-y)={\frac {1}{2}}(x-y)^{T}\nabla ^{2}f(y+t_{0}(x-y))(x-y),$

wobei offenbar $y+t_{0}(x-y)$ in $K$ liegt. Mit Satz 2.28 folgt damit unter Anwendung der im Satz geforderten Eigenschaften der Hesse-Matrix von $f$ auf $K$ die Behauptung.

(iv): $K$ sei offen und $f$ sei auf $K$ konvex $(\beta =0)$ bzw. gleichmäßig konvex $(\beta >0)$. Weiter sei $x\in K$ und $h\in \mathbb {R} ^{n}$ beliebig. Dann ist $x+th\in K$ für alle hinreichend kleinen $t>0$. Für diese $t$ gilt nach Satz 2.28 (iii):

${\frac {1}{2}}\beta t^{2}\|h\|^{2}+f(x)+\nabla f(x)^{T}th\leq f(x+th),$

${\frac {1}{2}}\beta t^{2}\|h\|^{2}+f(x+th)+\nabla f(x+th)^{T}th\leq f(x).$

Addition der beiden Ungleichungen liefert

$\beta t^{2}\|h\|^{2}\leq [\nabla f(x+th)-\nabla f(x)]^{T}th,$

so dass für alle hinreichend kleinen $t>0$ folgt:

${\frac {1}{t}}[\nabla f(x+th)-\nabla f(x)]^{T}h\geq \beta \|h\|^{2}.$

Grenzübergang für $t\to 0+$ liefert schließlich die Ungleichung in (2.35).

q.e.d.

Die Umkehrung der Aussage (ii) von Satz 2.29 muss für eine offene konvexe Menge $K$ nicht gelten. Dies zeigt das folgende erste Beispiel 2.30.

Beispiel 2.30

(i) Sei $K:=(-1,1)$ und $f(x):=x^{4}$. Dann schließt man

$u<v\Rightarrow f'(u)=4u^{3}<4v^{3}=f'(v),$

so dass nach dem Mittelwertsatz für ein $\xi$ zwischen $x$ und $y$ folgt:

$f(y)-f(x)=f'(\xi )(y-x)>f'(x)(y-x).$

Gemäß Satz 2.28 ist also $f$ auf $K$ strikt konvex. Aber es ist $f'(0)=f''(0)=0$.

(ii) Für $f(x):=e^{x}$ ist $f''(x)=f'(x)=e^{x}>0$. Also ist $f$ nach Satz 2.29 strikt konvex auf $\mathbb {R}$. Wegen

$\lim _{x\to -\infty }f''(x)=\lim _{x\to -\infty }e^{x}=0$

existiert aber kein $\beta >0$, so dass $f''(x)\geq \beta$ für alle $x$ und damit (2.35) gilt. Demzufolge ist $f$ auf $\mathbb {R}$ nicht gleichmäßig konvex.

---

Als weiteres Beispiel wollen wir im nächsten Abschnitt die für die nichtlineare Optimierung wichtige Klasse der quadratischen Funktionen auf mögliche Konvexitätseigenschaften hin untersuchen. Dies ist mit Hilfe der nun zur Verfügung stehenden Ergebnisse einfacher als mit der ursprünglichen Definition 2.25.

2.8 Quadratische Funktionen

Definition 2.31

Unter einer quadratischen Funktion versteht man eine Funktion $f:\mathbb {R} ^{n}\to \mathbb {R}$, welche durch

(2.36) $f(x):={\frac {1}{2}}x^{T}Qx+c^{T}x+\alpha$

definiert ist, wobei $\alpha \in \mathbb {R} ,c\in \mathbb {R} ^{n}$ und $Q\in \mathbb {R} ^{n\times n}$ eine symmetrische Matrix ist.

Für die quadratische Funktion in (2.36) hat man

(2.37) $\nabla f(x)=Qx+c,\quad \nabla ^{2}f(x)=Q.$

Der Faktor $1/2$ vor dem quadratischen Term in (2.36) bewirkt also, dass der Gradient und die Hesse-Matrix von $f$ keinen Faktor vor $Q$ enthalten.

Bemerkung 2.32

Die Forderung der Symmetrie von $Q$ für eine quadratische Funktion stellt keine Einschränkung dar. Denn jede Funktion wie in (2.36), die nicht mit einer symmetrischen Matrix gegeben ist, kann auch mit einer symmetrischen Matrix dargestellt werden. Die Vorgehensweise dabei soll nicht allgemein beschrieben, sondern nur an dem folgenden kleinen Beispiel verdeutlicht werden:

$f(x,y):={\frac {1}{2}}{\begin{pmatrix}x&y\end{pmatrix}}{\begin{pmatrix}6&1\\-9&-1\end{pmatrix}}{\begin{pmatrix}x\\y\end{pmatrix}}+{\begin{pmatrix}3&0\end{pmatrix}}{\begin{pmatrix}x\\y\end{pmatrix}}-6={\frac {1}{2}}\left(6x^{2}-y^{2}+xy-9yx\right)+3x-6$

$={\frac {1}{2}}\left(6x^{2}-y^{2}-4xy-4yx\right)+3x-6={\frac {1}{2}}{\begin{pmatrix}x&y\end{pmatrix}}{\begin{pmatrix}6&-4\\-4&-1\end{pmatrix}}{\begin{pmatrix}x\\y\end{pmatrix}}+{\begin{pmatrix}3&0\end{pmatrix}}{\begin{pmatrix}x\\y\end{pmatrix}}-6.$

Mit Satz 2.29 lässt sich nun leicht charakterisieren, wann eine quadratische Funktion $f$ auf dem $\mathbb {R} ^{n}$ konvex bzw. gleichmäßig konvex ist.

Lemma 2.33

Für die quadratische Funktion $f$ in (2.36) gilt:

(i) $f$ ist genau dann konvex, wenn $Q$ positiv semidefinit ist.

(ii) $f$ ist genau dann gleichmäßig konvex, wenn $Q$ positiv definit ist.

(iii) Wenn $f$ gleichmäßig konvex ist, so ist

(2.38) $\beta :=\lambda _{\min(}Q)$

die größtmögliche Konvexitätskonstante für $f$.

Beweis.

Es ist $\nabla ^{2}f(x)=Q$. Die Aussagen (i) und (ii) folgen damit aus Satz 2.29, wobei man für (ii) die linke Ungleichung in (2.23) berücksichtige. Ist nun $f$ gleichmäßig konvex mit Konvexitätskonstante ${\tilde {\beta }}$, so ist nach Satz 2.29 $Q$ positiv definit und die Ungleichung in (2.35) mit ${\tilde {\beta }}$ erfüllt. Damit gilt also die linke Ungleichung in (2.23) mit ${\tilde {\beta }}$. Gemäß Bemerkung 2.20 ist $\beta :=\lambda _{\min(}Q)$ die größtmögliche Konstante für die letztere Ungleichung. Aus Teil (iii) von Satz 2.29 ergibt sich damit, dass $f$ auch mit der Konvexitätskonstante $\beta$ gleichmäßig konvex ist.

q.e.d.

Beispielsweise ist also die quadratische Funktion

$f(x,y):=0.6x^{2}+1.6y^{2}={\frac {1}{2}}{\begin{pmatrix}x&y\end{pmatrix}}{\begin{pmatrix}1.2&0\\0&3.2\end{pmatrix}}{\begin{pmatrix}x\\y\end{pmatrix}}$

auf $\mathbb {R} ^{2}$ gleichmäßig konvex. Denn die sie definierende Matrix hat die positiven Eigenwerte $\lambda _{1}=1.2$ und $\lambda _{2}=3.2$.

Ein praktisch relevantes Beispiel für eine quadratische Funktion ist die Funktion, welche bei der linearen Ausgleichsrechnung zu minimieren ist.

Beispiel 2.34

Hat ein lineares Gleichungssystem $Ax=b$ mit $A\in \mathbb {R} ^{n\times k}$ und $b\in \mathbb {R} ^{n}$ mehr Gleichungen als Unbekannte, so ist es typischerweise nicht lösbar. Für $n\geq k$ macht es also Sinn, ein $x^{*}$ als „Lösung“ zu akzeptieren, für welches der Defekt $Ax-b$ hinsichtlich der Norm $\|\cdot \|$ bzw., was äquivalent damit ist, hinsichtlich der quadrierten Norm $\|\cdot \|^{2}$ auf dem $\mathbb {R} ^{k}$ minimal wird. Gesucht ist dann also eine Lösung des linearen Ausgleichsproblems

$\inf _{x\in \mathbb {R} ^{k}}\|Ax-b\|^{2}.$

Die Zielfunktion dieses Problems lässt sich als quadratische Funktion der Gestalt (2.36) schreiben:

$\|Ax-b\|^{2}=(Ax-b)^{T}(Ax-b)=(Ax)^{T}Ax-(Ax)^{T}b-b^{T}Ax+b^{T}b$

$={\frac {1}{2}}x^{T}(2A^{T}A)x-(2A^{T}b)^{T}x+b^{T}b.$

Die Matrix $2A^{T}A$ darin ist wegen $\left(A^{T}A\right)^{T}=A^{T}A$ symmetrisch und wegen

$h^{T}(A^{T}A)h=(Ah)^{T}(Ah)=\|Ah\|^{2}\geq 0,\quad h\in \mathbb {R} ^{k}$

positiv semidefinit. Im Fall $\operatorname {Rang} (A)=k$ ist diese Matrix sogar positiv definit, da dann die Spalten von $A$ linear unabhängig sind und folglich gilt:

$h^{T}(A^{T}A)h=0\Leftrightarrow \|Ah\|=0\Leftrightarrow Ah=0\Leftrightarrow h=0.$

Gemäß Lemma 2.33 ist die Zielfunktion des linearen Ausgleichsproblems also eine konvexe und im Fall $\operatorname {Rang} (A)=k$ eine gleichmäßig konvexe, quadratische Funktion.

---

2.9 Problemstellung und zentrale Begriffe

Wir betrachten nun das allgemeine Optimierungsproblem

(2.39) Minimiere $f(x)$ über alle $x\in Z$

mit zulässigem Bereich $Z\subseteq \mathbb {R} ^{n}$ und Zielfunktion $f\in C(Z)$. In diesem und dem nächsten Abschnitt wollen wir einige grundlegende Begriffe und Aussagen über die Existenz und Eindeutigkeit von Lösungen für solche Optimierungsprobleme bereit stellen. Vorrangig denken wir dabei an den unrestringierten Fall $Z:=\mathbb {R} ^{n}$ und den restringierten Fall, bei dem $Z$ in der Form

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

mit Funktionen $g_{i},h_{j}\in C(\mathbb {R} ^{n})$ gegeben ist.

Ist $Z$ eine konvexe Menge und $f$ konvex auf $Z$, dann bezeichnet man das Problem (2.39) als ein konvexes Optimierungsproblem. Insbesondere ist $Z:=\mathbb {R} ^{n}$ ein Problem der Gestalt

${\begin{array}{ll}{\text{Minimiere}}&{\frac {1}{2}}x^{T}Qx+c^{T}x\\{\text{u. d. N.}}&(a^{j})^{T}x-b_{j}=0\quad (j=1,\ldots ,m),\\&(c^{i})^{T}x-d_{i}\leq 0\quad (i=1,\ldots ,l).\end{array}}$

Speziell im Fall $Q:=0$ liegt ein lineares Optimierungsproblem vor:

${\begin{array}{ll}{\text{Minimiere}}&c^{T}x\\{\text{u. d. N.}}&(a^{j})^{T}x-b_{j}=0\quad (j=1,\ldots ,m),\\&(c^{i})^{T}x-d_{i}\leq 0\quad (i=1,\ldots ,l).\end{array}}$

Der zulässige Bereich eines linearen und eines quadratischen Optimierungsproblems ist konvex (Lemma 2.27). Ein quadratisches Optimierungsproblem ist weiterhin genau dann konvex, wenn $Q$ eine positiv semidefinite Matrix ist (Lemma 2.33). Ergebnisse für quadratische Optimierungsprobleme mit positiv semidefiniter Matrix $Q$ sind offenbar auch auf lineare Optimierungsprobleme anwendbar. Die Voraussetzung der positiven Definitheit für $Q$ schließt aber den linearen Fall aus.

Wie ebenfalls schon Abschnitt 1.1 gesagt wurde, liegt ein nichtlineares Optimierungsproblem vor, wenn $f$ (im unrestringierten Fall) bzw. mindestens eine der Funktionen $f,g_{i}$ und $h_{j}$ (im restringierten Fall) nichtlinear ist. Konvexe Optimierungsprobleme sind also spezielle nichtlineare Optimierungsprobleme. Denkt man bei einem nichtlinearen Problem ausdrücklich nicht an ein konvexes Problem, so sagt man auch, dass das Problem nichtkonvex oder nichtkonvex-nichtlinear ist.

Den Wert

(2.41) $\mu :=\inf _{x\in Z}f(x)$

nennt man den Minimalwert von Problem (2.39). Für $Z\neq \emptyset$ ist er endlich oder $-\infty$. Beispiele sind

$\inf _{x\in \mathbb {R} }x=-\infty ,\quad \inf _{x\in \mathbb {R} }e^{x}=0,\quad \inf _{x\in \mathbb {R} }(x^{2}+1)=\min _{x\in \mathbb {R} }(x^{2}+1)=1.$

Für den Fall $Z=\emptyset$ definiert man

$\inf _{x\in Z}f(x):=+\infty ,\quad \sup _{x\in Z}f(x):=-\infty .$

Jedes $x^{*}\in Z$, für das $f(x)$ auf $Z$ den Minimalwert $\mu$ annimmt, für das also $\mu =f(x^{*})$ gilt, nennt man globale Lösung des Optimierungsproblems. Weitere Lösungsbegriffe werden mit der folgenden Definition eingeführt. Dabei bezeichne

${\mathcal {U}}_{\varepsilon }(x^{*}):=\{x\in \mathbb {R} ^{n}{\big |}\|x^{*}-x\|<\varepsilon \}$

für ein $\varepsilon >0$ die offene $\varepsilon$-Umgebung von $x^{*}$.

Definition 2.36

(i) $x^{*}\in Z$ heißt globale Lösung von Problem (2.39), falls

f$(x^{*})\leq f(x),\quad x\in Z$

gilt und strikt globale Lösung im Fall

$f(x^{*})<f(x),\quad x\in Z,\quad x\neq x^{*}.$

(ii) $x^{*}\in Z$ heißt lokale Lösung von Problem (2.39), falls ein $\varepsilon >0$ existiert, so dass

(2.42) $f(x^{*})\leq f(x),\quad x\in Z\cap {\mathcal {U}}_{\varepsilon }(x^{*})$

gilt und strikt lokale Lösung im Fall

$f(x^{*})<f(x),\quad x\in Z\cap {\mathcal {U}}_{\varepsilon }(x^{*}),\quad x\neq x^{*}.$

Statt von einer Lösung von Problem (2.39) spricht man auch von einem Minimalpunkt oder einem Minimierer.

Im Fall, dass $x^{*}$ eine lokale oder globale Lösung von Problem (2.39) ist, sagt man auch, dass $f$ bzw. $f(x)$ sein lokales bzw. globales Minimum in $x^{*}$ annimmt. Wir unterscheiden hier also zwischen einem Minimierer von $f$, einem Punkt, und einem Minimum von $f(x)$, d. h. dem zugehörigen Funktionswert.

Jede globale Lösung von Problem (2.39) ist gemäß Definition 2.36 auch eine lokale Lösung des Problems. Konvexe Probleme besitzen die wichtige Eigenschaft, dass für sie umgekehrt auch jede lokale Lösung eine globale Lösung ist:

Satz 2.37

Es sei $Z\subseteq \mathbb {R} ^{n}$ konvex und $f\in C(Z)$ eine konvexe Funktion. Dann gilt:

(i) Jede (strikt) lokale Lösung von Problem (2.39) ist auch (strikt) globale Lösung.

(ii) Ist $f$ strikt konvex auf $Z$, dann besitzt Problem (2.39) höchstens eine globale Lösung.

(iii) Die Menge aller globalen Lösungen von Problem (2.39) ist konvex. Ist $Z$ abgeschlossen, so ist sie auch abgeschlossen.

Beweis.

Übung!

2.10 Existenz und Eindeutigkeit von Lösungen

Wir diskutieren nun als nächstes die Existenz und Eindeutigkeit von Lösungen des Optimierungsproblems

(2.43) Minimiere $f(x)$ über alle $x\in Z$,

wobei wieder $Z\subseteq \mathbb {R} ^{n}$ und $f\in C(Z)$ seien. Ist $Z$ eine nichtleere, abgeschlossene und beschränkte Menge, so besitzt das Problem (2.43) nach dem folgenden, aus der Analysis bekannten Satz von Weierstraß eine globale Lösung. (Es sei daran erinnert, dass eine Menge im $\mathbb {R} ^{n}$ genau dann kompakt ist, wenn sie abgeschlossen und beschränkt ist.)

Satz 2.38 (Weierstraß)

Jede auf einer nichtleeren kompakten Menge stetige reellwertige Funktion in $n$ Veränderlichen nimmt dort ihr (globales) Minimum und Maximum an.

In der Praxis ist der zulässige Bereich $Z$ eines Minimierungsproblems jedoch häufig unbeschränkt und insbesondere ist er dies natürlich im Fall $Z:=\mathbb {R} ^{n}$ des unrestringierten Optimierungsproblems. Wie als nächstes gezeigt werden soll, genügt es jedoch für den Nachweis der Existenz einer Lösung von Problem (2.43), dass $Z$ nichtleer und dass für ein $x^{0}\in Z$ die Niveaumenge

$N(x^{0}):=\left\{x\in Z{\big |}f(x)\leq f(x^{0})\right\}$

beschränkt ist. Bevor wir dies zeigen wollen, seien einige Eigenschaften dieser Menge aufgeführt.

Lemma 2.39

Seien $Z\subseteq \mathbb {R} ^{n},x^{0}\in Z$ und $f\in C(Z)$. Dann gilt:

(i) Es ist $x^{0}\in N(x^{0})$.

(ii) Ist $Z$ eine konvexe Menge und $f$ konvex auf $Z$, d. h., ist das Problem (2.43) ein konvexes Optimierungsproblem, so ist $N(x^{0})$ konvex.

(iii) Ist $Z$ abgeschlossen, so ist auch $N(x^{0})$ abgeschlossen.

Beweis.

(i) Es ist $x^{0}\in Z$ und $f(x^{0})\leq f(x^{0})$. Demzufolge gilt $x^{0}\in N(x^{0})$.

(ii) Seien $x,y\in N(x^{0}),t\in [0,1]$ und $z:=tx+(1-t)y$. Dann folgt zunächst $x,y\in Z$ und wegen der Konvexität von $Z$ auch $z\in Z$. Da $Z$ nach Voraussetzung eine konvexe Menge ist, schließt man aus der ebenfalls vorausgesetzten Konvexität von $f$ auf $Z$, dass gilt:

$f(z)=f(tx+(1-t)y)\leq tf(x)+(1-t)f(y)\leq tf(x^{0})+(1-t)f(x^{0})=f(x^{0}).$

Also hat man zusammen $z\in N(x^{0})$ und ist damit $N(x^{0})$ konvex.

(iii) Sei nun $\{x^{k}\}$ eine Folge in $N(x^{0})$, welche gegen ein ${\hat {x}}$ konvergiert. Dann ist per Definition $x^{k}\in Z$ und wegen der vorausgesetzten Abgeschlossenheit von $Z$ auch ${\hat {x}}\in Z$. Außerdem hat man $f(x^{k})\leq f(x^{0})$, so dass mit der Stetigkeit von $f$ auch $f({\hat {x}})\leq f(x^{0})$ folgt. Zusammen hat man also ${\hat {x}}\in N(x^{0})$, was die Abgeschlossenheit von $N(x^{0})$ beweist.

q.e.d.

Im Hinblick auf die letzte Aussage stellen wir fest, dass $Z$ natürlich im Fall $Z:=\mathbb {R} ^{n}$ abgeschlossen ist und dass $Z$ dies auch im restringierten Fall ist, wenn $g_{i},h_{j}\in C(\mathbb {R} ^{n})$ gilt (vgl. Lemma 2.27). Es gilt nun, wie bereits oben gesagt wurde:

Satz 2.40

Es seien $Z\subseteq \mathbb {R} ^{n},x^{0}\in Z$ und $f\in C(Z)$. Ist die Niveaumenge $N(x^{0})$ kompakt, dann besitzt das Problem (2.43) eine globale Lösung.

Beweis.

Nach Satz 2.38 nimmt $f$ unter den gegebenen Voraussetzungen sein Minimum auf der gemäß Lemma 2.39 (i) nichtleeren Menge $N(x^{0})$ an, d. h., es existiert ein $x^{*}\in N(x^{0})$, so dass gilt:

$f(x^{*})\leq f(x)\leq f(x^{0}),\quad x\in N(x^{0}).$

Da man für $x\in Z\setminus N(x^{0})$ die Beziehung $f(x^{*})\leq f(x^{0})<f(x)$ hat, folgt damit die Behauptung.

q.e.d.

Die Voraussetzung der Kompaktheit der Niveaumenge $N(x^{0})$ für ein $x^{0}\in Z$ ist eine klassische Annahme in der Optimierung. Aufgrund der Beobachtung, die dem Satz 2.40 vorangeht, bleibt für deren Nachweis im Fall unrestringierter und restringierter Optimierungsprobleme mit stetigen Funktionen nur zu garantieren, dass $N(x^{0})$ beschränkt ist. Sind die Probleme insbesondere konvex, so kann man in diesem Zusammenhang beweisen, dass $N(x^{0})$ für jedes $x^{0}\in Z$ genau dann beschränkt ist, wenn die Menge der Lösungen des Problems beschränkt ist (z. B. [ReeRü98, S. 203]). Letzteres ist sicher für jedes vernünftige praktische Problem der Fall.

Der nächste Satz zeigt nun die Bedeutung der Eigenschaft der gleichmäßigen Konvexität für die Optimierung. Denn mit dem bis hierhin Erreichten können wir für konvexe Optimierungsprobleme mit einer differenzierbaren, gleichmäßig konvexen Zielfunktion die Existenz und Eindeutigkeit einer Lösung unter schwachen Voraussetzungen an $Z$ garantieren.

Satz 2.41

Es seien $Z\subseteq \mathbb {R} ^{n}$ eine abgeschlossene konvexe Menge, $x^{0}\in Z$ und $f\in C^{1}(Z)$ eine auf $N(x^{0})$ gleichmäßig konvexe Funktion. Dann folgt:

(i) Die Menge $N(x^{0})$ ist kompakt.

(ii) Problem (2.43) besitzt genau eine Lösung.

Beweis.

Zum Beweis von (i) machen wir für $x\in N(x^{0})$ folgende Abschätzung, wobei wir hintereinander die Definition der gleichmäßigen Konvexität von $f$ mit Konvexitätskonstante $\beta$, die Ungleichung $f(x)\leq f(x^{0})$ und Satz 2.28 (i) verwenden:

${\frac {\beta }{8}}\left\|x-x^{0}\right\|^{2}\leq {\frac {1}{2}}f(x)+{\frac {1}{2}}f(x^{0})-f\left({\frac {1}{2}}x+{\frac {1}{2}}x^{0}\right)\leq f(x^{0})-f\left({\frac {1}{2}}x+{\frac {1}{2}}x^{0}\right)$

$\leq -{\frac {1}{2}}\nabla f(x^{0})^{T}(x-x^{0})\leq {\frac {1}{2}}\left\|f(x^{0})\right\|\left\|x-x^{0}\right\|.$

Daraus schließen wir nach Division durch $\left\|x-x^{0}\right\|$ und Anwendung der Ungleichung aus (2.1)

$\|x\|\leq {\frac {4}{\beta }}\left\|\nabla f(x^{0})\right\|+\left\|x^{0}\right\|,\quad x\in N(x^{0}).$

Also ist (i) richtig. Aussage (ii) folgt aus (i) mit den Sätzen 2.37 und 2.40.

q.e.d.

Beispiel 2.42

Es seien $b_{j},d_{i}\in \mathbb {R} ,c,a^{j},c^{i}\in \mathbb {R} ^{n}$ und $Q\in \mathbb {R} ^{n\times n}$ eine symmetrische Matrix. Das quadratische Optimierungsproblem

${\begin{array}{lll}(QP):&{\text{Minimiere}}&{\frac {1}{2}}x^{T}Qx+c^{T}x\\&{\text{u. d. N.}}&(a^{j})^{T}x-b_{j}=0\quad (j=1,\ldots ,m),\\&&(c^{i})^{T}x-d_{i}\leq 0\quad (i=1,\ldots \ldots ,l)\end{array}}$

ist ein konvexes Optimierungsproblem, wenn $Q$ positiv semidefinit ist (Lemma 2.33). Man beachte, dass eine Konstante in der Zielfunktion fortgelassen werden kann, da sich durch sie nur der Minimalwert, aber nicht die Lösungsmenge des Problems ändert. Ist $Q$ sogar positiv definit und der zulässige Bereich von $(QP)$ nichtleer, so besitzt $(QP)$ genau eine Lösung (Lemma 2.33 und Satz 2.41).

---