《凸优化的分裂收缩算法》以简明统一的方式介绍了用于求解线性约束凸优化问题的分裂收缩算法。我们以变分不等式（VI）和邻近点算法（PPA）为基本工具，构建了求解线性约束凸优化问题的分裂收缩算法统一框架。在该框架中，所有迭代算法的基本步骤包括预测和校正，分裂是指通过求解（往往有闭式解的）的凸优化子问题来实现迭代的预测;收缩指通过校正生成的新迭代点在某种矩阵范数意义下更加接近解集。统一框架既涵盖了**意义下的PPA算法、用于求解线性约束凸优化问题的增广拉格朗日乘子法（ALM）和处理两个可分离块凸优化问题的乘子交替方向法（ADMM）等耳熟能详的算法，还为多块可分离凸优化问题的求解提供了多种方法。通过掌握这一并不复杂的统一框架，者可以根据可分离凸优化问题的具体特点，自行设计预测-校正方法求解。

第1章预备知识
　　凸优化是目标函数为凸函数，可行点集为凸集的优化问题.在预备知识这一章，我们分别介绍凸集和凸函数的*基本的知识、凸优化和变分不等式的关系、邻近点算法的基本概念和性质以及邻近点算法及其加速方法的收敛速率.
　　1.1凸集和凸函数
　　关于凸集和凸函数的知识，大量的优秀著作中都有论述，本书只要求读者有*基本的了解，也只做*简单的介绍.建议有进一步需要的读者参阅Boyd和Vandenberghe的专著[8]中第2～3章的内容.
　　1.1.1凸集
　　定义1.1(凸集(convexset))集合C中任意两点和xi的连线都在这个集合C内，则称集合C是凸的.换句话说，如果集合C是凸的，那么
　　根据定义，况"本身和它的任何子空间都是凸集.设A是确定的mxn矩阵，那么
　　(1)对给定的，集合和都是凸集；
　　(2)n-维空间中的非负卦限
　　和“箱子”
　　都是凸集；
　　(3)若干个凸集的交是凸集
　　对，维向量;的模定义为
　　任给一个的对称正定矩阵，维向量;的好-模定义为
　　(1)以原点为中心，半径为的模意义下的球
　　是闭凸集.
　　(2)同样，以原点为中心，半径为的意义下的球是闭凸集.
　　科学计算中，常常遇到一类问题的变量是矩阵对称矩阵的集合
　　和对称半正定矩阵的集合
　　都是闭凸集.我们说是凸集，因为对任意给定的和维向量，都有中正定矩阵的集合
　　是开凸集.和是以对称矩阵为变量的凸优化问题中常常遇到的重要凸集.1.1.2凸函数
　　定义1.2称一个函数为凸為数(convex function)如果它的定义域是凸集并且对所有的和满足，都有
　　(1.1.1)
　　(1)不等式(1.1.1)的几何意义是，连接和的线段，总是位于f的像的上面(图1.1).
　　(2)如果对于不同的和，严格不等式(1.1.1)成立，则说/是严格凸函数.
　　(3)如果是凸函数，则说/是凹(concave)函数.如果-/是严格凸函数，则说/是严格凹函数.
　　(4)对于形如这样的仿射(affine)函数，(1.1.1)总是等式成立.因此，仿射函数既是凸的，又是凹的.反之，既凸又凹的函数是仿射函数.
　　(5)凸函数在它的定义域的相对内点是连续的，只能在定义域的相对边界点不连续.
　　引理1.1设函数/是定义域上的凸函数，则对于任意的，和都有上面的不等式称为Jensen不等式，根据凸函数的定义，用数学归纳法容易证明.Jensen不等式也可以写成下面等价的形式.
　　引理1.2设函数/是定义域上的凸函数，则对于任意的，和都有
　　1.一次可微凸函数的性质
　　引理1.3设/在一个包含的开集中可微(f的梯度在这个开集的每一点存在).那么，的充分必要条件是为凸集并且
　　(1.1.2)
　　如图1.2所示.
　　证明设，我们记如果是凸的，那么根据定义就有因此
　　对所有的，都有
　　令，我们得到
　　反过来，因为和
　　我们就有
　　根据定义，是凸函数.
　　引理1.3给出了可微凸函数一条*基本的性质.据此，我们有

