これは何?
- 一変数関数 $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]$ とする.グラフの概形は以下の通り.
モジュールの 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_scalar
と制約の与え方が異なるので注意- 公式ドキュメント
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)
- Dual Annealing optimization
- 公式ドキュメント
結果の比較
結果は以下の通り.
- いずれの場合でも(局所的)最適解が得られている
minimize
を使った場合のみ大域的最適解が得られているminimize_scalar
およびshgo
は局所的最適解に収束しているminimize
は初期点を大域的最適解の近傍で生成しているので上手く大域的最適解に収束しているdifferential_evolution
およびdual_annealing
も大域的最適解が得られているが,あくまでヒューリスティック解法なので収束先が異なる場合があり得る
追記記録
differential_evolution
とdual_annealing
の記述を追加