11月26日

最適化手法講義資料（平成 26 年度冬学期）
実用的な直線探索の実装法
無制約最適化問題における直線探索の，具体的な実装方法について説明する．
• この資料は，
– 無制約最小化のプログラムを実際に組んでみたい
– アルゴリズムの実装法の詳細に興味がある
などという人向けの，補助資料です．講義の履修・単位の取得に，プログラミングは必要ではありません．
• 最急降下法の実装例を，講義資料の web ページに置きます（Matlab 版と Scilab 版）1 ．興味のある人
は，実際に動かしてみて下さい．Matlab や Scilab そのものの使い方については，例えばテキスト [1] な
どを参照して下さい．
1. 直線探索の復習
関数 f : Rn → R の無制約最小化を，更新公式
xk+1 = xk + αk dk
(1)
に基づく反復法で解く．ただし，探索方向 dk は点 xk における f の降下方向であるとする．このと
き，ステップ幅 αk を（たとえば）Wolfe の条件が満たされるように選べば，アルゴリズムの局所最適
解への大域的収束性を保証することができる2 ．簡単のために記号 fk := f (xk ), ∇fk := ∇f (xk ) を用
い，c1 ∈ (0, 1) および c2 ∈ (c1 , 1) を定数とすると，Wolfe の条件は
f (xk + αdk ) ≤ fk + c1 α∇fk⊤ dk
(2)
∇f (xk + αdk )⊤ dk ≥ c2 ∇fk⊤ dk ,
(3)
である．なお，条件 (2) は Armijo の条件である．
2. バックトラック法
直線探索を実行する手法として，バックトラック法 (backtracking approach) と呼ばれるアルゴリ
ズムがよく用いられる．その基本となるのは，次の事実である．
命題 1. 方向 dk を点 xk における関数 f の降下方向であるとする．また，直線探索を行う半直線
{xk + αdk | α ≥ 0} 上で f は下に有界であることを仮定する．このとき，α
ˆ > 0 が存在して，任意の
α ∈ (0, α
ˆ ] が条件 (2) を満たす．
証明. 関数 ϕ : R → R を
ϕ(α) = f (xk + αdk )
1
2
http://www.simplex.t.u-tokyo.ac.jp/~ykanno/lecture/
講義資料『直線探索による降下法の大域的収束性』を参照．
1
(4)
で定義する．仮定より，任意の α ≥ 0 に対して ϕ(α) の値は下に有界である．一方，直線
l(α) = fk + (c1 ∇fk⊤ dk )α
(α ≥ 0)
を考えると，∇fk⊤ dk < 0 （dk は降下方向であるから）かつ 0 < c1 < 1 であることから，
α → +∞ ととると l(α) は下に非有界である．従って，ϕ のグラフと l のグラフは α > 0
で少なくとも 1 回交差する．これらが交差するような α > 0 の値の最小値を α
ˆ とおくと，
α
ˆは
f (xk + α
ˆ dk ) = fk + (c1 ∇fk⊤ dk )ˆ
α
を満たす．また，十分小さな α > 0 は条件 (2) を満たすことは明らかなので，区間 (0, α
ˆ]
において条件 (2) が成り立つ．
Wolfe の条件において (3) が課されているのは，α が小さ過ぎる値を取ることを防ぐためである．つ
まり，α が条件 (2) を満たし，かつ小さ過ぎないならば，ステップ幅 αk として実用的には許容でき
る．次のアルゴリズム 1 では条件 (2) のみを判定しているが，実際に得られる出力 αk は小さくなり
過ぎないことが期待できる．
アルゴリズム 1 (バックトラック法による直線探索).
Step 0: 初期値 α
¯ > 0 と定数 ρ ∈ (0, 1), c1 ∈ (0, 1) を選ぶ．α = α
¯ とおく．
Step 1: 停止条件 f (xk + αdk ) ≤ fk + c1 α∇fk⊤ dk が満たされていれば，αk := α を解として
出力し，終了．
Step 2: α := ρα とおいて Step 1 へ．
命題 1 より，アルゴリズム 1 は有限回の反復で終了する．実際，初期値 α
¯ が条件 (2) を満たすなら
ば，αk = α
¯ を出力して終了する．それ以外の場合には，α
ˆ<α
¯ であり，α が初めて α
ˆ 以下になった
時点で終了する．いま，α = ρk α
¯ のように α を徐々に減少させながら探索しているので，α は有限回
の反復で α
ˆ 以下になる．これをまとめると，
αk = α
¯
αk ∈ (ρˆ
α, α
ˆ]
or
が成り立つ．このように，アルゴリズム 1 で得られる αk は（3 節で述べるような方法により α
¯ を適
切に選ぶと）小さ過ぎる値にはならない．
3. バックトラック法の初期値 α
¯ について
アルゴリズム 1 の Step 0 では，入力としてステップ幅 α の初期値 α
¯ を与える必要がある．ステッ
プ幅 αk は 0 < αk ≤ α
¯ の範囲だけで探索されるため，α
¯ を適切に選ぶ必要がある．
Newton 法や準 Newton 法では，最適解の十分近くにおいてステップ幅 αk = 1 が採用されるならば，
解への早い収束（超 1 次収束や 2 次収束）が保証される3 ．従って，アルゴリズム 1 において α
¯=1と
選ぶことは自然である．というのも，こう選ぶことで，もし α = 1 が Step 1 の条件を満たすならば
必ず αk = 1 が採用されるからである．
3
講義資料『準 Newton 法の超 1 次収束性』を参照．
2
最急降下法の探索方向は，このような性質を持たないため，α
¯ の選び方は自明ではない．よく用い
られる決め方は，
「1 つ前の反復における f の減少量と同じ程度の減少が期待できるような値 α を α
¯
として選ぶ」というものである．つまり，条件
fk − f (xk + αdk ) ≃ fk−1 − fk
を満たす α を α
¯ とすることを考える．実際には，この条件の両辺の 1 次の項のみに注目し，条件
⊤
α∇fk⊤ dk = αk−1 ∇fk−1
dk−1
を満たす α を選ぶこととする．従って，この場合に α
¯は
α
¯ = αk−1
⊤ d
∇fk−1
k−1
∇fk⊤ dk
で与えられる．
また，f の多項式補間を利用して α
¯ を決める方法もよく用いられる．そもそもステップ幅 αk は，
(4) で定義される ϕ(α) を（α > 0 の範囲で）最小化することが望ましい．そこで，
「ϕ を簡単な関数で
近似して，その近似関数の最小解を α
¯ として選ぶ」ことを考える．例えば，ϕ を 2 次関数
ϕQ (α) = a1 α2 + a2 α + a3
(5)
で近似することにする．近似の条件としては，ϕQ が
ϕQ (0) = ϕ(0),
ϕQ (1) = ϕ(1),
ϕ′Q (0) = ϕ′ (0)
(6)
を満たすことを要請する．ここで，ϕQ の定義 (5) より
ϕQ (0) = a3 ,
ϕ′Q (0) = a2
(7)
ϕ′ (0) = ∇fk⊤ dk
(8)
ϕQ (1) = a1 + a2 + a3 ,
であり，一方 ϕ の定義 (4) より
ϕ(0) = fk ,
ϕ(1) = f (xk + dk ),
である．(6) に (7) および (8) を代入し，a1 , a2 , a3 について解くと
a1 = f (xk + dk ) − fk − ∇fk⊤ dk ,
a2 = ∇fk⊤ dk ,
a3 = fk
が得られる．これで，関数 ϕQ が得られた．ところで，ϕQ の 1 次の最適性条件 ϕ′Q (α) = 0 より
α = −a2 /(2a1 ) が得られる．従って，α の初期値として
α
¯=−
∇fk⊤ dk
1 a2
1
=−
2 a1
2 f (xk + dk ) − fk − ∇fk⊤ dk
(9)
が得られる．
参考文献
[1] 櫻井鉄也：
『Matlab/Scilab で理解する数値計算』. 東京大学出版会 (2003).
(November 26, 2014, 寒野)
3

Download Report