大规模凸优化问题的一阶分裂算法研究

Many large-scale optimization problems in information science and engineering fields, such as video processing, machine learning, etc, can be captured by a class of separable convex programming problems with linear equality constraints. In many novel applications, the efficiency of Alternating Direction Method of Multipliers (ADMM) for the problems with two separable operators, as a typical one of the first order splitting methds, has been witnessed. The effectivity of the first order splitting methods for large-scale convex optimization is well recognized. In this programm, we investigate some key problems in the area of the first order splitting methods: the convergence properties of the primal-dual hybrid gradient method, the direct extension of the alternating direction method of multipliers for multi-block problems, and the adaptive rule for choosing the parameters which is highly sensitive for the speed of convergence. In addition, in the sense of contraction, we will establish the uniform framework, investigate the convergence complexity and study the acceleration strategy for the first order methods. By incorporating the techniques of relaxation, decomposition and integration, we anticipate providing problem oriented splitting methods for large-scale separable linearly constrained convex optimization problems, which should be theoretically guaranteed and practically efficient.

信息科学和工程领域中的许多大规模优化问题，如视频处理、机器学习中的问题, 可以归结为一类具有等式约束的可分凸优化问题。在一些最新的应用领域，以交替方向法为代表的处理两个可分算子凸优化问题的分裂算法，其有效性已得到充分证实。一阶分裂算法是求解大规模凸优化的有效算法已成共识。本项目对一阶分裂算法中几个症结问题：原始-对偶混合梯度法及交替方向法对多个算子问题直接推广的收敛性质、影响收敛速度的参数自调比准则进行深入研究。此外，在收缩意义下建立分裂算法的统一框架，并对收敛复杂性和加速策略进行系统的研究。采用松弛、分裂与整合等技术，为求解线性约束的大规模可分凸优化问题提供理论上有复杂性保证，实际计算中又行之有效的分裂方法。

本项目致力于全面系统地研究大规模凸优化问题的一阶分裂算法的理论、算法设计以及应用。主要结果如下：证明了交替方向法在非遍历意义下的计算复杂性；提出了用于刻画一阶算法的预测-校正框架，简化了一阶分裂算法的收敛性证明与收敛速率分析；证明了对具有多块分离结构的凸优化问题，用直接推广的交替方向法计算不一定收敛，进而提出了一系列高效、稳健并具全局收敛性的预测-校正收缩型算法。这些原创性成果实质性地加深了对以交替方向法为代表的一阶分裂算法的系统理解，极大地拓展了这类算法的适用范围，得到了国内外学者的广泛关注及认可。