求解一般带约束凸优化问题的一个简单的并行算法
优化领域小学生来报道，给大家介绍一个算法：a simple parallel algorithm with an O(1/T) convergence rate for general convex programs[1]，我最早知道这个算法应该是在@覃含章 那个关于ADMM算法的回答中：
交替方向乘子法（ADMM）算法的流程和原理是怎样的？ www.zhihu.com
其实这个算法步骤上和ADMM并不相似，ADMM的两个block 
和 是顺序更新的，先update 
，再用 update 
，我们称之为”Gauss-Seidel”；而如果 和 的更新完全是同时进行的，我们称之为”Jacobi”。但不要误会，ADMM作为一个知名的求解大规模优化问题的分布式算法，并行能力是很强的，它真正的并行其实是在decision variable 内部的multiple blocks上，decision variable 往往是人为构造出来处理constraint的，这也是为什么它虽然只有两个block，依然功能强大应用广泛，把ADMM extend到N-block这种idea在我看来是完全没必要的，说到底还是看你会不会用。说回到要介绍的算法，它其实和我整理过的另一个算法PCPM[2]很像：
门泊东吴：Predictor Corrector Proximal Multiplier Method zhuanlan.zhihu.com 
具体我会在下面慢慢分析。文章作者Hao Yu博士其实是有知乎号的，这工作完全不应该由我一个小学生来班门弄斧(捂脸)，我更多是给自己整理一个学习小笔记，方便以后快速refresh memory。学艺不精，一知半(不)解，欢迎大家批评指正。
1. 问题描述
考虑如下这个一般带约束的凸优化问题:
是 closed convex set， 
和 
, 
是 continuous and convex on 
。
2. 假设
Assumption 1. There exists a (possibly non-unique) optimal solution 
that solves (P0).
Assumption 2. (P0) has Lagrange multipliers 
attaining the strong duality.
Assumption 3. Function 
is Lipschitz continuous with modulus .
我私自调整了原paper里assumption的顺序，因为 Assumption 1 和 Asuumption 2 会经常捆绑起来以各种形式出现在求解convex problems的primal-dual type算法的assumption里，通常第一条就是，可以是Slater + existence of optimal solution推existence of saddle point，也可以是Slater + existence of saddle point推existence of optimal solution。比如在Mark Teboulle最近的一篇paper[3]里：
解一个标准的线性约束凸优化问题，他们是这样来写他们的assumption的：
当然，Hao Yu博士写得也很考究，还特别在 Assumption 2 后面指出了，Slater可以保证 Assumption 2 但并不必要。细微之处见真章，这些都是mathematical writing (包括assumption、lemma、proposition、theorem、corollary、proof)，可能还有analytical writing的能力，我自己因为缺乏系统的数学training以及本来写作就不行，在写paper这一方面能力特别差，这可能也是很多华人的通病，所以平时要多注重积累，(与大家共勉)。
Assumption 3 是一条我个人很不喜欢的assumption，但又确实很常见；它实际上就是在要求constraint function的增长速度不能快过线性，其实还是有点强的，哪怕Lipschitz gradient都会稍微好一点。而且，在实际求解过程中，你永远可以在decision variable上套一个很大的box constraint，比如 
，那好多functiond都是Lipschitz continuous了，但(我觉得)这样做就没意思了，还有一条我更不喜欢的assumption，就是bounded dual，就不在这里展开说了。
3. 算法描述
(因为是整理给自己看的，我的notation是按自己的习惯来的，和原paper稍有不同，但整体是自洽的。)
-
, 
-
- while termination conditions are not met do
为啥说这是个分布式算法呢？如果原问题(P0)有如下的N-block separable structure的话：
对所有 
： 
是 closed convex set， 
和 
, 是 continuous and convex on 
。
可以改写成:
算法步骤(3.1)里的(*)式是和PCPM算法中的dual predictor很像的，但因为该算法中 
的特殊更新步骤(3.2)，使得 
natually 
，所以就不需要额外再往 
上project，这一点是很妙的。看不懂没关系，我后面还会再讲。步骤(3.3)就是很标准的primal averaging，有经验的一看就知道要证 
。
文章作者管这个 
叫virtual queues，”because their update rule resembles a queueing equation”。下面来看看这个更新步骤(3.2)究竟在做啥，能使 有些什么性质。
Property 1. 
for all , 
.
Property 2. 
for all , .
Property 3. 
, 
for all 
.
Property 1 用induction(数学归纳法)很好证：对任意 ， 
。假设 ，分三种情况：
(1). 
：
(3.2)简化为 
，约束不满足的情况，dual variable往上增长，加大punish的力度，make sense。
(2). 
：
看图可知，(3.2)简化为 。
(3). 
：
看图可知，(3.2)简化为 
。
所以 Property 1 得证，后面的 Property 2、3 同样分这三种情况，一目了然。更重要的是，把这三种情况总结一下，我们得到了(3.2)的庐山真面目：
这个 的更新还是很妙的，不同于传统的Lagrange multiplier， 
永远都不会打到 ，它会一直待在 
的上面，哪怕这个约束已经满足了。
4. 收敛分析
Theorem 1. Let 
be an optimal solution of (P0) and 
be a Lagrange multiplier satisfying Assumption 2. If 
, then for all 
, we have:
, 
for all . 
(老规矩，下面扒一下证明；但也不会像以前一样全部写出来了，就稍微过一下。)
Define 
. Define Lyapunov drift :
(我其实不是很明白为啥它要叫Lyapunov drift。)
Lemma 1. 
for all .
Proof: 不同于原paper里的证明，我觉得把”庐山真面目”(3.2.simp)写出来后，分两种情况写一写，一下子就能出来。 
Lemma 2. Let be an optimal solution of (P0). If 
, then for all we have:
Proof: 很标准的一个proximal minimization point inequality加 Assumption 3 。
Lemma 3. Let be an optimal solution of (P0).
- If , then for all , we have
- If , then for all , we have
Proof: 看到第一个不等式， Theorem 1 的第一部分(4.1)式呼之欲出，因为我们有个著名的不等式：
至于 Theorem 1 的第二部分(4.2)，constraint violation，同学们自己去看paper吧，我就不扒了。(年纪大了 真，要早点睡了。)
5. 和PCPM的一个小比较
写不动了。。。我之前也写过，Teboulle的原paper[2]虽然只讨论了2-block linearly constrained convex optimization problem，但把PCPM推广到N-block nonlinearly constrained是非常trivial的，把线性约束矩阵的norm换成非线性约束函数的Lipschitz modulus就可以了，所有证明都轻松能过。如果用PCPM算法解(P1)：
它的算法步骤是这样的：
- ,
-
- while termination conditions are not met do
两个算法的assumption是完全一样的，差就差在dual variable的更新步骤上，PCPM把dual predictor 
和dual corrector 
都只是打到 ，而这里讲的这个算法是要把dual variable 拔高到 
的，个中玄机，诸位再参透参透。而且，原paper[2]给了global convergence，然后加了一个proximal Lagrangian inverse mapping在原点处Lipschitz continuous的假设后，给了个linear convergence rate；而如果没有这个假设，convergence rate是什么并没有讨论，不过我猜后面肯定有人证过了，加个primal averaging， 没跑的(狗头)。还有，其实仔细想想，PCPM算法里的 和这个算法里的 
是可以有个转换关系的： 
，再比比PCPM里对 的要求和这里对 的要求，嗯，好像还能发现点什么。。。
6. 写在最后
paper[1]后面其实还有个做得很好的应用，叫decentralized multipath network flow control problem，我实在不是个做control的人，就不扒了，感兴趣的同学，可自行阅读[1]。(悄悄说一句，Hao Yu博士的thesis也写得很好，很值得一读。) 最后的最后，本文是用markdown写的，用Zhihu On VSCode发的，还是觉得不是很方便，需要改进。
参考文献
[1]. H. Yu and M. J Neely, A Simple Parallel Algorithm with an O(1/t) Convergence Rate for General Convex Programs , SIAM Journal on Optimization, 27(2): 759 – 783, 2017.
[2]. G. Chen and M. Teboulle, A Proximal-based Decomposition Method for Convex Minimization Problems , Mathematical Programming, 64(1-3): 81 – 101, 1994.
[3]. S. Sabach and M. Teboulle, Faster Lagrangian-Based Methods in Convex Optimization , arXiv preprint arXiv:2010.14314, 2020.
About The Author
