凸優化

📚 內容摘要

一門全面的研究生級課程與教科書，涵蓋凸優化的理論、應用及數值演算法。強調在工程與科學領域中辨識與建立凸問題的能力。

掌握凸優化在工程與資料科學中的數學基礎與實用演算法。

作者： Stephen Boyd, Lieven Vandenberghe

致謝： 部分由國家科學基金（NSF）資助，並受益於史丹福大學與加州大學洛杉磯分校學生與同事的貢獻，特別感謝 Arkadi Nemirovski 與 Kishan Baheti。

🎯 學習目標

1. 定義數學優化問題的各個組成部分，包括目標函數、約束條件與變數。
2. 根據其數學性質，區分最小二乘法、線性規劃與凸優化問題。
3. 比較局部與全域優化策略，並評估各自對應的計算複雜度。
4. 使用正式的組合符號定義並區分仿射集合、凸集合與錐體。
5. 辨識並表示標準的凸集合，包括歐幾里得球體、橢球體、多面體與半正定錐體。
6. 應用保凸運算，如交集、仿射變換與投射函數，以驗證集合性質。
7. 辨識並應用保凸運算，包含仿射函數的點態上確界與向量組合規則。
8. 推導各種函數的拉格朗日共轭，並應用楊不等式（Young's inequality）。
9. 透過次水平集以及一階與二階可微條件來描述擬凸性。
10. 建構與轉換：利用鬆弛變數與約束消去法，將原始優化問題轉化為標準凸形式。

🔹 第1課：數學優化導論

概述： 本課介紹數學優化的基礎概念，從一般問題表述過渡到可解的特定類型，如最小二乘法與線性規劃。重點在於凸與非凸優化之間的關鍵區別，詳述凸方法如何作為效率可靠的「分水嶺」，並提供解決更困難的非線性問題的重要工具。

學習成果：

• 定義數學優化問題的各個組成部分，包括目標函數、約束條件與變數。
• 根據其數學性質，區分最小二乘法、線性規劃與凸優化問題。
• 比較局部與全域優化策略，並評估各自對應的計算複雜度。

🔹 第2課：凸集合理論

概述： 本課探討優化問題的基礎幾何結構，從基本的線性結構過渡到凸集合與錐體的複雜性質。內容涵蓋仿射與凸集合的數學定義，檢視多面體與半正定錐體等特定幾何形狀，並詳細說明可用於高維空間中描述與操作凸集合的運算與定理。

學習成果：

• 使用正式的組合符號定義並區分仿射集合、凸集合與錐體。
• 辨識並表示標準凸集合，包括歐幾里得球體、橢球體、多面體與半正定錐體。
• 應用保凸運算（如交集、仿射變換與投射函數）以驗證集合性質。

🔹 第3課：凸函數與性質

概述： 本課探討保留凸性的進階運算，如點態上確界與特定組合規則，並引入拉格朗日共轭函數。將凸性概念延伸至擬凸與對數凹函數，同時探討廣義不等式下的凸性，以及矩陣特有性質（如舒爾補）。這些概念構成辨識與建構複雜優化問題的數學基礎。

學習成果：

• 辨識並應用保凸運算，包括仿射函數的點態上確界與向量組合規則。
• 推導各類函數的拉格朗日共轭，並應用楊不等式。
• 透過次水平集與一階/二階可微條件來描述擬凸性。

🔹 第4課：凸優化問題的建構

概述： 本課涵蓋凸優化問題的形式結構與轉換，從標準形式與最優性條件，到特定問題類別如線性規劃（LP）、二次規劃（QP）與半定規劃（SDP）。學生將學習如何辨識全域最優性，使用二分法求解擬凸問題，並應用標量化技術處理多目標向量優化。

學習成果：

• 建構與轉換：利用鬆弛變數與約束消除法，將原始優化問題轉化為標準凸形式。
• 分析最優性：應用基於梯度的最優性準則，判斷某一點是否為全域最優。
• 分類與求解：區分線性規劃（LP）、二次規劃（QP）、SOCP、幾何規劃（GP）與半定規劃（SDP），並應用專用方法（如二分法）求解擬凸函數。

🔹 第5課：拉格朗日對偶與KKT條件

