三分探索：単峰関数の最適化

単峰関数の最小点

\(a<b\)を満たす実数\(a,b\in \mathbb{R} \)を端点とする有界閉区間上に定義された1変数関数\begin{equation*}f:\mathbb{R} \supset \left[ a,b\right] \rightarrow \mathbb{R} \end{equation*}が与えられているものとします。さらに、\(f\)の定義域上にある点\(c\in \left[ a,b\right] \)が存在して、\begin{eqnarray*}&&\left( a\right) \ f\text{は}\left[ a,c\right] \text{上において狭義単調減少である} \\
&&\left( b\right) \ f\text{は}\left[ c,b\right] \text{上において狭義単調増加である}
\end{eqnarray*}がともに成り立つものとします。このような性質を満たす関数を単峰関数（unimodal function）と呼びます。この場合、点\(c\)は\(f\)の唯一の最小点であり、\(f\left( c\right) \)は\(f\)の最小値です。つまり、\begin{equation*}\min_{x\in \left[ a,b\right] }f\left( x\right) =f\left( c\right)
\end{equation*}が成り立ちます。

関数\(f\)が単峰関数であることは分かっているものの、最小点\(c\)が判明していない状況を想定します。さらに、関数\(f\)は微分可能であるとは限らないものとします。つまり、最小点\(c\)を具体的に特定する上で微分を利用できないということです。この場合、\(\left[ a,b\right] \)上の点\(x\)に対して関数\(f\)が定める値\(f\left( x\right) \)どうしを比較しながら最小点\(c\)を見つける必要があります。

三分探索の基本戦略

単峰関数\(f:\mathbb{R} \supset \left[ a,b\right] \rightarrow \mathbb{R} \)の最小点を特定しようとしている状況を想定します。

まずは、区間\(\left[ a,b\right] \)を三等分する2つの点\(x_{1},x_{2}\in \left[ a,b\right] \)を特定し、それらの点に対して\(f\)が定める値\(f\left( x_{1}\right) ,f\left(x_{2}\right) \)どうしを比較します。具体的には、\begin{eqnarray*}x_{1} &=&a+\frac{b-a}{3} \\
x_{2} &=&a+2\cdot \frac{b-a}{3}
\end{eqnarray*}であるため、\begin{eqnarray*}
f\left( x_{1}\right) &=&f\left( a+\frac{b-a}{3}\right) \\
f\left( x_{2}\right) &=&f\left( a+2\cdot \frac{b-a}{3}\right)
\end{eqnarray*}の大小を比較します。その結果、以下の2つの場合が起こり得ます。

1つ目のケースは、\begin{equation*}
f\left( x_{1}\right) <f\left( x_{2}\right)
\end{equation*}である場合です。つまり、変数\(x\)の値が\(x_{1}\)から\(x_{2}\)へ増加すると\(f\left( x\right) \)の値は増加しますが、単峰性の仮定より、この場合には\(x\)が\(x_{2}\)を出発点に大きくなると\(f\left( x\right) \)の値は大きくなり続けます。したがって、\(f\)の最小点は\(\left[ x_{2},b\right] \)上に存在しないため、\(\left[ x_{2},b\right] \)上の点を最小点の候補から外すことができます。

2つ目のケースは、\begin{equation*}
f\left( x_{1}\right) \geq f\left( x_{2}\right)
\end{equation*}である場合です。つまり、変数\(x\)の値が\(x_{1}\)から\(x_{2}\)へ増加すると\(f\left( x\right) \)の値は減少しますが、単峰性の仮定より、この場合には\(x\)が\(x_{1}\)を出発点に小さくなると\(f\left( x\right) \)の値は大きくなり続けます。したがって、\(f\)の最小点は\(\left[ a,x_{1}\right] \)上に存在しないため、\(\left[ a,x_{1}\right] \)上の点を最小点の候補から外すことができます。

