Schrittweite nach Armijo-Goldstein Vorgegeben seien Konstanten δ

Schrittweite nach Armijo-Goldstein
Vorgegeben seien Konstanten δ ∈ (0, 1), γ > 0 und β1 , β2 mit 0 < β1 ≤ β2 ≤ 1.
(x)> d
Schritt 1: Wähle Startschrittweite σ (0) = −γ ∇fkdk
und setze j := 0.
2
Schritt 2: Ist f (x + σ (j) d) ≤ f (x) + δσ (j) ∇f (x)> d, so setze σA := σ (j) und beende die
Suche nach σA .
Schritt 3: Wähle σ (j+1) ∈ [β1 σ (j) , β2 σ (j) ], setze j := j + 1 und gehe zu Schritt 2.
Praktische Aspekte:
1. Ist d die Newton-Richtung, so wählt man σ (0) := 1, um von der lokal quadratischen
Konvegenz für gute Näherungswerte x = x(k) profitieren zu können. Im allgemeinen
wählt man
∇f (x)> d
∇f (x)> d
σ (0) ∈ [−γ
,
−γ̃
]
kdk2
kdk2
mit einer vorgegebenen Konstanten γ̃, um eine beschränkte Schrittweitenfolge (σk )
zu garantieren.
2. Typische Parameterwerte: δ = 10−3 , γ = 10−4 , γ̃ = 104 , β1 = 0.1, β2 = 0.7,
maximale Anzahl an Suchschritten: ≈ 25
3. Bestimmung von σ (j+1) in Schritt 3 des Algorithmus:
σ (j+1) := min{β2 σ (j) , σ̄ (j+1) }
mit σ̄ (j+1) gemäß
σ̄ (j+1) =
−∇f (x)> d
.
2(f (x + d) − f (x) − ∇f (x)> d)
Für quadratische Optimierungsprobleme ist σ̄ (j+1) = σE .
1

Download Report