基于变分分析的分裂算法线性收敛率研究

近年来，运用分裂算法求解可分离结构的优化问题引起了学者们的广泛关注和兴趣。这些具有特定结构的问题在机器学习、信号处理和统计等诸多领域都存在着重要的应用。随着大数据时代的到来，优化问题的数据规模通常较大甚至十分庞大。块坐标下降（BCD）算法、交替方向乘子法（ADMM）等分裂算法求解这类大规模问题的有效性，已经通过大量的数值实验得到了验证。关于BCD算法和ADMM的理论成果，特别是收敛性结果已经颇为丰富，但在快速收敛率研究方面仍存在较大的发展空间。此项目拟将变分分析的核心概念，即度量次正则/平稳性条件融合进算法收敛率的分析中，深入挖掘实际问题的潜在结构，发展出线性收敛率分析的理论框架，改进现有文献中的结果，推进分裂算法线性收敛率研究的进展。具体来说，针对多类重要的凸优化应用模型，此项目拟准确刻画循环BCD算法以及ADMM的线性收敛率，验证随机BCD算法在期望意义下的线性收敛性。

In recent years there has been an ever-increasing interest in the optimization community for algorithms suitable for solving optimization problems with separable structures. These optimization problems have arisen from various fields such as machine learning, signal processing, and statistics. With the advent of big data era, the problem instances are typically of large- and even huge-scale. Numerous experiments have demonstrated that first-order splitting methods such as the block coordinate descent (BCD) algorithm and the alternating direction method of multipliers (ADMM) are very powerful for solving them. The numerical efficiency and some theoretical progress on cyclic/randomized BCD have long been witnessed in diversified areas, but research on their convergence rates is still in its infancy. In this project, we will focus on introducing the well-established error bound/calmness/metric subregularity theories in variational analysis to the convergence rate analysis. The convergence rates of BCD and ADMM will be intensively investigated under error bound/calmness/metric subregularity. In particular, the linear convergence of cyclic BCD and several variants of ADMM will be verified to hold automatically for a wide class of structured convex models, and the convergence rates can be calculated. In addition, the subregularity conditions required for the expected value-type linear convergence of randomized BCD will be proved to hold automatically for some widely-used statistical learning models. Therefore, the new perspective enables us to improve some existing results and obtain novel results unknown in the literature.