Benutzer:Stepri2005/Kurs:Optimierung II/Schrittweitenregeln

Die Konstruktion von konkreten Verfahren zur Lösung des unrestringierten Optimierungsproblems

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

welche vom Typ des Modellalgorithmus 2.5 sind, erfordert die Festlegung einer Regel zur Bestimmung einer Abstiegsrichtung in der aktuellen Iterierten und einer Regel zur Berechnung der Schrittweite für diese Richtung. Da nun bekannt ist, welche Bedingung die von einer bestimmten Regel erzeugten Schrittweiten im Hinblick auf die Konvergenz eines Verfahrens erfüllen sollten (Definition 2.12), ist es möglich, diese beiden Schritte zur Spezifikation eines Verfahrens voneinander zu trennen.

Wir setzen hier generell die Bedingungen (V1) - (V3) voraus und betrachten wieder einen Punkt $x\in N_{0}$ und eine Abstiegsrichtung $p$ in $x$, für welche eine Schrittweite bestimmt werden muss, d. h., wir betrachten ein Paar von Vektoren

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

Insbesondere ist also $\nabla f(x)\neq 0$ und $x$ somit kein kritischer Punkt.

3.1 Exakte Schrittweiten

3.1.1 Existenz und Effizienz

Eine naheliegende Schrittweitenregel ist die, einen globalen Minimalpunkt des eindimensionalen Optimierungsproblems

$\inf _{t\in [0,\infty )}f(x+tp)$

als Schrittweite zu wählen. Denn ein globaler Minimalpunkt von $f(x+tp)$ liefert den größten Fortschritt bei der Reduzierung des Zielfunktionswertes von $f$ bei $x$ in Richtung $p$. Wir definieren also:

Definition 3.1

Jedes $t_{M}:=t_{M}(x,p)$, für welches

$f(x+t_{M}p)=\inf _{t\in [0,\infty )}f(x+tp)$

gilt, heißt Minimumschrittweite.

Es ist jedoch nur für einfache Funktionen wie z. B. konvexe Funktionen und dann zumeist auch nur näherungsweise möglich, eine Minimumschrittweite zu berechnen. Für alle anderen Funktionen ist es daher praxisnäher, den kleinsten, positiven, kritischen Punkt der Funktion $\varphi (t):=f(x+tp)$ als Schrittweite zu akzeptieren. Diese Überlegung motiviert die folgende Definition.

Definition 3.2

Die Curry-Schrittweite $t_{C}:=t_{C}(x,p)$ ist definiert durch

$t_{C}(x,p):=\inf \left\{{\bar {t}}\in [0,\infty ){\big |}{\frac {d}{dt}}f(x+tp){\bigg |}_{t:={\bar {t}}}=0\right\}.$

Minimumschrittweiten und die Curry-Schrittweite bezeichnet man auch als exakte Schrittweiten. Für diese können wir zeigen:

Satz 3.3

Es seien (V1) - (V3) erfüllt. Für alle Paare $x$ und $p$ mit (3.1) existieren eine Minimumschrittweite und die Curry-Schrittweite und diese sind positive Zahlen. Ferner sind die Curry- und jede Minimumschrittweite effiziente Schrittweiten mit der Konstanten

$\vartheta _{M}=\vartheta _{C}:={\frac {1}{2\gamma }}.$

Beweis.

Wir weisen zunächst die Existenz von beiden Schrittweiten nach. Dazu sei $\varphi (t):=f(x+tp)$. Nach Lemma 2.8 ist $\psi (t)=\varphi (0)-\varphi (t)$ auf $(0,{\hat {t}})$ für ein ${\hat {t}}:={\hat {t}}(x,p)>0$ positiv und folglich

$\varphi (0)>\varphi (t),\quad t\in (0,{\hat {t}}).$

Ferner existiert nach diesem Lemma ein $\kappa \geq {\hat {t}}$, so dass

$\varphi (0)<\varphi (t),\quad t\geq \kappa$

gilt. Zusammen erschließt man die Existenz eines $t_{M}\in (0,\kappa )$ mit

$\varphi (t_{M})=\min _{t\in [0,\kappa ]}\varphi (t)=\min _{t\in [0,\infty )}\varphi (t).$

Die Menge aller kritischen Punkte von $\varphi$ in $[0,\kappa ]$, d. h. die Menge

