実行可能領域

この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "実行可能領域" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2018年11月)

実行可能領域（じっこうかのうりょういき、許容領域、実行可能集合、解空間、英: feasible region, feasible set, solution space）とは、数理最適化および計算機科学において最適化問題に与えられた不等式、等式、整数といった制約条件を満たすすべての解の集合を指す^[1]。これは最適解の候補を探索する前の初期の集合を表す。

例として、関数 ${\displaystyle x^{2}+y^{4}}$ の最小化問題について考える。ただし、各変数 ${\displaystyle x}$、${\displaystyle y}$ は制約条件として、${\displaystyle 1\leq x\leq 10}$、${\displaystyle 5\leq y\leq 12.\,}$ が課せられているとする。このときの実行可能集合は ${\displaystyle x}$ が1以上10以下、${\displaystyle y}$ は5以上12以下の値からなる組 (x, y) の集合である。問題の実行可能集合と目的関数は異なっており、上記の例では目的関数は ${\displaystyle x^{2}+y^{4}}$ を指す。

多くの問題において一つあるいは複数の変数が非負の値をとるという制約が与えられる。すべての変数に整数条件が与えられた整数計画問題における実行可能集合は整数（その部分集合）からなる。線形計画問題における実行可能領域は多次元空間において超平面と頂点を持つ凸多面体となる。

制約充足性（英語版）については実行可能領域内の点を求めることを指す。

凸実行可能集合とは実行可能集合の任意の2点を結ぶ線分内における点もまた必ず実行可能集合の要素となるような集合である。凸実行可能集合は線形計画問題といった多くの問題で用いられており、もし最適化問題の目的関数が凸関数でこれを最小化する際に実行可能集合が凸集合となる場合は局所最適解がかならず大域的最適解となるため、問題を解くのが容易であるとされる。

最適化問題の制約を満たすような点が存在しない場合、実行可能領域は空となる。このような場合を実行不可能（実行不能）と呼ぶ。

実行可能集合は有界・非有界のいずれかとなる。制約が {x ≥ 0, y ≥ 0} のときの実行可能集合は各変数の値がいくらでも大きく取り得るため、非有界となる。一方、制約が {x ≥ 0, y ≥ 0, x + 2y ≤ 4} の場合での実行可能集合は各制約によって変数の取り得る範囲が制限されるため、有界となる。

n変数における線形計画問題において実行可能集合が有界となる必要条件は制約の数が少なくとも n + 1 個以上存在しなければならない。

実行可能集合が非有界の場合、最適解が存在しない場合があり、これは目的関数に依存して決まる。例として、実行可能集合が {x ≥ 0, y ≥ 0} のときに関数 x + y を最大化する場合は x、y を任意に増大したとしても実行可能集合を満たすため、最適解が存在しないが、関数 x + y を最小化する場合は最適解（(x, y) = (0, 0) である。）が存在する。

候補解^{[注釈 1]}とは、最適化や探索アルゴリズム、（計算機科学などの）他の数学の分野において問題の実行可能領域内の要素を表す^[2]。候補解は最適解である必要がなく、与えられた制約をすべて満たす解自体を指し、 すなわち、実行可能解の集合となる。最適化問題に対するいくつかの解法では実行可能解の部分集合である候補解を限定していくことで最適解を求めており、候補解を限定しつつ、それ以外の解は候補解から除外することを行っている。

実行可能な候補解が取り除かれる前の全体の空間は次の名称で呼ばれる:実行可能領域（feasible region）、実行可能集合（feasible set）、探索空間（search space）、解空間（solution space）^[2]。制約充足性（英語版）ではこれらの実行可能集合の中から解を一つ求めることを指す。

遺伝的アルゴリズムでは、候補解は集団の中の個体に該当する^[3]。

微積分において最適解を求めるために一階微分判定法（英語版）により求める: このとき、一次の導関数がゼロとなる方程式を解くことで確かめられ、この方程式の解を候補解と呼ぶ。候補解の中には最適解とならないものも存在し、最大値を求めたいときに最小値が求まってしまう場合や、最大値・最小値でなく鞍点や変曲点が求まってしまう場合である。鞍点や変曲点では関数は局所的に関数の増減が停止されるため求まる場合がある。この場合二階微分判定法（英語版）により最適解かを判定することができる。さらに候補解が局所最適解であるが大域的最適解出ない場合が挙げられる。

単項式 ${\displaystyle x^{n},}$ の不定積分を導出する際にカヴァリエリの求積公式（英語版）を用いると、候補解 ${\displaystyle {\tfrac {1}{n+1}}x^{n+1}+C.}$ が得られる。これは ${\displaystyle n=-1.}$ を除いて正確な解となる。

線形計画問題に対する単体法では初期解として実行可能多面体の頂点を選択し、最適性の条件を満たすかを確認する。もし最適解でなければ、新たな解として隣接する頂点を新たに生成する。この手続きは現在の解が最適性の条件を満たすまで続けられる。