可行域
![](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)
在最優化與計算機科學中,可行域(feasible region)、可行集(feasible set)或解空間(solution space)指滿足問題約束(可能包括不等式、等式和/或整數約束)的最優化問題的所有可能點(選擇變量的值集)的集合。[1]在候選解的範圍縮小之前,這是問題的初始候選解集。
例如,考慮最小化關於變量x、y的函數之值的問題,且有約束這裡的可行集是x的值在1到10之間、y的值在5到12之間的有序數對組成的集合。問題的可行集與目標函數是分離的,後者是要優化的對象,上例中目標函數是。
很多問題中,可行集反映了變量必須非負的約束。在整數規劃問題中,可行集是整數集(或其子集)。線性規劃問題中,可行集是凸多胞形,即多維空間中的一個區域,其邊界由超平面構成,四角是頂點。
約束滿足(Constraint satisfaction)是在可行域內找到一個點的過程。
凸可行集
凸可行集中,連接任意兩可行點的線段只經過其他可行點,而不經過可行集以外的任何點。凸可行集遍布多種問題,如線性規劃。若問題有待最大化的凸目標函數,則在有凸可行集的情形下通常更容易求解,且局部最優必是全局最優。
無可行集
若優化問題的約束相互矛盾,則不存在滿足所有約束的點,可行域將是空集。這時問題無解,稱作不可行(infeasible)。
有界與無解的可行集
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/0/06/Bounded_unbounded.svg/220px-Bounded_unbounded.svg.png)
可行集可能是有界集合,也可能是無界集合。例如,約束集給出的可行集是無界的。而由約束集形成的可行集有界。
在n元線性規劃問題中,可行集有界的必要不充分條件是約束數不少於(如上例所示)。
若可行集無界,則可能有最優值,也可能無最優值,取決於目標函數的具體情況。例如,若可行域是由約束集,則最大化的問題沒有最優值,因為任何候選解都可通過增加x或y來改進;但若問題是最小化,則就有最優解(具體說是)。
候選解
最優化和數學的其他領域中,以及計算機科學的搜索算法中,候選解是給定問題的可行域中可能解集合的元素。[2]候選解不一定是問題的可能解或合理解,它只是滿足了所有約束,即在可行解集中。解各類優化問題的算法通常會將候選解範圍縮小到可行解的子集,其中的點仍作為候選解,其他可行解則被排除。
排除任何可行解前,所有候選解構成的空間稱作可行域、可行集、搜索空間或解空間。[2]約束滿足的滿足就是在可行集中找到一個點的過程。
遺傳算法
微積分
微積分中,最優解是通過一階導檢驗來尋找的:待優化函數的一階導等於0,任何滿足此條件的選擇變量值都被視作候選解(不滿足的則被排除)。候選解有幾種可能不是實際解。首先,求最大值時它可能會給出最小值(反之亦然);其次,它可能只給出了鞍點或拐點,二階導檢驗可排除這種候選解,使得候選解至少是局部最優;第三,候選解可能是局部最優,但不一定是全局最優。
在求形式為的單項式的不定積分時,使用卡瓦列里求積公式所得的候選解是。除時,此候選解實際上就是所求的解。
線性規劃
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/0/0c/Linear_Programming_Feasible_Region.svg/250px-Linear_Programming_Feasible_Region.svg.png)
在求解線性規劃問題的單純形法中,可行多胞形的一個頂點 (幾何)被選為初始候選解,並進行最優性測試,若該點不是最優解,則相鄰頂點被視作下一個候選解。這個過程一直持續到找到最優候選解。
參考文獻
- ^ 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).