$K_{\varphi }:=\{t\in [0,\kappa ]{\big |}\varphi '(t)=0\}$

enthält $t_{M}$ und ist somit nichtleer. Ferner ist $K_{\varphi }$ kompakt, so dass ein kleinster kritischer Punkt $t_{C}:=\min _{t\in K_{\varphi }}t$ in $[0,\kappa ]$ existiert. Wegen $\varphi '(0)=\nabla f(x)^{T}p<0$ gilt $t_{C}>0$.

Als nächstes wollen wir für jede Minimumschrittweite $t_{M}$ und für die Curry-Schrittweite $t_{C}$ eine Ungleichung des Typs (2.23) nachweisen. Mit (V3) erhalten wir

$0=\varphi '(t_{C})=\nabla f(x)^{T}p+(\nabla f(x+t_{C}p)-\nabla f(x))^{T}p\leq \nabla f(x)^{T}p+t_{C}\|p\|^{2}.$

Mit ${\tilde {t}}\in (0,{\hat {t}}]$ aus Lemma 2.11 impliziert dies

(3.2) $t_{C}\geq -{\frac {1}{\gamma }}{\frac {\nabla f(x)^{T}p}{\|p\|^{2}}}={\frac {\tilde {t}}{2}}>0.$

Wegen $\varphi '(0)<0$ und weil $t_{C}$ die kleinste positive Nullstelle von $\varphi '$ ist, gilt weiter $\varphi '(t)<0$ für alle $t\in [0,t_{C})$. Somit folgt aus (3.2), dass $\varphi ({\tilde {t}}/2)\geq \varphi (t_{C})$ ist und demnach

$f(x+t_{M}p)=\min _{t\in [0,\infty )}f(x+tp)\leq f(x+t_{C}p)\leq f(x+{\frac {\tilde {t}}{2}}p).$

Dies impliziert schließlich mit (3.2) und mit Lemma 2.11 (ii) wegen ${\tilde {t}}/2\leq {\hat {t}}$

(3.3) $f(x)-f(x+t_{M}p)\geq f(x)-f(x+t_{C}p)$

$\geq f(x)-f(x+{\frac {\tilde {t}}{2}}p)\geq {\frac {\tilde {t}}{2}}\nabla f(x)^{T}p-{\frac {{\tilde {t}}^{2}}{4}}{\frac {\gamma }{2}}\|p\|^{2}$

$={\frac {1}{\gamma }}\left\{{\frac {\nabla f(x)^{T}p}{\|p\|}}\right\}^{2}-{\frac {1}{2\gamma }}\left\{{\frac {\nabla f(x)^{T}p}{\|p\|}}\right\}^{2}={\frac {1}{2\gamma }}\left\{{\frac {\nabla f(x)^{T}p}{\|p\|}}\right\}^{2}$

q.e.d.

Wie man leicht verifiziert, ist die Funktion $\varphi (t):=f(x+tp)$ konvex, wenn $f$ konvex ist. Mit Korollar 1.17 und Satz 1.6 schließt man daher:

Bemerkung 3.4

Ist $f:\mathbb {R} ^{n}\to \mathbb {R}$ konvex und sind die Voraussetzungen von Satz 3.3 erfüllt, so ist $t_{C}:=t_{C}(x,p)$ auch eine Minimumschrittweite und zwar unter allen Minimumschrittweiten die kleinste. Ist $f$ strikt konvex, so existiert genau eine Minimumschrittweite $t_{M}:=t_{M}(x,p)$ und ist $t_{M}=t_{C}$.

Für eine gleichmäßig konvexe, quadratische Funktion, für welche ja die Voraussetzungen (V1) - (V3) erfüllt sind (vgl. Beispiel 2.7), ist also die Minimumschrittweite eindeutig. Man kann sie in diesem Fall explizit angeben:

Beispiel 3.5

Für die quadratische Funktion

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

mit beliebiger Matrix $Q$ hat man $\nabla f(x)=Qx+c$ und demnach

$0={\frac {d}{dt}}f(x+tp)=\nabla f(x+tp)^{T}p=[Q(x+tp)+c]^{T}p=(Qx+c)^{T}p+tp^{T}Qp$

(3.4) $=\nabla f(x)^{T}p+tp^{T}Qp.$

Ist $Q$ positiv definit, so folgt für $x$ und $p$ wie in (3.1)

(3.5) $t_{M}=t_{C}=-{\frac {(Qx+c)^{T}p}{p^{T}Qp}}=-{\frac {\nabla f(x)^{T}p}{p^{T}Qp}}>0.$

---

Wir bemerken noch:

Bemerkung 3.6

Für die quadratische Funktion

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

mit positiv definiter Matrix $Q$ ist $t_{M}$ berechenbar und durch (3.5) gegeben. Ist $p$ ein zu dem größten Eigenwert $\lambda _{\max(}Q)=\gamma$ gehörender Eigenvektor von $Q$ (vgl. (2.12)), für den das Vorzeichen so gewählt wird, dass $-\nabla f(x)^{T}p<0$ ist, dann folgt

$p^{T}Qp=p^{T}[\lambda _{\max(}Q)p]=\gamma \|p\|^{2}$

und damit

$f(x)-f(x+t_{C}p)=-t_{C}(Qx+c)^{T}p-{\frac {1}{2}}t_{C}^{2}p^{T}Qp=-t_{C}\nabla f(x)^{T}p-t_{C}^{2}{\frac {\gamma }{2}}\|p\|^{2}={\frac {1}{2}}\left\{{\frac {\nabla f(x)^{T}p}{\|p\|}}\right\}^{2}.$

Demnach ist die Konstante $\vartheta _{M}=\vartheta _{C}:=1/(2\gamma )$ in Satz 3.3 optimal.

3.1.2 Die Methode vom Goldenen Schnitt

Numerisch ist die (näherungsweise) Berechnung einer Minimumschrittweite nur für konvexe bzw. für andere einfache Funktionen wie unimodale Funktionen realistisch möglich.

Definition 3.7

Eine Funktion $\varphi :[a,b]\to \mathbb {R}$ heißt unimodal (auf $[a,b]),fallsgenauein<math>t^{*}\in [a,b]$ existiert mit

$\varphi (t^{*})=\min _{t\in [a,b]}\varphi (t)$

und falls $\varphi$ auf $[a,t^{*}]$ streng monoton fallend und auf $[t^{*},b]$ streng monoton wachsend ist.

Eine unimodale Funktion kann Sattelpunkte besitzen und muss somit nicht eine konvexe Funktion sein. Umgekehrt gilt zumindest:

Beispiel 3.8

Jede gleichmäßig konvexe Funktion $\varphi \in C^{1}[a,b]$ ist unimodal auf $[a,b]$ (vgl. Korollar 1.18).

---

Wir wollen im Folgenden ein ableitungsfreies Verfahren zur Berechnung des Minimalpunktes $t^{*}\in [a,b]$ einer auf $[a,b]$ unimodalen Funktion $\varphi$ beschreiben. Ist $[a_{k},b_{k}]$ ein Teilintervall von $[a,b]$ und $t^{*}\in [a_{k},b_{k}]$, dann folgt gemäß Definition 3.7 für Punkte $s_{k}$ und $t_{k}$ mit $a_{k}\leq s_{k}<t_{k}\leq b_{k}$

$\varphi (s_{k})>\varphi (t_{k})\Rightarrow \varphi (u)>\varphi (s_{k}),\quad u\in [a_{k},s_{k}),$

$\varphi (s_{k})\leq \varphi (t_{k})\Rightarrow \varphi (u)>\varphi (t_{k}),\quad u\in (t_{k},b_{k}].$

Demnach muss der Minimalpunkt $t^{*}$ von $\varphi$ im Fall $\varphi (s_{k})>\varphi (t_{k})$ in $[s_{k},b_{k}]$ und im Fall $\varphi (s_{k})\leq \varphi (t_{k})$ in $[a_{k},t_{k}]$ liegen. Es bietet sich also an, das folgende Intervall als neues Suchintervall zu wählen

Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. upstream connect error or disconnect/reset before headers. reset reason: connection termination“): {\displaystyle [a_{k+1},b_{k+1}]:={\begin{cases}[s_{k},b_{k}],&{\text{falls }}\varphi (s_{k})>\varphi (t_{k}),\\[a_{k},t_{k}],&{\text{falls }}\varphi (s_{k})\leq \varphi (t_{k}).\end{cases}}}

