摘要：最优化理论与方法是最接地气的应用数学。应用数学领域提出了大量优化问题，其中不少都可以归结为(或者松弛成) 一些典型的凸优化问题。我们围绕下面一些具有代表性的凸优化问题，研究凸优化的一阶算法。
最优化理论与方法是最接地气的应用数学。应用数学领域提出了大量优化问题，其中不少都可以归结为(或者松弛成) 一些典型的凸优化问题。我们围绕下面一些具有代表性的凸优化问题，研究凸优化的一阶算法。
(1) 简单约束的可微凸优化问题
(2) 鞍点问题
(3) 单块的线性约束凸优化问题
(4) 两个可分离块的线性约束凸优化问题
(5) 三个可分离块的线性约束凸优化问题
(6) 多个可分离块的线性约束凸优化问题
简单约束的可微凸优化问题的一阶最优性条件可以表示成一个单调变分不等式(variational inequality)。变分不等式其实就是盲人爬山判别是否已经到达顶点的数学表达式。约束凸优化问题的Lagrange函数的鞍点等同于相应的变分不等式的解点。读者将会看到，用变分不等式的观点处理凸优化问题，就像微积分中用导数求可微函数的极值点，常常会带来很大的方便。
邻近点算法(PPA 算法) 和增广Lagrange 乘子法(ALM) 是最优化中的一些经典算法。ALM 本身就是乘子的PPA 算法，这些算法生成的序列都具有向解集越靠越近的收缩性质，因此我们称其为收缩算法。变分不等式和邻近点算法这些概念，是我们研究凸优化分裂收缩算法的两大法宝。
应用领域中遇到的不少凸优化问题，具有可分离的结构，直接应用PPA算法或者ALM，有时会无从下手。乘子交替方向法(ADMM)，是利用可分离结构的松弛的ALM，在科学工程计算中发挥着越来越重要的作用。
《凸优化的分裂收缩算法》以简明统一的方式介绍了用于求解线性约束凸优化问题的分裂收缩算法，其介绍的方法都利用这些可分离性质，因此我们也把它们说成是ADMM类分裂收缩算法。
☟上下滑动查看更多
Slide for more photos
《凸优化的分裂收缩算法》
何炳生著
ISBN 978-7-03-080804-2
北京 : 科学出版社，2025. 4
本书以变分不等式(VI)和邻近点算法(PPA)为基本工具，构建了求解线性约束凸优化问题的分裂收缩算法统一框架。在该框架中，所有迭代算法的基本步骤包括预测和校正，分裂是指通过求解(往往有闭式解的)的凸优化子问题来实现迭代的预测；收缩指通过校正生成的新迭代点在某种矩阵范数意义下更加接近解集。统一框架既涵盖了经典意义下的PPA 算法、用于求解线性约束凸优化问题的增广拉格朗日乘子法(ALM)和处理两个可分离块凸优化问题的乘子交替方向法(ADMM)等耳熟能详的算法，还为多块可分离凸优化问题的求解提供了多种方法。通过掌握这一并不复杂的统一框架，读者可以根据可分离凸优化问题的具体特点，自行设计预测-校正方法求解。本书的核心内容可作为数学高年级学生的选修课教材，也可作为理工科相关专业研究生的教学参考书。本书的内容对从事优化计算的科技工作者也将有所裨益。
书的结构是这样编排的：基础知识部分简要介绍凸集和凸函数、凸优化和变分不等式的关系以及变分不等式的邻近点算法等基本概念。然后把算法介绍分为六个部分。
第一部分包括第2 ∼4 章。第2 章讲述求解问题(1)的投影梯度法，包括到解集越来越近的收缩算法和(目标函数值逐点变小的)下降算法；第3 章讲述求解鞍点问题(2)和单块线性约束凸优化问题(3)变分不等式意义下的PPA算法，这类PPA算法中的子问题目标函数中的二次项都是平凡的，因而求解相对容易；第4 章讲述求解结构性优化问题(4)的乘子交替方向法(ADMM)和线性化ADMM，在变分不等式框架下统一证明了收敛性和收敛速率。
第二部分包括第5 ∼7 章，都与算法统一框架有关。第5 章介绍求解(由约束凸优化导出的)变分不等式的预测-校正统一框架。第3 ∼4 章讨论过的算法都可以纳入这个框架，在框架的指导下，还可以据此在同一预测下并不费劲地构造一簇算法。第6 章和第7章分别阐述凸优化分裂收缩算法统一框架与经典单调变分不等式和线性单调变分不等式投影收缩算法之间的关系，同时介绍变分不等式投影收缩算法中的孪生方向和姊妹方法。
第三部分包括第8 ∼10 章，介绍用算法统一框架诠释和设计求解方法。第8 章讲述如何在统一框架指导下设计求解鞍点问题(2)的预测-校正方法；第9 章讲述求解问题(3)的ALM类算法，包括PPA算法指导下均(分)困(难)的ALM类算法；第10 章讲述在统一框架指导下设计的求解两个可分离块问题(4)的ADMM类方法，提供了花费相同、效率更高一些的ADMM类算法。
第四部分包括第11 ∼12 两章。由于把求解两个可分离块问题的ADMM直接推广用来求解三个可分离块问题(5)是不能保证收敛的，第11 章介绍一些修正的ADMM类方法，用统一框架来论证和设计求解三个可分离块问题的ADMM类方法。第12 章对线性化ALM，线性化ADMM，以及部分平行加正则化的方法求解三个可分离块问题，提出了相应的不定正则化方法，缩减这个看似无法缩小的正则化因子，相应地提高算法效率。
第五部分包括第13 ∼14 两章，讲述根据统一框架设计求解多块可分离问题变分不等式的一些分裂收缩算法。这些方法的预测分别采用Jacobi或者Gauss方式，校正则用广义秩二校正或者Gauss回代。第六部分包括第15 ∼17 章，讲述根据统一框架设计求解多块可分离问题的一些分裂收缩算法，把等式和不等式约束问题统一处理。这些预测-校正方法中，校正充分运用了分块矩阵技术。第15 和16 章分别介绍了广义秩一和秩二校正的方法，第17 章介绍广义PPA算法，方法所产生的迭代序列都有PPA算法所具有的优美性质。
设计工程师们看得懂、用得上的优化方法，是我们的奋斗目标。本书无论是陈述方法还是收敛性证明，都尽量避免工程师们不熟悉的概念和语言，只用最普通的大学数学和一般的优化原理。这些在凸优化求解领域自成体系的研究工作，追求的是简单与统一的原则。简单，他人才会拿来使用；统一，自己才有美的享受。我们坚信，有用的方法，一定是简单而且触类旁通的！
科学技术的发展对最优化理论与方法不断提出新的挑战，新成果和新方法也不断涌现。好在最优化理论与方法的先驱R.Fletcher在他的著作Practical Methods of Optimization 中说过:
“
Indeed，there is no general agreement on the best approach and much research is still to be done.
(事实上，对什么方法最好没有普遍的共识，许多研究仍有待继续。)
”
这句话，鼓起了我们撰写这本以自己的科研成果为主的著作的勇气！
本文摘编自《凸优化的分裂收缩算法》（何炳生著.北京 : 科学出版社，2025.4 ）一书“前言”，有删减修改，标题为编者所加。
ISBN 978-7-03-080804-2
责任编辑: 胡庆家 孙翠勤
本书以简明统一的方式介绍了用于求解线性约束凸优化问题的分裂收缩算法。我们以变分不等式(VI)和邻近点算法(PPA)为基本工具，构建了求解线性约束凸优化问题的分裂收缩算法统一框架。在该框架中，所有迭代算法的基本步骤包括预测和校正，分裂是指通过求解(往往有闭式解的)的凸优化子问题来实现迭代的预测；收缩指通过校正生成的新迭代点在某种矩阵范数意义下更加接近解集。统一框架既涵盖了经典意义下的PPA 算法、用于求解线性约束凸优化问题的增广拉格朗日乘子法(ALM)和处理两个可分离块凸优化问题的乘子交替方向法(ADMM)等耳熟能详的算法，还为多块可分离凸优化问题的求解提供了多种方法。通过掌握这一并不复杂的统一框架，读者可以根据可分离凸优化问题的具体特点，自行设计预测-校正方法求解。本书的核心内容可作为数学高年级学生的选修课教材，也可作为理工科相关专业研究生的教学参考书。本书的内容对从事优化计算的科技工作者也将有所裨益。
来源：科学出版社一点号
