你的進度
0/ 28 節已標記完成
下一節: 凸性與最優條件
完成記錄儲存在此瀏覽器中。
這門課在網上
MATH4230 筆記裏的內容
數字只算這門課 28 節公開筆記裏寫了甚麼,不是網上已記錄的關係。目前其中 0 節已細緻地記錄到網上。
在網上定理卡 79 · 定義 35 · 反例 30 · 概念視角 17 · 證明透視 31
第 1 章 · 1 節
凸性與最優條件
凸集、支撐平面及局部與全局最小值。
- 1.1
凸性與最優條件
凸集、支撐平面及局部與全局最小值。
第 2 章 · 3 節
拉格朗日對偶與 KKT 證書
對偶下界及受約束最優性證書。
- 2.1
拉格朗日對偶與 KKT 證書
對偶下界及受約束最優性證書。
- 2.2
Farkas 擇一原理與線性化最優性
推導線性不可行證書,並連接線性化下降方向與乘數條件。
- 2.3
局部靈敏度與乘子
推導等式約束最優解及其值如何隨右端項改變。
第 3 章 · 2 節
下降法、共軛方向與 BFGS
線搜索、共軛方向及逆 BFGS 更新。
- 3.1
下降法、共軛方向與 BFGS
線搜索、共軛方向及逆 BFGS 更新。
- 3.2
二次函數上的精確最速下降法
證明精確線搜索的譜下降界,並理解它仍可能走鋸齒路徑的原因。
第 4 章 · 3 節
局部最優性與約束資格條件
可行及臨界方向、乘子資格條件與二階判別。
- 4.1
局部最優性與約束資格條件
可行及臨界方向、乘子資格條件與二階判別。
- 4.2
約束資格條件與乘子的穩定性
由可行方向理解 MFCQ、KKT 乘子及其有界性。
- 4.3
等式約束二次問題與約化 Hessian
利用可行方向判斷二次問題的最小點是否存在、是否唯一。
第 5 章 · 5 節
分離、次梯度與強對偶
分離及 Slater 對偶的擾動證明與敏感度。
- 5.1
分離、次梯度與強對偶
分離及 Slater 對偶的擾動證明與敏感度。
- 5.2
次梯度運算與投影次梯度步驟
在明確條件下計算支持斜率,並證明非光滑凸最小化的最佳迭代點及平均點速率。
- 5.3
漸退方向與最小點的存在性
利用閉凸幾何區分逃逸方向、有界水平集、最小值的取得及唯一性。
- 5.4
Fenchel 共軛與對偶證書
共軛函數、Fenchel 等號與等式約束對偶證書。
- 5.5
雙共軛與閉凸包絡
從仿射下界重建閉凸函數,並理解條件不成立時的變化。
第 6 章 · 2 節
線搜索、收斂與牛頓法
Armijo、Wolfe 收斂與牛頓法的局部收斂。
- 6.1
線搜索、收斂與牛頓法
Armijo、Wolfe 收斂與牛頓法的局部收斂。
- 6.2
強 Wolfe 條件的括區與縮放搜索
建立帶方向的線搜索括區,證明精確算術下的有限步終止,並區分數學接受與數值停止。
第 7 章 · 4 節
共軛梯度法與擬牛頓更新
CG 遞推、BFGS 曲率與具條件的收斂結果。
- 7.1
共軛梯度法與擬牛頓更新
CG 遞推、BFGS 曲率與具條件的收斂結果。
- 7.2
阻尼與有限記憶 BFGS
在擬 Newton 更新中保持正曲率,並毋須儲存完整矩陣便能套用逆矩陣更新。
- 7.3
非線性共軛梯度法與下降性
構造 Fletcher–Reeves 方向,區分二次問題的共軛性與非線性下降性,並證明強 Wolfe 下降界。
- 7.4
DFP 逆 Hessian 更新
推導 DFP 更新,證明其曲率性質,並計算一個二次函數例子。
第 8 章 · 1 節
8. 投影方法
證明光滑凸目標的投影梯度下降。
- 8.1
光滑凸目標的投影梯度法
推導投影下降不等式及有限迭代目標界。
第 9 章 · 2 節
近端方法
推導軟閾值及其不擴張性。
- 9.1
作為近端映射的軟閾值
用次梯度推導閾值規則並證明穩定性。
- 9.2
近端梯度法
以梯度步與近端映射交替,極小化光滑凸函數加簡單凸懲罰項,並證明 O(1/k) 的目標值上界。
第 10 章 · 2 節
信賴域模型與一階收斂
二次模型證書、Cauchy 下降及受保障的一階全局收斂定理。
- 10.1
信賴域模型與一階收斂
求球內二次模型的最小值,推導 Cauchy 下降並證明有界模型的收斂結果。
- 10.2
Cauchy 點與截斷共軛梯度法
構造有限步的信賴域模型求解法,證明充分下降,並解讀內點與邊界的殘差證書。
第 11 章 · 2 節
精確罰函數與增廣拉格朗日法
精確等式罰函數及增廣拉格朗日法的近端對偶收斂證明。
- 11.1
精確罰函數與增廣拉格朗日法
利用對偶乘子證明精確性,並推導等式約束的增廣拉格朗日算法。
- 11.2
不等式增廣拉格朗日法與投影乘子
推導正部增廣拉格朗日函數及近端對偶步,並在明確的取到假設下證明精確算法收斂。
第 12 章 · 1 節
障礙法與內點法
對數障礙函數、中心路徑與可驗證的對偶間隙 m/t。
- 12.1
對數障礙法與中心路徑
以對數障礙函數取代不等式約束,沿中心路徑前進,並證明對偶間隙不超過 m/t。