Dabei ist es erstrebenswert, $s_{k},t_{k}\in [a_{k},b_{k}]$ mit $s_{k}<t_{k}$ für jedes $k$ so festzulegen, dass

• $b_{k}-s_{k}=t_{k}-a_{k}$, d. h. die Länge des Intervalls $[a_{k+1},b_{k+1}]$ unabhängig vom Ausgang der Abfrage "$\varphi (s_{k})>\varphi (t_{k})$" ist und
• beim Übergang von $k$ zu $k+1$ nur eine neue Funktionsauswertung erforderlich ist.

Die beiden an $s_{k}$ und $t_{k}$ gestellten Forderungen können in der Tat erfüllt werden (Übung!), indem man jedes Intervall $[a_{k},b_{k}]$ mittels eines Goldenen Schnittes in zwei Intervalle teilt. Und zwar sagt man, dass ein Intervall $[a,b]$ durch einen Goldenen Schnitt in zwei Intervalle $[a,c]$ und $[c,b]$ zerlegt wird, falls gilt:

(3.6) ${\frac {\mbox{Länge des ganzen Intervalls}}{\mbox{Länge des längeren Teilintervalls}}}={\frac {\mbox{Länge des längeren Teilintervalls}}{\mbox{Länge des kürzeren Teilintervalls}}}.$

Der Punkt $c$, der eine solche Zerlegung liefert, lässt sich berechnen (Übung!). Und zwar erhält man, wenn $[a,c]$ das längere Teilintervall ist,

(3.7) $c=a+F(b-a),\quad F:={\frac {{\sqrt {5}}-1}{2}}\approx 0.618\ 033\ 989$

und, wenn $[a,c]$ das kürzere Teilintervall ist,

(3.8) $c=a+(1-F)(b-a),\quad 1-F={\frac {3-{\sqrt {5}}}{2}}\approx 0.381\ 966\ 011.$

Demnach wählt man für jedes $k$ insbesondere

$s_{k}:=a_{k}+(1-F)(b_{k}-a_{k}),\quad t_{k}:=a_{k}+F(b_{k}-a_{k}).$

Damit haben wir die folgende Methode zur Minimierung einer unimodalen Funktion $\varphi :[a,b]\to \mathbb {R}$ beschrieben (siehe die Aufgabe dazu).

Algorithmus 3.9 (Methode vom Goldenen Schnitt)

(0) Wähle $\varepsilon \in (0,b-a)$ und setze $F:=({\sqrt {5}}-1)/2$ sowie

$a_{0}:=a,\quad b_{0}:=b,\quad s_{0}:=a+(1-F)(b-a),\quad t_{0}:=a+F(b-a).$

Berechne $\varphi (s_{0})$ und $\varphi (t_{0})$ und setze $k:=0$.

(1) Falls $b_{k}-a_{k}\leq \varepsilon$ ist, stop! (Es gilt $t^{*}\in [a_{k},b_{k}]$.)

(2) (i) Falls $\varphi (s_{k})>\varphi (t_{k})$ ist, setze

$a_{k+1}:=s_{k},\quad b_{k+1}:=b_{k},\quad s_{k+1}:=t_{k},\quad t_{k+1}:=s_{k}+F(b_{k}-s_{k})$

und berechne $\varphi (t_{k+1})$.

(ii) Falls $\varphi (s_{k})\leq \varphi (t_{k})$ ist, setze

$a_{k+1}:=a_{k},\quad b_{k+1}:=t_{k},\quad s_{k+1}:=a_{k}+(1-F)(t_{k}-a_{k}),\quad t_{k+1}:=s_{k}$

und berechne $\varphi (s_{k+1})$.

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

3.1.3 Anmerkungen

Das Verfahren vom Goldenen Schnitt oder andere ableitungsfreie Verfahren wie solche Verfahren, die $f$ in jedem Schritt durch eine Funktion approximieren, welche $f$ in bestimmten Punkten interpoliert und die damit eine Näherung für den gesuchten Minimalpunkt berechnen ([Bre73]), benötigen nur Funktionswerte von $f$ und konvergieren zum Teil unter schwachen Voraussetzungen superlinear. Allerdings ist z. B. die Voraussetzung der Unimodalität einer Funktion für die Konvergenz eines Verfahrens eine sehr gravierende Voraussetzung.

