本书系统阐述凸分析基础理论与梯度型优化算法。全书由紧密关联的两部分构成：第一部分（第1—6章）从一维凸函数引入，系统讲解凸集与投影、凸函数与次微分、共轭与临近、光滑与强凸、最优化条件与对偶以及稀疏优化条件等内容，为后续算法分析奠定严格的理论基础，每章末附有习题以供练习；第二部分（第7—13章）介绍梯度型算法，既涵盖梯度下降法、临近梯度法、次梯度方法和条件梯度法等经典方法，也囊括自适应梯度法、Polyak重球法与Nesterov加速算法、对偶梯度法，以及用于变分不等式问题的广义梯度外插算法等前沿内容，并统一采用势能函数法和误差界条件进行收敛性分析。
样章试读
目录
- 目录
“运筹与管理科学丛书”序
前言
第1章 预备知识 1
1.1 欧氏空间 1
1.2 集合与序列 7
1.3 函数及其近似 10
1.4 矩阵相关概念 15
1.5 最优化问题 17
1.6 一维凸函数 19
第1章习题 26
第2章 凸集与投影 31
2.1 凸集 31
2.1.1 凸集定义与例子 31
2.1.2 保凸运算 33
2.1.3 凸组合与凸包 38
2.2 投影 41
2.2.1 闭凸集投影算子 42
2.2.2 分离定理 46
2.2.3 投影计算的例子 48
2.2.4 随机Kaczmarz算法 50
2.3 锥 54
2.3.1 锥的概念与性质 54
2.3.2 Farkas引理与备择定理 57
2.3.3 线性规划的对偶定理 59
第2章习题 60
第3章 凸函数与次微分 63
3.1 凸函数 63
3.1.1 凸函数的几何定义与等价刻画 63
3.1.2 保凸运算 69
3.1.3 凸函数的基本性质 73
3.2 次微分理论 76
3.2.1 方向导数的性质 76
3.2.2 次微分与次梯度 77
3.2.3 最速下降方向 83
3.2.4 次微分法则 87
第3章习题 92
第4章 共轭与临近 95
4.1 共轭函数 95
4.1.1 定义与性质 95
4.1.2 卷积与共轭 101
4.2 临近点算子与Moreau函数 105
4.2.1 临近点算子 105
4.2.2 Moreau函数 111
第4章习题 115
第5章 光滑与强凸 117
5.1 定义与等价刻画 118
5.1.1 定义与引理 118
5.1.2 光滑性的等价刻画 120
5.1.3 强凸性的等价刻画 123
5.1.4 光滑强凸性的等价刻画 125
5.1.5 光滑与强凸之间的对偶 126
5.1.6 相对光滑与强凸条件 127
5.2 误差界条件 128
5.2.1 强凸松弛条件 129
5.2.2 强凸线性复合函数 135
第5章习题 138
第6章 最优化条件与对偶 140
6.1 最优化条件 140
6.1.1 无约束优化情形 140
6.1.2 约束优化情形 144
6.1.3 KKT条件 148
6.2 凸规划的对偶 154
6.2.1 备择定理 155
6.2.2 Lagrange对偶 156
6.3 稀疏优化条件 158
6.3.1 定理证明 162
6.3.2 判别准则 166
第6章习题 168
第7章 梯度下降法 169
7.1 梯度法的描述 169
7.1.1 迭代格式与下降引理 169
7.1.2 步长选取策略 171
7.2 收敛理论 173
7.2.1 基本收敛性质 173
7.2.2 线性收敛理论 179
7.2.3 线性收敛与误差界 187
7.3 参数无关的梯度法 192
7.3.1 局部几何自适应梯度法 192
7.3.2 自适应归一化梯度法 197
第8章 加速梯度法 200
8.1 Polyak重球法 200
8.1.1 算法描述 200
8.1.2 收敛性结果 202
8.2 Nesterov加速 206
8.2.1 经典的Nesterov加速算法格式 206
8.2.2 基于势能函数的加速 210
8.3 加速算法的线性收敛 214
8.4 重启加速方法 217
第9章 临近梯度法 220
9.1 算法格式与梯度映射 220
9.2 梯度映射的基本性质 222
9.3 收敛理论 230
9.4 加速的临近梯度法 233
9.5 基于线搜索的临近梯度法 238
9.6 线性收敛 244
9.6.1 临近梯度法线性收敛 244
9.6.2 加速临近梯度法线性收敛 248
第10章 次梯度方法 253
10.1 步长选取与Lipschitz连续性 255
10.2 收敛性与收敛率 257
10.3 求解凸可行性问题 266
10.4 推广的格式 269
第11章 条件梯度法 274
11.1 收敛性分析 275
11.2 改进的收敛率 277
11.3 CCCP的条件梯度法解释 284
第12章 对偶梯度法 286
12.1 符号与预备知识 287
12.2 对偶梯度型随机算法 290
12.2.1 随机对偶坐标算法 290
12.2.2 统一的算法框架 291
12.3 收敛性分析 292
12.3.1 广义下降引理 292
12.3.2 线性收敛性 298
12.4 典型算法设计示例 302
12.4.1 最佳逼近问题 302
12.4.2 稀疏优化问题 304
第13章 变分不等式问题的广义梯度法 308
13.1 Bregman距离 308
13.2 相对Lipschitz连续与单调型条件 310
13.3 广义梯度算法框架 312
13.3.1 两大支柱 312
13.3.2 两个广义梯度外插算法框架 315
13.3.3 经典算法作为特例 316
13.3.4 求解鞍点优化问题 320
13.4 收敛性分析 322
13.4.1 镜像EG方法的收敛分析 322
13.4.2 镜像EP方法的收敛分析 326
评注与文献索引 332
参考文献 336
“运筹与管理科学丛书”已出版书目 341
京公网安备 11010102004214号