実現可能な地域

数学的最適化とコンピュータサイエンスにおいて、実行可能領域、 実行可能集合、または解空間とは、最適化問題において問題の制約条件を満たすすべての可能な点（選択変数の値の集合）の集合であり、不等式、等式、整数制約条件が含まれる可能性がある。^[1]これは、候補集合が絞り込まれる前の、問題に対する 候補解の初期集合である。

たとえば、およびを条件として、変数およびに関して関数を最小化する問題を考えます。ここで、実行可能集合は、 xの値が1以上10以下であり、yの値が5以上12以下のペア( x、y )の集合です。問題の実行可能集合は、最適化される基準を示す目的関数とは別のもので、上記の例では、${\displaystyle x^{2}+y^{4}}$${\displaystyle x}$${\displaystyle y,}$${\displaystyle 1\leq x\leq 10}$${\displaystyle 5\leq y\leq 12.\,}$${\displaystyle x^{2}+y^{4}.}$

多くの問題では、実行可能集合は、1 つ以上の変数が非負でなければならないという制約を反映します。純粋な整数計画問題では、実行可能集合は整数の集合 (またはそのサブセット) です。線形計画問題では、実行可能集合は凸 多面体です。凸多面体は、境界が超平面によって形成され、角が頂点である多次元空間の領域です。

制約充足は、実行可能な領域内の点を見つけるプロセスです。

凸実行可能集合とは、任意の 2 つの実行可能点を結ぶ線分が、他の実行可能点のみを通り、実行可能集合外の点を通らない集合のことです。凸実行可能集合は、線形計画問題を含む多くの種類の問題で発生します。特に興味深いのは、問題に最大化すべき凸目的関数がある場合、凸実行可能集合があると一般に解決が容易になり、局所最適値も大域最適値になるからです。

最適化問題の制約が相互に矛盾する場合、すべての制約を満たす点は存在せず、実行可能領域は空集合になります。この場合、問題には解がなく、実行不可能であると言われます。

実行可能集合は、有界の場合と有界でない場合があります。たとえば、制約集合 { x ≥ 0, y ≥ 0} によって定義される実行可能集合は、方向によっては実行可能領域内にとどまる範囲に制限がないため、有界ではありません。対照的に、制約集合 { x ≥ 0, y ≥ 0, x + 2 y ≤ 4} によって形成される実行可能集合は、任意の方向への移動範囲が制約によって制限されるため、有界です。

n変数の線形計画問題では、実行可能集合が制限されるための必要条件だが不十分な条件は、制約の数が少なくともn + 1 であることです (上記の例で示されているように)。

実行可能集合が無制限である場合、目的関数の詳細に応じて、最適値が存在する場合と存在しない場合があります。たとえば、実行可能領域が制約セット { x ≥ 0, y ≥ 0} によって定義されている場合、xまたはy を増やすことで候補ソリューションを改善できるため、 x + yを最大化する問題には最適値がありません。ただし、問題がx + y を最小化することである場合、最適値（具体的には ( x , y ) = (0, 0)の場合）が存在します。

最適化やその他の数学の分野、および探索アルゴリズム（コンピュータサイエンスのトピック ）では、候補解とは、与えられた問題の実行可能領域内の可能な解の集合のメンバーです。 ^[2]候補解は、問題に対する可能性のある、または合理的な解である必要はなく、単にすべての制約を満たす集合、つまり実行可能解の集合に含まれていればよいのです。さまざまな種類の最適化問題を解くアルゴリズムでは、候補解の集合を実行可能解のサブセットに絞り込むことが多く、そのサブセットの点は候補解として残り、他の実行可能解は候補として除外されます。

実行可能な点が除外される前のすべての候補解の空間は、実行可能領域、実行可能集合、探索空間、または解空間と呼ばれます。^[2]これは、問題の制約を満たすすべての可能な解の集合です。制約充足は、実行可能集合内の点を見つけるプロセスです。

遺伝的アルゴリズムの場合、候補解はアルゴリズムによって進化させられる集団内の個体である。^[3]

微積分学では、最適解は第 1 導関数テストを使用して求められます。つまり、最適化される関数の第 1 導関数はゼロとみなされ、この式を満たす選択変数の値はすべて候補解と見なされます (満たさない値は候補として除外されます)。候補解が実際の解ではない場合がいくつかあります。第 1 に、最大値を求めているときに最小値を与える場合 (またはその逆)、第 2 に、最小値も最大値も与えず、関数の局所的な上昇または下降が一時的に停止する鞍点または変曲点を与える場合があります。このような候補解は、第 2 導関数テストを使用して除外できる場合があります。このテストが満たされていれば、候補解は少なくとも局所的に最適であると判断できます。第 3 に、候補解は局所的最適値であっても、大域的最適値ではない場合があります。

の形の単項式の原始積分をとると、カヴァリエリの求積法を使った候補解は次のようになる。この候補解は、次の場合を除いて正しい。${\displaystyle x^{n},}$${\displaystyle {\tfrac {1}{n+1}}x^{n+1}+C.}$${\displaystyle n=-1.}$

線形計画問題を解くための単体法では、実行可能な多面体の頂点が最初の候補解として選択され、最適性についてテストされます。最適解として拒否された場合、隣接する頂点が次の候補解として考慮されます。このプロセスは、候補解が最適解であると判明するまで続けられます。