目录
《计算与应用数学丛书》序
前言
第1章 预备知识 1
1.1 凸集和凸函数 1
1.1.1 凸集 1
1.1.2 凸函数 2
1.2 凸优化和变分不等式 7
1.2.1 变分不等式和盲人爬山原理 7
1.2.2 线性约束可微凸优化问题的*优性条件 13
1.2.3 线性约束凸优化问题和等价的单调变分不等式 15
1.3 凸优化和单调变分不等式的邻近点算法 18
1.4 凸优化的邻近点算法及其加速方法的收敛速率 24
1.4.1 求解凸优化问题PPA算法的收敛速率 24
1.4.2 预测-校正的具有加速性质的PPA算法 27
第2章 投影收缩算法和投影梯度法 33
2.1 投影的定义和基本性质 33
2.2 凸二次优化投影收缩算法带来的启示 38
2.2.1 求解凸二次优化问题的投影收缩算法 38
2.2.2 凸二次优化投影收缩算法的数值表现 40
2.3 自适应投影梯度收缩算法 45
2.4 自适应投影梯度下降算法 50
2.5 具有加速性质的投影梯度下降算法 56
第3章 鞍点问题的原始-对偶算法 62
3.1 鞍点问题对应的变分不等式 62
3.2 不能保证收敛的原始-对偶混合梯度法 63
3.3 求解鞍点问题的邻近点算法 67
3.4 鞍点问题PPA算法的一些应用 70
3.5 子问题目标函数含非平凡二次项的PPA算法 74
第4章 乘子交替方向法 79
4.1 从增广Lagrange乘子法到ADMM 79
4.2 ADMM的收敛性分析 84
4.3 线性化的ADMM90
4.4 ADMM及线性化ADMM的收敛性证明 95
4.4.1 ADMM及线性化ADMM的全局收敛性 95
4.4.2 ADMM点列意义下的收敛速率 96
4.4.3 ADMM遍历意义下的收敛速率 99
4.5 Glowinski交替方向法中更新乘子的步长法则 102
第5章 凸优化分裂收缩算法的预测-校正统一框架 105
5.1 分裂收缩算法的预测-校正统一框架 105
5.1.1 统一框架中的预测 105
5.1.2 统一框架中的校正 106
5.2 按照统一框架修正的一些算法 108
5.2.1 平凡松弛校正的算法 108
5.2.2 必要非平凡校正的算法 110
5.3 统一框架中的算法收敛性质 113
5.3.1 采用固定步长校正的算法收敛性 113
5.3.2 采用计算步长校正的算法收敛性 115
5.4 统一框架下算法的迭代复杂性 117
5.4.1 遍历意义下的迭代复杂性 117
5.4.2 点列意义下的迭代复杂性 120
5.5 合格预测确定后选取校正矩阵的通用法则 122
第6章 统一框架与**单调变分不等式的投影收缩算法 128
6.1 单调变分不等式及与其等价的投影方程 128
6.1.1 保护资源-保障供给中的互补问题 129
6.1.2 交通疏导中的互补问题 131
6.1.3 与变分不等式等价的投影方程 132
6.2 PPA算法和投影收缩算法的三个基本不等式 133
6.3 投影收缩算法和分裂收缩算法中的预测 135
6.3.1 求解**变分不等式的投影收缩算法中的预测 135
6.3.2 求解混合变分不等式的分裂收缩算法中的预测 137
6.4 投影收缩算法和分裂收缩算法的校正 137
6.4.1 两类方法中采用固定步长的校正 138
6.4.2 两类算法中计算步长的校正 139
6.5 投影收缩算法中的孪生方向和姊妹方法 142
6.6 单调变分不等式投影收缩算法遍历意义下的收敛速率 146
6.7 投影收缩算法在求解可分离凸优化上的应用 151
第7章 统一框架与单调线性变分不等式的投影收缩算法 160
7.1 单调线性变分不等式及相应的优化问题 160
7.2 线性变分不等式的投影收缩算法和算法统一框架 166
7.3 求解线性变分不等式的孪生方向和姊妹方法 171
7.4 线性变分不等式投影收缩算法的收敛速率 175
7.5 孪生方向姊妹方法在*短距离和问题中的计算表现 180
第8章 统一框架下求解鞍点问题的收缩算法 185
8.1 修正Chambolle-Pock算法的预测-校正方法 186
8.2 基于C-P方法的自适应预测-校正方法 193
8.3 采用平行预测的预测-校正方法 200
8.4 子问题目标函数中含非平凡二次项的PPA算法 203
8.5 求解鞍点问题的投影收缩算法 206
第9章 统一框架下求解单块凸优化问题的收缩算法 210
9.1 从增广Lagrange乘子法到PPA算法 210
9.2 非平凡校正的ALM类算法 212
9.3 平凡松弛校正的PPA算法 217
9.4 均困平衡的增广Lagrange乘子法 220
9.5 非平凡校正的均困ALM 223
9.6 平凡松弛校正的均困PPA算法 226
9.7 平行处理预测子问题的均困方法 229
第10章 统一框架下两可分离块凸优化问题的ADMM类方法 232
10.1 **ADMM在统一框架中的演译 233
10.2 交换顺序的ADMM 239
10.3 对称的ADMM 242
10.4 利用统一框架设计的PPA算法 247
10.5 线性化ADMM和自适应线性化ADMM 249
10.5.1 线性化ADMM在统一框架下的演译 249
10.5.2 自适应的线性化ADMM 251
10.6 统一框架下计算步长的线性化ADMM 255
10.7 利用统一框架设计的均困PPA算法 260
第11章 三个可分离块凸优化问题的修正ADMM类方法 264
11.1 直接推广的ADMM对三个可分离块问题不保证收敛 264
11.2 部分平行分裂的ADMM预测-校正方法 269
11.3 带Gauss回代的ADMM类方法 275
11.4 线性化的带Gauss回代的ADMM类方法 283
11.5 部分平行并加正则项的ADMM类方法 288
11.6 利用统一框架设计的PPA算法 291
第12章 线性化ALM和ADMM中的不定正则化准则 294
12.1 不定正则化方法的意义和两个引理 294
12.2 等式约束优化问题的不定正则化 ALM 298
12.2.1 不定正则化方法 ALM 的变分不等式表示 298
12.2.2 不定正则化方法 ALM 的收敛性证明 300
12.3 不等式约束问题的不定正则化 ALM 303
12.3.1 不定正则化方法 ALM 的预测-校正格式 305
12.3.2 不定正则化 ALM 的收敛性证明 308
12.4 不定正则的*优线性化ADMM 313
12.4.1 不定正则化方法ADMM的预测-校正格式 315
12.4.2 不定正则化ADMM的收敛性证明 318
12.5 不定正则化ADMM类方法求解三个可分离块问题 322
第13章 多个可分离块凸优化问题的ADMM类方法 327
13.1 带Gauss回代的ADMM类方法 329
13.2 线性化的带Gauss回代的ADMM类方法 337
13.3 子问题平行正则化的ADMM类方法 341
13.4 利用统一框架设计的PPA算法 347
第14章 平行预测的求解多块问题的方法 350
14.1 平行预测不加正则项的方法 351
14.1.1 方法转换成统一框架下的模式 352
14.1.2 基于同一预测的其他校正方法 356
14.2 平行预测加正则项的方法 358
14.2.1 采用统一框架中计算步长的校正方法 359
14.2.2 采用统一框架中单位步长的校正方法 361
14.3 Jacobi预测的PPA算法 365
14.4 均困平衡的PPA算法 368
第15章 求解多块可分离问题的广义秩一预测-校正方法 373
15.1 变分不等式变量代换下的预测-校正框架 374
15.2 多块可分离问题的串行预测 378
15.3 基于Primal-Dual预测构造校正矩阵 385
15.4 基于Dual-Primal预测构造校正矩阵 388
15.5 统一框架中的串行预测和广义秩一校正 391
第16章 求解多块可分离问题的广义秩二预测-校正方法 394
16.1 用统一框架指导设计方法 394
16.2 根据统一框架设计串型预测 395
16.2.1 Primal-Dual预测后再校正的方法 395
16.2.2 Dual-Primal预测后再校正的方法 400
16.3 根据统一框架设计平行预测的方法 404
第17章 预测-校正的广义PPA算法 410
17.1 变分不等式**算法的两个主要性质 410
17.2 预测-校正的广义PPA算法.412
17.3 变量替换下的广义PPA算法 414
17.4 基于秩一预测的广义PPA算法 416
17.4.1 Primal-Dual预测的广义PPA算法 417
17.4.2 Dual-Primal预测的广义PPA算法 419
17.5 基于秩二预测的广义PPA算法 421
17.5.1 Primal-Dual预测的广义PPA算法 422
17.5.2 Dual-Primal预测的广义PPA算法 425
17.6 平行秩二预测的广义PPA算法 427
后记 429
参考文献 434
《计算与应用数学丛书》已出版书目 442