制約なし非線形最適化問題

制約なし非線形最適化問題

次の問題を解くことを考えます。

最適化問題（制約なし非線形最適化問題）

\(f:\mathbb{R}^n\to\mathbb{R}\) は微分可能な関数とするとき

\[ \min_{\boldsymbol{x}}f(\boldsymbol{x}) \]

大域的最適解と局所的最適解

定義（大域的最適解）

関数 \(f:\mathbb{R}^n\to\mathbb{R}\) と \(\boldsymbol{x}^*\in\mathbb{R}^n\) に対して

\[ \forall \boldsymbol{x}\in\mathbb{R}^n,\quad f(\boldsymbol{x}) \ge f(\boldsymbol{x}^*) \]

が成り立つとき、\(\boldsymbol{x}^*\) を大域的最小解という。

定義（局所的最適解）

関数 \(f:\mathbb{R}^n\to\mathbb{R}\) と \(\boldsymbol{x}^*\in\mathbb{R}^n\) に対して

\[ \forall \boldsymbol{x}\in N(\boldsymbol{x}^*),\quad f(\boldsymbol{x}) \ge f(\boldsymbol{x}^*) \]

が成り立つとき、\(\boldsymbol{x}^*\) を局所的最小解という。 ただし、\(N(\boldsymbol{x}^*)\) は \(\boldsymbol{x}^*\) の近傍を表す。

最適性条件

局所的最適解であるための必要条件として、次のものがあります。

定理（1次の最適性条件）

多変数関数 \(f(\boldsymbol{x})\) に対して、点 \(\boldsymbol{x}^*\) が局所的最適解ならば、次が成り立つ。

\[ \nabla f(\boldsymbol{x}^*)=\boldsymbol{0} \]

反復法のアルゴリズム

アルゴリズム（反復法）
  1. 初期解 \(\boldsymbol{x}_0\in\mathbb{R}^n\) を定め、\(k=0\) とする。
  2. 停止条件を満たしていれば \(\boldsymbol{x}_k\) を出力する。
  3. 探索方向 \(\boldsymbol{d}_k\in\mathbb{R}^n\) を定める。
  4. ステップ幅 \(\alpha_k\gt0\) を定める。
  5. \(\boldsymbol{x}_{k+1}=\boldsymbol{x}_k+\alpha_k\boldsymbol{d}_k\) と更新する。
  6. \(k\gets k+1\) として (2) に戻る。