Zur Lösung des eindimensionalen Optimierungsproblems

$\min _{t\in [0,\infty )}\varphi (t):=f(x+tp)$

mit einer konvexen oder unimodalen Funktion $\varphi$ kann man auch eine Nullstelle von $\varphi '$ z. B. mit einem der aus der Numerischen Mathematik bekannten Verfahren, wie z. B. der Regula Falsi oder dem Sekanten-Verfahren, bestimmen, welche nur Funktionswerte von $\varphi '$ und damit nur den Gradienten von $f$ verwenden. Das Newton-Verfahren benötigt dagegen $\varphi ''$ und damit im Hinblick darauf, dass $\varphi$ nur eine Funktion in einer Veränderlichen ist, numerisch häufig zu teuere Auswertungen der Hesse-Matrix von $f$. Im nichtkonvexen Fall muss man aber bei solchen Vorgehensweisen noch sicherstellen, dass es sich bei der gefundenen Nullstelle tatsächlich um einen globalen Minimierer von $\varphi$ handelt.

Für die Berechnung der Curry-Schrittweite, also der kleinsten positiven Nullstelle von $\varphi '(t)=\nabla f(x+tp)^{T}p$, müssen keine speziellen Forderungen an $f$ gestellt werden. Man beginnt normalerweise mit einer Einschachtelungsprozedur, bei der man mittels eines Vergleichs von Funktionswerten von $\varphi '$ versucht, ein hinreichend kleines Intervall zu finden, in dem sich die gesuchte Nullstelle befindet. Anschließend kann man jedes Verfahren zur Bestimmung einer Nullstelle einer Funktion in einer Veränderlichen auf einem Intervall anwenden, wie z. B. eines der oben genannten.

Die Berechnung exakter Schrittweiten für eine allgemeine nichtlineare Funktion bedingt, dass zunächst die richtige Lösung des eindimensionalen Optimierungsproblems eingeschachtelt wird und dass das zu deren Bestimmung eingesetzte Verfahren mit ausreichender Geschwindigkeit konvergiert. Überdies können exakte Schrittweiten im Allgemeinen nur näherungsweise berechnet werden und muss darauf vertraut werden, dass das entsprechende Verfahren zur Lösung von Problem $(P)$ auch mit diesen Näherungen konvergent ist. Aus all diesen Gründen verwendet man zumeist andere, leichter umzusetzende Schrittweitenregeln, für die auch Theorie und Praxis konsistent sind. Einige solcher Regeln werden wir im Folgenden beschreiben.

3.2 Die Armijo-Schrittweite

Eine sehr populäre, da sehr leicht berechenbare Schrittweite ist die folgende.

Definition 3.10

Seien $\eta \in (0,1)$ und $\zeta \in (0,1/2)$ gegebene Zahlen. Ferner sei $q:=q(x,p)$ die kleinste Zahl aus $\mathbb {N} _{0}$ derart, dass die Ungleichung

(3.9) $f(x)-f(x+\eta ^{q}p)\geq -\zeta \eta ^{q}\nabla f(x)^{T}p$

erfüllt ist. Dann heißt $t_{A}=t_{A}(x,p):=\eta ^{q}$ Armijo-Schrittweite.

Die Armijo-Schrittweite ist also die größte Zahl aus der Menge

(3.10) $\left\{1,\eta ,\eta ^{2},\eta ^{3},\eta ^{4},...\right\},$

für welche die Ungleichung in (3.9) erfüllt ist. Da $1\geq \eta \geq \eta ^{2}\geq \eta ^{3}\geq ...$ gilt, muss man mit 1 beginnend und abnehmender Größe nur rechnerisch überprüfen, für welche Zahl $\eta ^{q}$ die Ungleichung (3.9) zum ersten Mal erfüllt ist. Die Berechnung der Armijo-Schrittweite ist also trivial.

Beispiel 3.11

Sei $f$ die quadratische Funktion

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

mit positiv definiter Matrix $Q$ und seien $x$ und $p$ Punkte wie in (3.1) gegeben. Im Hinblick auf die Ungleichung (3.9) stellen wir fest, dass

$f(x)-f(x+tp)=-t(Qx+c)^{T}p-{\frac {1}{2}}t^{2}p^{T}Qp\geq -\zeta t\nabla f(x)^{T}p$

genau dann gilt, wenn

$t\leq -2(1-\zeta ){\frac {\nabla f(x)^{T}p}{p^{T}Qp}}=2(1-\zeta )t_{C}$

ist, wobei die Identität $\nabla f(x)=Qx+c$ und die Curry-Schrittweite $t_{C}$ für $f$ aus (3.5) verwendet wurden. Die Armijo-Schrittweite $t_{A}$ ist also die größte Zahl aus der Menge (3.10), welche der Ungleichung

(3.11) $\eta ^{q}=t_{A}\leq 2(1-\zeta )t_{C}$

genügt. Für $\zeta \in (0,1/2)$ ist sie kleiner als $2t_{C}$.

---

Der leichten Berechenbarkeit der Armijo-Schrittweite steht entgegen, dass sie nur semieffizient ist.

Satz 3.12

Es seien (V1) - (V3) erfüllt und Zahlen $\eta \in (0,1)$ und $\zeta \in (0,1/2)$ gegeben. Für alle Paare $x$ und $p$ mit (3.1) existiert genau eine Armijo-Schrittweite, und diese ist eine semieffiziente Schrittweite mit der Konstanten

$\vartheta _{A}:=\min \left(\zeta ,{\frac {2\zeta \eta (1-\zeta )}{\gamma }}\right).$

Beweis.

Aus der Definition der Richtungsableitung erhält man für $\zeta \in (0,1/2)$

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

