Benutzer:Stepri2005/Kurs:Optimierung II/Ein Modellalgorithmus

2.1 Schrittweitenbestimmung und Trust-Region

Wir wollen uns nun Verfahren zur Lösung der unrestringierten Optimierungsaufgabe

$(P):{\text{ Minimiere }}f(x){\mbox{ über alle }}x\in \mathbb {R} ^{n}$

zuwenden. Im Allgemeinen fordern wir dabei, dass $f$ mindestens einmal stetig differenzierbar ist, und nehmen wir an bzw. werden wir durch geeignete Voraussetzungen garantieren, dass $(P)$ einen globalen Minimalpunkt besitzt.

Ein ideales Verfahren zur Lösung des Problems $(P)$, d. h. ein Verfahren mit Abbruchschranke $\nabla f(x)=0$, soll zwei Kriterien genügen. Es soll erstens in jeder Iteration einen Abstieg oder zumindest keinen Aufstieg hinsichtlich des Funktionswertes erzeugen, d. h., es soll $f(x^{k+1})<f(x^{k})$ oder zumindest $f(x^{k+1})\leq f(x^{k})$ für die Iterierten $x^{k},k=0,1,2,\ldots$ gelten. Man spricht daher auch von einem Abstiegsverfahren. Und zweitens soll jeder Häufungspunkt der vom Verfahren erzeugten unendliche Iteriertenfolge $\left\{x^{k}\right\}$ ein stationärer Punkt von $f$ sein, sofern das Verfahren nicht bereits nach endlich vielen Iterationen mit einem stationären Punkt von $f$ abbricht. (Den Grenzwert einer konvergenten Teilfolge einer Folge bezeichnet man als einen Häufungspunkt.)

Wenn der Startpunkt $x^{0}$ für ein solches Verfahren nicht gerade ein lokaler Maximalpunkt von $f$ ist, so dass das Verfahren mit diesem stationären Punkt terminiert (man sollte es dann mit einem anderen $x^{0}$ nochmals beginnen), dann ist der gefundene stationäre Punkt $x^{*}$ entweder ein lokaler Minimalpunkt oder ein Sattelpunkt von $f$. Dass $x^{*}$ ein Sattelpunkt ist, ist z. B. ausgeschlossen, wenn $f$ eine konvexe Funktion ist oder es kann möglicherweise durch die Überprüfung von Optimalitätsbedingungen zweiter Ordnung ausgeschlossen werden. Zumindest für größere Probleme ist aber eine Überprüfung solcher Bedingungen zweiter Ordnung oft numerisch zu teuer, so dass man sich zumeist damit zufrieden gibt zu wissen, dass $x^{*}$ entweder ein lokaler Minimalpunkt oder ein Sattelpunkt von $f$ ist.

Leider ist es bis heute nur für relativ „einfache“ nichtlineare Funktionen möglich, globale Minimalpunkte, an denen man ja eigentlich interessiert ist, zu bestimmen. Es lässt sich daher nicht ausschließen, dass man bei der beschriebenen Vorgehensweise in einem lokalen Minimalpunkt hängenbleibt, der einen im Vergleich mit dem Minimalwert des Problems relativ großen Funktionswert besitzt. Aus diesem Grund ist es häufig sinnvoll, ein Verfahren für ein gegebenes Problem von verschiedenen, eventuell mit einem Zufallsgenerator erzeugten Startpunkten aus zu starten, um auf diesem Wege möglicherweise unterschiedliche stationäre Punkte der Zielfunktion zu erhalten.

Wir gehen nun davon aus, dass $x^{k}$ kein kritischer Punkt von $f$ ist, also $\nabla f(x^{k})\neq 0$ gilt. Erstes Ziel, wie beschrieben, ist es dann, einen neuen Punkt $x^{k+1}$ zu bestimmen, für den der Funktionswert von $f$ kleiner oder zumindest nicht größer als der Funktionswert bei $x^{k}$ ist. In diesem Zusammenhang definieren wir:

Definition 2.1

Ein Vektor $p\in \mathbb {R} ^{n}$ heißt Abstiegsrichtung für $f:\mathbb {R} ^{n}\to \mathbb {R}$ in $x\in \mathbb {R} ^{n}$, falls ein $t_{1}>0$ existiert, so dass gilt:

(2.1) $f(x+tp)<f(x),\quad t\in (0,t_{1}].$

Schreiben wir $x^{k+1}:=x^{k}+t_{k}p^{k}$, so geht es also darum, für einen nichtkritischen Punkt $x^{k}$ eine Abstiegsrichtung $p^{k}$ und eine geeignete Schrittweite $t_{k}>0$ zu bestimmen bzw., wenn wir ${\tilde {p}}^{k}:=t_{k}p^{k}$ setzen, eine Abstiegsrichtung ${\tilde {p}}^{k}$ mit geeigneter Länge $\left\|{\tilde {p}}^{k}\right\|$ zu finden. (Mit $p^{k}$ ist offenbar auch ${\tilde {p}}^{k}$ Abstiegsrichtung.) Die Schrittweite $t_{k}$ bzw. die Länge $\left\|{\tilde {p}}^{k}\right\|$ von ${\tilde {p}}^{k}$ darf dabei nicht zu groß sein, da anderenfalls auch für eine Abstiegsrichtung die Funktionswerte normalerweise wieder ansteigen.

In diesem Zusammenhang gibt es nun zwei grundsätzlich verschiedene Vorgehensweisen. Bei den meisten bekannten Verfahren wird zunächst eine Abstiegsrichtung und anschließend eine geeignete Schrittweite bestimmt. Bei den Trust-Region-Verfahren dagegen kombiniert man die Richtungssuche und die Schrittweitenbestimmung, indem man $f(x^{k}+p)$ z. B. durch eine quadratische Näherung $q_{k}(p)$ ersetzt und für eine passend gewählte Konstante $\Delta _{k}$ das folgende Teilproblem mit einer Nebenbedingung bezüglich $p\in \mathbb {R} ^{n}$ löst:

(2.2) ${\begin{array}{ll}{\text{Minimiere}}&q_{k}(p)\\{\text{u. d. N.}}&\|p\|\leq \Delta _{k}.\end{array}}$

Die Konstante $\Delta _{k}$ in diesem Problem definiert ein „trust region“, einen Vertrauensbereich, in dem die gesuchte Richtung liegen darf. Ob eine Lösung ${\tilde {p}}^{k}$ dieses Problems akzeptabel ist, muss anschließend entschieden werden. (Nach dem Satz von Weierstraß besitzt das Problem (2.2) für stetiges $q_{k}$ eine Lösung.) Falls eine Lösung nicht brauchbar ist, muss $\Delta _{k}$ verkleinert und muss das Problem (2.2) erneut gelöst werden. Die Funktion $f(x^{k}+p)$ selbst kann man in einem solchen Teilproblem übrigens nicht als Zielfunktion verwenden, da dieses Problem dann von demselben Schwierigkeitsgrad oder wegen der zusätzlichen Restriktion sogar von einem höheren Schwierigkeitsgrad wie das eigentlich zu lösende Problem $(P)$ wäre.

Die meisten Verfahren, die wir vorstellen werden, sind vom ersten Typ und erfordern eine Schrittweitenbestimmung. Jedoch werden wir in Kapitel 8 auch Trust-Region-Verfahren diskutieren. Die Kritiker von Trust-Region-Verfahren bemängeln vor allem, dass die Richtung, in welche eine Lösung ${\tilde {p}}^{k}$ des Teilproblems zeigt, zumeist stark von der Wahl von $\Delta _{k}$ abhängt und dass man die Richtung für einen Abstiegsschritt nicht von einer für den Schritt vorgegebenen Länge abhängig machen sollte.

