可行域 - 维基百科，自由的百科全书

在最优化与计算机科学中，可行域（feasible region）、可行集（feasible set）或解空间（solution space）指满足问题约束（可能包括不等式、等式和/或整数约束）的最优化问题的所有可能点（选择变量的值集）的集合。^[1]在候选解的范围缩小之前，这是问题的初始候选解集。

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

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

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

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

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

可行集可能是有界集合，也可能是无界集合。例如，约束集${\displaystyle \{x\geq 0,\ y\geq 0\}}$给出的可行集是无界的。而由约束集${\displaystyle \{x\geq 0,\ y\geq 0,\ x+2y\leq 4\}}$形成的可行集有界。

在n元线性规划问题中，可行集有界的必要不充分条件是约束数不少于${\displaystyle n+1}$（如上例所示）。

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

最优化和数学的其他领域中，以及计算机科学的搜索算法中，候选解是给定问题的可行域中可能解集合的元素。^[2]候选解不一定是问题的可能解或合理解，它只是满足了所有约束，即在可行解集中。解各类优化问题的算法通常会将候选解范围缩小到可行解的子集，其中的点仍作为候选解，其他可行解则被排除。

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

遗传算法中，候选解是算法进化群体中的个体。^[3]

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

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

在求解线性规划问题的单纯形法中，可行多胞形的一个顶点 (几何)被选为初始候选解，并进行最优性测试，若该点不是最优解，则相邻顶点被视作下一个候选解。这个过程一直持续到找到最优候选解。