為何存在性需要另外證明
在凸最優化問題中,一階最優性條件可以證明某點是最小點;例如,無約束可微凸函數在梯度為零的點取得最小值,但這個條件本身不能保證這樣的點存在。即使函數連續且凸,它的下確界也可能永遠取不到。當中尚待處理的是逃逸問題:一列目標值愈來愈好的可行點,會否走到任意遠的地方?漸退方向描述一條直線路徑:沿此方向平移整個凸可行集,仍不會離開該集。當可行集無界、不能一開始便假設緊緻性時,這個概念特別有用。
下文所有空間均為有限維歐氏空間。一個集合若包含在某個半徑有限的球內,便稱為有界。最小點是取得下確界的可行點;僅有有限下確界,並不保證最小點存在。有關漸退方向的結論,需要所述的閉性與凸性假設,不能單憑一幅無界集合的圖像便斷定。
由一條射線推得整個集合可平移
對非空閉凸集 ,定義其漸退錐為
零向量必定屬於這個錐。它是一個閉凸錐:定義中的每個條件對 都是閉條件;乘上非負純量只會改變參數 ;而若 都屬於錐,凸性保證 屬於 ,再以 代替 ,便知 亦屬於錐。更一般地,任意非負線性組合都屬於它。
定理 5.3.1
(一條射線便能確定漸退方向)
設 非空、閉且凸。若存在一點 ,使每個 都有 ,則 。此外, 有界當且僅當 。
證明
(收縮的凸組合與取極限)
固定 及 。對每個足夠大而滿足 的整數 ,凸性給出
這些點收斂至 ;由於 是閉集,極限亦屬於 。這便證明第一項結論。若 有界,非零漸退方向會產生一條無界射線,故其漸退錐只能含零向量。
反過來,假設 無界,選取 及 ,使 。單位球面的緊緻性保證 有一個子序列收斂至某單位向量 。固定 後,最終有 ,所以凸組合 屬於 。由閉性得 。這對每個固定的 均成立,再用第一項結論,便知非零向量 是漸退方向。
證明透視
閉性如何把射線轉移至每個起點
閉性用了兩次,每次都在最後一步。在第一項結論中,凸組合 對每個足夠大的 都屬於 ,只有閉性才能把誤差項 去掉。不顯然的一步是把遠點 向外推,同時把其權重 縮小,使從 出發的位移除該誤差外總是 。凸性保證每個中間點都可行。在反方向中,單位球面的緊緻性從一列無界序列造出候選方向,閉性再次讓我們取極限,第一項結論則把從 出發的射線提升為漸退方向。
取極限這一步不能省略,下面的集合說明這點。
反例模式
一條射線的定理不能省略閉性
設 是 中射線 與點 的凸包。因此 包含 ,但其中第二個座標為 的點只有 。定義
集合 是凸的:邊界部分內的線段仍在 中;若線段有一端的 為正,則除了另一端可能例外,線段上點的 都為正。這個集合不是閉集。從 出發、方向為 的整條射線都在 中,可是 不在其中。因此 不屬於 。證明中的取極限步驟確實使用了閉性。
線性約束及最小值取得的定量判據
設 ,並假設 非空。則
事實上, 保證對所有可行的 及 ,均有 。反過來,若 的某一個分量為正,則對任何可行起點 ,沿 移動時,所對應的不等式最終都會失效。等式約束 同理帶來條件 。因此,只要已知可行集非空,漸退錐便由約束的法向量決定,而與右端項無關。
定理 5.3.2
(線性目標取得最小值的充分條件)
設 非空、閉且凸,並令 。若每個非零 都滿足 ,則 在 上取得最小值,且其最小點集合非空及緊緻。
證明
(緊緻的次水平集)
任取 ,並令 。這個非空集合是閉且凸的。若它無界,前面的定理便給出一個非零 。因為 ,射線 位於 中,故 ;而定義 的上界亦迫使 ,矛盾。因此 緊緻。 的連續性保證它在 上取得最小值,而 以外的點,其目標值都大於 的目標值,所以這亦是 上的最小值。最小點集合是 的閉子集,故亦緊緻。
嚴格不等式是取得最小值的充分條件,並非必要條件。若某個漸退方向滿足 ,則沿該方向從任意可行點出發,目標值均趨向 。若某個非零漸退方向滿足 ,沿該方向移動便不改變目標值;假如最小點存在,這會令最小點集合不緊緻,卻不會單憑這一點便阻止最小值取得。餘下的一種情況是下確界有限,卻沒有最小點;即使可行集閉且凸、目標為線性函數,這仍可能發生,下面的例子會展示這點。
例題 5.3.3
(同一個無界集合上的三個目標)
設 。它的漸退錐正是 本身。對 ,每個非零 均有 ,故定理保證最小點集合緊緻;直接檢查可知唯一最小點是 。對 ,方向 的目標變化率為零。最小值仍然取得,所有 對應的 都是最小點,因此最小點集合無界。對 ,方向 的目標變化率為負,所以下確界是 。每個非零漸退方向上的變化率均為正,保證最小點集合緊緻;負變化率迫使下確界為 ;非零漸退方向上的零變化率,則在最小點存在時排除最小點集合的緊緻性。 取得最小值,是由直接檢查得知的。
例題 5.3.4
(多面體可行集)
設 ,並最小化 。把約束寫成 ,漸退錐由 、 及 給出;最後一項是多餘條件,所以 是非負象限。對每個非零錐中向量,目標變化率 均為正,故定理證明最小值取得。為求最小點,固定 :最小的可行 是 。當 ,目標值至少為 ;當 ,則至少為 。只有 取等號,所以它是唯一最小點,最小值為 。右端項 對漸退錐毫無影響,只用來確定最小點的位置。
反例模式
可行集閉、下確界有限,卻沒有最小點
設 ,並最小化線性目標 。由於 連續且凸,其上圖集閉且凸。每個可行點都有 ,但 可行,且其目標值趨向零。因此下確界為零,卻取不到。這裏 是目標變化率為零的漸退方向。此例否定了「閉且凸加上有限下確界,就能推出最小值取得」的推論,也說明零變化率的漸退方向本身不能判定最小值能否取得。
非線性目標與次水平集
同樣的緊緻性推理不需要線性假設。
命題 5.3.5
(有界次水平集給出最小點)
設 非空且閉, 連續。若某個非空次水平集 有界,則 在 上取得最小值,而且最小點集合緊緻。
證明
(限制在次水平集上)
是 在閉集上連續函數下的原像,所以是閉集;它又有界,故緊緻。非空緊緻集上的連續函數取得最小值,設在 取得。 以外的點,其函數值大於 ,所以 是 在整個 上的最小點。最小點集合 是 的閉子集,故緊緻。這個存在性論證並不需要凸性。
一個有用的充分假設是在 上的強制性:對每個滿足 的序列 ,都有 。此條件令每個次水平集都有界。強制性是充分而非必要條件: 上的常數零函數處處取得最小值,卻不具強制性。另一個不同的條件——嚴格凸性——則保證唯一性:若 凸,且 在 上嚴格凸,兩個相異最小點的中點便會有嚴格較小的函數值。嚴格凸性本身不保證存在性: 在 上嚴格凸,卻只會趨近零而不取到零。
常見錯誤
(強制性要在 上檢驗,而非在 上)
取 及 。在 上它不具強制性,因為 而 ;但當 時這些點並不可行。對於滿足 的可行序列,有 ,故 ,從而 。因此 在 上具強制性,其最小點集合 緊緻。若在整個空間檢驗強制性,便會錯失一個有效的存在性論證。
例題 5.3.6
(有存在性而無唯一性)
設 ,定義於 。它連續且具強制性,因為當 時 。其次水平集 非空且緊緻,所以命題保證最小點存在。由 ,候選點為 及 ,而 、。因此最小值是 ,在 及 同時取得。存在性不需要凸性;唯一性失效,是因為 不凸: 大於 與 的平均值 。
概念視角幾何
存在性與唯一性回答不同問題
非空緊緻次水平集包含一個最小點,並讓我們選取一列有界的最小化序列。嚴格凸性則阻止兩個相異點同時具有最低函數值。兩個條件互不蘊含: 上的 同時具有兩種性質;常數函數取得最小值,但最小點不唯一; 則嚴格凸,卻不取得最小值。
練習與解答
快速檢查
(在 上最小化 。求最小點,並判斷最小點集合是否緊緻。目標函數在 上是否具強制性?)
沿方向 觀察。
解答 · 答案
由於 ,最小值是 ,並在所有 對應的 取得。這個集合閉但無界,因此不緊緻。沿 ,範數趨向無限,但目標值保持為 ,故目標在 上不具強制性。然而它仍然取得最小值。這裏沒有把線性目標的定理套用於 。
快速檢查
(在 上最小化 。求下確界,並判斷它能否取得。次水平集命題的哪個假設不成立?)
追蹤序列 。
解答 · 答案
下確界為零,因為 時的 趨向零,但每個可行的 都有 。雖然可行集及其次水平子集均有界,但這裏每個非空次水平集都是區間 或 ,不是 中的閉集,因此不緊緻。特別地,序列 沒有可行極限。由於 不是閉集,命題不適用。
快速檢查
(設 。證明 是漸退方向。對 、 及 ,分別求下確界,並判斷它能否取得。)
對 ,不要只考慮直線射線。
解答 · 答案
加上 只會增加 而不改變 ,所以對所有 均保持可行。對 ,有 ,且只在 取等號,所以最小值為零。對 ,可行射線 令目標值趨向 。對 ,可行點 令目標值趨向 。鉛直方向對 的變化率為零,說明一個零變化率方向既不能排除沿彎曲序列逃逸,也不能證明下確界有限。事實上,這裏的漸退錐只有向上的鉛直射線:非零水平分量會令 隨 二次增長,而 只會線性增長。若 且 ,則 最終會低於固定的 。