Letzteres ist so, als ob man sich im Gebirge, wenn man dort einen Weg ins Tal sucht, als erstes eine Länge für den nächsten Schritt vorgibt und man erst anschließend eine geeignete Richtung wählt. Auf der anderen Seite kennt man bei den Verfahren, welche eine Schrittweitenbestimmung erfordern, zwar die Richtung, in die man einen Abstieg erzielen möchte (die Verfahren unterscheiden sich vor allem durch die Wahl der Richtungen), die Schrittweitenbestimmung kann aber sehr viele Funktionsauswertungen erfordern und es besteht die Gefahr, dass Schrittweiten gewählt werden, die für den weiteren Verlauf des Verfahrens z. B. zu klein und damit ungünstig sind. In der Praxis haben sich aber beide Typen von Verfahren bewährt, zum Teil in unterschiedlichen Zusammenhängen.

2.2 Ein Modellalgorithmus

Wir wollen nun zunächst nur Algorithmen mit einer Schrittweitenstrategie betrachten und in diesem Abschnitt ein Grundmodell für derartige Algorithmen diskutieren. Zunächst stellen wir eine einfache Bedingung bereit, mit deren Hilfe wir leicht Abstiegsrichtungen in einem vorgegebenen Punkt angeben können.

Lemma 2.2

Es sei $f\in C^{1}(\mathbb {R} ^{n})$. Gilt für $p$

$\nabla f(x)^{T}p<0,$

so ist $p$ Abstiegsrichtung für $f$ in $x$.

Beweis.

Die Definition der Richtungsableitung von $f$ bei $x$ in Richtung $p$ liefert

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

Folglich gilt für ein $t_{1}>0$

${\frac {f(x+tp)-f(x)}{t}}<0,\quad t\in (0,t_{1}]$

und ist somit (2.1) richtig.

q.e.d.

Beispiel 2.3

Es sei $f\in C^{1}(\mathbb {R} ^{n})$ und es sei $H\in \mathbb {R} ^{n\times n}$ eine symmetrische, positiv definite Matrix. Für ein $x$ mit $\nabla f(x)\neq 0$ ist dann der Vektor $p$ mit

$p:=-H\nabla f(x)$

Abstiegsrichtung für $f$ in $x$, da gilt:

$\nabla f(x)^{T}p=-\nabla f(x)^{T}H\nabla f(x)<0.$

Insbesondere erhält man für $H:=I$ die Abstiegsrichtung

(2.4) $p:=-\nabla f(x).$

---

Die auf 1 normierte Abstiegsrichtung in (2.4) ist, wie in Optimierung I gezeigt worden war, die eindeutige Lösung des Optimierungsproblems

(2.5) ${\begin{array}{ll}{\text{Minimiere}}&\nabla f(x)^{T}p\\{\text{u. d. N.}}&\|p\|=1.\end{array}}$

Sie wird als Richtung des steilsten Abstiegs bezeichnet. Man kann sie lokal als „beste“ Abstiegsrichtung ansehen. Global gesehen muss sie es dies jedoch nicht sein.

Bemerkung 2.4

Die Definition der Richtung des steilsten Abstiegs kann mittels einer symmetrischen positiv definiten Matrix $A\in \mathbb {R} ^{n\times n}$ verallgemeinert werden, wobei man mittels $A$ das Skalarprodukt

$\langle x,y\rangle _{A}:=x^{T}Ay,\quad x,y\in \mathbb {R} ^{n}$

und darüber die Norm

$\|x\|_{A}:=\langle x,x\langle _{A}^{1/2},$

eine sog. elliptische Norm, auf dem $\mathbb {R} ^{n}$ definiert. Ist nun $f\in C^{1}(\mathbb {R} ^{n})$ und $x$ ein Punkt mit $\nabla f(x)\neq 0$, so lässt sich zeigen, dass

$p^{*}:=-{\frac {A^{-1}\nabla f(x)}{\|A^{-1}\nabla f(x)\|_{A}}}$

die eindeutige Lösung der Optimierungsaufgabe

(2.6) ${\begin{array}{ll}{\text{Minimiere}}&\nabla f(x)^{T}p\\{\text{u. d. N.}}&\|p\|_{A}=1.\end{array}}$

ist. Der Vektor $-A^{-1}\nabla f(x)$ ist demnach die Richtung des steilsten Abstiegs in $x$ bezüglich $\|\cdot \|_{A}$ und für den optimalen Zielfunktionswert von (2.6) gilt $\nabla f(x)^{T}p^{*}<0$.

Wir wollen nun den folgenden Algorithmus betrachten, der ein Modell für Algorithmen mit Schrittweitenbestimmung zur Lösung von $(P)$ darstellt.

Modellalgorithmus 2.5

(0) (Initialisierung)
Wähle $x^{0}\in \mathbb {R} ^{n}$. Setze $k:=0$.

(1) (Abbruchkriterium)
Falls $\nabla f(x^{k})=0$ ist, stop!

(2) (Bestimmung einer Abstiegsrichtung)
Bestimme ein $p^{k}\in \mathbb {R} ^{n}$ mit $\nabla f(x^{k})^{T}p^{k}<0$.

(3) (Bestimmung einer Schrittweite)
Bestimme ein $t_{k}>0$ mit $f(x^{k}+t_{k}p^{k})<f(x^{k})$.

(4) (Bestimmung der nächsten Iterierten)
Setze $x^{k+1}:=x^{k}+t_{k}p^{k},k:=k+1$ und gehe nach (1).

Im Hinblick auf Konvergenzuntersuchungen wird im Modellalgorithmus das ideale Abbruchkriterium „$\nabla f(x^{k})=0$“ verwendet. Für die Praxis ist dieses durch ein realistisches Abbruchkriterium zu ersetzen. In diesem Zusammenhang wird zumeist das Kriterium

$\left\|\nabla f(x^{k})\right\|\leq \varepsilon$

für ein vorgegebenes $\varepsilon >0$ genutzt. Man bedenke jedoch, dass es Funktionen wie die Funktion $f(x):=10^{-6}x^{2}$ gibt, für welche $\nabla f(x^{k})\approx 0$ auch für Punkte $x^{k}$ gilt, die noch weit von einer kritischen Lösung $x^{*}$ des Problems entfernt sind.

Deshalb kann es beispielsweise sinnvoll sein, für den Abbruch eines Verfahrens (zusätzlich) zu fordern, dass die Bedingung

$\left|f(x^{k})-f(x^{k-1})\right|/\left|f(x^{k-1})\right|\leq \delta _{1}$

über einige Iterationen hinweg für ein genügend kleines $\delta _{1}>0$ erfüllt ist, da dann keine signifikante Verminderung des Funktionswertes von $f$ mehr zu erwarten ist. Mit einer Iteration ist hier - und analog bei anderen Verfahren - ein Durchlauf der Schritte (1) bis (4) des Modellalgorithmus 2.5 gemeint. Letzteres Kriterium zielt darauf ab, dass die Größe des beim Abbruch eines Verfahrens erreichten Funktionswertes $f(x^{k})$ in der Praxis häufig viel interessanter ist als die Größe der Abweichung $\left\|x^{k}-x^{*}\right\|$. Ist man an der Genauigkeit von $x^{k}$ selbst interessiert, so kann man (zusätzlich) auch das Kriterium

$\left\|x^{k}-x^{k-1}\right\|/\left\|x^{k-1}\right\|\leq \delta _{2}$

für ein $\delta _{2}>0$ heranziehen.

