目　　錄
第1章 凸集合 1
1.1 仿射集、凸集和凸錐 1
1.1.1 直線與線段 1
1.1.2 仿射集 1
1.1.3 仿射維數(shù)與相對內(nèi)部 3
1.1.4 凸集合 3
1.1.5 凸錐 5
1.2 凸集合的示例 5
1.2.1 超平面和半空間 5
1.2.2 歐氏球和橢球 6
1.2.3 范數(shù)球和范數(shù)錐 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
練習(xí)題 11
參考文獻 13
第2章 凸函數(shù) 14
2.1 凸函數(shù)的定義和例子 14
2.1.1 凸函數(shù)的概念 14
2.1.2 凸函數(shù)的例子 18
2.1.3 強凸性 19
2.1.4 其他凸集合和凸不等式 20
2.2 保持凸性的運算 22
2.3 共軛函數(shù) 25
2.3.1 共軛函數(shù)的概念 25
2.3.2 共軛概念的理解 27
2.4 次梯度與次微分 27
2.4.1 次微分的概念 27
2.4.2 對偶 29
練習(xí)題 29
參考文獻 32
第3章 凸優(yōu)化模型 33
3.1 優(yōu)化模型 33
3.1.1 基本術(shù)語 33
3.1.2 等價問題 34
3.2 標(biāo)準(zhǔn)形式及最優(yōu)性條件 35
3.2.1 標(biāo)準(zhǔn)形式的凸優(yōu)化問題 35
3.2.2 局部最優(yōu)解與全局最優(yōu)解 36
3.2.3 最優(yōu)性條件 36
3.3 線性規(guī)劃 38
3.3.1 標(biāo)準(zhǔn)型線性規(guī)劃和不等式線性規(guī)劃 38
3.3.2 線性規(guī)劃轉(zhuǎn)化為標(biāo)準(zhǔn)型 39
3.3.3 線性規(guī)劃應(yīng)用舉例 39
3.4 二次規(guī)劃模型 41
3.4.1 二次規(guī)劃的例子 42
3.4.2 二階錐規(guī)劃 44
3.5 幾何規(guī)劃 44
3.5.1 幾何規(guī)劃的擴展 45
3.5.2 幾何規(guī)劃轉(zhuǎn)化為凸優(yōu)化問題 45
3.5.3 幾何規(guī)劃的例子 46
3.6 廣義不等式約束 47
3.6.1 錐規(guī)劃問題 47
3.6.2 半定規(guī)劃 47
3.6.3 組合優(yōu)化中的SDP 48
練習(xí)題 50
參考文獻 52
第4章 對偶理論 53
4.1 Lagrange對偶函數(shù) 53
4.1.1 Lagrange函數(shù) 53
4.1.2 Lagrange對偶函數(shù) 53
4.1.3 最優(yōu)值的下界 54
4.1.4 Lagrange對偶函數(shù)的例子 54
4.2 Lagrange對偶問題 55
4.2.1 對偶約束 55
4.2.2 弱對偶性 57
4.2.3 強對偶性與Slater約束規(guī)范 57
4.3 Lagrange對偶的理解 58
4.3.1 鞍點 58
4.3.2 博弈論解讀 58
4.4 最優(yōu)性條件 59
4.4.1 非凸問題的KKT條件 60
4.4.2 凸問題的KKT條件 60
4.4.3 通過對偶求解優(yōu)化問題 61
練習(xí)題 62
參考文獻 64
第5章 非凸優(yōu)化算法 65
5.1 全局優(yōu)化算法的復(fù)雜度 65
5.2 優(yōu)化算法構(gòu)造思想 68
5.3 梯度下降法 69
5.4 牛頓法 78
5.4.1 牛頓法思想 79
5.4.2 梯度下降法與牛頓法的關(guān)系 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 高斯-牛頓法與牛頓法的關(guān)系 96
5.7.3 增量梯度方法 97
5.8 Lagrange乘子法 98
5.8.1 二次懲罰函數(shù)法 100
5.8.2 拉格朗日乘子估計-不精確最小化 100
5.8.3 關(guān)于條件數(shù)較大的問題 101
5.8.4 乘子方法的主要思想 102
5.9 DC規(guī)劃算法及CCCP算法 104
5.10 進化算法 107
應(yīng)用案例5.1：CCCP算法求解基于ramp損失的二分類問題 113
練習(xí)題 118
參考文獻 119
第6章 凸優(yōu)化算法 120
6.1 梯度投影法 120
6.1.1 基于投影方法的可行方向和步長規(guī)則 120
6.1.2 步長選擇和收斂性 121
6.1.3 收斂速度 122
6.2 坐標(biāo)下降法 123
6.2.1 算法 123
6.2.2 收斂性 123
6.2.3 有利于使用坐標(biāo)下降法的問題結(jié)構(gòu) 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 應(yīng)用舉例：ADMM方法求解Lasso問題 133
6.4.4 應(yīng)用舉例：ADMM算法求解Bi-convex問題 135
6.5 隨機梯度下降法 137
6.5.1 隨機優(yōu)化方法與批處理優(yōu)化方法 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 在線凸優(yōu)化 152
6.6.1 在線凸優(yōu)化的基本框架 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
練習(xí)題 162
參考文獻 163