Folglich gilt für alle genügend kleinen $t>0$

$f(x)-f(x+tp)>-\zeta \nabla f(x)^{T}p.$

Wegen $\lim _{q\to \infty }\eta ^{q}=0$ kann demzufolge Ungleichung (3.9) für genügend großes $q$ erfüllt werden, wobei $q$ offenbar eindeutig ist. Also existiert die Armijo-Schrittweite. (Dies kann man sogar für $\zeta \in (0,1)$ schließen, aber z. B. für Satz 6.10 muss $\zeta \in (0,1/2)$ vorausgesetzt werden.)

Als nächstes zeigen wir, dass die Armijo-Schrittweitenregel eine semieffiziente Schrittweitenregel ist. Ist $q=0$, also $t_{A}=1$, so folgt aus (3.9)

(3.12) $f(x)-f(x+t_{A}p)\geq -\zeta \nabla f(x)^{T}p.$

Ist $q>0$, so gilt zum einen natürlich für $\eta ^{q}=t_{A}$ die Ungleichung (3.9) und zum anderen weiß man, dass dann die Ungleichung (3.9) für $\eta ^{q-1}=\eta ^{-1}t_{A}$ noch nicht erfüllt und daher Folgendes richtig ist:

(3.13) $f(x)-f(x+\eta ^{-1}t_{A}p)<-\zeta \eta ^{-1}t_{A}\nabla f(x)^{T}p.$

Für ${\hat {t}}$ aus Lemma 2.8 betrachten wir jetzt zuerst den Fall $\eta ^{-1}t_{A}\leq {\hat {t}}$. Für diesen folgt mit (3.13) und Lemma 2.11

$-\zeta \eta ^{-1}t_{A}\nabla f(x)^{T}p>f(x)-f(x+\eta ^{-1}t_{A}p)\geq -\eta ^{-1}t_{A}\nabla f(x)^{T}p-\left(\eta ^{-1}t_{A}\right)^{2}{\frac {\gamma }{2}}\|p\|^{2}.$

Division durch $\eta ^{-1}t_{A}$ und anschließendes Auflösen nach $t_{A}$ liefert damit

$t_{A}\geq -{\frac {2\eta (1-\zeta )}{\gamma }}{\frac {\nabla f(x)^{T}p}{\|p\|^{2}}}>0.$

Unter Verwendung von (3.9) erhalten wir also

(3.14) $f(x)-f(x+t_{A}p)\geq {\frac {2\eta \zeta (1-\zeta )}{\gamma }}\left\{{\frac {\nabla f(x)^{T}p}{\|p\|}}\right\}^{2}.$

Ist andererseits $\eta ^{-1}t_{A}\geq {\hat {t}}$, so ergibt sich mit Lemma 2.11 und ${\tilde {t}}$ von dort

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

Mit (3.9) erhält man daher

(3.15) $f(x)-f(x+t_{A}p)\geq {\frac {2\eta \zeta }{\gamma }}\left\{{\frac {\nabla f(x)^{T}p}{\|p\|}}\right\}^{2}.$

Aus (3.12), (3.14) und (3.15) zusammen folgt das gewünschte Ergebnis.

q.e.d.

3.3 Wolfe-Powell-Schrittweiten

3.3.1 Definition und Effizienz

Im Fall der Schrittweitenregel von Wolfe und Powell muss neben einer Ungleichung vom Armijo-Typ wie in (3.9) eine weitere Ungleichung erfüllt werden. (Wir folgen hier der Namensgebung z. B. in [Fle91] und [GeiKa99]. Man findet auch die Bezeichnungen Powell-Wolfe- ([Kos89]) und Powell-Schrittweitenregel ([Wer92], [Alt02]).)

Definition 3.13

Es seien Zahlen �$\tau \in (0,1/2)$ und $\sigma \in [\tau ,1)$ gegeben. Dann heißt jedes Element der Menge

$T_{WP}(x,p):=\{t\in \mathbb {R} _{+}{\big |}-\tau t\nabla f(x)^{T}p\leq f(x)-f(x+tp),-\nabla f(x+tp)^{T}p\leq -\sigma \nabla f(x)^{T}p\}$

Wolfe-Powell-Schrittweite.

Wir betrachten auch für diese Schrittweitenregel zuerst wieder das Beispiel einer gleichmäßig konvexen, quadratischen Funktion.

Beispiel 3.14

Es sei $f$ die quadratische Funktion

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

wobei $Q$ positiv definit sei. Weiter mögen $x$ und $p$ die Bedingungen in (3.1) erfüllen. Ähnlich wie in Beispiel 3.11 zeigt man unter Verwendung der Curry-Schrittweite $t_{C}$ für $f$ (Übung!):

(3.17) $T_{WP}(x,p)=[(1-\sigma )t_{C},2(1-\tau )t_{C}].$

Aufgrund der Forderungen $\tau \in (0,1/2)$ und $\sigma \in [\tau ,1)$ ist die Menge der Wolfe-Powell-Schrittweiten in diesem Fall ein ganzes Intervall, welches $t_{C}$ in seinem Inneren enthält. (Deshalb wählt man $\tau \in (0,1/2)$, der Beweis des folgenden Satzes ist auch für $\tau \in (0,1)$ richtig.)

---

Wir verwenden wieder die Funktion $\psi$ mit

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

Damit entspricht die Menge $T_{WP}(x,p)$ der Wolfe-Powell-Schrittweiten der Menge aller $t\geq 0$, welche den beiden Ungleichungen

(3.19) $\tau \psi '(0)t\leq \psi (t),\quad \psi '(t)\leq \sigma \psi '(0)$

