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).
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
über
liefert die folgende, bereits aus der Numerischen Mathematik bekannte Definition einer Norm. Es sei dabei

- Eine Abbildung
heißt Norm (auf
), falls Folgendes gilt:
- (i)

- (ii)
(Positive Homogenität),
- (iii)
(Dreiecksungleichung).
Aus den Normgesetzen leitet man die Beziehung
(2.1)

ab. Einen Vektorraum
, auf dem eine Norm
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.
und
.)
- Es sei
eine Norm auf
. Eine Folge
von Vektoren
konvergiert gegen
, kurz

- wenn gilt:

Unter Verwendung der Ungleichung in (2.1) schließt man damit:
- Eine Norm
ist eine stetige Abbildung, d. h., es gilt

Eine auf
definierte Norm bezeichnet man als Vektornorm und eine auf dem Raum
aller reellen
-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
-Norm
(2.2)

die Summen- oder
-Norm
(2.3)

und die Maximum- oder
-Norm
(2.4)

wobei jeweils
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.
-Normen für
und
sind.
Ein wichtiges Ergebnis in diesem Zusammenhang, das insbesondere für die Räume
und
relevant ist, lautet:
- Ist
ein endlich-dimensionaler Vektorraum und sind
und
zwei beliebige Normen auf
, so sind diese „äquivalent“, d. h., es gibt Konstanten
, so dass gilt:
(2.5)

Demnach ist jede Folge im
, die bezüglich irgendeiner Norm konvergiert, auch bezüglich jeder anderen Norm auf dem
konvergent. Der Beweis des Satzes kann hier nicht gegeben werden (siehe dafür z. B. [Heu92, S. 103]). Der Nachweis der Äquivalenz speziell der
-Normen auf dem
ist eine Aufgabe in der Numerischen Mathematik.
Als nächstes gehen wir auf Matrixnormen ein. Spezielle Matrixnormen für Matrizen
sind die Zeilensummennorm
(2.6)

und die Spaltensummennorm
(2.7)

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.
Man betrachte die Matrix

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

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

Im Folgenden sei
entweder eine Vektornorm auf dem
oder eine Matrixnorm auf dem Raum
, wobei durch den Inhalt „
“ von
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.
- Sei
eine Norm auf dem
. Dann heißt die durch
(2.8)

- für
definierte Norm die durch die Vektornorm
induzierte Matrixnorm.
Man beachte, dass in der Definition (2.8) von
nur die Vektornorm verwendet wird. Wegen der Kompaktheit der Menge

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 „
“ korrekt ist. Offenbar gilt für die Norm in (2.8)
(2.9)

Speziell für die Einheitsmatrix
erhält man bei beliebiger Wahl der Vektornorm für die durch diese Norm induzierte Matrixnorm

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

Weiter sei zunächst
. Dann schließt man für jedes
mit
, dass
und damit
ist. Aus den Axiomen für die Vektornorm folgt daher
für jedes
mit
. Dies ist nur für
möglich, da im Fall, dass
für mindestens ein
und
ist, für den Einheitsvektor
folgen würde:
. Ist umgekehrt
, so ergibt sich mit (2.10)

Weiter erschließt man unter Verwendung der Normaxiome für die Vektornorm mit

und für

Damit erhält man für ein geeignetes
mit


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.
- Für die in Definition 2.6 eingeführte Matrixnorm gilt
(2.11)

- sowie
(2.12)

Für
ist die Ungleichung in (2.11) trivialerweise erfüllt. Für
ergibt sie sich aus den Abschätzungen

Weiter gilt für
und damit

Im Fall
und
hat man trivialerweise

Somit folgt für alle

und damit

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
und
induzierten Matrixnormen sind.
- Sei
. Für die durch die Vektornormen
und
induzierte Matrixnorm
bzw.
gilt
(Zeilensummennorm),
(Spaltensummennorm).
Wir weisen die Behauptung für die Zeilensummennorm nach. Für jedes
gilt

Somit ergibt sich für

und demzufolge gemäß (2.9)

Zum Beweis der umgekehrten Abschätzung sei
beliebig, aber fest gewählt und
der Vektor mit Koeffizienten

Offenbar ist
. Somit schließt man
(2.13)

