フィボナッチ探索：単峰関数の最適化と黄金分割探索との違い

単峰関数の最小点

\(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} \)の最小点を特定しようとしている状況を想定します。黄金分割探索では、以下の定数\begin{equation*}\rho =\frac{3-\sqrt{5}}{2}\approx 0.382
\end{equation*}のもとで探索区間を分割していきます。具体的なプロセスは以下の通りです。

最初のステップでは、当初の探索範囲\(\left[ a,b\right] \)を以下の割合\begin{equation*}\rho :1-2\rho :\rho
\end{equation*}で三分する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+\rho \left( b-a\right) \\
x_{2} &=&a+\left( 1-\rho \right) \left( b-a\right)
\end{eqnarray*}であるため、\begin{eqnarray*}
f\left( x_{1}\right) &=&f\left( a+\rho \left( b-a\right) \right) \\
f\left( x_{2}\right) &=&f\left( a+\left( 1-\rho \right) \left( b-a\right)
\right)
\end{eqnarray*}です。その上で、新たな探索範囲\(\left[ a^{\prime},b^{\prime }\right] \)を、\begin{eqnarray*}f\left( x_{1}\right) &<&f\left( x_{2}\right) \Rightarrow \left[ a^{\prime
},b^{\prime }\right] =\left[ a,x_{2}\right] \\
f\left( x_{1}\right) &\geq &f\left( x_{2}\right) \Rightarrow \left[
a^{\prime },b^{\prime }\right] =\left[ x_{1},b\right] \end{eqnarray*}と定めます。当初の探索範囲\(\left[ a,b\right] \)と新たな探索範囲\(\left[ a^{\prime },b^{\prime }\right] \)の長さの比は\(1:1-\rho \)であるため、本ステップにおいて探索範囲が\(1-\rho \)に絞り込まれます。

次のステップでは、新たに得られた探索範囲\(\left[ a^{\prime },b^{\prime }\right] \)を先と同じ割合\begin{equation*}\rho :1-2\rho :\rho
\end{equation*}で三分する2つの点\(x_{1}^{\prime },x_{2}^{\prime }\in \left[ a^{\prime },b^{\prime }\right] \)を特定し、それらの点に対して\(f\)が定める値\(f\left( x_{1}^{\prime }\right) ,f\left( x_{2}^{\prime }\right) \)どうしを比較します。上図では\(\left[ a^{\prime },b^{\prime }\right] =\left[ a,x_{2}\right] \)の場合を想定していますが、\(\left[a^{\prime },b^{\prime }\right] =\left[ x_{1},b\right] \)の場合も同様です。具体的には、\begin{eqnarray*}x_{1}^{\prime } &=&a^{\prime }+\rho \left( b^{\prime }-a^{\prime }\right) \\
x_{2}^{\prime } &=&a^{\prime }+\left( 1-\rho \right) \left( b^{\prime
}-a^{\prime }\right)
\end{eqnarray*}であるため、\begin{eqnarray*}
f\left( x_{1}^{\prime }\right) &=&f\left( a^{\prime }+\rho \left( b^{\prime
}-a^{\prime }\right) \right) \\
f\left( x_{2}^{\prime }\right) &=&f\left( a^{\prime }+\left( 1-\rho \right)
\left( b^{\prime }-a^{\prime }\right) \right)
\end{eqnarray*}です。ここでのポイントは、先の値\(\rho \)のもとでは新たな三分点\(x_{1}^{\prime },x_{2}^{\prime }\)のどちらか一方が最初の三分点\(x_{1},x_{2}\)のどちらか一方と一致することが保証されるため、\(f\left(x_{1}^{\prime }\right) ,f\left( x_{2}^{\prime }\right) \)のどちらか一方が\(f\left( x_{1}\right),f\left( x_{2}\right) \)のどちらか一方と一致し、ゆえに実際には\(f\left( x_{1}^{\prime }\right) ,f\left(x_{2}^{\prime }\right) \)のどちらか一方を計算するだけです。その上で、新たな探索範囲\(\left[ a^{\prime \prime },b^{\prime\prime }\right] \)を、\begin{eqnarray*}f\left( x_{1}^{\prime }\right) &<&f\left( x_{2}^{\prime }\right)
\Rightarrow \left[ a^{\prime \prime },b^{\prime \prime }\right] =\left[
a^{\prime },x_{2}^{\prime }\right] \\
f\left( x_{1}^{\prime }\right) &\geq &f\left( x_{2}^{\prime }\right)
\Rightarrow \left[ a^{\prime \prime },b^{\prime \prime }\right] =\left[
x_{1}^{\prime },b^{\prime }\right] \end{eqnarray*}と定めます。もとの探索範囲\(\left[ a^{\prime },b^{\prime }\right] \)と新たな探索範囲\(\left[a^{\prime \prime },b^{\prime \prime }\right] \)の長さの比は\(1:1-\rho \)であるため、本ステップにおいても探索範囲が\(1-\rho \)に絞り込まれます。