Die zentralen Schritte (2) und (3) des Algorithmus sind prinzipiell ausführbar (was nicht heißt, dass ein entsprechend spezifizierter Algorithmus auch konvergieren muss). Denn in Schritt (2) kann man offenbar z. B. die Richtung steilsten Abstiegs $p^{k}:=-\nabla f(x^{k})$ als Abstiegsrichtung wählen. (Es ist dort ja $\nabla f(x^{k})\neq 0$.) Bei dieser Richtungswahl spricht man von dem Gradientenverfahren, das wir in Abschnitt 4 genauer untersuchen wollen. Ferner existiert gemäß der Definition 2.1 einer Abstiegsrichtung und gemäß Lemma 2.2 immer eine Schrittweite $t_{k}>0$, wie sie in Schritt (3) des Modellalgorithmus zu bestimmen ist.

Da der Wert $\varphi _{k}(t):=f(x^{k}+tp^{k})$ in der $k$-ten Iteration eines Verfahrens vom Typ des Modellalgorithmus möglichst klein werden sollte, liegt es zumindest aus theoretischer Sicht zunächst nahe, als Schrittweite ein $t_{k}$ zu wählen, für welches

(2.7) $f(x^{k}+t_{k}p^{k})=\min _{t\in [0,\infty )}f(x^{k}+tp^{k})$

gilt, d. h., für welches die eindimensionale Funktion $\varphi _{k}$ auf $[0,\infty )$ ein globales Minimum annimmt. Dass eine solche Minimumschrittweite existiert, werden wir unter relativ schwachen Voraussetzungen in Abschnitt 3.1 zeigen. Aus numerischer Sicht ist aber die Bestimmung des globalen Minimums einer nichtkonvexen Funktion eine Aufgabe, die im Allgemeinen nicht oder bestenfalls nur näherungsweise gelöst werden kann. Es wird deshalb erforderlich sein, auch noch andere Regeln zur Bestimmung von Schrittweiten zu diskutieren.

Der Modellalgorithmus bricht also entweder nach endlich vielen Schritten mit einer kritischen Lösung von $(P)$ ab oder er erzeugt eine unendliche Folge $\left\{x^{k}\right\}$ mit

(2.8) $f(x^{k+1})<f(x^{k})<f(x^{0}),\quad k\in \mathbb {N} .$

Für jedes spezielle Verfahren vom Typ des Modellalgorithmus ist demnach zu zeigen, dass eine solche durch das Verfahren erzeugte Iteriertenfolge für jeden geeigneten Startpunkt $x^{0}$ mindestens einen Häufungspunkt besitzt und dass zumindest ein Häufungspunkt oder besser noch, dass jeder Häufungspunkt dieser Folge eine kritische Lösung von $(P)$ ist. Bevor wir auf spezielle Verfahren, d. h. spezielle Richtungs- und Schrittweitenstrategien eingehen werden, wollen wir eine Reihe von allgemeinen Aussagen zur Konvergenz des Modellalgorithmus selbst herleiten. Diese Aussagen werden zum einen Richtungs- und Schrittweitenwahlen motivieren und zum anderen für den Nachweis der Konvergenz im Spezialfall nützlich sein.

2.3 Standardvoraussetzungen

Zunächst einmal stellen wir Standardvoraussetzungen bereit, auf die wir uns durchgängig beziehen werden:

(V1) $f\in C^{1}(\mathbb {R} ^{n}).$

(V2) Für ein $x^{0}\in \mathbb {R} ^{n}$ ist die Niveaumenge

(2.9) $N_{0}:=N(x^{0})=\left\{x\in \mathbb {R} ^{n}{\big |}f(x)\leq f(x^{0})\right\}$

kompakt, wobei $x^{0}$ im Zusammenhang mit einem Verfahren der Startpunkt des Verfahrens ist.

(V3) Der Gradient $\nabla f$ ist auf $N_{0}$ Lipschitz-stetig, d. h., es existiert eine Konstante $\gamma >0$ derart, dass gilt:

(2.10) $\|\nabla f(x)-\nabla f(y)\|\leq \gamma \|x-y\|,\quad x,y\in N_{0}.$

Gelegentlich, insbesondere für globale Konvergenzaussagen, werden wir zusätzlich noch folgende Bedingung voraussetzen (vgl. dazu Satz 1.3):

(V4) Die Niveaumenge $N_{0}$ ist konvex und $f$ ist gleichmäßig konvex auf $N_{0}$, d. h., es existiert eine Konstante $\beta >0$ mit

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

Diese Voraussetzungen haben einige Implikationen, welche in der nachstehenden Bemerkung erläutert sind.

Bemerkung 2.6

(i) Die Voraussetzung (V2) sichert nach Satz 1.8, dass das Problem $(P)$ eine Lösung besitzt. Zum anderen garantiert sie nach dem aus der Analysis II bekannten Satz von Bolzano-Weierstraß, dass jede Folge $\left\{x^{k}\right\}$ mit $x^{k}\in N_{0}$ bzw. mit $f(x^{k})\leq f(x^{0})$ einen Häufungspunkt in $N_{0}$ hat. Wegen (2.8) erzeugen Abstiegsverfahren solche Folgen.

(ii) Die Voraussetzung (V3) ist erfüllt, wenn (V2) erfüllt und $f\in C^{2}(K)$ für eine kompakte, konvexe Menge $K\supseteq N_{0}$ ist. (Letzteres ist wegen (V2) offenbar gegeben, wenn $f\in C^{2}(\mathbb {R} ^{n})$ ist.) Denn dann existiert

(2.11) $\gamma :=\max _{z\in K}\left\|\nabla ^{2}f(z)\right\|$

und ist $x+t(y-x)\in K$ für alle $x,y\in N_{0}$ und $t\in [0,1]$. Für

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

folgt dann für alle $x,y\in N_{0}$ mit einem $\vartheta \in (0,1)$ nach dem Mittelwertsatz $u(1)-u(0)=u'(\vartheta )$ bzw.

$\nabla f(y)-\nabla f(x)=\nabla ^{2}f(x+\vartheta (y-x))(y-x).$

Letzteres impliziert die Ungleichung (2.10) mit $\gamma$ aus (2.11).

(iii) Die Voraussetzungen (V1) und (V4) zusammen implizieren, dass die gemäß (V4) konvexe Niveaumenge $N_{0}$ für jedes $x^{0}$ kompakt ist und damit (V2) gilt (Satz 1.9). Ferner garantieren sie, dass das Problem $(P)$ genau einen kritischen Punkt $x^{*}$ besitzt, welcher die eindeutige Lösung von $(P)$ ist (Korollar 1.18).

Als Beispiel betrachten wir quadratische Funktionen.

Beispiel 2.7

Es sei $Q\in \mathbb {R} ^{n\times n}$ symmetrisch und positiv semidefinit und $f$ die somit konvexe quadratische Funktion

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

Unter Verwendung der oberen Schranke aus (1.10) und der Symmetrie von $Q$ erhält man dann, wenn $\lambda _{i}(A)$ die Eigenwerte einer Matrix $A\in \mathbb {R} ^{n\times n}$ bezeichnet:

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

$=(x-y)^{T}Q^{T}Q(x-y)\leq \lambda _{\max(}Q^{T}Q)\|x-y\|^{2}=\lambda _{\max(}Q^{2})\|x-y\|^{2}=[\lambda _{\max(}Q)]^{2}\|x-y\|^{2}.$

Neben (V1) genügt $f$ also auch der Voraussetzung (V3) mit

(2.12) $\gamma :=\lambda _{\max(}Q),$

wobei dieses $\gamma$ offenbar die kleinst mögliche Konstante für $f$ ist, für welche (V3) gilt. Ist $Q$ positiv definit, so ist zusätzlich (V4) erfüllt (Lemma 1.13) und damit auch (V2) (Bemerkung 2.6 (iii)). Es kann dann insbesondere

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

gewählt werden. Für positiv definites $Q$ gilt somit gemäß (1.9) hinsichtlich der Spektralnorm