結論をまとめると、\begin{eqnarray*}
f\left( x_{1}\right) &<&f\left( x_{2}\right) \Rightarrow \text{最小点は}\left[ a,x_{2}\right] \text{上にある} \\
f\left( x_{1}\right) &\geq &f\left( x_{2}\right) \Rightarrow \text{最小点は}\left[ x_{1},b\right] \text{上にある}
\end{eqnarray*}となります。つまり、この1回の比較により、探索範囲を\(\frac{2}{3}\)に絞り込めるということです。

続いて、残された探索範囲である区間を対象に、同様のプロセスを繰り返します。つまり、残された区間を三等分する2つの点を特定し、それらの点に対して\(f\)が定める値を比較し、\(f\)の最小点が存在する区間を絞り込むということです。その結果、先と同様の理由により、最小点の探索範囲を\(\frac{2}{3}\)に絞り込めます。

同様のプロセスを\(k\in \mathbb{N} \)回繰り返すことにより、最小点が存在する区間の長さが、\begin{equation*}\left( b-a\right) \left( \frac{2}{3}\right) ^{k}
\end{equation*}にまで絞り込まれます。つまり、探索範囲は指数関数的に縮小するということです。最終的には、\begin{equation*}
\lim_{k\rightarrow +\infty }\left( b-a\right) \left( \frac{2}{3}\right)
^{k}=0
\end{equation*}となるため、最小点だけが残ります。このような探索法を三分探索（Ternary search）と呼びます。

三分探索の定式化

単峰関数\(f:\mathbb{R} \supset \left[ a,b\right] \rightarrow \mathbb{R} \)の最小点を特定しようとしている状況を想定します。三分探索は以下のように定式化されます。