以降も同様のプロセスを繰り返します。最初のステップでは2つの値\(f\left( x_{1}\right) ,f\left( x_{2}\right) \)を評価する必要がありますが、以降のステップでは、直前のステップにおいて得られた2つの関数値のうちの一方を再利用できるため、関数評価を1回行えば次のステップへ進めます。各ステップにおいて探索範囲が\(1-\rho \)に絞り込まれるため、同様のステップを\(k\in \mathbb{N} \)回繰り返すことにより、探索範囲の長さが、\begin{equation*}\left( b-a\right) \left( 1-\rho \right) ^{k}
\end{equation*}にまで絞り込まれます。

以前に解説した三分探索では各ステップにおいて関数評価を2回行う必要があるため、各ステップにおいて関数評価を1回行うだけでよい黄金分割探索は効率的なアルゴリズムです。ただし、黄金分割探索にも改善の余地がないわけではありません。黄金分割探索ではすべてのステップにおいて同一の割合のもとで区間を三分します。一方、各ステップにおいて異なる割合のもとで区間を三分することにより、黄金分割探索と同様に直前のステップにおいて得られた関数値を再利用しつつも、黄金分割探索より素早く探索範囲を絞り込める可能性があります。以上の課題を解決するのがフィボナッチ探索（Fibonacci search）です。

フィボナッチ探索の基本戦略