(2.14) $\operatorname {cond} (Q)={\frac {\lambda _{\max(}Q)}{\lambda _{\min(}Q)}}={\frac {\gamma }{\beta }}$

Dabei ist $\beta$ die gleichmäßige Konvexitätskonstante von $f$ und $\gamma$ die Lipschitz-Konstante von $\nabla f$.

---

2.4 Hilfsmittel

In diesem Abschnitt stellen wir einige Hilfsmittel bereit, die wir zur Untersuchung des Modellalgorithmus benötigen werden.

In jeder Iteration des Modellalgorithmus 2.5 sind, ausgehend von einem Punkt $x$ mit $\nabla f(x)\neq 0$, eine Abstiegsrichtung $p$, eine Schrittweite $t>0$ und damit ein neuer Punkt $x+tp$ zu bestimmen, so dass ein Abstieg bezüglich des Funktionswertes von $f$ erzielt wird. (Der Einfachheit halber lassen wir hier den Iterationsindex weg.) Das folgende Lemma gibt für solche Vektoren $x$ und $p$ ein Intervall von Schrittweiten an, in dem die Funktion

(2.15) $\psi (t):=f(x)-f(x+tp)$

positive Werte annimmt und demnach eine Reduktion des Zielfunktionswertes von Problem $(P)$ möglich ist.

Lemma 2.8

Es seien (V1) und (V2) erfüllt und

$x\in N_{0},\quad p\in \mathbb {R} ^{n}\ mit\ \nabla f(x)^{T}p<0$

gegeben. Dann besitzt die in (2.15) definierte Funktion $\psi \in C^{1}(\mathbb {R} )$ eine kleinste positive Nullstelle ${\hat {t}}:={\hat {t}}(x,p)>0$ und es gilt mit einem $\kappa \geq {\hat {t}}$

$\psi (t)>0,~t\in (0,{\hat {t}});\quad x+tp\in N_{0},~t\in [0,{\hat {t}}];\quad x+tp\notin N_{0},~\psi (t)<0,~t\geq \kappa .$

Beweis.

Es ist $\psi (0)=0$ und es folgt

(2.16) $\psi '(t)=-\nabla f(x+tp)^{T}p,\quad \psi '(0)=-\nabla f(x)^{T}p>0.$

Somit existiert ein $\delta >0$, so dass $\psi (t)>0$ für alle $t\in (0,\delta )$ gilt. Da $N_{0}$ beschränkt und $p\neq 0$ ist, hat man ferner $x+tp\notin N_{0}$ für alle genügend großen $t>0$ und hat man somit für diese $t$

$f(x+tp)>f(x^{0})\geq f(x).$

Also existiert ein $\kappa >0$, so dass $x+tp\notin N_{0}$ sowie $\psi (t)<0$ für alle $t\geq \kappa$ gilt.

Damit ist die Menge

$N:=\{t\in [\delta ,\kappa ]{\big |}\psi (t)=0\}$

der Nullstellen von $\psi$ nichtleer. Sie ist ferner kompakt, so dass nach dem Satz von Weierstraß ein ${\hat {t}}:=\min _{t\in N}t$, d. h. eine kleinste positive Nullstelle existiert. Mit den anfangs genannten Eigenschaften von $\psi$ schließt man daher, dass $\psi (t)>0$ für $t\in (0,{\hat {t}})$ sowie $\psi (t)\geq 0$ für $t\in [0,{\hat {t}}]$ gilt und damit $\kappa \geq {\hat {t}}$ ist. Weil $x$ in $N_{0}$ liegt, impliziert Letzteres

$f(x+tp)\geq f(x)\geq f(x^{0})$

und somit $x+tp\in N_{0}$ für alle $t\in [0,{\hat {t}}]$.

q.e.d.

Unter den Voraussetzungen (V1) - (V4) können wir einige sehr nützliche Abschätzungen für gleichmäßig konvexe Funktionen beweisen. Es sei daran erinnert, dass das Problem $(P)$ unter diesen Voraussetzungen eine eindeutige Lösung $x^{*}$ besitzt (Bemerkung 2.6 (iii)). Wegen $f(x^{*})\leq f(x^{0})$ liegt diese in $N_{0}$.

Lemma 2.9

Es seien (V1) - (V4) erfüllt und es sei $x^{*}\in N_{0}$ die Lösung von $(P)$. Dann gilt mit $\beta$ und $\gamma$ aus (V4) bzw. (V3) für alle $x,y\in N_{0}$:

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

(ii) $\beta \|y-x\|^{2}\leq (\nabla f(y)-\nabla f(x))^{T}(y-x),$

(iii) ${\frac {\beta }{2}}\|x-x^{*}\|^{2}\leq f(x)-f(x^{*}),$

(iv) $\|x-x^{*}\|\leq {\frac {1}{\beta }}\|\nabla f(x)\|,$

(v) $f(x)-f(x^{*})\leq {\frac {1}{2\beta }}\|\nabla f(x)\|^{2},$

(vi) ${\frac {1}{2\gamma }}\|\nabla f(x)\|^{2}\leq f(x)-f(x^{*}).$

Beweis.

Seien $x,y$ und $x^{*}$ wie vorgegeben. Man beachte, dass $N_{0}$ gemäß (V4) eine konvexe Menge ist und somit $x+s(y-x)\in N_{0}$ für alle $s\in [0,1]$ gilt.

(i) Die linke Ungleichung von (i) wird durch (V4) impliziert (vgl. Satz 1.3 (iii)). Sei nun $\phi \in C^{1}[0,1]$ durch $\phi (t):=f(x+t(y-x))$ definiert. Dann ist

$\phi '(s)=\nabla f(x+s(y-x))^{T}(y-x)$

und

(2.17) $f(y)-f(x)=\phi (1)-\phi (0)=\phi '(0)+\int _{0}^{1}[\phi '(s)-\phi '(0)]\,ds.$

Unter Verwendung der Cauchy-Schwarz-Ungleichung und von (V3) gilt dabei

$\int _{0}^{1}[\phi '(s)-\phi '(0)]\,ds=\int _{0}^{1}[\nabla f(x+s(y-x))-\nabla f(x)]^{T}(y-x)\,ds$

(2.18) $\leq \int _{0}^{1}\|\nabla f(x+s(y-x))-\nabla f(x)\|\|y-x\|\,ds\leq \int _{0}^{1}\gamma s\|y-x\|^{2}\,ds={\frac {\gamma }{2}}\|y-x\|^{2}.$

Damit ergibt sich die rechte Ungleichung von (i) aus (2.17).

(ii) Die linke Ungleichung in (i) liefert

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

und mit vertauschten Rollen von $x$ und $y$

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

Addition von beiden Ungleichungen ergibt die gewünschte Beziehung.

(iii), (iv) Für $y:=x$ und $x:=x^{*}$ folgt wegen $\nabla f(x^{*})=0$ aus der linken Ungleichung von (i) die Abschätzung in (iii) und aus der Ungleichung in (ii) die Abschätzung in (iv) mit

$\beta \|x-x^{*}\|^{2}\leq \nabla f(x)^{T}(x-x^{*})\leq \|\nabla f(x)\|\|x-x^{*}\|.$

(v) Die Funktion

$g_{x}(h):={\frac {\beta }{2}}h^{T}h+\nabla f(x)^{T}h,\quad h\in \mathbb {R} ^{n}$

ist nach Lemma 1.13 gleichmäßig konvex und nimmt folglich ihr Minimum in genau einem Punkt $h^{*}$ an, für den gilt:

$\nabla g_{x}(h^{*})=0\Leftrightarrow h^{*}+\nabla f(x)=0,h^{*}=-{\frac {1}{\beta }}\nabla f(x).$

Wegen der Kompaktheit von $N_{0}$ und unter Verwendung von (i) folgt damit

