`optimize-steepdescent2d-linesearch.py` 技術ドキュメント

プログラムの動作

optimize-steepdescent2d-linesearch.py は、2次元関数の最小値を探索するためのPythonスクリプトです。最急降下法（Steepest Descent Method）を最適化アルゴリズムとして採用し、ステップサイズを決定するために複数の直線探索（Line Search）手法を実装しています。

このプログラムの主な機能は以下の通りです。

目的関数の定義: 楕円関数と、より複雑な非線形関数の2種類の2次元関数を最適化のターゲットとして選択できます。
勾配の計算: 各目的関数の1階微分（勾配）がコード内で明示的に定義されています。
直線探索手法の実装: 以下の5つの異なる直線探索アルゴリズムを提供します。
- one (または空文字列): 固定ステップサイズ
- simple: シンプルなステップサイズ増加法
- exact: 2次近似に基づく厳密な直線探索
- golden: 黄金分割法
- armijo: アルミホ条件に基づく直線探索
最適化過程の視覚化: 3D曲面プロットと2次元等高線プロットを使用して、最適化の進行状況（探索点の移動軌跡と関数値の変化）をリアルタイムでグラフィカルに表示します。
コマンドライン引数による設定: 初期点、使用する直線探索モード、ターゲット関数をコマンドライン引数で柔軟に指定できます。

このプログラムは、様々な直線探索手法が最急降下法の収束性や効率にどのように影響するかを理解し、可視化するのに役立ちます。

原理

本プログラムは、最急降下法 を基盤とした数値最適化手法を用いて、与えられた2次元関数 $f(x_0, x_1)$ の最小値を探索します。最急降下法は、現在の点 $x_k$ における関数の勾配 $\nabla f(x_k)$ が最も急峻に増加する方向を示すことを利用し、その逆方向（最も急峻に減少する方向）に探索点を移動させることで、関数の最小値に近づきます。

最適化の更新式は以下の通りです。

\[x_{k+1} = x_k - \alpha_k \nabla f(x_k)\]

ここで、$x_k = (x_{k,0}, x_{k,1})$ は現在の探索点、$\nabla f(x_k)$ は点 $x_k$ における勾配ベクトル、$\alpha_k$ は ステップサイズ （または学習率）と呼ばれる正の値です。$\alpha_k$ の選択は最適化の収束速度と安定性に大きく影響するため、直線探索 と呼ばれるプロセスで決定されます。直線探索は、与えられた探索方向 $p_k = -\nabla f(x_k)$ に対して、関数 $\phi(\alpha) = f(x_k + \alpha p_k)$ を最小化する $\alpha$ を見つける問題と見なせます。

プログラムで実装されている主な直線探索手法の原理は以下の通りです。

1. Simple Line Search (`linesearch_simple`)

最も単純な方法の一つで、初期ステップサイズ alpha から徐々にステップサイズを増加させていきます ($ \alpha, 2\alpha, 3\alpha, \dots $)。関数値が減少しなくなるまで続け、関数値が減少しなくなった直前のステップサイズを採用します。

2. Exact Line Search (`linesearch_exact`)

探索方向への1次元関数 $\phi(\alpha) = f(x_k - \alpha \nabla f(x_k) / ||\nabla f(x_k)||)$ を2次関数で近似し、その近似関数の最小値を与える $\alpha$ を求めます。2次関数の最小値は、1階微分が0となる点です。プログラムでは、数値微分（中心差分）を用いて1階微分と2階微分を近似し、以下の式でステップサイズ $\alpha_2$ を計算します。

