PROFILPELAJAR.COM

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

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

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

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

凸可行集

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

无可行集

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

有界与无解的可行集

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

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

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

候选解

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

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

遗传算法

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

微积分

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

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

线性规划

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

参考文献

^ Beavis, Brian; Dobbs, Ian. Optimisation and Stability Theory for Economic Analysis. New York: Cambridge University Press. 1990: 32. ISBN 0-521-33605-8.
^ ^2.0 ^2.1 Boyd, Stephen; Vandenberghe, Lieven. Convex Optimization. Cambridge University Press. 2004-03-08. ISBN 978-0-521-83378-3.
^ Whitley, Darrell. A genetic algorithm tutorial (PDF). Statistics and Computing. 1994, 4 (2): 65–85 [2024-04-04]. S2CID 3447126. doi:10.1007/BF00175354. （原始内容存档 (PDF)于2024-05-11）.