乘子何時代表局部變化率?
最優化模型常有一個指定的資源水平 。若已經解出某個水平下的問題,當 稍微改變時,是否必須從頭計算?乘子可以預測最優值的一階變化,但我們必須先說清楚正在追蹤哪個最優解,以及為甚麼它會平滑移動。我們會對正則的嚴格局部極小值證明這點;後面的例子則說明全局最優值未必有同一個導數。
設 及 在 附近二次連續可微,考慮
右端項是參數。採用拉格朗日(Lagrange)函數 。在 ,假設 的駐點乘子為 ,即 。記 及 。注意 包含約束的曲率,不只是 的 Hessian。
定理 2.3.1
(嚴格局部極小值的平滑分支)
假設 行滿秩,而且對每個滿足 的非零 都有 。那麼,對靠近 的 ,在 附近存在唯一駐點對 ,並且它連續可微地依賴 。每個 都是嚴格局部極小點。分支值 滿足
這是所選局部分支的結論,並不斷言該分支為全局最優。
證明
(由帶邊系統得到隱函數)
駐點及可行性方程 、 對 的導數在基點為
若 ,則 且 。把第二式與 取內積,得 。在 上的正定性迫使 ;接著 ,行滿秩便迫使 。因此方陣 非奇異,隱函數定理給出 附近唯一的 駐點分支 。由連續性, 的行滿秩,以及 在 上的正定性,在足夠小的鄰域內仍然成立,因此等式約束的二階充分條件保證每個分支點均為嚴格局部極小點。
對 微分得 。利用鏈式法則及駐點方程,
證明透視
每個假設在哪裏用上
行滿秩用了兩次:一次是把 從 的核中排除,另一次是透過 把駐點方程轉化為值的導數。二階正定性只需在 上成立;唯一不顯然的一步是與 取內積:由於 ,乘子項 消失,只剩下切向曲率。值的公式之後無需任何最優性論證便可完成,因為沿分支有 。證明從未把分支與遠處的可行點比較,所以既沒有用到、也沒有得到全局最優性;若 失去滿秩,如下面最後一個例題,第一步便已失效。
對小改變 ,結果寫成 。按照這裏的符號慣例,預測的邊際成本是乘子的負值。
常見錯誤
(未說明慣例便解讀乘子的正負)
「乘子為正,代表值隨 增加」這種說法,在寫出約束形式之前並無意義。採用 時,值的導數是 ;採用 時,乘子反號,導數變成 。解讀符號前先核對慣例。
計算解如何變化
沿方向 微分駐點及可行性方程。在基點,導數 及 滿足
這裏目標函數和約束函數除了上述右端項外,並不直接依賴 。如果參數還出現在其他地方,微分相應方程時便會產生額外項。由 ,局部值的 Hessian 為 。
當 在整個空間正定時,帶邊系統可以用消元法解出。
命題 2.3.2
( 時的響應矩陣)
在定理的假設下,再設 於 上成立。則 正定,並且
證明
(消去原變量的響應)
對 ,行滿秩給出 ,故 ;所以 正定且可逆。響應系統的第一個塊行給出 。代入 得 ,於是 ,且 。由於 任意,這些就是所述導數;再由 得最後一式。
這公式計算方便,但 比定理的假設更強:即使 在切空間之外奇異或不定,帶邊系統仍可能非奇異。
常見錯誤
(用目標函數的 Hessian 代替拉格朗日函數的 Hessian)
曲率條件針對的是 ,而不是 。若目標函數是線性而約束彎曲,如下面的圓周例題,便有 ,二階檢驗看似失敗;其實全部曲率都來自約束項。
例題
例題 2.3.3
(分配指定總量)
最小化 ,約束為 。駐點方程給出 和 ,因此 、、。所以 ,而 。這裏 、,故 ,。Hessian 正定,因此這個可行駐點對每個 都是唯一全局極小值。
例題 2.3.4
(由約束提供的曲率)
在 時,最小化 ,約束為 。駐點方程給出 和 ,故 ;可行性給出 。兩個駐點為 ,對應 。
在 ,,且 ,故定理適用。分支值為 ,而
在 ,、,故 ,命題預測 ;直接計算 也得出同一數值。另一個駐點有 及 ,切向曲率為負,它是極大點,而不是極小值分支。
以下兩項說明定理不涵蓋的情況。
反例模式
平滑局部分支可以交換全局最優地位
最小化 ,約束為 。當 , 與 都是嚴格局部極小點,值均為零;等式梯度行滿秩,切向曲率亦為正。因此每個點都有平滑局部分支。然而全局值 在零不可微。事實上 ,而可行點 與 顯示 。若 在零有導數,右側差商會迫使導數至多為 ,左側差商則迫使它至少為 。矛盾反映兩個局部分支互相競爭;切換點的全局值不能由任何一個局部乘子單獨微分。
在更一般的參數化下,另一種失敗是正則性消失。
例題 2.3.5
(約束梯度消失時)
最小化 ,約束為 。可行集為 ,故全局值是 ,它在 不可微。在 ,唯一可行點是 ,該處 :行滿秩失效。更甚者,駐點方程 在 無解,所以根本不存在乘子。不能只因為最優值有限,就套用乘子公式。
練習與解答
快速檢查
(最小化 ,約束 。求解、乘子、值及值的導數。)
採用 的慣例。
解答 · 答案
駐點方程給出 、,可行性給出 ,故 。所以 ,,且 。嚴格凸的目標函數保證唯一全局極小值。
快速檢查
(最小化 ,約束 。儘管目標 Hessian 不定,驗證定理在 的假設,並求分支值。)
只在 上檢驗曲率。
解答 · 答案
這裏 、。在 上,對 二次型為 。可行問題中 ,在 取得最小值,故 ,而 ,。負曲率不違反定理,因為定理只要求沿切方向正定;含 的命題則不適用,因為 。
快速檢查
(最小化 ,約束 。把約束寫成 ,求其乘子,並與值的導數比較。)
寫出 。
解答 · 答案
對 的駐點方程為 ,故 。值為 ,其導數為 。若使用原本的 慣例,乘子則為 ,導數為 。
快速檢查
(在第一個例題中,用 的導數估計 增加 時值的變化,再與精確變化比較。)
回想 。
解答 · 答案
,故一階估計為 。精確地,。差額 是二次項,並非一階公式失效。