$g_{x}(h^{*})=-{\frac {1}{2\beta }}\|\nabla f(x)\|^{2}=\min _{h\in \mathbb {R} ^{n}}g_{x}(h)\leq \min _{y\in N_{0}}g_{x}(y-x)=\min _{y\in N_{0}}\left\{{\frac {\beta }{2}}\|y-x\|^{2}+\nabla f(x)^{T}(y-x)\right\}$

$\leq \min _{y\in N_{0}}\{f(y)-f(x)\}=f(x^{*})-f(x).$

(vi) Es sei ${\hat {y}}:=x-{\frac {1}{\gamma }}\nabla f(x)$. Wir zeigen zunächst, dass ${\hat {y}}\in N_{0}$ ist. Da dies für $\nabla f(x)=0$ trivial ist, können wir dabei $\nabla f(x)\neq 0$ annehmen.

Nach Lemma 2.8 angewandt auf $p:=-\nabla f(x)$ besitzt die Funktion

$\chi (t):=f(x)-f(x-t\nabla f(x)),\quad t\geq 0$

eine erste positive Nullstelle ${\hat {t}}$ und ist $x-t\nabla f(x)\in N_{0}$ für alle $t\in [0,{\hat {t}}]$. Ferner folgt mit der rechten Ungleichung von (i)

$0=f(x-{\hat {t}}\nabla f(x))-f(x)\leq {\frac {\gamma }{2}}{\hat {t}}^{2}\|\nabla f(x)\|^{2}-{\hat {t}}\|\nabla f(x)\|^{2}$

und daraus ${\hat {t}}\geq 2/\gamma \geq 1/\gamma$. Demnach ist ${\hat {y}}\in N_{0}$. Unter Ausnutzung der Optimalität von $x^{*}$ und der von Aussage (i) erhalten wir schließlich

$f(x^{*})-f(x)\leq f({\hat {y}})-f(x)\leq {\frac {1}{2\gamma }}\|\nabla f(x)\|^{2}-{\frac {1}{\gamma }}\|\nabla f(x)\|^{2}=-{\frac {1}{2\gamma }}\|\nabla f(x)\|^{2}.$

q.e.d.

Bemerkung 2.10

Für $f(x):={\frac {1}{2}}x^{T}x$ können wir gemäß Beispiel 2.7

$\beta =\lambda _{\min(}I)=1,\quad \gamma =\lambda _{\max(}I)=1$

wählen. Wie man leicht nachprüft, gelten für dieses $f$ alle Ungleichungen in Lemma 2.9 mit Gleichheit. Sie können also nicht mehr verschärft werden.

Man beachte, dass die gleichmäßige Konvexität von $f$ unter den Voraussetzungen von Lemma 2.9 also insbesondere eine obere Abschätzung des Fehlers $\|x-x^{*}\|$ durch $f(x)-f(x^{*})$ liefert, was für den Nachweis der Konvergenz von Verfahren genutzt werden wird. Eine obere Abschätzung umgekehrt von $f(x)-f(x^{*})$ durch $\|x-x^{*}\|$ hat man ja für jede Lipschitz-stetige Funktion, also für jede Funktion $f\in C^{1}(\mathbb {R} ^{n})$.

2.5 Bedingungen an die Schrittweiten

Als die ersten Verfahren zur Lösung unrestringierter Optimierungsprobleme entwickelt wurden, wurde immer wieder Konvergenz von Verfahren bewiesen, die sich „nur“ durch die Schrittweitenregel unterschieden. Es war daher irgendwann sinnvoll zu fragen, welche Eigenschaften eine Schrittweitenregel besitzen sollte, damit Konvergenz für ein Verfahren nachgewiesen werden kann. Die Herleitung zweier Bedingungen in diesem Zusammenhang, welche zu den Definitionen einer effizienten und einer semieffizienten Schrittweitenregel führen werden, sind Thema dieses Abschnitts.

Lemma 2.8 gibt für ein $x$ und eine Abstiegsrichtung $p$ ein offenes Intervall $(0,{\hat {t}})$ an, in dem die Funktion

(2.19) $\psi (t):=f(x)-f(x+tp)$

positiv ist, also der Zielfunktionswert von Problem $(P)$ verkleinert werden kann. Es ist jedoch zu vermuten, dass die Iteriertenfolge eines Abstiegverfahrens bei einer, je nach Entfernung von dem angestrebten kritischen Punkt, zu geringen Verminderung des Zielfunktionswertes von $(P)$ pro Iteration nicht konvergieren könnte (s. [Alt02, S. 76] für ein Beispiel). Wegen $\psi (0)=\psi ({\hat {t}})=0$ sollte daher die Schrittweite nicht zu nahe bei 0 oder ${\hat {t}}$ liegen bzw. sollte $\psi (t)$ genügend groß sein. Das nächste Lemma dient dazu, eine geeignete Forderung an die Schrittweiten zu formulieren.

Lemma 2.11

Es seien (V1) - (V3) erfüllt und

$x\in N_{0},\quad p\in \mathbb {R} ^{n}\ mit\ \nabla f(x)^{T}p<0$

gegeben. Weiter sei ${\hat {t}}:={\hat {t}}(x,p)>0$ die nach Lemma 2.8 existierende erste positive Nullstelle von $\psi$ in (2.19). Dann gilt:

(i) ${\hat {t}}\geq {\frac {2}{\gamma }}{\frac {\nabla f(x)^{T}p}{\|p\|^{2}}}:={\tilde {t}}>0.$

(ii) $\psi (t)\geq -t\nabla f(x)^{T}p-t^{2}{\frac {\gamma }{2}}\|p\|^{2}:=\Psi (t),\quad t\in [0,{\hat {t}}].$

Beweis.

Nach Lemma 2.8 hat man $x+tp\in N_{0}$ für alle $t\in [0,{\hat {t}}]$. Weiter ist $\psi (0)=0$ und somit

$\psi (t)=\psi '(0)t+\int _{0}^{t}[\psi '(s)-\psi '(0)]\,ds.$

Für alle $t\in [0,{\hat {t}}]$ folgt daher unter Anwendung von (V3) mit einer ähnlichen Abschätzung für das Integral wie in (2.18)

(2.20) $f(x)-f(x+tp)=-t\nabla f(x)^{T}p-\int _{0}^{t}[\nabla f(x+sp)-\nabla f(x)]^{T}p\,ds\geq -t\nabla f(x)^{T}p-t^{2}{\frac {\gamma }{2}}\|p\|^{2}.$

Damit ist (ii) bewiesen. Setzt man $t:={\hat {t}}$ in (2.20) ein, so erhält man wegen $\psi ({\hat {t}})=0$ die Abschätzung in (i).

q.e.d.

In Lemma 2.11 werden ein ${\tilde {t}}\in [0,{\hat {t}}]$ und die Parabel

$\Psi (t):=-t\nabla f(x)^{T}p-t^{2}{\frac {\gamma }{2}}\|p\|^{2},\quad t\in \mathbb {R}$

definiert. Wie man nachrechnet, gilt insbesondere $\Psi (0)=\Psi ({\tilde {t}})=0$ und nimmt die Funktion $\Psi$ ihr Maximum bei

(2.21) ${\frac {\tilde {t}}{2}}=-{\frac {1}{\gamma }}{\frac {\nabla f(x)^{T}p}{\|p\|^{2}}}\in [0,{\hat {t}}]$

an. Das Maximum von $\Psi$ hat den Wert

(2.22) $\max _{t\in [0,{\hat {t}}]}\Psi (t)=\Psi \left({\frac {\tilde {t}}{2}}\right)=-{\frac {1}{2\gamma }}\left\{{\frac {\nabla f(x)^{T}p}{\|p\|}}\right\}^{2}.$