\[\alpha_2 = \frac{\phi'(0)}{\phi''(0)}\]

ただし、分母が0に近くなるのを避けるため、少量の dump パラメータが追加されます。

3. Golden Section Search (`linesearch_golden`)

単峰性（unimodal）の1次元関数 $\phi(\alpha)$ の最小値を効率的に探索する手法です。探索区間 $[a, b]$ を黄金比（約 $0.618$ またはその補数約 $0.382$）に基づいて徐々に縮小していくことで、最小値を含む区間を絞り込みます。プログラムでは eta = 0.381966011 を縮小係数として使用しています。

4. Armijo Condition (`linesearch_armijo`)

不正確な直線探索の一種で、関数値が十分に減少していることを保証する「アルミホ条件」を利用します。ステップサイズ $\alpha$ は、以下の条件を満たすように決定されます。

\[f(x_k + \alpha p_k) \le f(x_k) + \xi \alpha \nabla f(x_k)^T p_k\]

ここで $p_k = -\nabla f(x_k)$ であり、$\nabla f(x_k)^T p_k = -||\nabla f(x_k)||^2$ となります。 $\xi$ は $0 < \xi < 1$ の範囲の定数（プログラムでは xi = 0.5）、$\alpha$ は初期値から $0 < \tau < 1$ の定数（プログラムでは tau = 0.5）を乗じて減少させていきます。この条件を満たす最小の $\alpha$ を見つけることで、適切なステップサイズを決定します。

目的関数

プログラムには以下の2つの目的関数が実装されています。

Ellipsoid Function (efunc): $$f(x_0, x_1) = x_0^2 + 9.0 x_1^2$$ この関数は凸関数であり、大域的最小値は $(0,0)$ です。
General Function (gfunc): $$f(x_0, x_1) = -3.0 - 10.0 x_0 - 30.0 x_0^2 + 1.5 x_0^3 + 3.0 x_0^4 + 30.0 x_1 - 30.0 x_1^2 + 3.0 x_1^4 + 3.0 x_0 x_1^2$$ この関数はより複雑な非線形関数であり、複数の局所最小値を持つ可能性があります。

必要な非標準ライブラリとインストール方法

本プログラムを実行するには、以下の非標準ライブラリが必要です。

NumPy: 高性能な数値計算を可能にするPythonライブラリです。配列オブジェクトや線形代数演算を提供します。
Matplotlib: Pythonのグラフ描画ライブラリです。静的な、アニメーション化された、およびインタラクティブな可視化を作成できます。特に mpl_toolkits.mplot3d は3Dプロットに必要です。

これらのライブラリは pip コマンドを使用してインストールできます。

pip install numpy matplotlib

必要な入力ファイル

本プログラムは、実行に必要な外部入力ファイルを指定しません。すべての設定パラメータ（初期点、直線探索モード、目的関数など）はプログラムコード内で初期値が設定されており、必要に応じてコマンドライン引数で上書きすることができます。

生成される出力ファイル

本プログラムは、実行時にいかなるファイルも生成しません。最適化の進行状況や結果は、標準出力（コンソール）にテキストとして表示されるほか、matplotlib を用いたグラフィカルなウィンドウに3D曲面と2D等高線プロットとしてリアルタイムで描画されます。

コマンドラインでの使用例 (Usage)

本プログラムは、以下の形式でコマンドラインから実行できます。

python optimize-steepdescent2d-linesearch.py [x0_val] [y0_val] [lsmode] [functype]

引数は以下の意味を持ちます。

[x0_val] (省略可能): 初期点の $x$ 座標。浮動小数点数で指定します。デフォルト値は 0.0 です。
[y0_val] (省略可能): 初期点の $y$ 座標。浮動小数点数で指定します。デフォルト値は 0.0 です。
[lsmode] (省略可能): 使用する直線探索モード。以下のいずれかの文字列で指定します。デフォルト値は 'simple' です。
- '' または 'one': 固定ステップサイズ
- 'simple': シンプルなステップサイズ増加法
- 'exact': 2次近似に基づく厳密な直線探索
- 'golden': 黄金分割法
- 'armijo': アルミホ条件に基づく直線探索
[functype] (省略可能): 最適化対象の関数。以下のいずれかの文字列で指定します。デフォルト値は 'general' です。
- 'ellipsoid': 楕円関数 $f(x_0, x_1) = x_0^2 + 9.0 x_1^2$
- 'general': より複雑な非線形関数

引数を指定しない場合、プログラムはデフォルト設定 (x0=[0.0, 0.0], lsmode='simple', functype='general') で実行されます。

コマンドラインでの具体的な使用例

例1: 楕円関数をシンプルな直線探索で最適化

初期点を $(1.0, 1.0)$ とし、楕円関数 (ellipsoid) を 'simple' モードの直線探索で最適化します。

python optimize-steepdescent2d-linesearch.py 1.0 1.0 simple ellipsoid

実行結果の説明: プログラムは標準出力に以下のような最適化の進行状況を表示します。

Find minimum / maximum point by Newton-Raphson method

x0 = (1.0, 1.0): f = 10.0
   dx= [-0.002  -0.018]
   0(  2): x = ( 0.998,  0.982) dx =  0.018: f =  9.7028
   dx= [-0.001996  -0.017676]
   1(  2): x = ( 0.996004,  0.964324) dx =  0.017676: f =  9.41477
...
   dx= [-2.42767e-07 -2.18491e-06]
 199(  2): x = ( 1.21384e-07,  -1.21384e-08) dx =  2.18491e-06: f =  1.48835e-14
Converged at x =  [1.21383790e-07 -1.21383790e-08]  dx = 2.184908221808447e-06   f = 1.4883466185671195e-14
Press enter to terminate:

初期点 x0 = (1.0, 1.0) から開始し、関数値 f = 10.0 から徐々に減少し、最終的に x = (約0, 約0) に収束し、関数値も f = 約0 に近づいていることがわかります。これは楕円関数 $f(x_0, x_1) = x_0^2 + 9.0 x_1^2$ の大域的最小値が $(0,0)$ であることと一致します。同時に、最適化の軌跡を示すグラフウィンドウが表示され、探索点が最小値に向かって移動していく様子が視覚的に確認できます。

例2: 複雑な非線形関数をアルミホ条件の直線探索で最適化

初期点を $(-2.0, -2.0)$ とし、一般的な非線形関数 (general) を 'armijo' モードの直線探索で最適化します。

python optimize-steepdescent2d-linesearch.py -2.0 -2.0 armijo general

実行結果の説明: プログラムは同様に標準出力に最適化のログを表示します。

Find minimum / maximum point by Newton-Raphson method

x0 = (-2.0, -2.0): f = 64.0
   dx= [ 0.051515  0.024242]
   0(  3): x = (-1.948485, -1.975758) dx =  0.051515: f =  59.4187
   dx= [ 0.050478  0.023758]
   1(  3): x = (-1.898007, -1.952000) dx =  0.050478: f =  54.9961
...
   dx= [-2.60731e-06 -1.82136e-06]
 199(  1): x = ( 2.21980, -0.635887) dx =  2.60731e-06: f = -39.1173
Not converged
Press enter to terminate:

初期点 x0 = (-2.0, -2.0) から開始し、複雑な general 関数を探索します。関数値 f = 64.0 から減少し、最終的に f = 約-39.1173 の点で収束基準 (dxmax < eps) を満たさずに最大反復回数に達して「Not converged」と表示されていますが、これは局所最適解の一つに近づいていることを示唆します。複雑な関数では、異なる初期点から異なる局所解に収束する可能性があります。グラフウィンドウでは、探索パスが局所的な「谷」へと向かっていく様子が描画されます。

optimize-steepdescent2d-linesearch.py 技術ドキュメント