genügen. Wir zeigen als nächstes unter den Standardvoraussetzungen, dass die Wolfe-Powell-Schrittweitenregel effizient ist und für jedes $f$ die Wahl einer Schrittweite aus einem ganzen Intervall erlaubt.

Satz 3.15

Es seien (V1) - (V3) erfüllt. Für alle Paare $x$ und $p$ mit (3.1) und jedes $\tau \in (0,1/2)$ und $\sigma \in [\tau ,1)$ enthält die Menge $T_{WP}(x,p)$ mindestens ein nichtleeres abgeschlossenes Intervall. Ferner ist jede Wolfe-Powell-Schrittweite $t_{WP}:=t_{WP}(x,p)$ eine effiziente Schrittweite mit der Konstanten

(3.20) $\vartheta _{WP}:={\frac {1}{\gamma }}\min \left({\frac {1-\sigma ^{2}}{2}},2\tau (1-\tau )\right).$

Beweis.

Seien $x,p,\sigma$ und $\tau$ gegeben wie angenommen und sei

$d(t):=\psi (t)-\tau \psi '(0)t,\quad d'(t)=\psi '(t)-\tau \psi '(0).$

Dann ist $d(0)=0$ und mit der Curry-Schrittweite $t_{C}$

$d'(0)=(1-\tau )\psi '(0)>0,\quad d'(t_{C})=-\tau \psi '(0)<0.$

Also besitzt $d$ in $[0,t_{C}]$ einen lokalen Maximalpunkt $t_{1}$ mit $d(t_{1})>0$. Weiter existiert ein $t_{2}\in [t_{1},t_{C}]$, so dass für $I:=[t_{1},t_{2}]$ folgt:

(3.21) $d(t)>0,\quad d'(t)\leq 0,\quad t\in I.$

Wie man am Vergleich mit (3.19) erkennt, implizieren diese letzten beiden Ungleichungen die Inklusion $I\subseteq T_{WP}(x,p)$, da aus der zweiten Ungleichung für alle $t\in I$ folgt:

(3.22) $\psi '(t)=-\nabla f(x+tp)^{T}p\leq -\tau \nabla f(x)^{T}p\leq -\sigma \nabla f(x)^{T}p.$

Für den Nachweis, dass die Wolfe-Powell-Schrittweitenregel $t_{WP}$ effizient ist, untersuchen wir zunächst den Fall

(3.23) $t_{WP}\leq -{\frac {2(1-\tau )}{\gamma }}{\frac {\nabla f(x)^{T}p}{\|p\|^{2}}}:=t_{r}.$

Nach der Definition von $t_{WP}$ gilt

$-\nabla f(x+t_{WP}p)^{T}p\leq -\nabla f(x)^{T}p+(1-\sigma )\nabla f(x)^{T}p.$

Unter Anwendung von Voraussetzung (V3) können wir daraus schließen:

$-(1-\sigma )\nabla f(x)^{T}p\leq [\nabla f(x+t_{WP}p)-\nabla f(x)]^{T}p\leq \gamma t_{WP}\|p\|^{2}.$

Daher erhalten wir mit (3.23) und ${\hat {t}}$ aus Lemma 2.11

$0<t_{l}:=-{\frac {1-\sigma }{\gamma }}{\frac {\nabla f(x)^{T}p}{\|p\|^{2}}}\leq t_{WP}\leq t_{r}\leq {\hat {t}}.$

Nun verwenden wir, dass eine nach unten geöffnete Parabel wie die Parabel $\Phi$ aus Lemma 2.11 ihr Minimum auf dem Intervall $[t_{l},t_{r}]$ in $t_{l}$ oder $t_{r}$ annimmt. Folglich liefert Anwendung von Lemma 2.11

$f(x)-f(x+t_{WP}p)\geq -t_{WP}\nabla f(x)^{T}p-t_{WP}^{2}{\frac {\gamma }{2}}\|p\|^{2}\geq \min _{t\in [t_{l},t_{r}]}\left(-t\nabla f(x)^{T}p-t^{2}{\frac {\gamma }{2}}\|p\|^{2}\right)$

$\geq {\frac {1}{\gamma }}\min \left({\frac {1-\sigma ^{2}}{2}},2\tau (1-\tau )\right)\left\{{\frac {\nabla f(x)^{T}p}{\|p\|}}\right\}^{2}.$

Ist andererseits

$t_{WP}\geq {\frac {2(1-\tau )}{\gamma }}{\frac {\nabla f(x)^{T}p}{\|p\|^{2}}}>0,$

dann folgt direkt mit der Definition von $t_{WP}$

$f(x)-f(x+t_{WP}p)\geq -\tau t_{WP}\nabla f(x)^{T}p\geq {\frac {2\tau (1-\tau )}{\gamma }}\left\{{\frac {\nabla f(x)^{T}p}{\|p\|}}\right\}^{2}.$

Fassen wir die in beiden Fällen gewonnenen Ungleichungen zusammen, so erhalten wir eine Ungleichung des Typs (2.23) mit der Konstante aus (3.20).

q.e.d.

3.3.2 Numerische Berechnung

Die Wolfe-Powell-Schrittweitenregel ist auch numerisch realisierbar, da in ihrem Fall nicht wie bei den exakten Schrittweitenregeln ein einzelner Punkt, sondern gemäß Satz 3.15 nur ein $t$ aus einem Intervall gefunden werden muss. Insbesondere kann eine Wolfe-Powell-Schrittweite in endlich vielen Schritten mit folgendem Algorithmus berechnet werden, wie der daran anschließende Satz beweist.