Nach Lemma 2.11 gilt ferner $\psi (t)\geq \Psi (t)$ für alle $t\in [0,{\hat {t}}]$. Wünschenswert ist es nun, dass $\psi (t)$, d. h. die Verminderung des Zielfunktionswertes von $f$ beim Übergang von $x$ zu $x+tp$ die Größenordnung von $\{\nabla f(x)^{T}p/\|p\|\}^{2}$ besitzt und idealerweise größer oder gleich dem maximalen Wert von $\Psi$ aus (2.22) ist. Letzteres ist insbesondere für eine Minimumschrittweite (2.7) der Fall, wie mit Satz 3.3 gezeigt werden wird. Aus diesem Grund definiert man:

Definition 2.12

Eine Schrittweitenregel heißt effizient (mit Konstante $\vartheta$), wenn sie jedem Paar

$x\in N_{0},\quad p\in \mathbb {R} ^{n}\ mit\ \nabla f(x)^{T}p<0$

ein wohldefiniertes (nicht notwendig eindeutig bestimmtes) $t:=t(x,p)>0$ zuordnet und wenn ein von $x,p$ und $t$ unabhängiges $\vartheta >0$ existiert, so dass gilt:

(2.23) $f(x)-f(x+tp)\geq \vartheta \left\{{\frac {\nabla f(x)^{T}p}{\|p\|}}\right\}^{2}.$

Gilt entsprechend nur

(2.24) $f(x)-f(x+tp)\geq \vartheta \min \left(-\nabla f(x)^{T}p,\left\{{\frac {\nabla f(x)^{T}p}{\|p\|}}\right\}^{2}\right),$

so heißt die Schrittweitenregel semieffizient. Bei Verwendung einer effizienten bzw. semieffizienten Schrittweitenregel bezeichnen wir auch kurz die Schrittweiten selbst als effizient bzw. semieffizient.

Spellucci [Spe93] führt für eine Schrittweitenregel das Prinzip des hinreichenden Abstiegs ein, welches die Bedingung (2.23) der Effizienz unmittelbar impliziert. (Eine Motivation dafür wird in [Alt02] gegeben.) Der Begriff einer effizienten Schrittweitenregel geht auf die in diesem Zusammenhang grundlegende Arbeit [WaWe77] von Warth und Werner zurück. Er wurde von Kosmol [Kos89] aufgegriffen, der zusätzlich den Begriff der semieffizienten Schrittweitenregel definierte. Da jede effiziente Schrittweitenregel offenbar auch semieffizient ist und man sich diese Implikation anhand der gewählten Benennungen gut merken kann, haben wir diese Bezeichnungen übernommen. (Alle unten in Kapitel 3 eingeführten Schrittweitenregeln sind somit zumindest semieffizient.)

Für manche Verfahren kann man Konvergenz beweisen, wenn sie mit einer effizienten Schrittweitenregel verbunden werden, während dies für eine semieffiziente Regel nicht gelingt oder bisher nicht gelungen ist. Die Bezeichnungen in Definition 2.12 sind aber insofern etwas irreführend, als sie nichts über die numerische Effizienz eines Verfahrens bei Verwendung einer entsprechenden Regel aussagen und eine „semieffiziente“ Schrittweitenregel im Hinblick auf die Konvergenzgeschwindigkeit oder den numerischen Aufwand eines Verfahrens nicht notwendig weniger effizient als eine „effiziente“ ist.

2.6 Konvergenzaussagen

Wir kehren nun zu dem Modellalgorithmus 2.5 zurück. Wie wir dort festgestellt haben, ist dieser generell durchführbar. In diesem Abschnitt wollen wir Konvergenzaussagen für dieses allgemeine Modell eines Abstiegsverfahrens beweisen, wobei wir das Modell nur insoweit spezifizieren, als dass wir voraussetzen, dass in Schritt (3) eine effiziente Schrittweitenregel verwendet wird. Anschließend werden wir für eine wichtige Klasse von Abstiegsrichtungen auch Konvergenz des Verfahrens für semieffiziente Schrittweiten zeigen.

Wir beginnen damit, dass wir in dem folgenden Lemma unter den relativ schwachen Voraussetzungen (V1) und (V2) einige, zum Teil offenkundige Aussagen für den Modellalgorithmus zusammenfassen. Es sei daran erinnert, dass die Niveaumenge $N_{0}$ in (V2) durch den Startpunkt $x^{0}$ des Verfahrens definiert wird und dass die Voraussetzungen (V1) und (V2) die Existenz einer globalen Lösung des unrestringierten Optimierungsproblems $(P)$ garantieren (Bemerkung 2.6). Folglich dürfen wir „$\min _{x\in \mathbb {R} ^{n}}f(x)$“ schreiben.

Lemma 2.13

Es seien (V1) und (V2) erfüllt und der Modellalgorithmus 2.5 sei mit einer beliebigen Schrittweitenregel versehen. Dann gilt für alle $k$: (Wir schreiben „für alle $k$“, wenn nicht klar ist, ob die Iterierten $x^{k}$ nur für endlich viele $k$ definiert sind, da der Algorithmus nach endlich vielen Schritten mit einer kritischen Lösung abbricht. Erzeugt er eine unendliche Folge $\left\{x^{k}\right\}$, so machen wir dies durch einen Zusatz wie „$k\in \mathbb {N} _{0}$“ deutlich.)

(i) $f(x^{k+1})<f(x^{k})<f(x^{0}).$

(ii) $x^{k}\in N_{0}.$

Bricht der Algorithmus nicht nach endlich vielen Schritten mit einer kritischen Lösung von Problem $(P)$ ab, so erzeugt er eine unendliche Folge $\left\{x^{k}\right\}$ mit folgenden Eigenschaften:

(iii) $\left\{x^{k}\right\}$ besitzt einen Häufungspunkt.

(iv) $\lim _{k\to \infty }f(x^{k})={\hat {f}}\ f{\ddot {u}}r\ ein\ {\hat {f}}\geq \min _{x\in \mathbb {R} ^{n}}f(x).$

(v) Gilt zusätzlich $\lim _{k\to \infty }\nabla f(x^{k})=0$, so folgt:

$(\alpha )$ Jeder Häufungspunkt von $\left\{x^{k}\right\}$ ist kritische Lösung von $(P)$.

$(\beta )$ Hat $(P)$ genau eine kritische Lösung $x^{*}$, so ist $\lim _{k\to \infty }x^{k}=x^{*}$.

Beweis.

Aussage (i) ist nach Konstruktion des Algorithmus trivialerweise erfüllt und impliziert Aussage (ii). Ist $\left\{x^{k}\right\}$ eine unendliche Folge, so folgt aus (ii) wegen (V2) die Aussage (iii) (vgl. Bemerkung 2.6). Schließlich garantiert Aussage (i) wegen

$\min _{x\in \mathbb {R} ^{n}}f(x)\leq f(x^{k+1})<f(x^{k}),\quad k\in \mathbb {N} _{0},$

dass die Folge der Funktionswerte $\{f(x^{k})\}$ monoton fallend und nach unten beschränkt ist. Dies hat die in (iv) angegebene Konvergenz zur Folge.

Es gelte nun $\lim _{k\to \infty }\nabla f(x^{k})=0$. Ist $x^{*}$ ein Häufungspunkt von $\left\{x^{k}\right\}$, so existiert eine Teilfolge $\left\{x^{k_{i}}\right\}$ von $\left\{x^{k}\right\}$ mit $\lim _{i\to \infty }x^{k_{i}}=x^{*}$ und folgt wegen der vorausgesetzten Stetigkeit von $\nabla f$

$0=\lim _{i\to \infty }\nabla f(x^{k_{i}})=\nabla f(x^{*})$

Also ist die Aussage $(\alpha )$ richtig.

