最優化模型與算法 — 基於 Python 實現

本書介紹了最優化模型的基礎知識，梳理了大數據和人工智能時代涌現出來的最優化算法，使用Python語言給出算法的代碼，展示了若乾實例。本書主要內容包括最優化模型基礎知識和最優化算法兩部分，介紹了凸集合、凸函數、凸優化模型、對偶理論，梳理了梯度下降法、牛頓法、Lagrange 乘子法、DC 規劃算法、梯度投影法、隨機梯度下降法、在線梯度下降法等優化算法。本書的讀者只需要具備微積分和線性代數的基礎知識即可。讀者可登錄華信教育資源網免費下載書中案例的源代碼。

目　　錄
第1章 凸集合 1
1.1 仿射集、凸集和凸錐 1
1.1.1 直線與線段 1
1.1.2 仿射集 1
1.1.3 仿射維數與相對內部 3
1.1.4 凸集合 3
1.1.5 凸錐 5
1.2 凸集合的示例 5
1.2.1 超平面和半空間 5
1.2.2 歐氏球和橢球 6
1.2.3 範數球和範數錐 7
1.2.4 多面體 7
1.2.5 半正定錐 7
1.3 保持凸性的運算 8
1.3.1 交集 8
1.3.2 仿射變換 8
1.4 支撐超平面 10
1.5 對偶錐 10
練習題 11
參考文獻 13
第2章 凸函數 14
2.1 凸函數的定義和例子 14
2.1.1 凸函數的概念 14
2.1.2 凸函數的例子 18
2.1.3 強凸性 19
2.1.4 其他凸集合和凸不等式 20
2.2 保持凸性的運算 22
2.3 共軛函數 25
2.3.1 共軛函數的概念 25
2.3.2 共軛概念的理解 27
2.4 次梯度與次微分 27
2.4.1 次微分的概念 27
2.4.2 對偶 29
練習題 29
參考文獻 32
第3章 凸優化模型 33
3.1 優化模型 33
3.1.1 基本術語 33
3.1.2 等價問題 34
3.2 標準形式及最優性條件 35
3.2.1 標準形式的凸優化問題 35
3.2.2 局部最優解與全局最優解 36
3.2.3 最優性條件 36
3.3 線性規劃 38
3.3.1 標準型線性規劃和不等式線性規劃 38
3.3.2 線性規劃轉化為標準型 39
3.3.3 線性規劃應用舉例 39
3.4 二次規劃模型 41
3.4.1 二次規劃的例子 42
3.4.2 二階錐規劃 44
3.5 幾何規劃 44
3.5.1 幾何規劃的擴展 45
3.5.2 幾何規劃轉化為凸優化問題 45
3.5.3 幾何規劃的例子 46
3.6 廣義不等式約束 47
3.6.1 錐規劃問題 47
3.6.2 半定規劃 47
3.6.3 組合優化中的SDP 48
練習題 50
參考文獻 52
第4章 對偶理論 53
4.1 Lagrange對偶函數 53
4.1.1 Lagrange函數 53
4.1.2 Lagrange對偶函數 53
4.1.3 最優值的下界 54
4.1.4 Lagrange對偶函數的例子 54
4.2 Lagrange對偶問題 55
4.2.1 對偶約束 55
4.2.2 弱對偶性 57
4.2.3 強對偶性與Slater約束規範 57
4.3 Lagrange對偶的理解 58
4.3.1 鞍點 58
4.3.2 博弈論解讀 58
4.4 最優性條件 59
4.4.1 非凸問題的KKT條件 60
4.4.2 凸問題的KKT條件 60
4.4.3 通過對偶求解優化問題 61
練習題 62
參考文獻 64
第5章 非凸優化算法 65
5.1 全局優化算法的復雜度 65
5.2 優化算法構造思想 68
5.3 梯度下降法 69
5.4 牛頓法 78
5.4.1 牛頓法思想 79
5.4.2 梯度下降法與牛頓法的關系 82
5.5 擬牛頓法 84
5.6 共軛梯度法 89
5.6.1 生成Q共軛方向 92
5.6.2 共軛梯度迭代公式 93
5.7 最小二乘問題 95
5.7.1 高斯-牛頓法 95
5.7.2 高斯-牛頓法與牛頓法的關系 96
5.7.3 增量梯度方法 97
5.8 Lagrange乘子法 98
5.8.1 二次懲罰函數法 100
5.8.2 拉格朗日乘子估計-不精確最小化 100
5.8.3 關於條件數較大的問題 101
5.8.4 乘子方法的主要思想 102
5.9 DC規劃算法及CCCP算法 104
5.10 進化算法 107
應用案例5.1：CCCP算法求解基於ramp損失的二分類問題 113
練習題 118
參考文獻 119
第6章 凸優化算法 120
6.1 梯度投影法 120
6.1.1 基於投影方法的可行方向和步長規則 120
6.1.2 步長選擇和收斂性 121
6.1.3 收斂速度 122
6.2 坐標下降法 123
6.2.1 算法 123
6.2.2 收斂性 123
6.2.3 有利於使用坐標下降法的問題結構 125
6.3 迫近梯度法 126
6.3.1 正則化模型的方法 126
6.3.2 使用凸正則項的一階方法 127
6.4 交替方向乘子法 130
6.4.1 ADMM算法 130
6.4.2 收斂性 132
6.4.3 應用舉例：ADMM方法求解Lasso問題 133
6.4.4 應用舉例：ADMM算法求解Bi-convex問題 135
6.5 隨機梯度下降法 137
6.5.1 隨機優化方法與批處理優化方法 138
6.5.2 隨機方法的動機 138
6.5.3 SG算法的收斂性分析 142
6.5.4 降噪-梯度聚合方法 144
6.5.5 二階方法—高斯-牛頓法 148
6.5.6 動量梯度法 150
6.5.7 加速梯度法 151
6.6 在線凸優化 152
6.6.1 在線凸優化的基本框架 152
6.6.2 Follow-The-Leader 152
6.6.3 Follow-The-Regularized-Leader 154
6.6.4 在線梯度下降法 156
6.6.5 強凸正則子 158
6.6.6 在線鏡像下降(OMD) 159
練習題 162
參考文獻 163