凸優(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)化問(wèn)題 45
3.1 凸優(yōu)化問(wèn)題 45
3.1.1 基本術(shù)語(yǔ) 45
3.1.2 問(wèn)題的標(biāo)準(zhǔn)表示 46
3.1.3 等價(jià)問(wèn)題 47
3.2 凸優(yōu)化 51
3.2.1 標(biāo)準(zhǔn)形式的凸優(yōu)化問(wèn)題 51
3.2.2 局部最優(yōu)解與全局最優(yōu)解 52
3.2.3 最優(yōu)性準(zhǔn)則 52
3.3 線性規(guī)劃問(wèn)題 55
3.4 二次優(yōu)化問(wèn)題 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ì)偶問(wèn)題 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 通過(guò)解對(duì)偶問(wèn)題求解原問(wèn)題 96
4.6 擾動(dòng)及靈敏度分析 97
4.6.1 擾動(dòng)的問(wèn)題 98
4.6.2 一個(gè)全局不等式 98
4.6.3 局部靈敏度分析 99
4.7 例子 101
習(xí)題4 105
第5章 無(wú)約束優(yōu)化 114
5.1 無(wú)約束優(yōu)化問(wèn)題 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 問(wèn)題模型 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)問(wèn)題 152
習(xí)題5 154
第6章 等式約束優(yōu)化 159
6.1 等式約束優(yōu)化問(wèn)題 159
6.1.1 等式約束凸二次規(guī)劃 160
6.1.2 消除等式約束 161
6.1.3 用對(duì)偶方法求解等式約束問(wèn)題 162
6.2 具有可行初始點(diǎn)的Newton方法 163
6.2.1 Newton方向 163
6.2.2 等式約束問(wèn)題的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問(wèn)題 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