Jetzt sei angenommen, dass $(P)$ genau eine kritische Lösung $x^{*}$ besitzt. Würde $\left\{x^{k}\right\}$ nicht gegen $x^{*}$ konvergieren, dann existierte ein $\varepsilon >0$, so dass für unendlich viele $x^{k}$, d. h. für eine Teilfolge $\left\{x^{k_{i}}\right\}$ von $\left\{x^{k}\right\}$ gelten würde:

(2.25) $\left\|x^{k_{i}}-x^{*}\right\|\geq \varepsilon ,\quad i\in \mathbb {N} _{0}.$

Weil $x^{k_{i}}$ gemäß Aussage (ii) in $N_{0}$ liegt und $N_{0}$ gemäß (V2) kompakt ist, könnte dann jedoch aus $\left\{x^{k_{i}}\right\}$ eine konvergente Teilfolge $\left\{x^{k_{i_{j}}}\right\}$ ausgewählt werden, die nach Aussage $(\alpha )$ notwendig gegen den einzigen kritischen Punkt $x^{*}$ von $(P)$ konvergieren würde. Letzteres steht aber im Widerspruch zu (2.25), wie man sieht, wenn man dort $i:=i_{j}$ mit $j\in \mathbb {N}$ setzt. Damit ist alles bewiesen.

q.e.d.

Wenn man von Konvergenz eines Verfahrens zur Lösung des unrestringierten Optimierungsproblems $(P)$ spricht, meint man damit im Allgemeinen, dass jeder Häufungspunkt der durch das Verfahren erzeugten Iteriertenfolge eine kritische Lösung von $(P)$ ist (siehe Aussage $(\alpha )$ von Lemma 2.13). Im Fall, dass $(P)$ eine eindeutige Lösung besitzt, folgt dann unter den Voraussetzungen des Lemmas auch die Konvergenz der ganzen Folge (Aussage $(\beta )$ von Lemma 2.13).

Wir sind nun in der Lage, den zentralen Konvergenzsatz für den Modellalgorithmus zu beweisen. Mit Hilfe dieses Satzes werden wir später auch die Konvergenz von speziellen Verfahren verifizieren.

Satz 2.14

Es seien (V1) und (V2) erfüllt. Der Modellalgorithmus 2.5 sei mit einer effizienten Schrittweitenregel versehen und breche nicht nach endlich vielen Iterationen mit einer kritischen Lösung von Problem $(P)$ ab. Weiter gelte für die somit erzeugten unendlichen Folgen $\left\{x^{k}\right\}$ und $\left\{p^{k}\right\}$ die Zoutendijk-Bedingung

$\sum _{k=0}^{\infty }\alpha _{k}^{2}=\infty$ für $\alpha _{k}:=-{\frac {\nabla f(x^{k})^{T}p^{k}}{\|\nabla f(x^{k})\|\|p^{k}\|}}$

Dann folgt:

(i) Die Folge $\left\{x^{k}\right\}$ hat mindestens einen Häufungspunkt, der kritische Lösung von $(P)$ ist.

(ii) Sind zusätzlich (V3) und (V4) erfüllt und ist $x^{*}$ die dann eindeutig existierende Lösung von $(P)$, so gilt $\lim _{k\to \infty }x^{k}=x^{*}$. Die Voraussetzung (V3) wird wegen Bezugs auf Lemma 2.9 im Beweis vorausgesetzt. Für den Nachweis der verwendeten Ungleichungen aus Lemma 2.9 wird sie aber eigentlich nicht benötigt.

Beweis.

Wir nehmen an, dass der Algorithmus nicht nach endlich vielen Schritten abbricht. Da die Schrittweitenregel im Algorithmus effizient ist, gilt dann mit einem $\vartheta >0$ für alle $k$

(2.27) $f(x^{k})-f(x^{k+1})\geq \vartheta \left\{{\frac {\nabla f(x^{k})^{T}p^{k}}{\|p^{k}\|}}\right\}^{2}=\vartheta \alpha _{k}^{2}\|\nabla f(x^{k})\|^{2}>0.$

(i) Durch Summation von (2.27) für $k=0,\ldots ,\ell$ erhalten wir

$\sum _{k=0}^{\ell }\alpha _{k}^{2}\|\nabla f(x^{k})\|^{2}\leq {\frac {1}{\vartheta }}\sum _{k=0}^{\ell }\left[f(x^{k})-f(x^{k+1})\right]={\frac {1}{\vartheta }}\left[f(x^{0})-f(x^{\ell +1})\right].$

Folglich bekommen wir unter Verwendung von Lemma 2.13 (iv) durch Grenzübergang für $\ell \to \infty$

(2.28) $\sum _{k=0}^{\infty }\alpha _{k}^{2}\|\nabla f(x^{k})\|^{2}\leq {\frac {1}{\vartheta }}\left[f(x^{0})-{\hat {f}}\right]<\infty .$

Wäre nun kein Häufungspunkt von $\left\{x^{k}\right\}$ kritischer Punkt von $(P)$, so existierte ein $\varepsilon >0$ mit

(2.29) $\varepsilon \leq \left\|\nabla f(x^{k})\right\|,\quad k\in \mathbb {N} _{0}.$

(Denn sonst gäbe es eine Teilfolge $\left\{x^{k_{j}}\right\}$ von $\left\{x^{k}\right\}$ mit $\lim _{j\to \infty }\nabla f(x^{k_{j}})=0$, da Lemma 2.13 aber genauso für die Folge $\left\{x^{k_{j}}\right\}$ gültig ist, folgte daraus die Existenz eines Häufungspunktes von $\left\{x^{k_{j}}\right\}$ und damit eines Häufungspunktes von $\left\{x^{k}\right\}$, der kritische Lösung von $(P)$wäre.) Mit (2.29) würde aber aus (2.28) die Abschätzung

$\varepsilon ^{2}\sum _{k=0}^{\infty }\alpha _{k}^{2}\leq \sum _{k=0}^{\infty }\alpha _{k}^{2}\left\|\nabla f(x^{k})\right\|^{2}<\infty$

folgen, welche der vorausgesetzten Zoutendijk-Bedingung widerspricht.

(ii) Aus (2.27) können wir mit Aussage (v) aus Lemma 2.9 die folgende Abschätzung gewinnen:

$f(x^{k})-f(x^{k+1})\geq \vartheta \alpha _{k}^{2}\left\|\nabla f(x^{k})\right\|^{2}\geq 2\beta \vartheta \alpha _{k}^{2}\left[f(x^{k})-f(x^{*})\right].$

Auflösen dieser Abschätzung nach $f(x^{k+1})-f(x^{*})$, Mehrfachanwendung des erhaltenen Ergebnisses sowie Verwendung der Beziehung $1+x\leq e^{x},x\in \mathbb {R}$ liefern

$0\leq f(x^{k+1})-f(x^{*})\leq \left(1-2\beta \vartheta \alpha _{k}^{2}\right)\left[f(x^{k})-f(x^{*})\right]$

$\leq \left[f(x^{0})-f(x^{*})\right]\prod _{i=0}^{k}\left(1-2\beta \vartheta \alpha _{i}^{2}\right)\leq \left[f(x^{0})-f(x^{*})\right]\exp \left(-2\beta \vartheta \sum _{i=0}^{k}\alpha _{i}^{2}\right).$

Da gemäß der vorausgesetzten Zoutendijk-Bedingung $\lim _{k\to \infty }\sum _{i=0}^{k}\alpha _{i}^{2}=\infty$ gilt, können wir damit

$\lim _{k\to \infty }f(x^{k})=f(x^{*})$

schließen. Die Konvergenz $x^{k}\to x^{*}$ $(k\to \infty )$ ist nun eine Konsequenz von Lemma 2.9 (iii).

q.e.d.

Bemerkung 2.15

