最優化問題包括可行決策的集合,以及給每個決策一個數值的目標函數。導數可提出候選點;可行集合與函數的形狀則決定候選點有甚麼意義。凸性的好處是兩個可行點之間的線段仍然可行,函數值亦不高於端點值的線性插值。因此局部資訊可推導出全局結論。
凸集合與凸函數
定義 1.1.1
(凸集)
若對所有 及 ,均有 ,則 稱為凸集。
空集和單點集均是凸集。凸集的交仍然凸:交集內兩點的連線在每個集合內。仿射等式 與半空間 都是凸集,故由有限個此類集合相交得到的多面體也是凸集。凸集的聯集卻未必凸;例如 不含零。
定義 1.1.2
(凸函數與嚴格凸函數)
設 為凸集。若
對所有 和 成立,則 稱為凸函數。若當 、 時不等式均嚴格成立,則稱 嚴格凸。
概念視角幾何
函數的凸性即集合的凸性
上圖集 凸,當且僅當 凸:由函數不等式可證上圖集凸;反過來取上圖集中的點 與 即得函數不等式。因此函數不等式就是高一維的集合定義,凸集的封閉性質亦變成凸函數的封閉性質。同一圖像說明每個次水平集 都凸。反命題不成立,例如 在 的次水平集都是區間,函數卻不凸。
一階與二階判別
對可微函數,可用切平面判別凸性;對二次可微函數,則可用曲率判別。
定理 1.1.3
(凸性的一階與二階刻劃)
設 是開凸集, 在 上可微。則 凸當且僅當
若 在 上二次連續可微,則它凸當且僅當每一點 的 Hessian 半正定。
證明
(先用差商,再限制到直線)
必要性:凸性給出對 有 ;令 即得結果。充分性:取 ,分別在 對 和 使用不等式,再乘以 和 相加;線性項抵消,得到凸性的定義。
至於二階判別,沿線段令 ,其二階導數為 。若 Hessian 半正定,則 不遞減,故 ,這正是一階不等式。反過來,把凸函數限制在經過 、方向為 的直線上,得到開區間上的一元凸函數,其二階導數 非負。
因此切平面是全局下界,不只是在接觸點附近的近似。處處正定的 Hessian 蘊含嚴格凸,但並非必要: 嚴格凸,卻有 。
局部、全局及存在性
可行點 若在附近的可行點中不大於任何目標值,便是局部最小點;若對所有可行點都成立,便是全局最小點。凸集上的凸函數的局部最小點必為全局最小點。否則存在更好的可行點 ;沿 至 的線段取足夠靠近 的點 ,由凸性其值不超過 ,矛盾。
命題 1.1.4
(嚴格凸性與唯一性)
凸可行集上的嚴格凸函數至多有一個全局最小點。若函數連續,而可行集非空且緊緻,則恰有一個。
證明
(以中點證唯一,以緊緻性證存在)
若 是兩個值為 的全局最小點,則中點可行,而嚴格凸性令其值小於 ,矛盾。若可行集非空且緊緻而 連續,極值定理給出最小點,它於是是唯一的最小點。
存在和唯一是不同結論: 在 上嚴格凸,下確界為零但沒有最小點。緊緻性是充分而非必要條件: 在非緊緻的實線上仍有最小值。另一常用條件是閉可行集上的連續函數具強制性,即沿任何滿足 的可行序列有 。取最小化序列,它最終位於有界次水平集內;閉性與連續性提供收斂子列,其可行極限取得下確界。
對可微凸目標,一條不等式便可證明受約束最小點。
定理 1.1.5
(凸可行集上的全局證書)
設非空凸集 包含於開凸定義域,而 在該定義域可微且凸。 在 上最小化 ,當且僅當對所有 ,。
證明
(可行線段證必要性,切平面證充分性)
設 是最小點,。由 凸,點 ()均可行,所以 滿足 。因此零處的右導數 非負。反過來,若不等式成立,一階刻劃給出對每個 有 。
證明透視
兩種凸性假設各用在哪一步
兩個方向用的是不同假設。必要性只用可微性及可行集的凸性:後者保證由 指向 的整條線段可行;目標函數的凸性在此不起作用。充分性只用目標函數的凸性,經由切平面下界;它完全不沿線段移動。正因切平面是全局下估計, 處的局部一階資訊已足夠,每個可行點一條不等式便完成論證。若 ,可同時在 與 測試,不等式便化為 。
每個假設都是使用它的那一個方向所必需的。
反例模式
去掉集合或目標函數的凸性
聲稱:對任何可行集上的任何可微目標,方向不等式都刻劃最小點。必要性方面,令 ,。兩個可行點都是全局最小點,但在 ,指向 的位移給出 ;目標函數是凸的,令線段論證失效的是非凸可行集。充分性方面,在 上取 。在 ,對每個可行 有 ,但 。修正後的敍述就是上述定理:必要性需要凸可行集,充分性需要凸目標函數。
邊界處梯度可以非零:在 最小化 ,最小點為零,所有可行位移與梯度的內積均非負。
例子:受約束二次函數
例題 1.1.6
(以方向不等式證明的邊界最小點)
最小化 ,條件是 。無約束最小點 不可行。考慮邊界點 ;其梯度為 ,而對每個可行 ,
一階條件證明它全局最優。Hessian 為 ,嚴格凸性保證唯一;最小值是 。這個證書比只看圖像或檢查幾個邊界點更有說服力。
強凸性與二次增長
嚴格凸性能區分不同點的函數值,卻沒有量化差距。要作數值估計,便需要一個正常數。
定義 1.1.7
(強凸性)
設 。若 在凸集 上凸,則稱 在 上為 -強凸。
開定義域上可微時,對此差函數使用一階不等式並展開平方,可得
最後一項把強凸與一般凸性區分開來。若凸可行集上存在最小點 ,方向最優條件令中間項對每個可行 非負。因此目標值與最優值之差至少是 。若另有最優值下界,便可由目標差距估計到最優點的距離,這可用來解讀停止準則。嚴格凸未必有固定的正二次下界: 在零附近趨向零。
例題:檢查假設
例題 1.1.8
(有平坦方向的二次函數)
考慮 上的 。其 Hessian 為 ,二次型為 ,故函數凸。直線 上每點的值均為零,因此有無限多個最小點。Hessian 在方向 奇異,嚴格凸性不成立。半正定性證明凸性,並不保證唯一。
例題 1.1.9
(投影到區間)
在 最小化 。取 ,導數為 ,每個可行 滿足 ,所以 。一階證書證明 全局最優,嚴格凸性保證唯一。導數非零與最優並不矛盾,因向右移動不可行。直接計算也可見整個區間上 ,故最小值為 。
例題 1.1.10
(駐點本身並不足夠)
設 ,原點梯度為零,但非零 滿足 而 。因此原點每個鄰域都有較大和較小的值,是鞍點而不是最小點。Hessian 不定。這說明梯度為零後仍須檢查曲率或其他全局條件。
如何使用證書
實際證明應指出定義域、確認候選點可行、建立凸性,再檢查方向不等式。無約束時先解 ,然後用支撐平面不等式證明;邊界問題則應判斷可行方向及其梯度內積。若題目要求唯一解,還須另外交代嚴格凸性或其他唯一性理由。
開凸域上的二次可微函數若某一點 Hessian 不定便不凸;但單點半正定不能說明其他點。Hessian 判別中的「每一點」不可省略。可行集即使由非凸函數描述,也可能本身是凸集;反之,凸目標函數在不連通可行集上未必有局部最小即全局最小的性質。
線性組合、複合及注意事項
若 在同一凸定義域上凸,且 ,則 凸。只需將各函數的凸性不等式乘以非負係數後相加。負係數一般會反轉不等式,故此證明不適用於任意帶符號的和。加上仿射函數會保持凸性,因仿射函數在線段上取等號,減去它也不影響結果。
有限個凸函數的逐點最大值亦凸:對每個 ,;再對 取最大值即可。例如 凸,雖然它在零不可微。因此可微的一階判別只適用於其假設所涵蓋的函數,並非所有凸函數的定義。
次梯度接替切平面的角色,無約束的證書變成零屬於次梯度集合。
通往推廣的路徑
目標函數有尖點時,甚麼取代梯度?
次梯度接替切平面的角色,無約束的證書變成零屬於次梯度集合。
對 上的凸函數 ,若對所有 有 ,則稱 為 在 的次梯度;這就是去掉梯度唯一性的切平面不等式。上面充分性的論證於是變成: 是全局最小點,當且僅當 是 的次梯度。 在零點的次梯度組成 ,其中包含零。有約束時, 的法錐會進入條件,而把它與次梯度結合需要某種約束資格條件。
另設 凸,而 在包含 值域的區間上凸且不遞減,則 凸:先用單調性將 作用於 的線段上界,再用 的凸性。單調性不可省略。外函數 雖凸,卻非在整條實線上不遞減;若 ,複合函數 在零的值大於它在 和 的平均值,所以不凸。
這些封閉性質有助建模。仿射殘差的平方和是凸的,因為每個仿射函數的平方都凸,而非負組合保持凸性。例如 的 Hessian 為 ,其二次型為 。若 有滿列秩,每個非零 的二次型嚴格為正,故函數嚴格凸且最小二乘解唯一。若 有非零零空間向量,沿該方向移動不改變目標值;一旦最小點存在,便不唯一。曲率的幾何性質因此連接到矩陣的秩。
常見錯誤
常見錯誤
(只在幾點或圖像上檢查凸性)
凸性涉及定義域內每一對點;檢查幾個例子,或在小範圍內畫出圖像,都不能證明無界定義域上的凸性。相反,一個反例便足以否定凸性,練習中 在 上的例子正是如此。
常見錯誤
(強求邊界最小點的梯度為零)
駐點要在相應凸性假設下才可證為全局最優,邊界最小點也不必滿足無約束的零梯度條件。在投影例題中,最小點 有 ;正確的檢驗是對可行位移的方向不等式。
常見錯誤
(把曲率或唯一性當作存在)
半正定曲率支持凸性,卻未必給出嚴格凸性或唯一性,平坦方向的例題已說明這點。沒有存在證明的唯一性論證,只說明解至多有一個: 嚴格凸,卻沒有最小點。
總結
以可行線段理解集合的幾何,用支撐平面將可微性轉化為全局下界,再用方向不等式證明受約束最小點。存在和唯一需要分開證明。當可行集由具體等式及不等式描述時,這些工具將引向乘子證書。
練習
快速檢查
(證明 有唯一全局最小點,並求出它。)
配方。
解答 · 答案
配方得 ,唯一最小點為 ,值為 。
快速檢查
( 在 上凸嗎?直接給出違反定義不等式的反例。)
試取區間左半的兩點。
解答 · 答案
不凸。取 、、,左邊為 ,大於右邊 ,違反凸性不等式。
快速檢查
(在 最小化 ;為何答案處的導數無須為零?)
找出最小點處的可行方向。
解答 · 答案
最小點為 ,因整個區間上 。雖然 ,左端的可行位移非負,故對每個可行 有 ,方向條件成立。