Da
beliebig gewählt war, folgt die behauptete Darstellung für
. 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.
Eine symmetrische Matrix
heißt positiv semidefinit, wenn

gilt und positiv definit im Fall

Bezeichnen wir die Eigenwerte von
mit
und insbesondere den größten Eigenwert von
mit
, so ist aus der Linearen Algebra folgende Aussage bekannt:
- Eine symmetrische Matrix
ist genau dann positiv semidefinit, wenn

- ist und genau dann positiv definit, wenn gilt:

Über die Eigenwerte einer Matrix definieren wir weiter:
- Für eine Matrix
heißt

- das Spektrum und

- der Spektralradius von
.
Die durch die Euklidische Vektornorm induzierte Matrixnorm einer Matrix
kann mit dem Spektralradius, d. h. dem größten Eigenwert von
dargestellt werden.
- Sei
. Für die durch die Euklidische Vektornorm
induzierte Matrixnorm
gilt

Die Matrix
ist wegen
symmetrisch und wegen

positiv semidefinit. Somit besitzt
Eigenwerte
und gibt es zu
ein System
von orthonormalen Eigenvektoren, d. h., es ist

und
(2.15)

Für
gibt es daher mit Koeffizienten
eine Darstellung
. Damit folgt

sowie
(2.16)


Somit hat man
(2.17)

Für einen Eigenvektor
zu einem maximalen Eigenwert
gilt

Folglich wird das Maximum in (2.17) für
angenommen und kann das „
“ dort durch „
“ ersetzt werden.
q.e.d.
Die Matrixnorm
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.
- Sei
eine symmetrische Matrix, d. h.
. Dann gilt
(2.18)

- Für jede andere durch eine Vektornorm induzierte Matrixnorm
folgt
(2.19)