フィボナッチ探索ではフィボナッチ数列（Fibonacci sequence）を利用します。フィボナッチ数列\(\left\{ F_{n}\right\} \)は以下の再帰式\begin{equation*}\left\{
\begin{array}{l}
F_{0}=F_{1}=1 \\
F_{n}=F_{n-1}+F_{n-2}\quad \left( n=2,3,\cdots \right)
\end{array}\right.
\end{equation*}によって定義されます。定義にもとづいて項を列挙すると、\begin{eqnarray*}
F_{0} &=&1 \\
F_{1} &=&1 \\
F_{2} &=&2 \\
F_{3} &=&3 \\
F_{4} &=&5 \\
F_{5} &=&8 \\
&&\vdots
\end{eqnarray*}などとなります。つまり、直前の2つの項を足して次の項を作るということです。

黄金分割探索と同様、フィボナッチ探索においても探索範囲を三分した上で、三分点における関数値を評価するプロセスを繰り返します。フィボナッチ探索の特徴の1つは、そのようなプロセスを何回繰り返すか、その回数を事前に設定する必要があるということです。そこで、実行するステップ数を規定する自然数を、\begin{equation*}
N\in \mathbb{N} \end{equation*}で表記します。

黄金分割探索では定数\(\rho =\frac{3-\sqrt{5}}{2}\)を採用し、任意のステップ\(k\)において同一の割合\begin{equation*}\rho :1-2\rho :\rho
\end{equation*}で探索範囲を分割します。一方、フィボナッチ探索では、各ステップ\(k\)ごとに異なる値\(\rho _{k}\)を採用し、その値にもとづいて探索範囲を、\begin{equation*}\rho _{k}:1-2\rho _{k}:\rho _{k}
\end{equation*}の割合で分割します。その際、\(\rho _{k}\)の値は、フィボナッチ数列\(\left\{ F_{n}\right\} \)と総ステップ数を規定する数値\(N\in \mathbb{N} \)より、\begin{equation}\rho _{k}=\frac{F_{N-k-1}}{F_{N-k+1}} \quad \cdots (1)
\end{equation}と定められます。このとき、\begin{eqnarray*}
1-\rho _{k} &=&1-\frac{F_{N-k-1}}{F_{N-k+1}}\quad \because \left( 1\right)
\\
&=&\frac{F_{N-k+1}-F_{N-k-1}}{F_{N-k+1}} \\
&=&\frac{\left( F_{N-k}+F_{N-k-1}\right) -F_{N-k-1}}{F_{N-k+1}}\quad
\because F_{N-k+1}=F_{N-k}+F_{N-k-1} \\
&=&\frac{F_{N-k}}{F_{N-k+1}}
\end{eqnarray*}すなわち、\begin{equation}
1-\rho _{k}=\frac{F_{N-k}}{F_{N-k+1}} \quad \cdots (2)
\end{equation}であることに注意してください。以上をもとに、プロセスを具体的に記述すると以下のようになります。

単峰関数\(f:\mathbb{R} \supset \left[ a,b\right] \rightarrow \mathbb{R} \)の最小点を特定しようとしている状況を想定します。フィボナッチ数列を\(\left\{ F_{n}\right\} \)で表記し、総ステップ数を規定する数値を\(N\in \mathbb{N} \)で表記します。

まずは、区間\(\left[ a,b\right] \)を以下の割合、\begin{equation*}\rho _{1}:1-2\rho _{1}:\rho _{1}
\end{equation*}で三分する2つの点\(x_{1},x_{2}\in \left[ a,b\right] \)を特定し（上図）、それらの点に対して\(f\)が定める値\(f\left( x_{1}\right) ,f\left( x_{2}\right) \)どうしを比較します。ただし、\(\left( 1\right) ,\left( 2\right) \)より、\begin{eqnarray*}\rho _{1} &=&\frac{F_{N-2}}{F_{N}} \\
1-\rho _{1} &=&\frac{F_{N-1}}{F_{N}}
\end{eqnarray*}であるとともに、\begin{eqnarray*}
x_{1} &=&a+\rho _{1}\left( b-a\right) \\
x_{2} &=&a+\left( 1-\rho _{1}\right) \left( b-a\right)
\end{eqnarray*}となり、したがって、\begin{eqnarray*}
f\left( x_{1}\right) &=&f\left( a+\rho _{1}\left( b-a\right) \right) \\
f\left( x_{2}\right) &=&f\left( a+\left( 1-\rho _{1}\right) \left(
b-a\right) \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] \)上の点を最小点の候補から外すことができます。

以上の議論より、新たな探索範囲\(\left[ a^{\prime},b^{\prime }\right] \)が、\begin{eqnarray*}f\left( x_{1}\right) &<&f\left( x_{2}\right) \Rightarrow \left[ a^{\prime
},b^{\prime }\right] =\left[ a,x_{2}\right] \\
f\left( x_{1}\right) &\geq &f\left( x_{2}\right) \Rightarrow \left[
a^{\prime },b^{\prime }\right] =\left[ x_{1},b\right] \end{eqnarray*}と定まります。当初の探索範囲\(\left[ a,b\right] \)と新たな探索範囲\(\left[ a^{\prime},b^{\prime }\right] \)の長さの比は\(1:1-\rho _{1}\)であるため、本ステップにおいて探索範囲が\(1-\rho _{1}\)に絞り込まれます。

続いて、新たな探索範囲\(\left[ a^{\prime },b^{\prime }\right] \)を対象に、同様のプロセスを繰り返します。つまり、\(\left[ a^{\prime },b^{\prime }\right] \)を以下の割合\begin{equation*}\rho _{2}:1-2\rho _{2}:\rho _{2}
\end{equation*}で三分する2つの点\(x_{1}^{\prime },x_{2}^{\prime }\in \left[ a^{\prime },b^{\prime }\right] \)を特定し、それらの点に対して\(f\)が定める値\(f\left( x_{1}\right) ,f\left( x_{2}\right) \)どうしを比較します。ただし、\(\left( 1\right) ,\left( 2\right) \)より、\begin{eqnarray*}\rho _{2} &=&\frac{F_{N-3}}{F_{N-1}} \\
1-\rho _{2} &=&\frac{F_{N-2}}{F_{N-1}}
\end{eqnarray*}です。ただし、新たな点\(x_{1}^{\prime },x_{2}^{\prime }\)のどちらか一方は先の点\(x_{1},x_{2}\)のどちらか一方と一致します。理由は以下の通りです。