Die Idee dabei ist es, zunächst ein Intervall zu bestimmen, dessen linker Randpunkt die Armijo-Ungleichung, also die erste Ungleichung in $T_{WP}(x,p)$ erfüllt und dessen rechter dies nicht tut. Wenn der linke Randpunkt des Intervalls auch der zweiten Ungleichung in $T_{WP}(x,p)$ genügt, ist man fertig. Anderenfalls wird die Länge des Intervalls, ähnlich wie beim Bisektionsverfahren zur Bestimmung einer Nullstelle einer reellwertigen Funktion, so lange unter Beibehaltung der mit dem Intervall verbundenen Eigenschaften halbiert, bis der linke Randpunkt auch die zweite Ungleichung erfüllt.

Algorithmus 3.16

(0) Gib $x\in N_{0}$ und $p\in \mathbb {R} ^{n}$ mit $\nabla f(x)^{T}p<0,\tau \in (0,1/2)$ und $\sigma \in (\tau ,1)$ und setze $k:=0$. (Achtung: im Hinblick auf den Beweis von Satz 3.17 wird hier anders als in Definition 3.13 der Fall $\sigma =\tau$ ausgeschlossen.)

(1) (i) Falls für $t:=1$ die Armijo-Ungleichung

(3.24) $f(x)-f(x+tp)\geq -\tau t\nabla f(x)^{T}p$

erfüllt ist, bestimme die größte Zahl $b_{k}\in \{2,2^{2},2^{3},...\}$, so dass (3.24) für $t:=b_{k}$ verletzt ist, und setze $a_{k}:=b_{k}/2$.

(ii) Anderenfalls bestimme die größte Zahl $a_{k}\in \{2^{-1},2^{-2},2^{-3},...\}$, so dass (3.24) für $t:=a_{k}$ erfüllt ist, und setze $b_{k}:=2a_{k}$.

(2) Falls für $t:=a_{k}$ die Ungleichung

(3.25) $-\nabla f(x+tp)^{T}p\leq -\sigma \nabla f(x)^{T}p$

gilt, setze $t_{WP}:=a_{k}$. Stop!

(3) Berechne

$t_{k}:={\frac {a_{k}+b_{k}}{2}}.$

Falls $t_{k}$ die Bedingung (3.24) erfüllt, setze

$a_{k+1}:=t_{k},\quad b_{k+1}:=b_{k}.$

Anderenfalls setze

$a_{k+1}:=a_{k},\quad b_{k+1}:=t_{k}.$

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

Satz 3.17

Es seien (V1) - (V3) erfüllt. Dann bricht Algorithmus 3.16 nach endlich vielen Iterationen mit einer Wolfe-Powell-Schrittweite $t_{WP}\in T_{WP}(x,p)$ ab.

Beweis.

Nach Lemma 2.8 ist $f(x)<f(x+tp),t\geq \kappa$ für ein $\kappa >0$. Somit wird in Schritt (1) (i) nach endlich vielen Schritten ein $t:=b_{0}$, wie angegeben, gefunden. Gemäß Satz 3.12 für $\eta :=1/2$ und $\zeta :=\tau$ kann weiter in (ii) nach endlich vielen Schritten die Armijo-Schrittweite $a_{0}$ bestimmt werden. Am Ende von Schritt (1) hat man somit in beiden Fällen für $k=0$

(3.26) $a_{k}<b_{k},\quad t:=a_{k}$ erfüllt (3.24), $t:=b_{k}$ erfüllt (3.24) nicht.

Ist auch (3.25) für $t:=a_{k}$ richtig, so ist offenbar $a_{k}\in T_{WP}(x,p)$ und bricht das Verfahren in (2) erfolgreich ab. Anderenfalls hat man zu Beginn von Schritt (3) die Situation in (3.26) und wird nun die Länge des Intervalls $[a_{k},b_{k}]$ in jedem Durchlauf von Schritt (3) halbiert, wobei entweder $a_{k}$ vergrößert oder $b_{k}$ verkleinert wird und $a_{k}$ und $b_{k}$ die Eigenschaften in (3.26) bewahren.

Würde Schritt (3) unendlich oft durchlaufen, so konvergierten die Folgen $\{a_{k}\}$ und $\{b_{k}\}$ aufgrund ihrer sich aus

$a_{k+1}\leq a_{k}\leq b_{k}\leq b_{0},\quad a_{0}\leq a_{k+1}\leq b_{k+1}\leq b_{k}$

ergebenden Monotonie und der Tatsache, dass die Länge der Intervalle $[a_{k},b_{k}]$ gegen 0 geht, gegen dieselbe Zahl $t^{*}$. Aufgrund von (3.26) wäre dann weiter die Armijo-Ungleichung in (3.24) für $t^{*}$ gleichzeitig erfüllt und "verletzt", d. h., es wäre $d(t^{*})=0$ für

$d(t):=f(x)-f(x+tp)+\tau t\nabla f(x)^{T}p.$

Es folgte außerdem $d'(t^{*})\leq 0$, da anderenfalls

${\frac {d(b_{k})-d(t^{*})}{b_{k}-t^{*}}}>0$

und damit $d(b_{k})>0$ für alle hinreichend großen $k$ gelten würde, was aber im Widerspruch dazu stünde, dass $b_{k}$ die Bedingung (3.24) verletzt. Wegen $d'(t^{*})\leq 0$ und $\tau <\sigma$ hätte man dann jedoch

$-\nabla f(x+t^{*}p)^{T}p\leq -\tau \nabla f(x)^{T}p<-\sigma \nabla f(x)^{T}p$

und damit für alle hinreichend großen $k$

$-\nabla f(x+a_{k}p)^{T}p<-\sigma \nabla f(x)^{T}p.$

Also wäre die Ungleichung (3.25) für $t:=a_{k}$ mit hinreichend großem $k$ erfüllt, was aber der Annahme widerspricht, dass (3) unendlich oft durchlaufen wird. Demzufolge bricht der Algorithmus nach endlich vielen Durchgängen von Schritt (3) ab.

