数学の計算機科学やオペレーションズリサーチの分野における数理最適化(すうりさいてきか、英: mathematical optimization)または数理計画法(英: mathematical programming)とは、(ある条件に関して)最もよい元を、利用可能な集合から選択することをいう[1]。
最も簡単な最適化問題には、ある許された集合から入力をシステマティックに選び、函数の値を計算することによる実数函数(英語版)の最大化と最小化がある。最適化理論とその手法の、他の形式への一般化は応用数学の広範な分野をなすものである。より一般に、最適化はある与えられた定義域(あるいは制約の集合)についてある目的函数の「利用可能な最も良い」値を見つけることも含む。そのような目的函数と定義域は多様な異なるタイプのものも含む。
最適化問題詳細は「最適化問題」を参照
最適化問題は、次のように表現される:与えられるもの:ある集合 A から実数への函数 f : A → {\displaystyle \to } R目的:A 内のすべての x に対して最小化問題であれば f(x0) ? f(x) を満たす A 内の元 x0(最小点)と、あるいは最大化問題であれば f(x0) ? f(x) を満たす A 内の元 x0(最大点)を見つけること。
このような問題は最適化問題あるいは数理計画問題(コンピュータプログラミングとは直接的には関係ないが、例えば線型計画法では用いられる)と呼ばれる。多くの実世界での問題や理論的問題は、一般的な枠組みでモデル化される。物理学やコンピュータビジョンの分野における、この手法による問題は、エネルギー最小化(energy minimization)と呼ばれることもある。この場合、函数 f の値はモデル化されるシステムのエネルギーを表す。
典型的に集合 A はユークリッド空間 Rn の部分集合であり、しばしばある制約(英語版)の集合によって特徴づけられ、A の元は求められる等式あるいは不等式を満たす必要がある。f の定義域 A は探索空間(search space)あるいは選択集合(choice set)あるいは実行可能領域と呼ばれ、A の元は可能解(candidate solution, feasible solution)あるいは実行可能解と呼ばれる。
函数 f は、目的函数(objective function)や損失函数(loss function)、費用函数(cost function)、効用函数(utility function)、適合函数(fitness function)、エネルギー函数(energy function)あるいはエネルギー汎函数(energy functional)と呼ばれる[2]。目的函数を最小化(あるいは最大化)する可能解は、最適解と呼ばれる。
数学においてよくある最適化問題は、最小化に関するものである。最小化問題においては,「可能領域が凸領域でかつ目的函数がそこに於ける凸関数」となっていない場合には,一般に複数の局所最小解が存在しうる。ここで x* が局所最小解であるとは、ある定数 δ > 0 が存在して、 ‖ x − x ∗ ‖ ≤ δ ; {\displaystyle \|\mathbf {x} -\mathbf {x} ^{*}\|\leq \delta ;\,}
を満たすような任意の x に対して次が成立することをいう。 f ( x ∗ ) ≤ f ( x ) . {\displaystyle f(\mathbf {x} ^{*})\leq f(\mathbf {x} ).}
すなわち、点 x* はその(十分小さな)近傍内での最小点である。局所最大解も同様に定義される。
対比して問題の可能領域A全体における最小点のことを大域(的な)最小点ということがある。 最適化問題では、しばしば特殊な記号が用いられる。ここではそれらのいくつかを紹介する。 次の記号を考える: min x ∈ R ( x 2 + 1 ) . {\displaystyle \min _{x\in \mathbb {R} }\;(x^{2}+1).} これは x を実数の集合 R {\displaystyle \mathbb {R} } から選んだときの目的函数 x 2 + 1 {\displaystyle x^{2}+1} の最小値を意味する。この場合の最小値は x = 0 {\displaystyle x=0} のときの 1 {\displaystyle 1} である。 同様に、記号 max x ∈ R 2 x {\displaystyle \max _{x\in \mathbb {R} }\;2x} は、任意の実数 x に対する目的函数 2x の最大値を意味する。この場合、目的函数は非有界なのでそのような最大値は存在せず、「無限大」あるいは「定義されない」が答えとなる。 次の記号を考える。 a r g m i n x ∈ ( − ∞ , − 1 ] ( x 2 + 1 ) . {\displaystyle {\underset {x\in (-\infty ,-1]}{\operatorname {arg\,min} }}\;(x^{2}+1).} あるいは、次の同値なものを考える。 a r g m i n x ( x 2 + 1 ) , subject to: x ∈ ( − ∞ , − 1 ] . {\displaystyle {\underset {x}{\operatorname {arg\,min} }}\;(x^{2}+1),\;{\text{subject to:}}\;x\in (-\infty ,-1].} これは、区間 ( − ∞ , − 1 ] {\displaystyle (-\infty ,-1]} において目的函数 x2 + 1 を最小化する引数 x 自身の値を与える(その函数の最小値がどのような値であるかはここでは問題とされない)。この場合、x = 0 は不可能、すなわち実行可能領域
記号
函数の最小値と最大値
最適入力引数詳細は「arg max」を参照
同様に a r g m a x x ∈ [ − 5 , 5 ] , y ∈ R x cos ( y ) {\displaystyle {\underset {x\in [-5,5],\;y\in \mathbb {R} }{\operatorname {arg\,max} }}\;x\cos(y)}
あるいは a r g m a x x , y x cos ( y ) , subject to: x ∈ [ − 5 , 5 ] , y ∈ R {\displaystyle {\underset {x,\;y}{\operatorname {arg\,max} }}\;x\cos(y),\;{\text{subject to:}}\;x\in [-5,5],\;y\in \mathbb {R} }