梅谷俊治：しっかり学ぶ数理最適化

概要

副題は「モデルからアルゴリズムまで」。

章末には文献ノートと演習問題があり、巻末には演習問題の解答がある。

感想

私のような、頭が弱い者にはわからない。

「第１章 数理最適化入門」の末尾に、文献ノートがある。ここで挙げられている入門書のうち、 「福島雅夫，新版 数理計画入門，朝倉書店，2011．」は、版が改まるとともに共著者が加わり、 「福島雅夫・山下信雄，数理計画入門 第３版，朝倉書店，2024．」となっている。

「第３章 非線形計画」の pp.099-100 で掲げられているアルゴリズム 3.1 最急降下法 を引用する。

Step 1:初期点 \( \boldsymbol{x}^{0} \) を定める．`k = 0` とする．
Step 2:\( \| \nabla f ( \boldsymbol{x}^{(k)}) \| \) が十分に小さければ終了する．
Step 3:探索方向 \( \boldsymbol{d}( \boldsymbol{x}^{k}) = - \nabla f ( \boldsymbol{x}^{(k)}) \) に沿って直線探索し，ステップ幅 `alpha_k` を求める．
Step 4:\( \boldsymbol{x}^{(k+1)} = \boldsymbol{x}^{(k)} + \alpha_k \boldsymbol{d}(\boldsymbol{x}^{(k)}) \) とする．`k = k + 1` として Step 2 に戻る．

p.100 では、次の問題を考えている。

最小化	\( f( \boldsymbol{x}) = (x_1 - 2)^4 + (x_1 - 2x_2)^2 \)
条件	\( \boldsymbol{x}\) `= (x_1, x_2)^"T" in RR^2`

さて、p.100 の(3.80) 式は次のようになっている。

\[ \nabla f ( \boldsymbol{x}) = \begin{pmatrix} 4(x_1-2)^3 + 2(x_1-2x_2)^2 \\ -4(x_1 - 2x_2) \end{pmatrix} \]

これは誤りで、次が正しい。

\[ \nabla f ( \boldsymbol{x}) = \begin{pmatrix} 4(x_1-2)^3 + 2(x_1-2x_2) \\ -4(x_1 - 2x_2) \end{pmatrix} \]

理由は、最小化すべき \( f(\boldsymbol{x}) \) の式を見てみれば明らかだろう。

ここで \( \| \nabla f ( \boldsymbol{x}^{(0)}) \| \) を求めないといけない。本書では、\( \boldsymbol{x}^{(0)} = (0, 3)^T \) としているので、 \( \boldsymbol{d}( \boldsymbol{x}^{(0)}) = (44, -24)^T \) となる。ここまではいい。問題はこの先だ。本書 p.100 では、 直線探索を適用するとステップ幅 `alpha_0 = 0.0625`が得られ，とさらりと書いているが、それを行なうにはどうすればいいのだろう。しょうがない。 `alpha = 1` から初めて、`alpha = 0.5, 0.25, 0.125, 0.0625 ... ` としていくしかないのか。

以下は初期点からさまざまなステップ幅 `alpha` を適用して得られた目的関数 `f` の値と点の位置 \( \boldsymbol{x} \)である

第３章の文献ノートの中で読んだことがあるのは以下の書籍である。

• 福島雅夫，非線形最適化の基礎
• 金森敬文／鈴木大慈／竹内一郎／佐藤一誠：機械学習のための連続最適化

数式記述ほか

数式記述は ASCIIMathML を、 数式表現は MathJax4 を用いている。計算のライブラリには mathjs を用いている。

書誌情報