凸優化演算法 Algorithms for Convex Optimization

目 錄
譯者序
前言
致謝
記號
第 1 章 連續最佳化與離散最佳化的關聯　 1
1.1 一個例子：最大流問題 1
1.2 線性規劃6
1.3 基於內點法的快速精確演算法　 9
1.4 簡單線性規劃之外的橢球法 10
第 2 章 預備知識 13
2.1 導數、梯度與黑塞矩陣　 13
2.2 微積分基本定理 14
2.3 泰勒近似 15
2.4 線性代數、矩陣與特徵值 16
2.5 柯西–施瓦茲不等式 18
2.6 範數　 19
2.7 歐幾裡得拓樸 20
2.8 動力系統 21
2.9 圖　 21
2.9.1 圖上的結構 22
2.9.2 圖的關聯矩陣 23
2.9.3 與圖相關聯的多胞形　 24
習題 24
註記 28
第 3 章 凸性　 29
3.1 凸集　 29
3.2 凸函數　 30
3.3 凸性的作用 35
3.3.1 凸集的分離超平面與支撐超
平面　 35
3.3.2 次梯度的存在性37
3.3.3 凸函數的局部最優值是全域最優值　 38
習題 39
註記 41
第 4 章 凸優化與高效能 42
4.1 凸規劃　 42
4.2 計算模型 44
4.3 凸集的從屬問題 45
4.4 最佳化問題的求解 50
4.5 凸優化的多項式時間概念 53
習題 55
註記 57
第 5 章 對偶性與最適性 58
5.1 Lagrange 對偶　 58
5.2 共軛函數 63
5.3 KKT 最優條件 65
5.4 Slater 條件下的強對偶性證明　 66
習題 67
註記 70
第 6 章 梯度下降法 71
6.1 預備　 71
6.2 梯度下降法概論 71
6.2.1 為什麼要沿著梯度下降　 72
6.2.2 關於函數、梯度和初始點的假設　 73
6.3 梯度 Lipschitz 連續時的分析　 75
6.3.1 下界　 79
6.3.2 約束優化的投影梯度下降法　 80
6.4 應用：最大流問題　 81
6.4.1 s-t 最大流問題　 81
6.4.2 主要結果 82
6.4.3 建模成無約束凸規劃　 82
6.4.4 梯度下降法中的步驟　 84
6.4.5 運行時間分析 85
6.4.6 處理近似解 86
習題 86
註記 90
第 7 章 鏡像下降法與乘性權重更新法　 92
7.1 Lipschitz 梯度條件之外 92
7.2 局部最佳化原理與正規化項 93
7.3 指數梯度下降法 96
7.3.1 指數梯度下降法的主要定理　 99
7.3.2 Bregman 散度的性質 99
7.3.3 指數梯度下降法的收斂性證明 101
7.4 鏡像下降法　 103
7.4.1 指數梯度下降法的推廣與近端視角 103
7.4.2 鏡像下降法的演算法表述 104
7.4.3 收斂性證明　 105
7.5 乘性權重更新法 107
7.6 應用：二部圖的完美匹配　108
7.6.1 主要結果　 109
7.6.2 演算法 110
7.6.3 分析 110
習題　 113
註記　 122
第 8 章 加速梯度下降法 123
8.1 預備 123
8.2 加速梯度下降法的主要結果　 124
8.3 證明策略：估計序列 124
8.4 估計序列的建構 126
8.4.1 步驟 1：迭代的構造 126
8.4.2 步驟 2：確保下界條件 128
8.4.3 步驟 3：確保上界與 yt 的動態更新　 129
8.4.4 步驟 4：確保條件（2）和xt 的動態更新 131
8.5 演算法及其分析　 131
8.6 強凸光滑函數的一種演算法　 133
8.7 應用：線性方程組 134
習題　 136
註記　 138
第 9 章 牛頓法139
9.1 求一元函數的根 139
9.1.1 迭代規則的推導 139
9.1.2 二次收斂　 141
9.2 多元函數的牛頓法 142
9.3 無約束優化的牛頓法 143
9.3.1 從最佳化到求根　 143
9.3.2 作為二階方法的牛頓法 144
9.4 分析初探　 145
9.4.1 歐氏範數意義下的收斂問題 146
9.4.2 牛頓法的仿射不變性 148
9.5 視為最速下降的牛頓法 148
9.5.1 局部範數意義下的最速下降法 150
9.5.2 局部範數是黎曼度量 152
9.6 基於局部範數的分析 152
9.6.1 一個新的位能函數 153
9.6.2 局部範數的界　 154
9.6.3 局部範數收斂性的證明 155
9.7 以歐氏範數為基礎的分析 158
習題　 159
註記　 161
第 10 章 線性規劃的內點法　 162
10.1 線性規劃 162
10.2 利用障礙函數求解約束優化問題 163
10.3 對數障礙函數 164
10.4 中心路徑 165
10.5 線性規劃的路徑追蹤演算法 166
10.6 路徑追蹤演算法的分析　 169
10.6.1 終止條件 172
10.6.2 初始化 176
10.6.3 定理 10.10的證明 182
習題　 183
註　 188
第 11 章 內點法的變體與自和諧性　 189
11.1 最小成本流問題　 189
11.1.1 是否為基於線性規劃的快速演算法 190
11.1.2 路徑追蹤內點法的問題 190
11.1.3 剔除全維度的線性規劃 191
11.2 一種求解線性規劃標準型的內點法 192
11.2.1 有等式限制的牛頓法　 193
11.2.2 在子空間上定義黑塞矩陣與梯度 194
11.2.3 在