凸優(yōu)化的理論和方法

目錄
前言
第1章 凸集 1
1.1 仿射集合和凸集 1
1.1.1 仿射維數(shù)與相對內部 2
1.1.2 凸集 3
1.1.3 錐 3
1.2 一些重要的例子 3
1.2.1 超平面與半空間 3
1.2.2 Euclid球和橢球 4
1.2.3 范數(shù)球和范數(shù)錐 5
1.2.4 多面體 6
1.2.5 半正定錐 7
1.3 保凸運算 8
1.3.1 交集 8
1.3.2 仿射函數(shù) 10
1.3.3 線性分式及透視函數(shù) 11
1.4 分離與支撐超平面 13
1.4.1 超平面分離定理 13
1.4.2 支撐超平面 15
1.5 對偶錐 16
習題1 18
第2章 凸函數(shù) 23
2.1 基本性質和例子 23
2.1.1 定義及擴展值延伸 23
2.1.2 凸函數(shù)的判定 24
2.1.3 一些例子 26
2.1.4 下水平集和上境圖 29
2.1.5 Jensen不等式及其擴展 31
2.2 保凸運算 32
2.2.1 非負加權求和 32
2.2.2 復合仿射映射 33
2.2.3 逐點最大和逐點上確界 33
2.2.4 最小化形式的凸性 35
2.2.5 透視函數(shù) 36
2.3 共軛函數(shù) 37
習題2 40
第3章 凸優(yōu)化問題 45
3.1 凸優(yōu)化問題 45
3.1.1 基本術語 45
3.1.2 問題的標準表示 46
3.1.3 等價問題 47
3.2 凸優(yōu)化 51
3.2.1 標準形式的凸優(yōu)化問題 51
3.2.2 局部最優(yōu)解與全局最優(yōu)解 52
3.2.3 最優(yōu)性準則 52
3.3 線性規(guī)劃問題 55
3.4 二次優(yōu)化問題 59
3.4.1 幾個例子 60
3.4.2 二階錐規(guī)劃 62
習題3 65
第4章 對偶 74
4.1 Lagrange對偶函數(shù) 74
4.1.1 Lagrange函數(shù) 74
4.1.2 Lagrange對偶函數(shù)及性質 74
4.1.3 一些例子 75
4.1.4 Lagrange對偶函數(shù)和共軛函數(shù) 78
4.2 Lagrange對偶問題 80
4.2.1 顯式表達對偶約束 80
4.2.2 弱對偶性 82
4.2.3 強對偶性和Slater約束準則 82
4.2.4 幾個例子 83
4.3 強對偶性的證明 88
4.4 鞍點解釋 89
4.4.1 強弱對偶性的極大極小描述 89
4.4.2 鞍點解釋 90
4.5 最優(yōu)性條件 91
4.5.1 次優(yōu)解認證和終止準則 91
4.5.2 互補松弛性 92
4.5.3 KKT最優(yōu)性條件 93
4.5.4 通過解對偶問題求解原問題 96
4.6 擾動及靈敏度分析 97
4.6.1 擾動的問題 98
4.6.2 一個全局不等式 98
4.6.3 局部靈敏度分析 99
4.7 例子 101
習題4 105
第5章 無約束優(yōu)化 114
5.1 無約束優(yōu)化問題 114
5.1.1 幾個例子 114
5.1.2 強凸性及其性質 116
5.2 下降方法 118
5.3 梯度下降方法 120
5.3.1 收斂性分析 121
5.3.2 幾個例子 123
5.3.3 結論 127
5.4 二塊凸優(yōu)化模型的梯度型算法 127
5.4.1 問題模型 127
5.4.2 臨近梯度方法 129
5.4.3 算法和收斂性 131
5.4.4 快速臨近梯度方法 137
5.5 Newton方法 141
5.5.1 Newton方向 141
5.5.2 阻尼Newton方法 143
5.5.3 收斂性分析 143
5.5.4 幾個例子 148
5.5.5 總結 151
5.6 Newton方法的實現(xiàn)問題 152
習題5 154
第6章 等式約束優(yōu)化 159
6.1 等式約束優(yōu)化問題 159
6.1.1 等式約束凸二次規(guī)劃 160
6.1.2 消除等式約束 161
6.1.3 用對偶方法求解等式約束問題 162
6.2 具有可行初始點的Newton方法 163
6.2.1 Newton方向 163
6.2.2 等式約束問題的Newton方法 164
6.2.3 Newton方法和消除法 165
6.2.4 收斂性分析 166
6.3 不可行初始點的Newton方法 167
6.3.1 不可行點的Newton方向 167
6.3.2 不可行初始點Newton方法 169
6.3.3 收斂性分析 171
6.3.4 數(shù)值算例 174
習題6 177
第7章 內點法 179
7.1 對數(shù)障礙函數(shù)和中心路徑 180
7.1.1 對數(shù)障礙 180
7.1.2 中心路徑 181
7.2 障礙函數(shù)方法 183
7.2.1 障礙函數(shù)方法 184
7.2.2 收斂性分析 185
7.2.3 修改的KKT方程的Newton方向 186
7.3 可行性和階段 1方法 187
7.3.1 基本的階段 1方法 187
7.3.2 用不可行初始點Newton方法求解階段1問題 188
7.4 原對偶內點法 189
7.4.1 原對偶搜索方向 189
7.4.2 代理對偶間隙 192
7.4.3 原對偶內點法 192
7.5 算法的實現(xiàn) 193
7.5.1 標準形式線性規(guī)劃 194
7.5.2 l1-范數(shù)逼近 194
習題7 196
第8章 線性半定規(guī)劃 200
8.1 預備知識 200
8.1.1 矩陣空間的一些記號和運算 200
8.1.2 凸集與半定錐 201
8.1.3 矩陣積 204
8.2 線性半定規(guī)劃的一些性質 205
8.2.1 模型與基本概念 206
8.2.2 對偶性 207
8.2.3 可行性 211
8.2.4 最優(yōu)性條件 218
8.2.5 解的唯一性 220
8.3 一個算法 226
習題8 227
第9章 交替方向乘子法 232
9.1 ADMM算法簡介 232
9.2 具可分結構的一些凸優(yōu)化模型 233
9.3 最優(yōu)性條件和停止準則 236
9.4 收斂性分析 237
9.5 目標函數(shù)是多塊情形的ADMM 240
習題9 247
參考文獻 250