10月29日

最適化手法講義資料（平成 26 年度冬学期）
最急降下法の概要
微分可能な関数 f : Rn → R の無制約最小化問題を考える．簡単のために，記号
fk ≡ f (xk ),
∇fk ≡ ∇f (xk )
を用いる．
この問題の最適解を求める最急降下法 (steepest descent method) の概要は次の通りである．
アルゴリズム 1 (最急降下法).
Step 0: 初期点（出発点）x0 ∈ Rn を選ぶ．十分小さい定数 ϵ > 0 を定め，k = 0 とおく．
Step 1: 停止条件 ∥∇fk ∥ < ϵ が満たされていれば，xk を解として終了．
Step 2: 探索方向を dk = −∇fk で定める．
Step 3: 直線探索（後述）によりステップ幅 αk > 0 を定める．
Step 4: xk+1 = xk + αk dk と更新する．k ← k + 1 とおいて Step 1 へ．
注意 1. 無制約最小化の計算法では，最適性の 1 次の必要条件
∇f (x∗ ) = 0
を満たす点 x∗ を求めることを目標にする．この条件は
∥∇f (x∗ )∥ = 0
(1)
と等価である．しかし，現実には数値誤差などが存在するため，条件 (1) が厳密に満たさ
れることは期待できない．そこで，条件 (1) を少し緩めて，たとえば条件
∥∇f (xk )∥ < ϵ
(2)
を満たす xk が得られたならば，それを解として出力する（ここで，ϵ はあらかじめ定め
た十分に小さい正の定数である）．アルゴリズム 1 の step 1 では，条件 (2) をアルゴリズ
■
ムの停止条件として用いている．
アルゴリズム 1 の step 3 において αk を定める方法を説明する．まず，関数 ϕk : R → R を
ϕk (α) = f (xk + αdk ),
α≥0
(3)
で定義する．Step 2 において dk が既に得られているので，(3) における xk および dk は定ベクトル
であることに注意する．つまり，ϕk は 1 変数の関数である．
点 xk を通り，向きが dk で与えられる直線を考える．ϕk (α) は，この直線上で目的関数 f がどの
ように変化するかを表している．そこで，α ≥ 0 を満たす α のうち ϕk (α) を最小にするものをステッ
1
プ幅 αk として採用することを考える．この操作を正確な直線探索 (exact line search) と呼ぶ．つま
り，1 変数の最小化問題
min{ϕk (α) | α ≥ 0}
(4)
α
の最適解を αk とおく．
問題 (4) は 1 変数の最小化問題なので，元の問題（n 変数の最小化問題）よりは扱いやすい．とはい
うものの，正確な直線探索はあくまで理論上の考え方である．実際には，(4) を解く必要はなく，もっ
と「緩い」条件を満たす α をステップ幅 αk として選べば十分であることが知られている．Armijo
の条件や Wolfe の条件は，直線探索において実際に用いられる代表的な条件である．
図 1 は，関数
f (x) = 3x21 − 4x1 x2 + 3x1 + 6x22 + 8x2
(5)
の最小化問題に，Armijo の条件を用いた直線探索付きの最急降下法を適用した様子を表している．こ
こで，初期点は x0 = (4, 8)⊤ と選んだ．また，この問題の最適解は x∗ = (−2.4286, −2.1429)⊤ である．
steepest descent
10
x2
5
0
−5
−10
−5
0
5
x1
図 1: (5) の最小化問題に対する最急降下法の収束の様子
(October 29, 2014, 寒野)
2

Download Report