実行可能領域のソースを表示

{{出典明記|date=2018-11}}
[[File:IP polytope with LP relaxation.svg|350px|thumb|五つの線形制約が与えられた問題の例（青線で表しており、これは非負条件の制約も含まれている。）。整数制約が無い場合の実行可能領域は青い線で囲まれた領域となるが、[[整数制約]]が加わると赤い点が実行可能領域となる。]]
[[File:3dpoly.svg|thumb|right|3変数における[[線形計画問題]]の有界な実行可能領域は凸[[多面体]]となる。]]

'''実行可能領域'''（じっこうかのうりょういき、'''許容領域'''、'''実行可能集合'''、'''解空間'''、{{Lang-en-short|feasible region, feasible set, solution space}}）とは、[[数理最適化]]および[[計算機科学]]において[[最適化問題]]に与えられた不等式、等式、整数といった[[制約条件]]を満たすすべての解の集合を指す<ref>{{cite book |first1=Brian |last1=Beavis |first2=Ian |last2=Dobbs |title=Optimisation and Stability Theory for Economic Analysis |location=New York |publisher=Cambridge University Press |year=1990 |isbn=0-521-33605-8 |page=32 |url=https://books.google.com/books?id=L7HMACFgnXMC&pg=PA32 }}</ref>。これは最適解の候補を探索する前の初期の集合を表す。

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

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

{{仮リンク|制約充足性|en|Constraint satisfaction}}については実行可能領域内の点を求めることを指す。

== 凸実行可能集合 ==
{{See also|凸最適化}}

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

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

== 有界・非有界の実行可能集合 ==
 [[Image:Bounded unbounded.svg|right|thumb|有界な実行可能集合（上）と非有界の実行可能集合（下）。下記の実行可能集合は右側にいくらでも存在する。]]

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

''n''変数における線形計画問題において実行可能集合が有界となる{{仮リンク|必要十分条件|en|Necessary and sufficient conditions|label=必要条件}}は制約の数が少なくとも ''n'' + 1 個以上存在しなければならない。

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

== 候補解 ==
候補解{{Efn|{{Lang-en-short|candidate solution}}}}とは、[[数理最適化|最適化]]や[[探索アルゴリズム]]、（[[計算機科学]]などの）他の[[数学]]の分野において問題の実行可能領域内の[[元 (数学)|要素]]を表す<ref name=":0">{{Cite book |last1=Boyd |first1=Stephen |url=http://dx.doi.org/10.1017/cbo9780511804441 |title=Convex Optimization |last2=Vandenberghe |first2=Lieven |date=2004-03-08 |publisher=Cambridge University Press |doi=10.1017/cbo9780511804441 |isbn=978-0-521-83378-3}}</ref>。候補解は最適解である必要がなく、与えられた[[制約 (数学)|制約]]をすべて満たす解自体を指し、
すなわち、実行可能解の集合となる。最適化問題に対するいくつかの解法では実行可能解の部分集合である候補解を限定していくことで最適解を求めており、候補解を限定しつつ、それ以外の解は候補解から除外することを行っている。

実行可能な候補解が取り除かれる前の全体の空間は次の名称で呼ばれる:実行可能領域（feasible region）、実行可能集合（feasible set）、探索空間（search space）、解空間（solution space）<ref name=":0" />。{{仮リンク|制約充足性|en|Constraint satisfaction}}ではこれらの実行可能集合の中から解を一つ求めることを指す。

=== 遺伝的アルゴリズム ===
[[遺伝的アルゴリズム]]では、候補解は集団の中の個体に該当する<ref>{{Cite journal | last=Whitley | first=Darrell | title=A genetic algorithm tutorial | journal=Statistics and Computing | doi=10.1007/BF00175354 | volume=4 | issue=2 | pages=65–85 | year=1994 | s2cid=3447126 | url=https://cobweb.cs.uga.edu/~potter/CompIntell/ga_tutorial.pdf }}</ref>。

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

[[単項式]] <math>x^n,</math> の{{仮リンク|不定積分|en|antiderivative}}を導出する際に{{仮リンク|カヴァリエリの求積公式|en|Cavalieri's quadrature formula}}を用いると、候補解 <math>\tfrac{1}{n+1}x^{n+1}+C.</math> が得られる。これは <math>n=-1.</math> を除いて正確な解となる。

=== 線形計画法 ===
[[Image:Linear_Programming_Feasible_Region.svg|thumb|[[線形計画問題]]において与えられた制約を満たし、これらの変数がとり得る領域を表した実行可能領域（feasible region）を表したものである。二変数の問題において実行可能領域が有界の場合は[[凸集合|凸]][[単純多角形]]として表される。実行可能点を逐次生成するアルゴリズムでは、候補解として各々最適解であるかを判定する。]]
[[線形計画問題]]に対する[[単体法]]では初期解として実行可能多面体の頂点を選択し、最適性の条件を満たすかを確認する。もし最適解でなければ、新たな解として隣接する頂点を新たに生成する。この手続きは現在の解が最適性の条件を満たすまで続けられる。

{{Clear}}

== 脚注 ==
{{脚注ヘルプ}}
=== 注釈 ===
{{Notelist}}
=== 出典 ===
{{Reflist}}

{{DEFAULTSORT:しつこうかのうりよういき}}
[[Category:最適化]]
[[Category:数学に関する記事]]