最初のステップにおいて\(f\left( x_{1}\right) <f\left( x_{2}\right) \)であった状況を想定します。この場合、新たな探索範囲\(\left[ a^{\prime },b^{\prime }\right] \)は\(\left[ a,x_{2}\right] \)です。その上で、新たな探索範囲\(\left[ a,x_{2}\right] \)を\(\rho _{2}:1-2\rho _{2}:\rho_{2}\)の割合で三分する2つの点\(x_{1}^{\prime },x_{2}^{\prime }\in \left[ a,x_{2}\right] \)を特定します（上図）。\(x_{1}^{\prime }<x_{2}^{\prime }\)です。ただし、\(a<x_{1}<x_{2}\)であるため、先に特定した点\(x_{1}\)を再利用できれば関数評価を1回節約できます。\(\rho _{2}<\frac{1}{2}\)ゆえに点\(x_{1}\)は新たな探索範囲\(\left[ a,x_{2}\right] \)の中点よりも右側にあるため、\(x_{1}^{\prime }\)ではなく\(x_{2}^{\prime }\)として\(x_{1}\)を再利用することになります。実際、\begin{eqnarray*}x_{2}^{\prime } &=&a+\left( 1-\rho _{2}\right) \left( x_{2}-a\right) \\
&=&a+\frac{F_{N-2}}{F_{N-1}}\left\{ \left[ a+\frac{F_{N-1}}{F_{N}}\left(
b-a\right) \right] -a\right\} \\
&=&a+\frac{F_{N-2}}{F_{N-1}}\cdot \frac{F_{N-1}}{F_{N}}\left( b-a\right) \\
&=&a+\frac{F_{N-2}}{F_{N}}\left( b-a\right) \\
&=&x_{1}
\end{eqnarray*}となるため、\(x_{2}^{\prime }\)は\(x_{1}\)と一致することが明らかになりました。つまり、\begin{eqnarray*}x_{1}^{\prime } &=&a+\rho _{2}\left( x_{2}-a\right) \\
x_{2}^{\prime } &=&x_{1}
\end{eqnarray*}です。その上で、これらの点に対して\(f\)が定める値\(f\left( x_{1}^{\prime }\right) ,f\left(x_{2}^{\prime }\right) \)どうしを比較することにより、新たな探索範囲\(\left[ a^{\prime \prime},b^{\prime \prime }\right] \)が、\begin{eqnarray*}f\left( x_{1}^{\prime }\right) &<&f\left( x_{2}^{\prime }\right)
\Rightarrow \left[ a^{\prime \prime },b^{\prime \prime }\right] =\left[
a^{\prime },x_{2}^{\prime }\right] \\
f\left( x_{1}^{\prime }\right) &\geq &f\left( x_{2}^{\prime }\right)
\Rightarrow \left[ a^{\prime \prime },b^{\prime \prime }\right] =\left[
x_{1}^{\prime },b^{\prime }\right] \end{eqnarray*}となり、探索範囲が\(1-\rho _{2}\)に絞り込まれます。

