可行域
在最优化与计算机科学中,可行域(feasible region)、可行集(feasible set)或解空间(solution space)指满足问题约束(可能包括不等式、等式和/或整数约束)的最优化问题的所有可能点(选择变量的值集)的集合。[1]在候选解的范围缩小之前,这是问题的初始候选解集。
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/0/06/IP_polytope_with_LP_relaxation.svg/350px-IP_polytope_with_LP_relaxation.svg.png)
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/e/ef/3dpoly.svg/220px-3dpoly.svg.png)
例如,考虑最小化关于变量x、y的函数之值的问题,且有约束这里的可行集是x的值在1到10之间、y的值在5到12之间的有序数对组成的集合。问题的可行集与目标函数是分离的,后者是要优化的对象,上例中目标函数是。
很多问题中,可行集反映了变量必须非负的约束。在整数规划问题中,可行集是整数集(或其子集)。线性规划问题中,可行集是凸多胞形,即多维空间中的一个区域,其边界由超平面构成,四角是顶点。
约束满足(Constraint satisfaction)是在可行域内找到一个点的过程。
凸可行集
凸可行集中,连接任意两可行点的线段只经过其他可行点,而不经过可行集以外的任何点。凸可行集遍布多种问题,如线性规划。若问题有待最大化的凸目标函数,则在有凸可行集的情形下通常更容易求解,且局部最优必是全局最优。
无可行集
若优化问题的约束相互矛盾,则不存在满足所有约束的点,可行域将是空集。这时问题无解,称作不可行(infeasible)。
有界与无解的可行集
可行集可能是有界集合,也可能是无界集合。例如,约束集 给出的可行集是无界的。而由约束集 形成的可行集有界。
在n元线性规划问题中,可行集有界的必要不充分条件是约束数不少于 (如上例所示)。
若可行集无界,则可能有最优值,也可能无最优值,取决于目标函数的具体情况。例如,若可行域是由约束集 ,则最大化 的问题没有最优值,因为任何候选解都可通过增加x或y来改进;但若问题是最小化 ,则就有最优解(具体说是 )。
候选解
最优化和数学的其他领域中,以及计算机科学的搜索算法中,候选解是给定问题的可行域中可能解集合的元素。[2]候选解不一定是问题的可能解或合理解,它只是满足了所有约束,即在可行解集中。解各类优化问题的算法通常会将候选解范围缩小到可行解的子集,其中的点仍作为候选解,其他可行解则被排除。
排除任何可行解前,所有候选解构成的空间称作可行域、可行集、搜索空间或解空间。[2]约束满足的满足就是在可行集中找到一个点的过程。
遗传算法
微积分
微积分中,最优解是通过一阶导检验来寻找的:待优化函数的一阶导等于0,任何满足此条件的选择变量值都被视作候选解(不满足的则被排除)。候选解有几种可能不是实际解。首先,求最大值时它可能会给出最小值(反之亦然);其次,它可能只给出了鞍点或拐点,二阶导检验可排除这种候选解,使得候选解至少是局部最优;第三,候选解可能是局部最优,但不一定是全局最优。
在求形式为 的单项式的不定积分时,使用卡瓦列里求积公式所得的候选解是 。除 时,此候选解实际上就是所求的解。
线性规划
在求解线性规划问题的单纯形法中,可行多胞形的一个顶点 (几何)被选为初始候选解,并进行最优性测试,若该点不是最优解,则相邻顶点被视作下一个候选解。这个过程一直持续到找到最优候选解。
参考文献
- ^ 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).