Python SciPy : 多変数スカラー関数の制約なし局所的最適化

多変数関数の最適化手法は様々な方法が提案されており、局所的または大域的最適化のどちらが必要なのか、問題の制約条件の有無、偏導関数を定義できるかどうか等を考慮して手法を選択します。
SciPy でも様々なルーチンで最適化計算ができます。その中で今回は多変数スカラー関数の制約なし局所的最適化アルゴリズムについてまとめます。

関数について

SciPy で多変数関数の最適解を求めるには minimize を使います。
minimize はオプション引数の method で最適化アルゴリズムを指定できるようになっています。
fmin, fmin_powell 等の関数でも同じに計算できますが、minimize の使用が推奨されています。

Table 1: 多変数スカラー関数の制約なし局所的最適化
関数 説明 勾配ベクトル、ヘッセ行列の要否
minimize(method="nelder-mead") Nelder-Mead の 滑降シンプレックス法 不要
minimize(method="powell") 修正 Powell 法 不要
minimize(method="cg") 共役勾配法(Polak-Ribiere 法) 勾配ベクトル
minimize(method="bfgs") BFGS 法 (Broyden-Fletcher-Goldfarb-Shanno 法) 勾配ベクトル
minimize(method="newton-cg") Newton-CG 法(Newton-Conjugate-Gradient 法 ) 勾配ベクトル、ヘッセ行列
minimize(method="trust-ncg") 信頼領域 Newton-CG 法 勾配ベクトル、ヘッセ行列
minimize(method="dogleg") 信頼領域 dog-leg 法 勾配ベクトル、ヘッセ行列

各最適化アルゴリズムの特徴は SciPy lecture notes の第 2 章にも書かれており大変参考になります。

最適化においては完全なアルゴリズムが存在しないため、問題ごとに 2 通り以上の方法を試し、結果や収束速度などを比較することが推奨されています。

Nelder-Mead の滑降シンプレックス法は偏導関数を使わないため収束が非常に遅いですが、場合によっては非常に頑強な手法です。ちょこっと試しに収束解を求めてみようというときには有用です。
滑降シンプレックス法以外の手法は基本的に次の探索方向の選び方が違うだけです。

修正 Powell 法は偏導関数の計算が困難なときによく使われます。
滑降シンプレックス法より収束が速いので、偏関数が与えられないときはこの手法を使ってみると良いでしょう。

共役勾配法と後述の BFGS 法は 1 階偏導関数を与えてやる必要があります。
偏導関数を与えなくても使えますが、その場合収束は遅くなります。
共役勾配法は、大規模問題でも比較的少量のメモリしか使わず、各ステップの計算が非常に速いという特徴があります。
ただ、BFGS 法と比べると反復計算の回数は多くなることがあります。
そのため、計算規模の小さな問題(関数とその勾配の計算が簡単)の最小化には BFGS 法より適しています。

BFGS 法 は 準 Newton 法の一つなので Newton 法に比べてヘッセ行列の逆行列を計算する必要がなく省メモリな方法です。
Newton 法と同じで、解の近傍に初期点を選ばないと必ずしも収束するとは限りません。
共役勾配法と比べて関数の評価回数が少ないため、計算規模の大きな関数の最適化に向いています。
また、問題が非 2 次形式の場合、共役勾配法よりも頑強です。

Newton-CG 法は Newton 法の修正版の一つで、探索方向の計算に共役勾配法を使用しています。
Newton 法の収束は速いですが、初期点が解の近傍にないと収束しないことがあり、ヘッセ行列が正定値である必要や、比較的大量のメモリを要し大規模問題に適用できない注意点があります。
newton-cg は Python で実装されており、C 言語で実装されている tnc (制約付き Newton-CG 法)の方が計算が速いため、制約なし最適化でも tnc を使いましょう。
小規模な問題なら newton-tnc は trust-ncg、dogleg よりも速いです。

信頼領域 Newton-CG 法は Newton 法でサブアルゴリズムに直線探索法ではなく信頼領域法を使用した方法です。
実質制約なしの最適化を制約付き最適化として計算するため、直線探索法より計算は複雑です。
信頼領域法はまず二次近似が妥当であると思われる領域を定め、その領域内において二次近似モデルの最小化を行います。
信頼領域内には必ず最小解が存在するため信頼領域法ではヘッセ行列が正定値である必要はありません。
直線探索法の Newton 法よりも信頼領域法の方が安定して解を得られますが、その分計算コストは高いです。

信頼領域 dog-leg 法はまず信頼領域法と同様にして信頼領域を構成した後、信頼領域内にて最降下方向と Newton 法の探索方向との間の方向を探索方法とする方法です。
具体的には、信頼領域が狭い場合には最降下方向に近く、信頼領域が広い場合には Newton 法の方向に近くなります。
信頼領域法や各 Newton 法よりも反復回数が多いですが、一回あたりの反復が遥かに速く、またメモリ使用量も僅かに少ないため多少大規模な問題にも適用できるのが利点です。
ヘッセ行列が正定値である必要があることには注意が必要です。

以前に自前で定義した Newton 法 と同様の例で収束解を求めてみます。
この例題だと Python で書いていても直線探索の Newton 法の方が若干速かったです。
問題によって適宜アルゴリズムを選択することが大事です。

# coding: utf-8
import numpy as np
from scipy.optimize import minimize

def objectiveFunction(x):
    # 目的関数
    # f(x,y) = 3*x1^2 + 2*x1*x2 + x2^2
    f = 3*x[0]**2 + 2*x[0]*x[1] + x[1]**2
    return f

def gradient(x):
    # 勾配ベクトル
    g = np.array([6*x[0] + 2*x[1], 2*x[0] + 2*x[1]])
    return g

def Hessian(x):
    # ヘッセ行列
    h = np.array([[6, 2],
		  [2, 2]])
    return h

x0 = [10.0, 10.0]
res = minimize(objectiveFunction, x0, jac=gradient, hess=Hessian, method="trust-ncg")
print(res)
    fun: 1.4791141972893971e-31
      x: array([ -2.22044605e-16,   4.44089210e-16])
   njev: 6
   hess: array([[6, 2],
      [2, 2]])
   nhev: 5
   nfev: 6
success: True
    nit: 5
message: 'Optimization terminated successfully.'
    jac: array([ -4.44089210e-16,   4.44089210e-16])
 status: 0

コメント

Comments powered by Disqus
書籍更新情報
2016-10-21
Pythonによる科学技術計算 基礎編
PDF版の販売を開始しました。
販売ページはこちら

2016-09-09
Pythonによる科学技術計算 基礎編
1.2版への更新が可能になりました。
サポートページはこちら
電子書籍
Pythonによる科学技術計算 基礎編
Kindle ストア、Leanpubで販売中です
Pythonによる科学技術計算 基礎編
PDF版の販売はこちら
同人誌
技術書典(2016/6/25)
Emacs/org-modeのPDF作成術
電子版をBOOTHで販売中です
Emacs/org-modeのPDF作成術
Share