最適化問題
概要
- 与えられた制約条件の中で目的関数を最小化または最大化させる問題.
定義
\(f\) を次のような実数 \(\mathbb{R}\) を値域とする関数とする. 定義域を \(S\) とする.
\[ \begin{aligned} f : X \supset S \rightarrow \mathbb{R} \end{aligned} \]
この時, \(f\) を最小化(minimization) する \(x \in S\) を求める問題を 最適化問題(optimization problem) という.
\(f\) を目的関数(objective function) , 定義域 \(S\) を許容領域(feasible region) または 許容集合(feasible set) と.
最適化問題は次のように表記する.
\[ \begin{aligned} \left \Vert \quad \begin{aligned} &\textbf{minimize} \quad f(x) \\ &\textbf{subject to} \quad x \in S \\ \end{aligned} \right. \end{aligned} \]
次のように略記することもある.
\[ \begin{aligned} \left \Vert \quad \begin{aligned} &\textbf{min.} \quad f(x) \\ &\textbf{s.t.} \quad x \in S \\ \end{aligned} \right. \end{aligned} \]
最大化(maximization) の場合は次のように表記する.
\[ \begin{aligned} \left \Vert \quad \begin{aligned} &\textbf{maximize} \quad f(x) \\ &\textbf{subject to} \quad x \in S \\ \end{aligned} \right. \end{aligned} \]
または
\[ \begin{aligned} \left \Vert \quad \begin{aligned} &\textbf{max.} \quad f(x) \\ &\textbf{s.t.} \quad x \in S \\ \end{aligned} \right. \end{aligned} \]
\(f(x)\) の 最大化 は \(-f(x)\) の 最小化 と書き換えることができるため, 最大化と最小化は本質的に同値な問題となる.
最適化問題の解を 最適解(optimal solution) という.
関連項目
参考文献
- 田村明久・村松正和 (2018) 『最適化法』, 共立出版株式会社．