最初のステップにおいて\(f\left( x_{1}\right) \geq f\left( x_{2}\right) \)であった場合についても同様です。この場合、この場合、新たな探索範囲\(\left[ a^{\prime },b^{\prime }\right] \)は\(\left[ x_{1},b\right] \)です。その上で、新たな探索範囲\(\left[ x_{1},b\right] \)を\(\rho _{2}:1-2\rho _{2}:\rho_{2}\)の割合で三分する2つの点\(x_{1}^{\prime },x_{2}^{\prime }\in \left[ x_{1},b\right] \)を特定します（上図）。\(x_{1}^{\prime }<x_{2}^{\prime }\)です。ただし、\(x_{1}<x_{2}<b\)であるため、先に特定した点\(x_{2}\)を再利用します。\(\rho _{2}<\frac{1}{2}\)ゆえに点\(x_{2}\)は新たな探索範囲\(\left[x_{1},b\right] \)の中点よりも左側にあるため、\(x_{2}^{\prime }\)ではなく\(x_{1}^{\prime }\)として\(x_{2}\)を再利用することになります。実際、\begin{eqnarray*}x_{1}^{\prime } &=&x_{1}+\rho _{2}\left( b-x_{1}\right) \\
&=&\left[ a+\frac{F_{N-2}}{F_{N}}\left( b-a\right) \right] +\frac{F_{N-3}}{F_{N-1}}\left\{ b-\left[ a+\frac{F_{N-2}}{F_{N}}\left( b-a\right) \right] \right\} \\
&=&a+\frac{F_{N-2}}{F_{N}}\left( b-a\right) +\frac{F_{N-3}}{F_{N-1}}\left(
b-a\right) -\frac{F_{N-3}F_{N-2}}{F_{N-1}F_{N}}\left( b-a\right) \\
&=&a+\left( \frac{F_{N-2}}{F_{N}}+\frac{F_{N-3}}{F_{N-1}}-\frac{F_{N-3}F_{N-2}}{F_{N-1}F_{N}}\right) \left( b-a\right) \\
&=&a+\left( \frac{F_{N-2}F_{N-1}+F_{N-3}F_{N}-F_{N-3}F_{N-2}}{F_{N-1}F_{N}}\right) \left( b-a\right)
\end{eqnarray*}となりますが、\begin{eqnarray*}
\frac{F_{N-2}}{F_{N}}+\frac{F_{N-3}}{F_{N-1}}-\frac{F_{N-3}F_{N-2}}{F_{N-1}F_{N}} &=&\frac{F_{N-2}F_{N-1}+F_{N-3}F_{N}-F_{N-3}F_{N-2}}{F_{N-1}F_{N}} \\
&=&\frac{F_{N-2}F_{N-1}+F_{N-3}\left( F_{N-1}+F_{N-2}\right) -F_{N-3}F_{N-2}}{F_{N-1}F_{N}}\quad \because F_{N}=F_{N-1}+F_{N-2} \\
&=&\frac{F_{N-2}F_{N-1}+F_{N-3}F_{N-1}+F_{N-3}F_{N-2}-F_{N-3}F_{N-2}}{F_{N-1}F_{N}} \\
&=&\frac{F_{N-2}F_{N-1}+F_{N-3}F_{N-1}}{F_{N-1}F_{N}} \\
&=&\frac{F_{N-2}+F_{N-3}}{F_{N}} \\
&=&\frac{F_{N-1}}{F_{N}}\quad \because F_{N-1}=F_{N-2}+F_{N-3}
\end{eqnarray*}ゆえに、\begin{eqnarray*}
x_{1}^{\prime } &=&a+\frac{F_{N-1}}{F_{N}}\left( b-a\right) \\
&=&x_{2}
\end{eqnarray*}となるため、\(x_{1}^{\prime }\)は\(x_{2}\)と一致することが明らかになりました。つまり、\begin{eqnarray*}x_{1}^{\prime } &=&x_{2} \\
x_{2}^{\prime } &=&x_{1}+\left( 1-\rho _{2}\right) \left( b-x_{1}\right)
\end{eqnarray*}です。その上で、これらの点に対して\(f\)が定める値\(f\left( x_{1}^{\prime }\right) ,f\left(x_{2}^{\prime }\right) \)どうしを比較することにより、新たな探索範囲\(\left[ a^{\prime \prime},b^{\prime \prime }\right] \)が、\begin{eqnarray*}f\left( x_{1}^{\prime }\right) &<&f\left( x_{2}^{\prime }\right)
\Rightarrow \left[ a^{\prime \prime },b^{\prime \prime }\right] =\left[
a^{\prime },x_{2}^{\prime }\right] \\
f\left( x_{1}^{\prime }\right) &\geq &f\left( x_{2}^{\prime }\right)
\Rightarrow \left[ a^{\prime \prime },b^{\prime \prime }\right] =\left[
x_{1}^{\prime },b^{\prime }\right] \end{eqnarray*}となり、探索範囲が\(1-\rho _{2}\)に絞り込まれます。

以降も同様のプロセスを繰り返します。

フィボナッチ探索の定式化

単峰関数\(f:\mathbb{R} \supset \left[ a,b\right] \rightarrow \mathbb{R} \)の最小点を特定しようとしている状況を想定します。フィボナッチ探索は以下のように定式化されます。ただし、フィボナッチ数列を\(\left\{ F_{n}\right\} \)で表記し、数値を\(N\in \mathbb{N} \)で表記します。その上で、それぞれの\(k\in\left\{ 1,\cdots ,N\right\} \)に対して、\begin{equation*}\rho _{k}=\frac{F_{N-k-1}}{F_{N-k+1}}
\end{equation*}と定義します。

