查看“︁可行域”︁的源代码

[[File:IP polytope with LP relaxation.svg|350px|thumb|有5个线性约束的问题（蓝，包括非负约束）。在无整数约束的情形下，可行集是以蓝色为边界的整个区域，若有[[整数规划|整数约束]]，则是红点组成的点集。]]
[[File:3dpoly.svg|thumb|right|3元[[线性规划]]问题的闭可行域是凸[[多面体]]。]]
在[[最优化]]与[[计算机科学]]中，'''可行域'''（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>在候选解的范围缩小之前，这是问题的初始候选解集。

例如，考虑最小化关于变量''x''、''y''的函数<math> x^2+y^4 </math>之值的问题，且有约束<math> 1 \le x \le 10 ,\ 5 \le y \le 12. \, </math>这里的可行集是''x''的值在1到10之间、''y''的值在5到12之间的有序数对<math>(x,\ y)</math>组成的集合。问题的可行集与[[目标函数]]是分离的，后者是要优化的对象，上例中目标函数是<math> x^2+y^4</math>。

很多问题中，可行集反映了变量必须非负的约束。在[[整数规划]]问题中，可行集是整数集（或其子集）。[[线性规划]]问题中，可行集是[[凸集|凸]][[多胞形]]，即多[[维度|维]]空间中的一个区域，其边界由[[超平面]]构成，四角是[[顶点 (几何)|顶点]]。

[[约束满足]]（Constraint satisfaction）是在可行域内找到一个点的过程。

==凸可行集==
{{See also|凸优化}}
[[凸集|凸]]可行集中，连接任意两可行点的线段只经过其他可行点，而不经过可行集以外的任何点。凸可行集遍布多种问题，如[[线性规划]]。若问题有待最大化的凸目标函数，则在有凸可行集的情形下通常更容易求解，且局部最优必是全局最优。

==无可行集==
若优化问题的约束相互矛盾，则不存在满足所有约束的点，可行域将是[[空集]]。这时问题无解，称作不可行（infeasible）。

==有界与无解的可行集==
 [[Image:Bounded unbounded.svg|right|thumb|有界可行集（上）与无界可行集（下）。下方的集合一直向右延伸。]]
可行集可能是[[有界集合]]，也可能是无界集合。例如，约束集<math>\{x\ge 0,\ y\ge 0\}</math>给出的可行集是无界的。而由约束集<math>\{x\ge 0,\ y\ge 0,\ x+2y\le 4\}</math>形成的可行集有界。

在''n''元[[线性规划]]问题中，可行集有界的必要不充分条件是约束数不少于<math>n+1</math>（如上例所示）。

若可行集无界，则可能有最优值，也可能无最优值，取决于目标函数的具体情况。例如，若可行域是由约束集<math>\{x\ge 0,\ y\ge 0\}</math>，则最大化<math>x+y</math>的问题没有最优值，因为任何候选解都可通过增加''x''或''y''来改进；但若问题是最小化<math>x+y</math>，则就有最优解（具体说是<math>(x,\ y)=(0,\ 0)</math>）。

==候选解==
[[最优化]]和[[数学]]的其他领域中，以及[[计算机科学]]的[[搜索算法]]中，'''候选解'''是给定问题的可行域中可能解[[集合]]的[[元素 (数学)|元素]]。<ref name=":0">{{Cite book |last=Boyd |first=Stephen |url=http://dx.doi.org/10.1017/cbo9780511804441 |title=Convex Optimization |last2=Vandenberghe |first2=Lieven |date=2004-03-08 |publisher=Cambridge University Press |isbn=978-0-521-83378-3}}</ref>候选解不一定是问题的可能解或合理解，它只是满足了所有约束，即在可行解集中。解各类优化问题的算法通常会将候选解范围缩小到可行解的子集，其中的点仍作为候选解，其他可行解则被排除。

排除任何可行解前，所有候选解构成的空间称作可行域、可行集、搜索空间或解空间。<ref name=":0" />[[约束满足]]的满足就是在可行集中找到一个点的过程。

===遗传算法===
[[遗传算法]]中，候选解是算法进化群体中的个体。<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 | access-date=2024-04-04 | archive-date=2024-05-11 | archive-url=https://web.archive.org/web/20240511195043/http://cobweb.cs.uga.edu/~potter/CompIntell/ga_tutorial.pdf | dead-url=no }}</ref>

===微积分===
微积分中，最优解是通过[[导数检验|一阶导检验]]来寻找的：待优化函数的一阶[[导数|导]]等于0，任何满足此条件的选择变量值都被视作候选解（不满足的则被排除）。候选解有几种可能不是实际解。首先，求最大值时它可能会给出最小值（反之亦然）；其次，它可能只给出了[[鞍点]]或[[拐点]]，二阶导检验可排除这种候选解，使得候选解至少是局部最优；第三，候选解可能是局部最优，但不一定是全局最优。

在求形式为<math>x^n</math>的[[单项式]]的[[不定积分]]时，使用[[卡瓦列里求积公式]]所得的候选解是<math>\tfrac{1}{n+1}x^{n+1}+C</math>。除<math>n=-1</math>时，此候选解实际上就是所求的解。

===线性规划===
[[File:Linear Programming Feasible Region.svg|frame|[[线性规划]]问题中，一系列线性约束会产生由变量的可能值组成的凸可行域。双变量情形下，可行域是凸[[简单多边形]]。在依次测试可行点的算法中，每个测试点都是一个候选解。]]
在求解[[线性规划]]问题的[[单纯形法]]中，可行[[多胞形]]的一个[[顶点 (几何)]]被选为初始候选解，并进行最优性测试，若该点不是最优解，则相邻顶点被视作下一个候选解。这个过程一直持续到找到最优候选解。

==参考文献==
{{reflist}}
[[Category:最佳化决策]]
[[Category:数学最佳化]]