【文献調査】BFGSの基礎

細江 則彰, 廣安 知之, 三木 光範

ISDL Report　 No. 20060807008

2006年 9月 20日

Abstract

本報告は，連続最適化問題かつ非線形計画問題に適用できる，準ニュートン法の代表的な手法であるBFGS法について文献調査を行う．BFGS法は，Broyden，Fletcher，Goldfarb，Shanno の4人によって発表された手法であり，ニュートン法の問題点である「Hesse行列の計算に多くの計算量が必要」を解決するアルゴリズムである．

1  はじめに

本報告では，準ニュートン法の代表的な手法であるBFGS法について文献調査を行う．BFGS法は，Broyden，Fletcher，Goldfarb，Shanno の4人によって発表された手法であり，ニュートン法の問題点である「Hesse行列の計算に多くの計算量が必要」を解決するアルゴリズムである．

2  最適化問題と最適化手法

2.1  最適化問題

最適化の定義は「与えられた制約条件g(x)のもとで, ある目的関数f(x)を最小にするような設計変数を求めること」である．

また最適化問題は一般的に以下のように表される.

eq-001 (1)

最適化問題は，その数学的性質から，連続最適化問題と離散最適化問題の２つに分けることができる．連続最適化問題とは探す値が連続的に分布している問題であり，離散最適化問題とは探す値が離散的に分布している問題である．また、連続最適化問題はさらに線形計画問題と非線形計画問題との２つに分けることができる．

2.2  最適化手法

最適化手法は，対象とする最適化問題の性質により，大きく以下のように分類される．

  1. 線形計画法（LP : Linear Programming）

    2. f(x) 及び gj(x) がすべて線形である場合．(シンプレックス法など)

  2. 非線形計画法（NP : Nonlinear Programming）

    3. f(x) または gj(x) に，非線形の式が含まれる場合．(制約なし：最急降下法，ニュートン法，準ニュートン法　　　制約あり：ペナルティ法，逐次2次計画法など)

  3. 組み合わせ最適化（Combinattorial Optimization）

    4. x の値として，離散的な値だけをとるような式が含まれる場合．(欲張り法，分枝限定法など)

  4. 探索的手法・経験的手法（Heuristics)

    5. 幅広い最適化問題に適用可能な方法である．(Simulated Annealing：SA，Genetic Algorithm：GA，Directed Heuristic Search：DHSなど)

3  非線形計画法

3.1  基本アルゴリズム

少なくとも1回微分可能なn次元の非線形関数 f(x) があるとき式(2), x = xopt が最適解であるための必要条件は式(3)が成り立つことである.

kansu (2)

joken (3)

∇f(x) は f(x) の勾配ベクトルであり, f(x) の等高面の法線ベクトルを与える. このベクトルの向きは関数の増加する方向になる.

最適解を求めるアルゴリズムは通常次の3つのステップで構成される.

  1. 適当な x の初期点 x0 を与える. 繰り返しのパラメータ k = 0 とする.
  2. 最適性の判定. || ∇f(x) = 0 ||　ならば終了.
  3. 次に調べる探索点 xk+1 を生成する. k = k + 1 とし, ステップ2に戻る.

ステップ3における次の探索点 xk+1 は, 現在の探索点 xk における目的関数値 f(xk) とその勾配によって決定される. 探索する向きを sk , その方向にそったステップ幅を α とすると, 式(4)のように表すことができる.

koshin (4)

探索する方向 sk を決める方法は大きく3つある.

本報告では, 代表的なアルゴリズムである「最急降下法」と「ニュートン法」と「準ニュートン法」について述べる.

3.2  最急降下法(Steepest Descent Method)

最急降下法では, xk+1を目的関数の勾配ベクトルを用いて決定する. 勾配ベクトルは目的関数値が最も大きくなる方向なので, 勾配ベクトルの逆向きに探索していけば良い. つまり探索の方向 sk は

