可行域

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

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

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

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

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

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

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

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

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

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

排除任何可行解前，所有候选解构成的空间称作可行域、可行集、搜索空间或解空间。

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

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

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

参考文献