Im Fall, dass (V1) - (V4) erfüllt sind, wird die Konvergenz des Modellalgorithmus 2.5 vollständig durch die Zoutendijk-Bedingung beschrieben. Denn dann gilt auch die Umkehrung der Aussage (ii) von Satz 2.14, dass die Konvergenz von $\left\{x^{k}\right\}$ die Zoutendijk-Bedingung impliziert (vgl. [WaWe77]).

Gemäß der Definition des Standardskalarproduktes auf dem $\mathbb {R} ^{n}$ gilt

$0<-\nabla f(x^{k})^{T}p^{k}=\left\|\nabla f(x^{k})\right\|\left\|p^{k}\right\|\cos \left(\sphericalangle (-\nabla f(x^{k})^{T},p^{k})\right).$

Die Zoutendijk-Bedingung bedeutet demnach, dass die Konstante

$\alpha _{k}:=-{\frac {\nabla f(x^{k})^{T}p^{k}}{\left\|\nabla f(x^{k})\right\|\left\|p^{k}\right\|}}=\cos \left(\sphericalangle (-\nabla f(x^{k})^{T},p^{k})\right)>0$

für $k\to \infty$ nicht zu schnell gegen 0 bzw. der Winkel zwischen $-\nabla f(x^{k})$ und $p^{k}$ nicht zu schnell gegen 90° streben darf.

Die Zoutendijk-Bedingung ist offenbar für das Gradientenverfahren mit $\alpha _{k}=1$ erfüllt und allgemeiner für jedes Verfahren erfüllt, für das mit einem $\sigma >0$ gilt:

(2.30) $\alpha _{k}\geq \sigma ,\quad k\in \mathbb {N} _{0}.$

Verfahren mit der Eigenschaft (2.30) bezeichnet man als gradientenähnliche Verfahren. Demnach ist Satz 2.14 insbesondere für gradientenähnliche Verfahren relevant. Zu diesen Verfahren gehören die wichtigen Verfahren, bei denen die Richtung

(2.31) $p^{k}:=-H_{k}\nabla f(x^{k})$

mit einer symmetrischen, positiv definiten Matrix $H_{k}\in \mathbb {R} ^{n\times n}$ gewählt wird (vgl. Beispiel 2.3) und bei denen für alle $k$ die Bedingung

(2.32) $m\|x\|^{2}\leq x^{T}H_{k}x\leq M\|x\|^{2},\quad x\in \mathbb {R} ^{n}$

mit Konstanten $m,M>0$ erfüllt ist (Übung!).

Bemerkung 2.16

Sind die $H_{k}$ für alle $k$ symmetrische Matrizen, welche der Bedingung (2.32) genügen, so folgt

(2.33) $0<m\leq \lambda _{\min(}H_{k})\leq \lambda _{\max(}H_{k})=\|H_{k}\|\leq M,$

wobei $\lambda _{\min(}H_{k})$ der kleinste und $\lambda _{\max(}H_{k})$ der größte Eigenwert von $H_{k}$ ist (vgl. Lemma 1.10 und Bemerkung 2.20 aus Optimierung I). Demnach impliziert die Bedingung (2.32), dass die kleinsten Eigenwerte der $H_{k}$ gleichmäßig von Null weg beschränkt sind. Man sagt in diesem Fall auch, dass die $H_{k}$ gleichmäßig positiv definit sind.

Für die zuletzt genannten Verfahren mit (2.31) und (2.32) können wir nun - sogar in Verbindung mit einer semieffizienten Schrittweitenregel - zu einer stärkeren Konvergenzaussage als der in Satz 2.14 gelangen. Denn letztere ist sehr schwach, da sie nicht ausschließt, dass $\left\{x^{k}\right\}$ Häufungspunkte besitzt, die nicht kritische Punkte von $(P)$ sind, und dass das Verfahren einen solchen nichtkritischen Häufungspunkt findet.

Satz 2.17

Es seien (V1) - (V3) erfüllt, und der Modellalgorithmus 2.5 sei mit einer semieffizienten Schrittweitenregel mit Konstante $\vartheta >0$ versehen. Weiter gelte für alle $k$

(2.34) $p^{k}:=-H_{k}\nabla f(x^{k}),$

wobei die $H_{k}$ symmetrische Matrizen seien, welche mit Konstanten $m,M>0$ für alle $k$ der folgenden Bedingung genügen:

(2.35) $m\|x\|^{2}\leq x^{T}H_{k}x\leq M\|x\|^{2},\quad x\in \mathbb {R} ^{n}$

Bricht dann der Algorithmus nicht nach endlich vielen Schritten ab, so hat man:

(i) Jeder Häufungspunkt von $\left\{x^{k}\right\}$ ist kritische Lösung von $(P)$.

(ii) Besitzt $(P)$ genau eine kritische Lösung $x^{*}$, so gilt $\lim _{k\to \infty }x^{k}=x^{*}.$

(iii) Ist zusätzlich (V4) erfüllt, so folgt $\lim _{k\to \infty }x^{k}=x^{*}$ und gelten mit Konstanten $\nu \in (0,1)$ und $c>0$ die Abschätzungen

(2.36) $0\leq f(x^{k+1})-f(x^{*})\leq \nu \left[f(x^{k})-f(x^{*})\right],\quad k\in \mathbb {N} _{0}$

und

(2.37) $\left\|x^{k}-x^{*}\right\|\leq c\left({\sqrt {\nu }}\right)^{k},\quad k\in \mathbb {N} _{0}$

wobei $\nu$ gegeben ist durch

$\nu :=1-2\beta \vartheta \min \left(m,m^{2}/M^{2}\right).$

Beweis.

Unter Verwendung von Bemerkung 2.16 haben wir

(2.38) $\|H_{k}\|=\lambda _{\max(}H_{k})\leq M.$

Damit erreichen wir unter Verwendung von (2.24)

$f(x^{k})-f(x^{k+1})\geq \vartheta \min \left(-\nabla f(x^{k})^{T}p^{k},\left\{{\frac {\nabla f(x^{k})^{T}p^{k}}{\|p^{k}\|}}\right\}^{2}\right)$

Fehler beim Parsen (Syntaxfehler): {\displaystyle \ge \vartheta \min \left( \nabla f(x^k)^T H_k \nabla f(x^k), \left\{ \frac{\nabla f(x^k)^T H_k \nabla f(x^k)}{\|H_k \nabla f(x^k)\|} \right\}^2 \right) \ge \vartheta \min \left( m \left\| \nabla f(x^k) \right\|^2, \left\{ \frac{m \left\| \nabla f(x^k) \right\|^2}[M \left\| \nabla f(x^k) \right\|} \right\}^2 \right)}

(2.39) $\geq \vartheta \min \left(m,{\frac {m^{2}}{M^{2}}}\right)\left\|\nabla f(x^{k})\right\|^{2}.$

Da Aussage (iv) von Lemma 2.13 den Grenzwert

$\lim _{k\to \infty }\left[f(x^{k})-f(x^{k+1})\right]=0$

impliziert, schließen wir aus (2.39) die Konvergenz $\nabla f(x^{k})\to 0$ $(k\to \infty )$. Aussagen (i) und (ii) folgen nun mit Lemma 2.13 (v). Der Beweis der Aussage (iii) wird als Aufgabe gestellt.

q.e.d.

Die zweite Abschätzung in (2.36) ist möglicherweise pessimistisch. Die Abschätzungen in (2.36) und (2.37) zeigen aber, dass der Modellalgorithmus unter den Voraussetzungen und Spezifikationen von Satz 2.17 (iv) bezüglich der Folge der Funktionswerte $\left\{f(x^{k})\right\}$ mindestens Q-linear und bezüglich der Iteriertenfolge mindestens R-linear konvergiert.