最適化問題

出典: ORWiki

【さいてきかもんだい (optimization problem)】

概要

「与えられた制約条件の下で目的を最適に達成するための数理モデル」で数理計画問題(mathematical programming problem)ともいう. 数学的には,

$\mbox{max.} \,$	$f(x) ( \,$ あるいは, $\mbox{min.} \quad f(x) ) \,$
$\mbox{s.t.}\,$	$x = (x_1,x_2,\ldots,x_n) \in F, \,$

と表現される. ここで, $F \,$ は $n \,$ 次元ベクトル空間 $\mathbf{R}^n \,$ の部分集合(実行可能集合)で, $f \,$ は $\mathbf{R}^n \,$ で定義された実数値関数(目的関数).

詳説

　最適化問題 （optimization problem）（数理計画問題）は, 「与えられた制約条件の下でより良い目的を達成するための数理モデル」で, 数学的には,

$\mbox{max.} \quad f(x) \mbox{(}$ あるいは, $\mbox{min.}\quad f(x))$

$\mbox{s.t.} \quad\quad x = (x_1,x_2,\ldots,x_n) \in F,$

のように表現される. ここで, $F\,$ は $n\,$ 次元ベクトル空間 $\mathbf {R}^n$ の部分集合で実行可能集合（feasible region）（許容集合）と呼ばれ, $f\,$ は $\mathbf {R}^n$ で定義された実数値関数で目的関数（objective function）と呼ばれる. また, $x \in F$ を実行可能解（許容解）, 実行可能解の中で目的関数の最大（あるいは, 最小）を達成する $x\,$ を最適解（optimal solution）と呼ぶ. 実行可能集合 $F\,$ は,

$F = \{ x \in S : g_i(x) \leq 0 \ (i=1,2,\ldots,m) \}$

のように表現されることが多い. ただし, $g_i\,$ は $\mathbf {R}^n$ で定義された実数値関数である. また, $S\,$ は対象とする最適化問題を記述するのに用いられる基礎となる空間と考えればよい. 基礎となる空間 $S\,$ , 実行可能領域 $F\,$ を表現するのに使われる関数 $g_i (i=1,2,\ldots,m),$ および, 目的関数 $f\,$ に種々の条件を課した多くのクラスの最適化問題が研究されている. 最適化問題は,

$S = \mathbf {R}^n$ （より一般的には, $S\,$ は $\mathbf {R}^n$ の開集合）
関数 $g_i (i=1,2,\ldots,m)$ は連続（多くの場合, 微分可能）

が仮定され, 変数ベクトル $x\,$ が連続的な値をとる連続最適化問題（continuous optimization problem）と,

$S\,$ は有限集合, または, 離散的な集合, たとえば, $S = \{ x \in \mathbf {R}^n : x_j = 0$ または $\mathrm{1}\,$ $\}\,$ （有限集合）, $S =\,$ あるグラフの部分グラフの集まり（有限集合）, $S = \{ x \in \mathbf {R}^n : x_j =$ 自然数 $\}\,$ （離散無限集合）.

が仮定され, 変数ベクトル $x\,$ が離散的な値をとる離散最適化問題（discrete optimization problem）に, 大きく分けることができる. 関数 $f, \ g_i (i=1,2,\ldots,m)$ に連続性（あるいは, 微分可能性）のみを仮定する非線形離散最適化問題のクラスも考えることができるが, そのような問題は非常に難しく, 関数 $f, \ g_i (i=1,2,\ldots,m)$ が線形（あるいは, 高々２次）関数である場合に限定することが多い. このように限定したとしても, 離散最適化問題には広範な応用がある. 個々の最適化問題は, それが定式化された元の（現実）問題と結びつけた名前で呼ばれることも多い. たとえば, 最小費用フロー問題, 最大フロー問題, 巡回セールスマン問題, グラフ分割問題等である. また, 上記の最適化問題に関する分類は厳密ではなく, 連続最適化と離散最適化の両方の特徴を共有する問題（たとえば, 施設配置問題, 線形混合整数計画問題）や, それらからはみ出た最適化問題も存在する.