U 09 – Wolfe-Powell-Schrittweitenstrategie

 

Gegeben seien die Funktionen f:{\mathbb{R}^n} \to \mathbb{R} mit f \in {C^1}\left( {{\mathbb{R}^n}} \right) sowie \sigma \in \left( {0,\frac{1}{2}} \right), \rho \in \left[ {\sigma ,1} \right). Ein {t_{WP}} > 0 ist eine Wolfe-Powell-Schrittweite für x \in {\mathbb{R}^n} und die Abstiegsrichtung d \in {\mathbb{R}^n}, falls

(WP1) f\left( {x+td} \right) \leq f\left( x \right)+\sigma t\nabla f{\left( x \right)^T}d

(WP2) \nabla f{\left( {x+td} \right)^T}d \geq \rho \nabla f{\left( x \right)^T}d

Für jedes x \in {\mathbb{R}^n} und d \in {\mathbb{R}^d} mit \nabla f{\left( x \right)^T}d < 0 sei

{T_{WP}}: = \left\{ {t > 0:t\:\:erf\ddot ullt\:\:WP1,WP2} \right\}

Eine Schrittweite für die Abstiegsrichtung d in x heißt effizient, falls mit \theta > 0 unabhängig von x und d die Abschätzung

f\left( {x+td} \right) \leq f\left( x \right)-\theta {\left( {\frac{{\nabla f{{\left( x \right)}^T}d}}{{\left\| d \right\|}}} \right)^2}

gilt.

Zeigen Sie nun folgende Aussage:

Ist der Gradient \nabla f auf \mathcal{L}\left( {{x_0}} \right) = \left\{ {x \in {\mathbb{R}^n}:f\left( x \right) \leq f\left( {{x_0}} \right)} \right\} Lipschitz-stetig, so ist für alle x \in \mathcal{L}\left( {{x_0}} \right) und alle d \in {\mathbb{R}^d} jedes t \in {T_{WP}} effizient.

Lösung

Exkurs: Schrittweitenstrategien

Betrachte den k-ten Schritt eines Abstiegsverfahrens.

f \in {C^1}\left( {{\mathbb{R}^n}} \right): zu minimierende Zielfunktion

x \in {\mathbb{R}^n}: aktuelle Näherung

d \in {\mathbb{R}^n}: Abstiegsrichtung

\nabla f{\left( x \right)^T}d < 0: Bedingung

Iterationsvorschrift: {x_{k+1}} = {x_k}+td

Veranschaulichung:

opti-u09-hoehenlinien

Aufgabe:

Bestimme Schrittweite, so dass die Hilfsfunktion

\varphi \left( t \right): = f\left( {x+td} \right),\quad t \geq 0

„näherungsweise“ minimiert wird. Dies ist die Schnittfunktion in Richtung der Abstiegsrichtung d.

opti-u09-schnitt-der-funktion

Beachte:

{\varphi ^\prime }\left( t \right) = \nabla f{\left( {x+td} \right)^T}d

Goldstein-Schrittweite