steepest_s (5)

となり, 次の探索点xk+1は

steepest_next (6)

で求めることができる. ステップ幅αは正の定数にする．この方法の変形として，ステップ幅αを１次元最適化によって求める方法を，最適勾配法(optimul gradient method)という．

最急降下法の特徴は以下の通りである．

3.3  ニュートン法(Newton's Method)

ニュートン法では各反復において，関数を xk でテイラー展開して得られる２次関数

008 (7)

が最小になる点を次の反復点 xk+1 とする． xk+1 を目的関数のHesse行列を用いて決定する. Hesse行列は f(x) の2回微分で,

hesse (8)

となる.

ニュートン法における探索の方向 sk は

newton_s (9)

となり, 次の探索点xk+1は

newton_next (10)

で求めることができる.

ニュートン法の特徴は以下の通りである．

3.4  準ニュートン法

ニュートン法においてHesse行列を計算せずに, 勾配ベクトルを用いて近似的に逐次生成する方法である．主にBFGS法とDFP法がある．以下にBFGS法について詳しく説明する．

4  BFGS法

ニュートン法の欠点である，Hesse 行列の逆行列を計算しなければならない点を解決するために，勾配ベクトルを用いて，Hesse 行列の逆行列に収束するような行列の列を，逐次近似によって構成していく方法である．そのアルゴリズムは以下に示す通りである．

  1. 初期化

    2. 初期点 x(0) を与え，k = 0，H(0) = I （単位行列）とする．

  2. 探索方向の計算

    3. ∇f(x(k)) を計算し，‖∇f(x(k)) ‖ ＜ ε ならば，計算を終了する．

  3. 直線探索

    4. 次点を　x(k+1) = x(k) - α(k) H(k) ∇f(x(k)) とすると，ステップ幅である α(k) を1次元探索[4.1節]で決める．α ＜ ε ならば，計算を終了する．

  4. H(k)の更新

    5. Hesse行列 H(k+1) を計算する．ただし，s(k) ≡ x(k+1) - x(k)， y(k) ≡ ∇f(x(k+1)) - ∇f(x(k)) 　とする．

    bfgs (11)

  5. k = k + 1 として，ステップ 2 へ戻る．

BFGS法の特徴は以下の通りである．

4.1  αの1次元探索

αの1次元探索の方法はいくつか考えられるが，ここでは黄金分割法と2次多項式近似による方法を説明する．

4.1.1  黄金分割法

区間 [a, b] の中に，f(x) が最小となる点が一つだけあるとする．黄金分割法では，最小点が存在する区間を徐々に狭めていくことによって，最小点を求めようとする方法である．

Fig 1の左図のように，区間内の１つの点の値を知っただけでは，区間 [a, c]，区間 [c, b] のいずれに最小点があるのかを一般的に知ることは不可能である．

Fig 1: サンプル点の違い [出展 : 参考文献2]

しかし，Fig 1の右図のように，区間内の２点における f(x) の値を知ることができれば，f(c) と f(d) の大小関係により，区間 [a, d]，区間 [c, b] のいずれに最小点があるかを知ることが可能である．

Fig 2: サンプル点の位置 [出展 : 参考文献2]

黄金分割法では，Fig 2のように τ = （50.5 - 1) / 2 ≒ 0.618 を使用する．初期区間 [a(0), b(0)] を与えた後，収束条件（｜b(k) - a(k)｜ < ε）が成立するまで，以下の手続きを繰り返す．

  1. f(x2(i)) ＞ f(x1(i)) のとき

    a(i+1) = a(i)
    b(i+1) = x2(i)
    x1(i+1) = a(i) + (1 - τ)(b(i+1) - a(i))
    x2(i+1) = x1(i)

  2. f(x2(i) ≦ f(x1(i)) のとき

    a(i+1) = x1(i)
    b(i+1) = b(i)
    x1(i+1) = x2(i)
    x2(i+1) = b(i) - (1 - τ)(b(i) - a(i+1))

従って，区間の幅を一定の比率 τ で減少させることができる．

4.1.2  2次多項式近似による方法

a1 ＞ a2 ＞ a3，かつ，f(a1) ＞ f(a2) ＜ f(a3) となる3点が与えられたとき，この3点を通る2次多項式 f(x) = ax2 + bx + c の係数は一意に決まる．また，この関数は， x = -b / 2a で，最小値をとる．2次多項式近似による方法は，この性質を利用して最小値を求めるものである．そのアルゴリズムは以下の通りである．

  1. 初期点 x0 と，初期の刻み幅 δ0 を与え，k = 0 とする．

  2. xk+1 = xk + δk とし，f(xk+1) を計算する．

  3. f(xk+1) ≦ f(xk) ならば，δk+1 = 2δk，k = k + 1 として 2. へ戻る．

  4. f(xk+1) ＞ f(xk) で，かつ，k ≧ 1 ならば，

    • xk+2 = xk+1 - δk / 2 とし，f(xk+2) を計算する．

    • δk/2 間隔の４点 xk-1，xk，xk+2，xk+1 の内，最小の関数値を与える点から最も遠い点を除去する．

    • 残った３点を小さい順に a1，a2，a3 として，5. へ進む．

    f(xk+1) ＞ f(xk) で，かつ，k ＝ 0 ならば，

    • f(x0-δ0) を計算する．

    • f(x0-δ0) ＞ ｆ(x0) ならば，
      • a1 = x0 - δ0，a2 = x0，a3 = x1 として，5. へ進む．
      f(x0-δ0) ≦ f(x0) ならば，
      • x1 = x0 - δ0，δ0 = -δ0，δ1 = 2δ0，k ＝ １ として，2. へ戻る（反対方向への探索）．

  5. a1，a2，a3 を用いて，2次多項式近似を作る（3点を通る2次多項式を決定）．この2次多項式の最小点は，δ を3点の間隔とすると，式(12)で与えられる．

    eq12 (12)

  6. |Δ|が十分小さければ， x を最小点として採用する．

    そうでなければ， x と a2 の，関数値の小さい方を x0，δ0 = δ / 2，k ＝ 0 として 2. へ戻る．

5  おわりに

本報告では，BFGS法について文献調査を行った．BFGS法は準ニュートン法に分類される．ニュートン法は探索の方向ベクトルをHesse行列の逆行列を用いて決定しているため非常に計算量が多くなる．そこでBFGS公式でHesse行列の逆行列を近似して計算量を軽減した手法がBFGS法である．数理計画法の中でも重要な手法であることが分かった．

Reference

[1]
福島雅夫.
システム制御情報ライブラリー　数理計画入門
朝倉書店，1998
[2]
システム・エンジニアの基礎知識
http://www.sist.ac.jp/~suganuma/kougi/other_lecture/SE/SE.html
[3]
Webコンピューティングを用いた教育システムの構築
http://zeus.mech.kyushu-u.ac.jp/~tsuji/java_edu/applet.html
[4]
佐藤史隆, 平井聡, 鈴木 和徳, 宇野尚子, 廣安 知之, 三木 光範
最適化の基礎
http://mikilab.doshisha.ac.jp/dia/research/report/2005/0716/002/report20050716002.html

Copyright


Copyright (C) 2006 Tomoyuki Hiroyasu, All rights reserved.
Copyright (C) 2006 Mitsunori Miki, All rights reserved.
Copyright (C) 2006 Noriaki Hosoe, All rights reserved.

No part of this document may be reproduced, copied, distributed,
transferred, modified, or transmitted, in any form or by any means,
without the prior written permission of the authors.
In no event shall the authors be liable for any damages caused in any way
out of the use of this document．



File translated from TEX by TTH, version 3.40.
Back to Top