2次補間法を
Juliaで実装してみた

数理最適化のざっっくり入門 (2)

• 任意の最適化問題に対して最適値\(x^*\)を求めたい！
• しかし問題の性質で使えるアルゴリズムは変わる
  • \(D\) は有限集合?
  • \(f\) は線形?
  • \(f\) は滑らか?
  • \(f\) の微分が計算可能?
  • \(f\) は凸?
  • \(D\) は凸?
  • \(f\) は単峰?
  • 最適値の近くに初期値を配置できる?
  • etc.

以降では非線形連続最適化を扱います

数理最適化のざっっくり入門 (3)

非線形連続最適化に使えるアルゴリズムの例

• Newton法
  • 2階微分まで参照
  • 2次近似して放物線の頂点を次の探索点とする
• 最急降下法
  • 1階微分まで参照
  • \(\operatorname{grad}(f)\)の向きに下って次の探索点とする
• 焼き鈍し法
  • \(\exp(-\beta f(x))\)を正規化して確率密度関数を定義
  • 逆温度\(\beta\)を上げつつMCMCで探索点を更新

数理最適化のざっっくり入門 (4)

解きたい問題

• 非線形滑らか関数
• 多峰性がある

数理最適化のざっっくり入門 (4)

Newton法

収束は早いが初期値依存性が強い

数理最適化のざっっくり入門 (4)

最急降下法

初期値依存性が弱いが局所最適解に陥る

数理最適化のざっっくり入門 (5)

焼き鈍し法

多峰性を考慮できるが、計算量が多い
(Desmos力が足りず、デモが不十分…)

数理最適化のざっっくり入門 (4)

• Newton法
  • 😵‍💫 2階微分の計算が必要
• 最急降下法
  • 😔 1階微分の計算が必要
  • 🙄 Newton法に比べると遅い
  • 🧐 学習率の決め方に工夫が必要
• 焼き鈍し法
  • 🧐 逆温度の下げ方やサンプリングに工夫が必要
  • 😵 サンプリングベースなので最適値への収束が遅い

微分の計算が不要で収束が早くハイパラの工夫が不要なアルゴリズムが欲しい！
(∵ \(f\)がブラックボックスなら微分が取れない)

2次補間法による最適化 (詳細)

3点\((x_1, f(x_1)), (x_2, f(x_2)), (x_3, f(x_3))\)が与えられれば
これらを通る放物線\(\tilde{f}\)が一意に定まる (Lagrange補間)

\begin{align} \scriptsize \tilde{f}(x) = f(x_1)\frac{(x-x_2)(x-x_3)}{(x_1-x_2)(x_1-x_3)} + f(x_2)\frac{(x-x_1)(x-x_3)}{(x_2-x_1)(x_2-x_3)} + f(x_3)\frac{(x-x_1)(x-x_2)}{(x_3-x_1)(x_3-x_2)} \end{align}

この係数を整理して次の探索点が計算できる

ところで記法の提案

• Newton法 \(\newcommand\iter[2]{\underset{#1}{\underline{#2}}}\)
  • \(\iter{n}{x} = \iter{n-1}{x} - \iter{n-1}{\frac{f''(x)}{f'(x)}}\)
• 最急降下法
  • \(\iter{n}{x} = \iter{n-1}{x} - \alpha f'(\iter{n-1}{x})\)
• 記法のメリット
  • 添字の上下が入り乱れたときに便利
  • 手書き数式にも使いやすい

この記法を広めたい！！

2次補間法による最適化 (詳細2)

以下の式で探索を繰り返す！ \(\newcommand\iter[2]{\underset{#1}{\underline{#2}}} \newcommand\Pare[1]{\left(#1\right)}\)

\begin{align} \small \iter{n}{x} = \frac{1}{2} \cdot \frac{\iter{n-1}{f(x)}(\iter{n-2}{x^2}-\iter{n-3}{x^2}) + \iter{n-2}{f(x)}(\iter{n-3}{x^2}-\iter{n-1}{x^2}) + \iter{n-3}{f(x)}(\iter{n-1}{x^2}-\iter{n-2}{x^2})}{\iter{n-1}{f(x)}(\iter{n-2}{x}-\iter{n-3}{x}) + \iter{n-2}{f(x)}(\iter{n-3}{x}-\iter{n-1}{x}) + \iter{n-3}{f(x)}(\iter{n-1}{x}-\iter{n-2}{x})} \end{align}

1次元問題, 収束の様子

using Plots
plot(f; xlims=(-5,5), color=:red3, label="objective")
plot!(xs, f.(xs); color=:blue3, label="iteration")
scatter!(xs_init, f.(xs_init); color=:blue3, label="initial points")

1次元問題, 目的関数の値の減少

目的関数に対して単調減少に探索できてるか確認

plot(f.(xs); label="objectve")

1次元問題, 目的関数の値の減少 (log)

logスケールで確認
→探索が進むにつれて放物線近似の数値誤差が拡大

plot(f.(xs).-minimum(f.(xs)).+eps(Float64); label="objectve", yscale=:log10)

最適化問題の設定

\begin{align} f\left(x,y\right)=x^{2}+\sin\left(x\right)+1.5y^{2}+\sinh\left(y\right)-\frac{xy}{5} \end{align}

解いてみる

using Random
Random.seed!(42)
f(x,y) = x^2 + sin(x) + 1.5y^2 + sinh(y) - x*y/5
xs_init = rand(6)
ys_init = rand(6)
xs = copy(xs_init)
ys = copy(ys_init)
for _ in 1:100
    x, y = rec2D(xs[end-5:end], ys[end-5:end])
    push!(xs,x)
    push!(ys,y)
end

2次元問題, 収束の様子

xs_plot = -3:0.1:3
ys_plot = -5:0.1:3
zs_plot = f.(xs_plot', ys_plot)
plot(xs_plot, ys_plot, zs_plot; levels=-40:40, label="objective")
plot!(xs, ys; color=:blue2, label="iteration")
scatter!(xs_init, ys_init, label="initial points")

2次元問題, 目的関数の値の減少

plot(f.(xs, ys); label="objective")

2次元問題, 目的関数の値の減少 (log)

plot(f.(xs, ys) .- minimum(f.(xs, ys)) .+ eps(Float64); label="objective", yscale=:log10)

FAQ

• なぜ2次近似なんですか？
  • 1次近似
    • 勾配は分かるが学習率を決める必要がある(すこし面倒)
  • 3次近似
    • 頂点が存在しなかったり
    • 非一意的だったり
• 有名な手法なんですよね？
  • わからない
  • しっかり学ぶ数理最適化に記載なし
  • ちょっと探して日本語文献が見つからなかった

参考文献

見つかった英語文献 (ちゃんと読んでない)

• Quadratic Interpolation Optimization (QIO): A new optimization algorithm based on generalized quadratic interpolation and its applications to real-world engineering problems
• Quadratic interpolation method of 1D minimization
• An Algorithm using Quadratic Interpolation for Unconstrained Derivative Free Optimization