t > 0 ist eine Goldstein-Schrittweite bezüglich des Parameters \sigma \in \left] {0,\frac{1}{2}} \right[, falls

{\varphi _u}\left( t \right) \leq \varphi \left( t \right) \leq {\varphi _o}\left( t \right)\quad \quad \quad \quad \left( G \right)

mit den Geraden

{\varphi _o}\left( t \right) = \varphi \left( 0 \right)+\sigma t{\varphi ^\prime }\left( 0 \right)

{\varphi _u}\left( t \right) = \varphi \left( 0 \right)+\left( {1-\sigma } \right)t{\varphi ^\prime }\left( 0 \right)

opti-u09-goldstein-schrittweiten

Extremfälle:

\sigma = 0\quad \Rightarrow \quad {\varphi _u}\left( t \right) = \varphi \left( 0 \right),\quad {\varphi _u}\left( t \right) = \varphi \left( 0 \right)+t{\varphi ^\prime }\left( 0 \right)

\sigma = \frac{1}{2}\quad \Rightarrow \quad {\varphi _o}\left( t \right) = {\varphi _u}\left( t \right)

opti-u09-goldstein-schrittweiten-2

Das Verfahren wird in vielen Büchern vorgestellt, in der Praxis aber nicht verwendet, da es verschiedene Probleme hat. Unter anderem kann es passieren, dass der optimale Parameter gar nicht im untersuchten Intervall liegt.

Wolfe-Powell-Schrittweite

t > 0 ist eine Wolfe-Powell-Schrittweite bezüglich der Parameter \sigma \in \left] {0,\frac{1}{2}} \right[ und \rho \in \left[ {\sigma ,1} \right[, falls

(WP1) f\left( {x+td} \right) \leq f\left( x \right)+\sigma t\nabla f{\left( x \right)^T}d

(WP2) \nabla f{\left( {x+td} \right)^T}d \geq \rho \nabla f{\left( x \right)^T}d

Wir verwenden wieder die Hilfsfunktion

\varphi \left( t \right) = f\left( {x+td} \right),\quad t \geq 0

{\varphi ^\prime }\left( t \right) = \nabla f{\left( {x+td} \right)^T}d

Dies setzen wir in (WP1) und (WP2) ein:

(WP1) \varphi \left( t \right) \leq \varphi \left( 0 \right)+\sigma t{\varphi ^\prime }\left( 0 \right)

(WP2) {\varphi ^\prime }\left( t \right) \geq \rho {\varphi ^\prime }\left( 0 \right)

So werden zu kleine Schrittweiten vermieden.


Effizienz

Für viele Schrittweitenstrategien gilt:

\mathop {\lim }\limits_{k \to \infty } \frac{{\nabla f{{\left( {{x_k}} \right)}^T}{d_k}}}{{\left\| {{d_k}} \right\|}} = 0

Häufig gilt sogar:

\underbrace {f\left( {{x_k}+{t_k}{d_k}} \right)}_{ = {f_{k+1}}}-f\left( {{x_k}} \right) \leq -\theta {\left( {\frac{{\nabla f{{\left( {{x_k}} \right)}^T}{d_k}}}{{\left\| {{d_k}} \right\|}}} \right)^2}\quad \forall k

Lösung der Aufgabenstellung

Es gilt nun, die Abschätzung

f\left( {x+td} \right) \leq f\left( x \right)-\theta {\left( {\frac{{\nabla f{{\left( x \right)}^T}d}}{{\left\| d \right\|}}} \right)^2}

unter Verwendung der Lipschitz-Stetigkeit nachzuweisen.

Für x \in \mathcal{L}\left( {{x_0}} \right) = \left\{ {x \in {\mathbb{R}^n}|f\left( x \right) \leq f\left( {{x_0}} \right)} \right\},\quad t \in {T_{WP}}\left( {x,d} \right) ist x+td \in \mathcal{L}\left( {{x_0}} \right)

Sei \gamma > 0 die Lipschitz-Konstante für\nabla f.

Nach (WP2) gilt:

\rho \nabla f{\left( x \right)^T}d \leq \nabla f{\left( {x+td} \right)^T}d

Diesen Ausdruck erweitern wir nun:

\quad \Rightarrow \quad \rho \nabla f{\left( x \right)^T}d-\nabla f{\left( x \right)^T}d \leq \nabla f{\left( {x+td} \right)^T}d-\nabla f{\left( x \right)^T}d

Es gilt:

\rho \in \left[ {\sigma ,1} \right) , \sigma \in \left( {0,\frac{1}{2}} \right),

\Rightarrow \quad 0 < \underbrace {\left( {\rho -1} \right)}_{ < 0}\underbrace {\nabla f{{\left( x \right)}^T}d}_{ < 0} \leq \left\| {\left( {\nabla f{{\left( {x+td} \right)}^T}-\nabla f{{\left( x \right)}^T}} \right)d} \right\|

Nun wenden wir die Cauchy-Schwarzsche Ungleichung an:

\Rightarrow \quad 0 < \left( {\rho -1} \right)\nabla f{\left( x \right)^T}d \leq \left\| {\nabla f{{\left( {x+td} \right)}^T}-\nabla f{{\left( x \right)}^T}} \right\|\left\| d \right\|

Anschließend kommt jetzt die Lipschitz-Stetigkeit von \nabla f zum Einsatz:

\Rightarrow \quad 0 < \left( {\rho -1} \right)\nabla f{\left( x \right)^T}d \leq \gamma \left\| {x+td-x} \right\|\left\| d \right\| =

\Rightarrow \quad \left( {\rho -1} \right)\nabla f{\left( x \right)^T}d \leq \gamma t{\left\| d \right\|^2}

Diese Formel stellen wir nun nach t um:

\Rightarrow \quad t \geq \frac{{\left( {\rho -1} \right)\nabla f{{\left( x \right)}^T}d}}{{\gamma {{\left\| d \right\|}^2}}}

Nun setzen wir in (WP2) ein:

f\left( {x+td} \right) \leq f\left( x \right)+\sigma t\nabla f{\left( x \right)^T}d \leq f\left( x \right)+\sigma \frac{{\left( {\rho -1} \right)\nabla f{{\left( x \right)}^T}d}}{{\gamma {{\left\| d \right\|}^2}}}\nabla f{\left( x \right)^T}d

\quad \Rightarrow \quad f\left( {x+td} \right) \leq f\left( x \right)+\underbrace {\frac{{\sigma \left( {\rho -1} \right)}}{\gamma }}_{: = -\theta }{\left( {\frac{{\nabla f{{\left( x \right)}^T}d}}{{\left\| d \right\|}}} \right)^2}

\quad \Rightarrow \quad f\left( {x+td} \right) \leq f\left( x \right)-\theta {\left( {\frac{{\nabla f{{\left( x \right)}^T}d}}{{\left\| d \right\|}}} \right)^2}

q.e.d.

    \[\mathcal{J}\mathcal{K}\]