【第2回】最適化問題〜最適化理論で考える問題・用語〜

前回のおさらい

前回、この記事

  • 最適化理論を勉強するモチベーション
  • 本ブログの目標

をご紹介しました。

本記事では最適化理論で考える「最適化問題」を考えます。

 

この記事の目標:

機械学習などで出てくる「最適化問題」を理解する。
基礎的な用語にふれる。

 

最適化問題とは

\begin{eqnarray}\min_x \ \  &f_0(x)& \\ {\rm subject \ to} \ \ &f_i(x)& \leq 0, \ i=1,2,\ldots,m \\ &h_j (x)& =0, \ j=1,2,\ldots, p \end{eqnarray}

を満たす \(x\) を得る問題です。

※ \(f_i(x) \leq 0, h_j (x) = 0\) はそれぞれ \(m,p\) 個あります。

 

日本語で言うと以下の通りとなります。

\(f_i (x) \leq 0, \ h_j (x) = 0\) をすべて満たし、

\(f_0(x)\) を最も小さくする  \(x\) を見つけなさい。

 

用語など

最適化問題を紹介したので、それに関連した用語にふれていきましょう。
たくさんありますが、頑張っていきましょう!

  • \(x\) は変数(一般にベクトル)
  • \(f_0(x)\) は目的関数(コスト関数ともいう)

(おさらい)やりたいこと:

「目的関数をできる限り小さくする変数を求める」

 

ただ、気をつけなければいけないことがあります。

  • \(f_i (x) \leq 0\) は不等式制約
  • \(h_j (x) = 0\) は等式制約

これらの制約を満たす \(x\) のなかで目的関数をできるだけ小さくします。

 

この制約を満たす \(x\) には特別に名前がついています。

  • 制約をすべて満たす \(x\):実行可能解
  • 実行可能解 \(x\) の全パターン:実行可能領域

 

制約があるとき、ないときそれぞれに名前が付いています。

  • 制約が(ある/ない)最適化問題:制約(あり/なし)最適化問題

 

この問題の解、つまり

\(f_i (x) \leq 0, \ h_j (x) = 0\) を満たす \(x\) (実行可能領域内の点)で、

\(f_0(x)\) を最も小さくする  \(x=x^{*}\)

の \(x^{*}\) を最適解といいます。

また、最適解の目的関数の値 \(f(x^{*})\) を最適値といいます。

 

例題

次の最適化問題を解きなさい。

\begin{eqnarray}\min_x \ \  &(x-1)^2& \\ {\rm subject \ to} \ \ &x& \leq 0\end{eqnarray}

つまり

\(x \leq 0\) を満たし、

\((x-1)^2\) を最も小さくする  \(x\) を見つけなさい。

目的関数: \((x-1)^2\)

不等式制約: \(x \leq 0\)

等式制約:なし

実行可能解: \(x \leq 0\) を満たす点

実行可能領域:\(x\) が 0 以下(図中灰色)

最適解: \(x^{*} = 0\)

最適値: \(f(x^{*}) = (0-1)^2 = 1\)

 

注意:

実行可能領域に含まれていないため、\(x=1\) は最適解ではありません。

「実行可能領域内で目的関数を一番小さくする点」を探すことが大切です。

 

次回予告

今回は

  • 最適化理論で考える「最適化問題」
  • その用語、例題

をご紹介しました。

次回は今回お話した

  • 「最適化問題」が機械学習で現れることを紹介します。

 

第3回「機械学習で現れる最適化問題」

 

参考文献

[1] S.Boyd and L. Vandenberghe, “Convex Optimization,” Cambridge University Press, Cambridge, 2004.

[2] 寒野, 土屋著 “東京大学工学教程 基礎系数学 最適化と変分法,” 丸善出版, 2014.

北海道大学大学院情報科学研究科修士課程修了。
機械メーカにて開発業務に従事したのち、フリーのエンジニア・講師として活動中。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です