概述： 本課探討拉格朗日對偶的基本理論，從拉格朗日對偶函數的定義過渡到對偶問題的建構。內容涵蓋原問題與對偶問題最優值之間的關鍵差距，這些關係的幾何與博弈論解釋，以及鑑別最佳解的卡魯什-庫恩-塔克（KKT）條件。最後，課程延伸至敏感度分析與影子價格。

學習成果：

• 推導拉格朗日對偶函數，並為各種優化問題建構對偶問題。
• 利用弱對偶性、強對偶性與斯萊特約束條件（Slater's constraint qualification）評估原問題與對偶問題之間的關係。
• 應用KKT最優性條件，求解並驗證凸與非凸問題的最佳解。

🔹 第6課：近似、擬合與正則化

概述： 本課探討線性方程組解的近似與資料擬合的數學基礎與實際應用。內容涵蓋基於範數的近似方法，包括懲罰函數與正則化，以管理異常值與稀疏性；以及處理資料不確定性的穩健優化技術。此外，還詳細討論在特定約束（如凸性與單調性）下進行函數擬合的方法。

學習成果：

• 建構並求解範數近似問題，解釋最小二乘法、切比雪夫與L1方法在幾何與統計上的差異。
• 設計並實現正則化近似模型，以取得殘差誤差、解大小與稀疏性之間的權衡。
• 建構穩健近似框架，以考慮資料矩陣中的不確定性。

🔹 第7課：統計估計與推論

概述： 本課探討統計推論與凸優化的交集。聚焦於將估計問題——包括最大概似估計、非參數分配估計與最佳偵測器設計——建構為凸規劃問題。學生將學習如何利用優化方法尋找參數，並設計具資訊量的實驗。

學習成果：

• 將最大概似估計（MLE）與邏輯回歸問題建構為凸優化任務並求解。
• 使用線性規劃（LP）設計最佳偵測器，並解釋受試者工作特性曲線（ROC）。
• 應用非參數估計技術，包括最大熵與克勞斯貝克-萊布勒散度最小化。

🔹 第8課：幾何問題與分類

概述： 本課探討凸優化在幾何問題中的應用，包括點到集合的投影、集合間距離的計算，以及集合中心的表徵。進一步將這些幾何原理應用於實際任務，如線性與非線性分類、最佳設施配置與使用幾何規劃的樓層佈局。

學習成果：

• 利用KKT條件與對偶表示，建構並求解凸集合間的投影與距離問題。
• 使用極大體積橢球逼近複雜凸集合，並識別其效率因子。
• 計算各種集合中心，並應用於穩健的區分與分類。

🔹 第9課：無約束最小化演算法

概述： 本課涵蓋凸函數無約束最小化的理論基礎與演算法實現。詳細說明從一階梯度下降法到二階牛頓法的下降方法。重點放在收斂性分析，特別是強凸性與自相容性（self-concordance）的仿射不變理論。

學習成果：

• 定義強凸性，並利用其後果對次優性與接近最佳解的距離提供上界。
• 在歐幾里得、二次與L1範數下，比較與對比梯度下降法與最陡下降法。
• 計算牛頓步與牛頓遞減量，解釋為何牛頓法具有仿射不變性。

🔹 第10課：等式約束最小化

概述： 本課探討求解具有線性等式約束的凸優化問題的方法。重點在牛頓步的推導與實現，比較可行與不可行起點方法，並在原-對偶框架中解釋這些步驟。特別強調透過KKT系統的塊消元法實現高效數值計算。

學習成果：

• 計算並解釋等式約束問題的牛頓步與遞減量。
• 展示帶等式約束的牛頓法與約束消去法的等價性。
• 實現不可行起點牛頓法，並解釋其原-對偶殘差降低特性。

🔹 第11課：內點法

概述： 本課介紹內點法，透過對一系列等式約束問題應用牛頓法，解決具有不等式約束的凸優化問題。核心在於對數障礙函數，追蹤通向最優解的中心路徑，並利用原-對偶框架提升效率與穩定性。

學習成果：

• 定義並建構對數障礙函數，描述中心路徑及其相關的對偶點。
• 實現障礙法，包含中心步與外層迭代之間的權衡。
• 建構並求解第一階段可行性問題，以找到嚴格可行的起始點。