冷めたコーヒー

Weniger, aber besser

非線型一変数関数の最小化(SciPy 使用)

これは何?

  • 一変数関数 $f\colon\mathbb{R}\to\mathbb{R}$ を与えられた閉区間 $\Omega \subseteq \mathbb{R}$ 上で最小化する $x^\star$ を求める方法について扱う
  • 最適化問題として記述すると以下のように表される: \begin{align} \min \quad &f(x) \\ \mathrm{s.t.} \quad &x \in \Omega. \end{align}
  • アルゴリズムの詳細には一切触れず,scipy.optimize モジュールに含まれる以下の関数を用いる:
    • minimize_scalar
    • shgo
    • minimize
    • differential_evolution
    • dual_annealing
  • 詳しい使い方は公式ドキュメントを参照されたい

実装

適当な関数 $f$ が必要なので,ここでは以下の非線型関数を扱う.

$$ f(x) = \frac{3}{7} \cos\left(\frac{3}{2} x\right) - \sin\left(\frac{1}{3} x\right) + \frac{1}{3} \sin(x^2) - 1 $$

制約条件は,$\Omega = [0, 2\pi]$ とする.グラフの概形は以下の通り.

f:id:mirucacule:20210914183056j:plain
グラフの概形

モジュールの import

import numpy as np
from scipy.optimize import minimize_scalar, shgo, minimize
import matplotlib.pyplot as plt
from scipy.optimize import differential_evolution, dual_annealing

minimize_scalar

res = minimize_scalar(f, bounds=(0, 2*np.pi), method="bounded")
print(res.x)
print(res.fun)
  • 結果は res.x で最適解,res.fun で最適値がそれぞれ得られる
  • 制約付きのため method="bounded" を指定
  • 公式ドキュメント

shgo

res = shgo(f, bounds=[(0, 2*np.pi)])
print(res.x)
print(res.fun)

minimize

div = 100
x = np.linspace(0, 2*np.pi, div)
y = f(x)
x0 = (2 * np.pi / div) * (np.argmin(y) + 1) # initial point
bnds = ((0, 2 * np.pi),)
res = minimize(f, x0, method='Nelder-Mead', bounds=bnds, tol=1e-6)
print(res.x)
print(res.fun)
  • minimize には初期点が必要
  • 初期点は閉区間 $\Omega=[0, 2\pi]$ を 100 分割し,その中で最も関数値が小さいところを採用
  • 制約を ((0, 2 * np.pi),) のように与えているが最後の , は誤字ではない
  • 公式ドキュメント

differential_evolution

res = differential_evolution(f, bounds=[(0, 2*np.pi)], disp=False)
print(res.x)
print(res.fun)

dual_annealing

lw = [0]
up = [2 * np.pi]
ret = dual_annealing(f, bounds=list(zip(lw, up)))
print(res.x)
print(res.fun)

結果の比較

結果は以下の通り.

f:id:mirucacule:20210914220644j:plain
結果

  • いずれの場合でも(局所的)最適解が得られている
  • minimize を使った場合のみ大域的最適解が得られている
  • minimize_scalar および shgo は局所的最適解に収束している
  • minimize は初期点を大域的最適解の近傍で生成しているので上手く大域的最適解に収束している
  • differential_evolution および dual_annealing も大域的最適解が得られているが,あくまでヒューリスティック解法なので収束先が異なる場合があり得る

追記記録

  • differential_evolutiondual_annealing の記述を追加