1. ステップ\(0\)：当初の探索範囲を、\begin{equation*}\left[ a_{0},b_{0}\right] =\left[ a,b\right] \end{equation*}で表記する。この区間の三分点は、\begin{eqnarray*}
   x_{0}^{\left( 1\right) } &=&a_{0}+\frac{b_{0}-a_{0}}{3} \\
   x_{0}^{\left( 2\right) } &=&a_{0}+2\cdot \frac{b_{0}-a_{0}}{3}
   \end{eqnarray*}である。その上で、新たな探索範囲\(\left[ a_{1},b_{1}\right] \)を、\begin{equation*}\left[ a_{1},b_{1}\right] =\left\{
   \begin{array}{cl}
   \left[ a_{0},x_{0}^{\left( 2\right) }\right] & \left( if\ f\left(
   x_{0}^{\left( 1\right) }\right) <f\left( x_{0}^{\left( 2\right) }\right)
   \right) \\
   \left[ x_{0}^{\left( 1\right) },b_{0}\right] & \left( if\ f\left(
   x_{0}^{\left( 1\right) }\right) \geq f\left( x_{0}^{\left( 2\right) }\right)
   \right)
   \end{array}\right.
   \end{equation*}と定める。
2. ステップ\(1\)：探索範囲\(\left[ a_{1},b_{1}\right] \)の三分点は、\begin{eqnarray*}x_{1}^{\left( 1\right) } &=&a_{1}+\frac{b_{1}-a_{1}}{3} \\x_{1}^{\left( 2\right) } &=&a_{1}+2\cdot \frac{b_{1}-a_{1}}{3}
   \end{eqnarray*}である。その上で、新たな探索範囲\(\left[ a_{2},b_{2}\right] \)を、\begin{equation*}\left[ a_{2},b_{2}\right] =\left\{
   \begin{array}{cl}
   \left[ a_{1},x_{1}^{\left( 2\right) }\right] & \left( if\ f\left(
   x_{1}^{\left( 1\right) }\right) <f\left( x_{1}^{\left( 2\right) }\right)
   \right) \\
   \left[ x_{1}^{\left( 1\right) },b_{1}\right] & \left( if\ f\left(
   x_{1}^{\left( 1\right) }\right) \geq f\left( x_{1}^{\left( 2\right) }\right)
   \right)
   \end{array}\right.
   \end{equation*}と定める。
3. ステップ\(k\)：探索範囲\(\left[ a_{k},b_{k}\right] \)の三分点は、\begin{eqnarray*}x_{k}^{\left( 1\right) } &=&a_{k}+\frac{b_{k}-a_{k}}{3} \\x_{k}^{\left( 2\right) } &=&a_{k}+2\cdot \frac{b_{k}-a_{k}}{3}
   \end{eqnarray*}である。その上で、新たな探索範囲\(\left[a_{k+1},b_{k+1}\right] \)を、\begin{equation*}\left[ a_{k+1},b_{k+1}\right] =\left\{
   \begin{array}{cl}
   \left[ a_{k},x_{k}^{\left( 2\right) }\right] & \left( if\ f\left(
   x_{k}^{\left( 1\right) }\right) <f\left( x_{k}^{\left( 2\right) }\right)
   \right) \\
   \left[ x_{k}^{\left( 1\right) },b_{k}\right] & \left( if\ f\left(
   x_{k}^{\left( 1\right) }\right) \geq f\left( x_{k}^{\left( 2\right) }\right)
   \right)
   \end{array}\right.
   \end{equation*}と定める。

先の議論から明らかになったように、三分探索の任意のステップにおいて、最小点は常に探索範囲内に残ります。

三分探索によって得られる極限点は最小点と一致します。

所与の誤差以内で真の最小値の近似値を実現する回数

三分探索のプロセスを限りなく繰り返せば、最終的に得られる極限点が最小点と一致することが明らかになりました。ただ、実際にプロセスを無限回繰り返すことはできません。では、真の最小点\(c\)との誤差を事前に設定した場合、プロセスを何回繰り返せば、誤差の範囲内に収まる値を得られるのでしょうか。

三分探索のステップ\(k\in \mathbb{N} \)における探索範囲を\(\left[ a_{k},b_{k}\right] \subset \left[ a,b\right] \)で表記し、さらにその中点を、\begin{equation*}m_{k}=\frac{a_{k}+b_{k}}{2}
\end{equation*}で表記します。真の最小点\(c\)との誤差として\(\varepsilon >0\)を採用した場合、\begin{equation*}\left\vert m_{k}-c\right\vert \leq \varepsilon
\end{equation*}を満たす\(k\)を特定することが目標になります。

三分探索の課題

三分探索では各ステップ\(k\)において探索範囲\(\left[ a_{k},b_{k}\right] \)の三分点\(x_{k}^{\left( 1\right) },x_{k}^{\left( 2\right) }\)を特定し、それらに対して\(f\)が定める値\begin{eqnarray*}&&f\left( x_{k}^{\left( 1\right) }\right) \\
&&f\left( x_{k}^{\left( 2\right) }\right)
\end{eqnarray*}を計算し、両者を比較します。つまり、1ステップにおいて関数評価が2回行われます。探索範囲が\(\left[a_{k+1},b_{k+1}\right] \)へと更新されると、新たに三分点\(x_{k+1}^{\left( 1\right) },x_{k+1}^{\left( 2\right) }\)を特定した上で、それらに対して\(f\)が定める値\begin{eqnarray*}&&f\left( x_{k+1}^{\left( 1\right) }\right) \\
&&f\left( x_{k+1}^{\left( 2\right) }\right)
\end{eqnarray*}を計算する必要があります。つまり、以前のステップにおいて計算した関数値が後のステップにおいて再利用されず、\(k\)ステップにおいて\(2k\)回の関数評価が必要になります。三分探索は関数評価の再利用を考慮していないため、効率性という観点から課題が残るということです。このような課題を克服するため、「1回の新しい関数評価だけで次のステップへ進める」よう工夫したのが黄金分割探索（Golden sectionsearch）です。黄金分割探索については場を改めて解説します。

演習問題