凸優(yōu)化算法

目 錄
譯者序
前言
致謝
記號
第 1 章 連續(xù)優(yōu)化與離散優(yōu)化的關聯(lián)　 1
1.1 一個例子：最大流問題 1
1.2 線性規(guī)劃6
1.3 基于內點法的快速精確算法　 9
1.4 簡單線性規(guī)劃之外的橢球法 10
第 2 章 預備知識 13
2.1 導數(shù)、梯度和黑塞矩陣　 13
2.2 微積分基本定理 14
2.3 泰勒近似 15
2.4 線性代數(shù)、矩陣和特征值 16
2.5 柯西–施瓦茨不等式 18
2.6 范數(shù)　 19
2.7 歐幾里得拓撲 20
2.8 動力系統(tǒng) 21
2.9 圖　 21
2.9.1 圖上的結構 22
2.9.2 圖的關聯(lián)矩陣 23
2.9.3 與圖相關聯(lián)的多胞形　 24
習題 24
注記 28
第 3 章 凸性　 29
3.1 凸集　 29
3.2 凸函數(shù)　 30
3.3 凸性的作用 35
3.3.1 凸集的分離超平面和支撐超
平面　 35
3.3.2 次梯度的存在性37
3.3.3 凸函數(shù)的局部最優(yōu)值是全局
最優(yōu)值　 38
習題 39
注記 41
第 4 章 凸優(yōu)化與高效性 42
4.1 凸規(guī)劃　 42
4.2 計算模型 44
4.3 凸集的從屬問題 45
4.4 優(yōu)化問題的求解 50
4.5 凸優(yōu)化的多項式時間概念 53
習題 55
注記 57
第 5 章 對偶性與最優(yōu)性 58
5.1 Lagrange 對偶　 58
5.2 共軛函數(shù) 63
X
5.3 KKT 最優(yōu)條件 65
5.4 Slater 條件下的強對偶性證明　 66
習題 67
注記 70
第 6 章 梯度下降法 71
6.1 預備　 71
6.2 梯度下降法概論 71
6.2.1 為什么要沿梯度下降　 72
6.2.2 關于函數(shù)、梯度和初始點的
假設　 73
6.3 梯度 Lipschitz 連續(xù)時的分析　 75
6.3.1 下界　 79
6.3.2 約束優(yōu)化的投影梯度下
降法　 80
6.4 應用：最大流問題　 81
6.4.1 s-t 最大流問題　 81
6.4.2 主要結果 82
6.4.3 建模成無約束凸規(guī)劃　 82
6.4.4 梯度下降法中的步驟　 84
6.4.5 運行時間分析 85
6.4.6 處理近似解 86
習題 86
注記 90
第 7 章 鏡像下降法和乘性權重更
新法　 92
7.1 Lipschitz 梯度條件之外 92
7.2 局部優(yōu)化原理與正則化項 93
7.3 指數(shù)梯度下降法 96
7.3.1 指數(shù)梯度下降法的主要
定理　 99
7.3.2 Bregman 散度的性質 99
7.3.3 指數(shù)梯度下降法的收斂性
證明 101
7.4 鏡像下降法　 103
7.4.1 指數(shù)梯度下降法的推廣和近
端視角 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 的
動態(tài)更新　 129
8.4.4 步驟 4：確保條件（2）和
xt 的動態(tài)更新 131
8.5 算法及其分析　 131
8.6 強凸光滑函數(shù)的一種算法　 133
8.7 應用：線性方程組 134
習題　 136
注記　 138
XI
第 9 章 牛頓法139
9.1 求一元函數(shù)的根 139
9.1.1 迭代規(guī)則的推導 139
9.1.2 二次收斂　 141
9.2 多元函數(shù)的牛頓法 142
9.3 無約束優(yōu)化的牛頓法 143
9.3.1 從優(yōu)化到求根　 143
9.3.2 作為二階方法的牛頓法 144
9.4 分析初探　 145
9.4.1 歐氏范數(shù)意義下的收斂
問題 146
9.4.2 牛頓法的仿射不變性 148
9.5 視為最速下降的牛頓法 148
9.5.1 局部范數(shù)意義下的最速下
降法 150
9.5.2 局部范數(shù)是黎曼度量 152
9.6 基于局部范數(shù)的分析 152
9.6.1 一個新的勢函數(shù) 153
9.6.2 局部范數(shù)的界　 154
9.6.3 局部范數(shù)收斂性的證明 155
9.7 基于歐氏范數(shù)的分析 158
習題　 159
注記　 161
第 10 章 線性規(guī)劃的內點法　 162
10.1 線性規(guī)劃 162
10.2 利用障礙函數(shù)求解約束優(yōu)化
問題 163
10.3 對數(shù)障礙函數(shù) 164
10.4 中心路徑 165
10.5 線性規(guī)劃的路徑跟蹤算法 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 是否為基于線性規(guī)劃的快
速算法 190
11.1.2 路徑跟蹤內點法的問題 190
11.1.3 剔除全維性的線性規(guī)劃 191
11.2 一種求解線性規(guī)劃標準型的內
點法 192
11.2.1 有等式約束的牛頓法　 193
11.2.2 在子空間上定義黑塞矩陣
和梯度 194
11.2.3 在