跳至內容

可行域

維基百科,自由的百科全書
有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).