跳转到内容

可行域

维基百科,自由的百科全书
有5个线性约束的问题(蓝,包括非负约束)。在无整数约束的情形下,可行集是以蓝色为边界的整个区域,若有整数约束,则是红点组成的点集。
3元线性规划问题的闭可行域是凸多面体

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

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

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

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

凸可行集

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

无可行集

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

有界与无解的可行集

有界可行集(上)与无界可行集(下)。下方的集合一直向右延伸。

可行集可能是有界集合,也可能是无界集合。例如,约束集给出的可行集是无界的。而由约束集形成的可行集有界。

n线性规划问题中,可行集有界的必要不充分条件是约束数不少于(如上例所示)。

若可行集无界,则可能有最优值,也可能无最优值,取决于目标函数的具体情况。例如,若可行域是由约束集,则最大化的问题没有最优值,因为任何候选解都可通过增加xy来改进;但若问题是最小化,则就有最优解(具体说是)。

候选解

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

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

遗传算法

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

微积分

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

在求形式为单项式不定积分时,使用卡瓦列里求积公式所得的候选解是。除时,此候选解实际上就是所求的解。

线性规划

线性规划问题中,一系列线性约束会产生由变量的可能值组成的凸可行域。双变量情形下,可行域是凸简单多边形。在依次测试可行点的算法中,每个测试点都是一个候选解。

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

参考文献

  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. ^ 2.0 2.1 Boyd, Stephen; Vandenberghe, Lieven. Convex Optimization. Cambridge University Press. 2004-03-08. ISBN 978-0-521-83378-3. 
  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).