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

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