Aufgrund der vorausgesetzten Symmetrie von
gilt
und
![{\displaystyle 0\leq \lambda _{\max(}A^{T}A)=\lambda _{\max(}A^{2})=[\lambda _{\max(}A)]^{2},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4035c14117ea40c37029a8fb906f5847d6d562bc)
da
die quadrierten Eigenwerte von
als Eigenwerte hat. Daher schließt man

Da
symmetrisch ist, sind ferner alle Eigenwerte von
reell. Ist
ein Eigenvektor zum Eigenwert
und somit
, dann folgt für eine beliebige durch die Vektornorm
induzierte Matrixnorm

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.
(1) Für die symmetrische Matrix

berechnet man die Eigenwerte
, so dass mit (2.18) folgt:

Weiter ergibt sich
. Man vergleiche hierzu (2.19).
(2) Für die nicht symmetrische Matrix
![{\displaystyle A={\begin{pmatrix}0&1\\0&1\end{pmatrix}}\quad \left[\Rightarrow A^{T}A={\begin{pmatrix}0&0\\0&2\end{pmatrix}}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2e9717e799bbbede85cc9e296df2371e83180792)
berechnet man unter Verwendung von Satz 2.12

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

In diesem Fall ist also
. Letzteres zeigt, dass auf die Voraussetzung der Symmetrie der Matrix in Satz 2.13 nicht verzichtet werden kann.
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
generell wieder eine Vektornorm oder die durch sie induzierte Matrixnorm.
- Sei
eine reguläre Matrix. Die Zahl

- heißt Kondition oder Konditionszahl der Matrix
(bezüglich der Norm
).
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:

- Sei
eine reguläre Matrix. Für die Kondition von
bezüglich der Matrixnorm
folgt
(2.20)

Die Beziehung (2.20) ergibt sich aus

q.e.d.
Die Konditionszahl
gibt also die Bandbreite an, um die sich die Vektorlänge eines Vektors
bei Multiplikation mit
ändern kann. Aus (2.20) ergibt sich zudem

wobei
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
eines Systems
mit der Lösung
eines gestörten Systems mit Matrix
und rechter Seite
verglichen, wobei die Größe der Störung, d. h.
nicht zu groß sein darf. (Einen Beweis des Satzes findet man in [Pla00].)
- Sei
eine reguläre Matrix und
eine Matrix mit
. Gilt für Vektoren 

- so folgt für den relativen Fehler von
bezüglich
die Abschätzung
(2.21)

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

Dieser Faktor ist offenbar um so größer je größer die Kondition
von
ist. Im Fall
spricht man daher von einem schlecht konditionierten Gleichungssystem. (Dabei steht „
“ für „viel größer als“.)
Für ein schlecht konditioniertes lineares Gleichungssystem können sich also kleine Eingabefehler in den „Daten“
und
sehr stark auf die Lösung des Systems
auswirken, und sie tun dies normalerweise auch. Solche Eingabefehler macht man z. B. natürlicherweise, wenn man irrationale Zahlen wie
oder
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.
Wenn nichts anderes gesagt ist, meinen wir von nun an mit
der Einfachheit halber immer die Euklidische Vektornorm bzw. die durch sie induzierte Matrixnorm, die Spektralnorm. Folglich bedeutet
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
der kleinste und
der größte Eigenwert der symmetrischen, positiv definiten Matrix
, so ist offenbar
der kleinste und
der größte Eigenwert von
. Demnach ist auch
eine symmetrische, positiv definite Matrix. Damit ergibt sich weiter für die Kondition einer solchen Matrix hinsichtlich der Spektralnorm:
(2.22)

Sei
mit
gegeben durch

Für kleines
ist diese Matrix nahezu singulär. Insbesondere errechnet man für
im Fall
die Eigenwerte

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

Ein lineares Gleichungssystem mit
als Systemmatrix ist demnach ein schlecht konditioniertes Gleichungssystem.
Wir benötigen ferner folgendes Resultat:
- Für eine symmetrische, positiv definite Matrix
gilt
(2.23)

- sowie
(2.24)

Da die Matrix
symmetrisch ist, existiert zu ihren Eigenwerten
eine Orthonormalbasis
von Eigenvektoren. Somit kann jedes
mit Koeffizienten
in der Form
dargestellt werden. Nun gilt

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

Letzteres impliziert wegen
und

die Ungleichungen in (2.23). Die Ungleichungen in (2.24) ergeben sich durch Anwendung von (2.23) auf
.
Wählt man
in (2.23) als einen zu
bzw.
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.
- Ist
eine symmetrische, positiv semidefinite Matrix und
, dann ist die Matrix
symmetrisch und positiv semidefinit. Ist überdies
positiv definit und
, dann ist auch
positiv definit.
Die Matrix
ist wegen
![{\displaystyle \left[CAC^{T}\right]^{T}=\left[C(CA)^{T}\right]^{T}=CAC^{T}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/261d12de4dd73a65f867dcc30d99337ab0bd347b)
symmetrisch und wegen
(2.25)

positiv semidefinit. Die Rangbedingung an
impliziert, dass
genau dann gilt, wenn
ist. Für
hat man daher in (2.25) „
“, wenn
positiv definit ist.
q.e.d.
Besonders einfach geformte Mengen im
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:
- Eine Menge
heißt konvex, wenn gilt:
![{\displaystyle x,y\in K,\quad t\in [0,1]\Rightarrow tx+(1-t)y\in K.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c527d6b68dd3697cdec09fc7485649ab455af476)
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.
- Hat
mit
die Gestalt

- so sagt man,
ist eine Konvexkombination der
.
Das folgende Lemma lässt sich mittels vollständiger Induktion beweisen.
- Jede Konvexkombination von endlich vielen Elementen einer konvexen Menge
ist wieder Element von
.
In Abschnitt 1.1 hatten wir bereits lineare und quadratische Funktionen eingeführt. Jede Funktion
, die auf
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
in
Veränderlichen konvex, wenn der Graph von
zwischen zwei beliebigen Punkten
und
unterhalb der Sekante liegt, welche die beiden Punkte
und
auf dem Graphen verbindet oder wenn er mit dieser Sekante zusammenfällt. Befindet sich der Graph von
, abgesehen von den beiden Punkten
und
, strikt unterhalb dieser Sekante, so bezeichnet man
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
auf
genau einen Minimalpunkt, während die strikt konvexe Funktion
für
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:
- Sei
eine Funktion und
eine konvexe Menge.
- (i)
heißt konvex auf
, falls gilt:
(2.26)
![{\displaystyle x,y\in K,\quad t\in [0,1]\Rightarrow f(tx+(1-t)y)\leq tf(x)+(1-t)f(y).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c6e5cd951ec737ec9fc271ec57d02b7d27ff53ee)
- (ii)
heißt strikt konvex auf
, falls gilt:

- (iii)
heißt gleichmäßig konvex auf
, falls eine Konstante
, genannt (gleichmäßige) Konvexitätskonstante, existiert, so dass gilt:
(2.27)
![{\displaystyle 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).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c421e793b803d59461dd11c0b03fdd788fb43337)
- (iv)
heißt konkav (strikt konkav, gleichmäßig konkav) auf
, wenn
konvex (strikt konvex, gleichmäßig konvex) auf
ist.
- Falls
ist, kann in (i) - (iv) der Zusatz „auf
“ fortgelassen werden.
Ist
eine affin-lineare Funktion der Gestalt

so gilt für alle
und
![{\displaystyle 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).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e3ae7047b2cd708fac9d5e664631d540f4e9e3b6)
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.
- Für
seien
und seien
konvexe Funktionen auf einer konvexen Menge
. Dann ist auch die Funktion
(2.28)

- 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ür
strikt konvex, aber nicht gleichmäßig konvex. Denn wäre sie gleichmäßig konvex, so erhielte man gemäß (2.26) für
und ein

Dies kann jedoch für hinreichend große
nicht richtig sein, da der rechte Ausdruck für
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.
- Seien
Funktionen und sei
die Menge
(2.29)

- (i) Sind die
und
stetig, so ist
abgeschlossen.
- (ii) Sind die
konvex und die
affin-linear, so ist
konvex.
Um die Abgeschlossenheit von
zu beweisen, zeigen wir, dass der Grenzwert jeder konvergenten Folge aus
wieder in
liegt. Sei also
eine Folge mit
und
. Dann folgt für alle
und

Es kann weder
noch
gelten, da dann auch
bzw.
für alle hinreichend großen
folgen würde. Also ist
.
Für den Nachweis der Konvexität von
seien
und

Da die
konvex und die
affin-linear sind, folgt dann


Also hat man
, womit die Konvexität von
bewiesen ist.
q.e.d.
Man beachte, dass in Aussage (ii) von Lemma 2.27 für die
Konvexität, aber für die
affine Linearität gefordert ist. Denn während eine Ungleichungsnebenbedingung
mit einer konvexen Funktion
einen konvexen Bereich definiert, tut dies eine Gleichungsrestriktion
mit einer nichtlinear-konvexen Funktion
nicht.
2.7 Charakterisierungen konvexer Funktionen
[Bearbeiten]
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.
- Sei
konvex und
. (Mit
bezeichnen wir die Menge aller auf einer offenen Obermenge
von
-mal stetig differenzierbaren Funktionen
, wobei
von
abhängen darf.) Dann gilt:
- (i)
ist auf
genau dann konvex, wenn gilt:
(2.30)

- (ii)
ist auf
genau dann strikt konvex, wenn gilt:

- (iii)
ist auf
genau dann gleichmäßig konvex mit Konstante
, wenn gilt:

„
für (i), (iii)“:
sei konvex bzw. gleichmäßig konvex auf
. Dann gilt mit
bzw.
für alle
und
:

Für
impliziert dies
(2.31)
![{\displaystyle {\frac {\beta }{2}}(1-t)\|x-y\|^{2}+{\frac {1}{t}}[f(y+t(x-y))-f(y)]\leq f(x)-f(y).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/549c4585ee10df9ee27aa388a12d9a246d2e59fc)
Nach Definition der Richtungsableitung von
bei
in Richtung
hat man

so dass Grenzwertbildung für
in (2.31) das gewünschte Ergebnis liefert:
(2.32)

„
für (ii)“: Ist
strikt konvex, dann ist
auch konvex, so dass für
gemäß (2.32) gilt:
(2.33)

Für alle
mit
und
folgt daher unter Ausnutzung von (2.33) und der strikten Konvexität von
![{\displaystyle \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)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/da71723507d56cd3e3c0167204304fa7b435c0d0)
![{\displaystyle =2\left[f\left({\frac {1}{2}}(x+y)\right)-f(y)\right]<f(x)-f(y).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2fd72408f30dbe97cf9bf86a3d21d5e9350e6853)
„
für (i), (iii)“: Mit
bzw.
sei
(2.34)

Da
eine konvexe Menge ist, liegt für
und jedes
auch
in
. Somit liefert (2.34), angewandt auf
und
bzw.
und
,


Multipliziert man die erste dieser Ungleichungen mit
und die zweite mit
und addiert man anschließend beide Ungleichungen, so erhält man
![{\displaystyle {\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)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/48eb091f24484ca1100da3cacd611f687c4df968)
![{\displaystyle \leq t[f(x)-f(z)]+(1-t)[f(y)-f(z)]=tf(x)+(1-t)f(y)-f(tx+(1-t)y).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e3d1f066f7f2571d12c4d6e9031e31793c83d66b)
Wegen der Definition von
ist dabei
![{\displaystyle {\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},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4bc4b57b6fd55ac4caf6c40d3cfc53410d482491)
womit das gewünschte Ergebnis folgt. Der Beweis der Richtung „
“ für (ii) erfolgt analog, indem man
setzt und überall „
“ gegen „
“ austauscht.
q.e.d.
Der nächste Satz charakterisiert die unterschiedlichen Konvexitätseigenschaften durch zweite Ableitungen.
- Sei
konvex und
. Dann gilt:
- (i) Ist
für alle
positiv semidefinit, so ist
konvex auf
.
- (ii) Ist
für alle
positiv definit, so ist
strikt konvex auf
.
- (iii) Gibt es eine Konstante
, so dass
(2.35)

- gilt, so ist
gleichmäßig konvex auf
mit Konstante
.
- (iv) Ist
offen, so gelten auch die Umkehrungen von (i) und (iii).
(i)-(iii): Seien
und
. Weiter sei
![{\displaystyle \varphi (t):=f(y+t(x-y)),\quad t\in [0,1].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/03285ed8fc18655e17f1e339bc8d308dbbdfbc3a)
Dann gilt nach dem Satz von Taylor mit einem

bzw.

wobei offenbar
in
liegt. Mit Satz 2.28 folgt damit unter Anwendung der im Satz geforderten Eigenschaften der Hesse-Matrix von
auf
die Behauptung.
(iv):
sei offen und
sei auf
konvex
bzw. gleichmäßig konvex
. Weiter sei
und
beliebig. Dann ist
für alle hinreichend kleinen
. Für diese
gilt nach Satz 2.28 (iii):


Addition der beiden Ungleichungen liefert
![{\displaystyle \beta t^{2}\|h\|^{2}\leq [\nabla f(x+th)-\nabla f(x)]^{T}th,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dc44fbc478da95d0ddff90e587a46fcda05f3da8)
so dass für alle hinreichend kleinen
folgt:
![{\displaystyle {\frac {1}{t}}[\nabla f(x+th)-\nabla f(x)]^{T}h\geq \beta \|h\|^{2}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/19cecb5725079b085e06852bdf8861d01d683e12)
Grenzübergang für
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
nicht gelten. Dies zeigt das folgende erste Beispiel 2.30.
(i) Sei
und
. Dann schließt man

so dass nach dem Mittelwertsatz für ein
zwischen
und
folgt:

Gemäß Satz 2.28 ist also
auf
strikt konvex. Aber es ist
.
(ii) Für
ist
. Also ist
nach Satz 2.29 strikt konvex auf
. Wegen

existiert aber kein
, so dass
für alle
und damit (2.35) gilt. Demzufolge ist
auf
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.
- Unter einer quadratischen Funktion versteht man eine Funktion
, welche durch
(2.36)

- definiert ist, wobei
und
eine symmetrische Matrix ist.
Für die quadratische Funktion in (2.36) hat man
(2.37)

Der Faktor
vor dem quadratischen Term in (2.36) bewirkt also, dass der Gradient und die Hesse-Matrix von
keinen Faktor vor
enthalten.
Die Forderung der Symmetrie von
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:


Mit Satz 2.29 lässt sich nun leicht charakterisieren, wann eine quadratische Funktion
auf dem
konvex bzw. gleichmäßig konvex ist.
- Für die quadratische Funktion
in (2.36) gilt:
- (i)
ist genau dann konvex, wenn
positiv semidefinit ist.
- (ii)
ist genau dann gleichmäßig konvex, wenn
positiv definit ist.
- (iii) Wenn
gleichmäßig konvex ist, so ist
(2.38)

- die größtmögliche Konvexitätskonstante für
.
Es ist
. 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
gleichmäßig konvex mit Konvexitätskonstante
, so ist nach Satz 2.29
positiv definit und die Ungleichung in (2.35) mit
erfüllt. Damit gilt also die linke Ungleichung in (2.23) mit
. Gemäß Bemerkung 2.20 ist
die größtmögliche Konstante für die letztere Ungleichung. Aus Teil (iii) von Satz 2.29 ergibt sich damit, dass
auch mit der Konvexitätskonstante
gleichmäßig konvex ist.
q.e.d.
Beispielsweise ist also die quadratische Funktion

auf
gleichmäßig konvex. Denn die sie definierende Matrix hat die positiven Eigenwerte
und
.
Ein praktisch relevantes Beispiel für eine quadratische Funktion ist die Funktion, welche bei der linearen Ausgleichsrechnung zu minimieren ist.
Hat ein lineares Gleichungssystem
mit
und
mehr Gleichungen als Unbekannte, so ist es typischerweise nicht lösbar. Für
macht es also Sinn, ein
als „Lösung“ zu akzeptieren, für welches der Defekt
hinsichtlich der Norm
bzw., was äquivalent damit ist, hinsichtlich der quadrierten Norm
auf dem
minimal wird. Gesucht ist dann also eine Lösung des linearen Ausgleichsproblems

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


Die Matrix
darin ist wegen
symmetrisch und wegen

positiv semidefinit. Im Fall
ist diese Matrix sogar positiv definit, da dann die Spalten von
linear unabhängig sind und folglich gilt:

Gemäß Lemma 2.33 ist die Zielfunktion des linearen Ausgleichsproblems also eine konvexe und im Fall
eine gleichmäßig konvexe, quadratische Funktion.
2.9 Problemstellung und zentrale Begriffe
[Bearbeiten]
Wir betrachten nun das allgemeine Optimierungsproblem
(2.39) Minimiere

über alle

mit zulässigem Bereich
und Zielfunktion
. 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
und den restringierten Fall, bei dem
in der Form
(2.40)

mit Funktionen
gegeben ist.
Ist
eine konvexe Menge und
konvex auf
, dann bezeichnet man das Problem (2.39) als ein konvexes Optimierungsproblem. Insbesondere ist
ein Problem der Gestalt

Speziell im Fall
liegt ein lineares Optimierungsproblem vor:

Der zulässige Bereich eines linearen und eines quadratischen Optimierungsproblems ist konvex (Lemma 2.27). Ein quadratisches Optimierungsproblem ist weiterhin genau dann konvex, wenn
eine positiv semidefinite Matrix ist (Lemma 2.33). Ergebnisse für quadratische Optimierungsprobleme mit positiv semidefiniter Matrix
sind offenbar auch auf lineare Optimierungsprobleme anwendbar. Die Voraussetzung der positiven Definitheit für
schließt aber den linearen Fall aus.
Wie ebenfalls schon Abschnitt 1.1 gesagt wurde, liegt ein nichtlineares Optimierungsproblem vor, wenn
(im unrestringierten Fall) bzw. mindestens eine der Funktionen
und
(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)

nennt man den Minimalwert von Problem (2.39). Für
ist er endlich oder
. Beispiele sind

Für den Fall
definiert man

Jedes
, für das
auf
den Minimalwert
annimmt, für das also
gilt, nennt man globale Lösung des Optimierungsproblems. Weitere Lösungsbegriffe werden mit der folgenden Definition eingeführt. Dabei bezeichne

für ein
die offene
-Umgebung von
.
- (i)
heißt globale Lösung von Problem (2.39), falls
f

- gilt und strikt globale Lösung im Fall

- (ii)
heißt lokale Lösung von Problem (2.39), falls ein
existiert, so dass
(2.42)

- gilt und strikt lokale Lösung im Fall

- Statt von einer Lösung von Problem (2.39) spricht man auch von einem Minimalpunkt oder einem Minimierer.
Im Fall, dass
eine lokale oder globale Lösung von Problem (2.39) ist, sagt man auch, dass
bzw.
sein lokales bzw. globales Minimum in
annimmt. Wir unterscheiden hier also zwischen einem Minimierer von
, einem Punkt, und einem Minimum von
, 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:
- Es sei
konvex und
eine konvexe Funktion. Dann gilt:
- (i) Jede (strikt) lokale Lösung von Problem (2.39) ist auch (strikt) globale Lösung.
- (ii) Ist
strikt konvex auf
, 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
abgeschlossen, so ist sie auch abgeschlossen.
Übung!
2.10 Existenz und Eindeutigkeit von Lösungen
[Bearbeiten]
Wir diskutieren nun als nächstes die Existenz und Eindeutigkeit von Lösungen des Optimierungsproblems
(2.43) Minimiere

über alle

,
wobei wieder
und
seien. Ist
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
genau dann kompakt ist, wenn sie abgeschlossen und beschränkt ist.)
- Jede auf einer nichtleeren kompakten Menge stetige reellwertige Funktion in
Veränderlichen nimmt dort ihr (globales) Minimum und Maximum an.
In der Praxis ist der zulässige Bereich
eines Minimierungsproblems jedoch häufig unbeschränkt und insbesondere ist er dies natürlich im Fall
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
nichtleer und dass für ein
die Niveaumenge

beschränkt ist. Bevor wir dies zeigen wollen, seien einige Eigenschaften dieser Menge aufgeführt.
- Seien
und
. Dann gilt:
- (i) Es ist
.
- (ii) Ist
eine konvexe Menge und
konvex auf
, d. h., ist das Problem (2.43) ein konvexes Optimierungsproblem, so ist
konvex.
- (iii) Ist
abgeschlossen, so ist auch
abgeschlossen.
(i) Es ist
und
. Demzufolge gilt
.
(ii) Seien
und
. Dann folgt zunächst
und wegen der Konvexität von
auch
. Da
nach Voraussetzung eine konvexe Menge ist, schließt man aus der ebenfalls vorausgesetzten Konvexität von
auf
, dass gilt:

Also hat man zusammen
und ist damit
konvex.
(iii) Sei nun
eine Folge in
, welche gegen ein
konvergiert. Dann ist per Definition
und wegen der vorausgesetzten Abgeschlossenheit von
auch
. Außerdem hat man
, so dass mit der Stetigkeit von
auch
folgt. Zusammen hat man also
, was die Abgeschlossenheit von
beweist.
q.e.d.
Im Hinblick auf die letzte Aussage stellen wir fest, dass
natürlich im Fall
abgeschlossen ist und dass
dies auch im restringierten Fall ist, wenn
gilt (vgl. Lemma 2.27). Es gilt nun, wie bereits oben gesagt wurde:
- Es seien
und
. Ist die Niveaumenge
kompakt, dann besitzt das Problem (2.43) eine globale Lösung.
Nach Satz 2.38 nimmt
unter den gegebenen Voraussetzungen sein Minimum auf der gemäß Lemma 2.39 (i) nichtleeren Menge
an, d. h., es existiert ein
, so dass gilt:

Da man für
die Beziehung
hat, folgt damit die Behauptung.
q.e.d.
Die Voraussetzung der Kompaktheit der Niveaumenge
für ein
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
beschränkt ist. Sind die Probleme insbesondere konvex, so kann man in diesem Zusammenhang beweisen, dass
für jedes
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
garantieren.
- Es seien
eine abgeschlossene konvexe Menge,
und
eine auf
gleichmäßig konvexe Funktion. Dann folgt:
- (i) Die Menge
ist kompakt.
- (ii) Problem (2.43) besitzt genau eine Lösung.
Zum Beweis von (i) machen wir für
folgende Abschätzung, wobei wir hintereinander die Definition der gleichmäßigen Konvexität von
mit Konvexitätskonstante
, die Ungleichung
und Satz 2.28 (i) verwenden:


Daraus schließen wir nach Division durch
und Anwendung der Ungleichung aus (2.1)

Also ist (i) richtig. Aussage (ii) folgt aus (i) mit den Sätzen 2.37 und 2.40.
q.e.d.
Es seien
und
eine symmetrische Matrix. Das quadratische Optimierungsproblem

ist ein konvexes Optimierungsproblem, wenn
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
sogar positiv definit und der zulässige Bereich von
nichtleer, so besitzt
genau eine Lösung (Lemma 2.33 und Satz 2.41).