3.4 Strenge Wolfe-Powell-Schrittweiten

In einigen Zusammenhängen hat sich die folgende Modifikation der Wolfe-Powell-Schrittweitenregel in der Praxis bewährt.

Definition 3.18

Es seien Zahlen $\tau \in (0,1/2)$ und $\sigma \in [\tau ,1)$ gegeben. Dann heißt jedes Element der Menge

(3.27) $T_{SWP}(x,p):={\big \{}t\in \mathbb {R} _{+}{\big |}-\tau t\nabla f(x)^{T}p\leq f(x)-f(x+tp),$

(3.28) $\left|\nabla f(x+tp)^{T}p\right|\leq -\sigma \nabla f(x)^{T}p{\big \}}$

strenge Wolfe-Powell-Schrittweite.

Zunächst betrachten wir auch hier wieder quadratische Funktionen:

Beispiel 3.19

Es sei $f$ die quadratische Funktion

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

mit positiv definiter Matrix $Q$ und $x$ sowie $p$ mögen die Bedingungen in (3.1) erfüllen. Mit einer einfachen Rechnung ähnlich wie in Beispiel 3.11 zeigt man

(3.29) $T_{SWP}(x,p)=[(1-\sigma )t_{C},\min\{1+\sigma ,2(1-\tau )\}t_{C}],$

wobei $t_{C}$ wieder die Curry-Schrittweite für $f$ ist. Für $\tau \in (0,1/2)$ und $\sigma \in [\tau ,1)$ folgt also $t_{C}\in T_{SWP}(x,p)$.

---

Mit der Funktion $\psi$ aus (3.18) ist die Menge $T_{SWP}(x,p)$ der strengen Wolfe-Powell-Schrittweiten gerade die Menge aller $t\geq 0$, welche gleichzeitig die Ungleichungen

(3.30) $\tau \psi '(0)t\leq \psi (t),\quad |\psi '(t)|\leq \sigma \psi '(0)$

erfüllen. Gegenüber der Wolfe-Powell-Schrittweitenregel werden bei der strengen Wolfe-Powell-Schrittweitenregel solche Schrittweiten ausgeschlossen, für welche die Steigung von $\psi$ einen zu großen negativen Wert hat.

Für die strenge Wolfe-Powell-Schrittweitenregel gilt ähnlich wie für die einfache:

Satz 3.20

Es seien (V1) - (V3) erfüllt. Für alle Paare $x$ und $p$ mit (3.1) und Zahlen $\tau \in (0,1/2)$ und $\sigma \in [\tau ,1)$ enthält die Menge $T_{SWP}(x,p)$ mindestens ein nichtleeres abgeschlossenes Intervall. Ferner ist jede strenge Wolfe-Powell-Schrittweite $t_{SWP}:=t_{SWP}(x,p)$ eine effiziente Schrittweite mit der Konstanten

$\vartheta _{SWP}:={\frac {1}{\gamma }}\min \left\{{\frac {1-\sigma ^{2}}{2}},2\tau (1-\tau )\right\}$

Beweis.

Für den Nachweis der Existenz eines Intervalls $I\subseteq T_{SWP}(x,p)$ kann man dem Beweis von Satz 3.15 folgen. Wählt man $t_{2}$ und damit $I$ so, dass

$d(t)>0,\quad t\in I,\qquad -\tau \psi '(0)\leq d'(t)\leq 0,\quad t\in I$

gilt, wobei Letzteres wegen $-\tau \psi '(0)<0$ und $d'(t_{1})=0$ möglich ist, so folgt zusätzlich zu (3.22) noch

$-\nabla f(x+tp)^{T}p=\psi '(t)=d'(t)+\tau \psi '(0)\geq 0,\quad t\in I.$

Damit ist $I\subseteq T_{SWP}(x,p)$. Wegen $T_{SWP}(x,p)\subseteq T_{WP}(x,p)$ folgt der zweite Teil der Behauptung aus Satz 3.15.

q.e.d.

Ein Algorithmus zur Berechnung einer strengen Wolfe-Powell-Schrittweite ist in [GeiKa99] zu finden.

Die Ungleichungen in (3.30) zeigen, dass man für festes $x$ und $p$ durch die Wahl von hinreichend kleinen Zahlen $\tau$ und $\sigma$ eine beliebig kleine Umgebung eines isolierten kritischen Punktes von $\psi (t)$ bzw. $\varphi (t):=f(x+tp)$ erzeugen kann. Startet man also den Algorithmus zur Berechnung einer strengen Wolfe-Powell-Schrittweite nahe genug bei der Curry-Schrittweite $t_{C}$ (man verwende dazu ein Einschachtelungsverfahren), so erlaubt die strenge Wolfe-Powell-Schrittweitenregel die Wahl einer Schrittweite, welche der Curry-Schrittweite beliebig nahe kommt. Beispielsweise liefert (3.29) im gleichmäßig konvexen, quadratischen Fall für $\tau =\sigma =0.1$ das Intervall $T_{SWP}(x,p)=[0.9t_{C},1.1t_{C}]$, während man für die Wolfe-Powell-Schrittweitenregel gemäß (3.17) das viel größere Intervall $T_{WP}(x,p)=[0.9t_{C},1.8t_{C}]$ erhält. Es liegt somit nahe, die strenge Wolfe-Powell-Schrittweitenregel zu verwenden, wenn ein Verfahren relativ empfindlich auf starke Abweichungen von den exakten Schrittweiten reagiert. Wir verweisen diesbezüglich z. B. auf die Bemerkungen zu CG-Verfahren in Abschnitt 5.5.