1. 1. ステップ\(1\)：当初の探索範囲を、\begin{equation*}\left[ a_{1},b_{1}\right] =\left[ a,b\right] \end{equation*}で表記する。この区間の三分点は、\begin{eqnarray*}
      \rho _{1} &=&\frac{F_{N-2}}{F_{N}} \\
      1-\rho _{1} &=&\frac{F_{N-1}}{F_{N}}
      \end{eqnarray*}のもとで、\begin{equation*}
      \left( x_{1}^{\left( 1\right) },x_{1}^{\left( 2\right) }\right) =\left(
      a_{1}+\rho _{1}\left( b_{1}-a_{1}\right) ,a_{1}+\left( 1-\rho _{1}\right)
      \left( b_{1}-a_{1}\right) \right)
      \end{equation*}と定まる。その上で、新たな探索範囲\(\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*}と定める。
   2. ステップ\(2\)：探索範囲\(\left[ a_{2},b_{2}\right] \)の三分点は、\begin{eqnarray*}\rho _{2} &=&\frac{F_{N-3}}{F_{N-1}} \\1-\rho _{2} &=&\frac{F_{N-2}}{F_{N-1}}
      \end{eqnarray*}のもとで、\begin{equation*}
      \left( x_{2}^{\left( 1\right) },x_{2}^{\left( 2\right) }\right) =\left\{
      \begin{array}{cl}
      \left( a_{2}+\rho _{2}\left( b_{2}-a_{2}\right) ,x_{1}^{\left( 1\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( 2\right) },a_{2}+\left( 1-\rho _{2}\right) \left(
      b_{2}-a_{2}\right) \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*}と定まる。その上で、新たな探索範囲\(\left[a_{3},b_{3}\right] \)を、\begin{equation*}\left[ a_{3},b_{3}\right] =\left\{
      \begin{array}{cl}
      \left[ a_{2},x_{2}^{\left( 2\right) }\right] & \left( if\ f\left(
      x_{2}^{\left( 1\right) }\right) <f\left( x_{2}^{\left( 2\right) }\right)
      \right) \\
      \left[ x_{2}^{\left( 1\right) },b_{2}\right] & \left( if\ f\left(
      x_{2}^{\left( 1\right) }\right) \geq f\left( x_{2}^{\left( 2\right) }\right)
      \right)
      \end{array}\right.
      \end{equation*}と定める。
   3. ステップ\(k\)：探索範囲\(\left[ a_{k},b_{k}\right] \)の三分点は、\begin{eqnarray*}\rho _{k} &=&\frac{F_{N-k-1}}{F_{N-k+1}} \\1-\rho _{k} &=&\frac{F_{N-k}}{F_{N-k+1}}
      \end{eqnarray*}のもとで、\begin{equation*}
      \left( x_{k}^{\left( 1\right) },x_{k}^{\left( 2\right) }\right) =\left\{
      \begin{array}{cl}
      \left( a_{k}+\rho _{k}\left( b_{k}-a_{k}\right) ,x_{k-1}^{\left( 1\right)
      }\right) & \left( if\ f\left( x_{k-1}^{\left( 1\right) }\right) <f\left(
      x_{k-1}^{\left( 2\right) }\right) \right) \\
      \left( x_{k-1}^{\left( 2\right) },a_{k}+\left( 1-\rho _{k}\right) \left(
      b_{k}-a_{k}\right) \right) & \left( if\ f\left( x_{k-1}^{\left( 1\right)
      }\right) \geq f\left( x_{k-1}^{\left( 2\right) }\right) \right)
      \end{array}\right.
      \end{equation*}と定まる。その上で、新たな探索範囲\(\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*}と定める。
   4. ステップ\(N-1\)：探索範囲\(\left[ a_{N-1},b_{N-1}\right] \)の三分点は、\begin{eqnarray*}\rho _{N-1} &=&\frac{F_{0}}{F_{2}}=\frac{1}{2} \\1-\rho _{N-1} &=&\frac{F_{1}}{F_{2}}=\frac{1}{2}
      \end{eqnarray*}のもとで、\begin{equation*}
      \left( x_{N-1}^{\left( 1\right) },x_{N-1}^{\left( 2\right) }\right) =\left(
      \frac{1}{2}\left( a_{N-1}+b_{N-1}\right) ,\frac{1}{2}\left(
      a_{N-1}+b_{N-1}\right) \right)
      \end{equation*}と定まる。つまり、\(x_{N-1}^{\left( 1\right) }=x_{N-1}^{\left( 2\right) }\)であるとともに、これは\(\left[ a_{N-1},b_{N-1}\right] \)の中点であるため三分点は存在しない。したがって、\begin{equation*}\left[ a_{N-1},b_{N-1}\right] \end{equation*}を最終的な候補と定める。真の最小点\(c\)はこの区間上にあるため、この区間の中点\(x^{\ast }\)を最小点の候補として採用した場合には、\begin{equation*}\left\vert x^{\ast }-c\right\vert \leq \frac{1}{2}\left(
      b_{N-1}-a_{N-1}\right)
      \end{equation*}が成り立つ。つまり、誤差は\(\frac{1}{2}\left( b_{N-1}-a_{N-1}\right) \)以下になる。

フィボナッチ探索の任意のステップにおいて、最小点は常に探索範囲内に残ることを確認しておきます。

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

番号\(N\in \mathbb{N} \)に関するフィボナッチ探索を実行した場合に最終的に得られる区間は、\begin{equation*}\left[ a_{N-1},b_{N-1}\right] \end{equation*}です。真の最小点\(c\)はこの区間上にあるため、この区間の中点\begin{equation*}x^{\ast }=\frac{a_{N-1}+b_{N-1}}{2}
\end{equation*}を最小点の候補として採用した場合には、\begin{equation*}
\left\vert x^{\ast }-c\right\vert \leq \frac{1}{2}\left(
b_{N-1}-a_{N-1}\right)
\end{equation*}が成り立ちます。では、逆に、真の最小点\(c\)との誤差として\(\varepsilon >0\)を採用した場合に、\begin{equation*}\left\vert x^{\ast }-c\right\vert \leq \varepsilon
\end{equation*}を満たすためには、番号\(N\)をいくつに設定すればよいでしょうか。

ちなみに、番号\(N\)のもとでのフィボナッチ探索を実行した場合、ステップ\(1\)において関数評価を2回行い、ステップ\(2\)からステップ\(N-2\)までは関数評価を1回ずつ行います。ステップ\(N-1\)では新たな三分点は出現しないため、関数評価の合計回数は、\begin{equation*}2+1\left[ \left( N-2\right) -2+1\right] =N-1
\end{equation*}となります。

フィボナッチ探索と黄金分割探索の比較

先の命題の証明において明らかにしたように、初期区間が\(\left[ a,b\right] \)である場合、番号\(N\)のもとでのフィボナッチ探索を行うと関数評価が\(N-1\)回行われるとともに、最終的な区間\(\left[ a_{N-1},b_{N-1}\right] \)の長さは、\begin{equation*}b_{N-1}-a_{N-1}=\frac{b-a}{F_{N}}
\end{equation*}となります。ただし、\(F_{N}\)はフィボナッチ数列\(\left\{ F_{n}\right\} \)の第\(N\)項です。この値\(\frac{b-a}{F_{N}}\)は、関数評価回数が\(N-1\)回であるという制約のもとで達成できる最小の区間長であることが知られています。つまり、フィボナッチ探索は、限られた回数の関数評価のもとで誤差を最小化するため、黄金分割探索よりも効率的なアルゴリズムです。

一方、黄金分割探索では、各ステップで区間を一定の値\(\rho =\frac{\sqrt{5}-1}{2}\)にもとづいて分割するため、実装が簡単であり、途中で停止しても近似解が得られるという利点を持ちます。ただし、先述のように、関数評価の回数を固定した場合には、フィボナッチ探索のほうが正確な結果をもたらします。

以上を踏まえると、評価回数が制限されている場合にはフィボナッチ探索が最適であり、柔軟に計算を打ち切りたい場合には黄金分割探索が実用的であることが明らかになりました。つまり、両者は競合する手法ではなく、目的に応じて使い分けるべき手法であると言えます。