我和乘子交替方向法20年

1997年,交通网络分析方面的问题把作者引进乘子交替方向法(ADMM)的研究领域.近10年来,原本用来求解变分不等式的ADMM在优化计算中被广泛采用,影响越来越大.这里总结了20年来我们在ADMM方面的工作,特别是近10年ADMM在凸优化分裂收缩算法方面的进展.梳理主要结果,说清来龙去脉.文章利用变分不等式的形式研究凸优化的ADMM类算法,论及的所有方法都能纳入一个简单的预测-校正统一框架.在统一框架下证明算法的收缩性质特别简单.通读,有利于了解ADMM类算法的概貌.仔细阅读,也许就掌握了根据实际问题需要构造分裂算法的基本技巧.也要清醒地看到,ADMM类算法源自增广拉格朗日乘子法(ALM)和邻近点(PPA)算法,它只是便于利用问题的可分离结构,并没有消除ALM和PPA等一阶算法固有的缺点.

一类单调非线性变分不等式的前向加速收缩算法

本文通过分析PPA算法和APPA算法的思想,利用Gauss-seidel迭代算法的技术获得了单调非线性变分不等式的前向加速收缩算法,利用邻近点收缩算法统一框架的技术给出了收敛性证明.一系列的数值试验表明了前向加速收缩算法的有效性和效率性.

凸优化和单调变分不等式收缩算法的统一框架

线性约束的凸优化问题可以转化成一个形式更一般的单调变分不等式.在变分不等式的框架下研究最优化问题的求解方法,就像微积分中利用导数求函数的极值,常常会带来很大的方便.求解单调变分不等式的投影收缩算法有一个预测-校正的统一框架,基于"孪生方向和相同步长"有两类花费几乎相当的算法,计算实践证明第二类算法效率往往更高.近年发展起来并被广泛采用的凸规划的分裂收缩算法属于一个更一般的框架,这个框架中的预测同样提供了一对孪生方向.迄今为止的凸规划的分裂收缩算法,都相当于变分不等式投影收缩算法中的第一类算法.本文指出,利用现有的步长法则,配上孪生方向中的另一个方向,同样可以构造相应的第二类算法.本文在统一框架下证明了两类算法的O(1/t)迭代复杂性.