大规模凸规划的不正则邻近增广拉格朗日算法研究

The proximal regularized augmented Lagrangian algorithm (ALM) is a class of theoretically rich and extensible algorithms for large-scale convex optimization, and has wide applications in areas such as machine learning, statistical analysis and imaging processing. It covers linearized ALM, linearized Bregman algorithm, parallel alternating direction method (ADMM) and many other first order algorithms as special cases. The algorithm is known to be convergent when the proximal term is positive definite. Recently we found that it is not necessary to ensure the positive definiteness of the proximal regularization and the convergence can be still theoretically hold. Indeed, the numerical performance can be significantly improved for this case. This project intends to deeply investigate the positive-indefinite proximal augmented Lagrangian algorithm. It mainly includes: (1) Develop positive-indefinite proximal algorithms based on the augmented Lagrangian function, such as positive-indefinite parallel ADMM, positive-indefinite linearized Peaceman-Rachford splitting algorithm and so on. (2) Analyze the convergence rate of the positive-indefinite proximal ALM, including the ergodic and non-ergodic case. (3) Study the adjustment strategy of the step sizes for the positive-indefinite algorithms, including the relationship between the primal and dual step sizes and self-adaptive adjusting strategy. (4) Study the applications of these positive-indefinite proximal algorithms in large-scale convex optimization problems. We believe the research of this project will further enrich the theory and improve the numerical performance of ALM, and has a promising application prospect.

带邻近项的增广拉格朗日算法是一类理论丰富、扩展性强的大规模凸优化算法，其包含线性增广拉格朗日算法、线性Bregman算法、并行交替方向法等许多一阶算法作为特例，在机器学习、统计分析、图像处理等领域应用广泛。当前学界普遍认为邻近项正则该算法才收敛，我们近期证明邻近项不正则该算法也收敛，并且不正则情形下数值性能大幅提升。本项目拟深化对邻近项不正则的增广拉格朗日算法的研究，主要包括：(1)设计基于增广拉格朗日函数的不正则邻近算法，如不正则的并行交替方向法、线性Peaceman-Rachford分裂算法等。(2)分析这类不正则算法的收敛速率，包括遍历与非遍历情形。(3)研究不正则情形下算法的步长调整策略，包括原始对偶步长取值关系及自调比准则等。(4)研究不正则算法在大规模凸规化问题上的应用。本项目的研究将进一步丰富增广拉格朗日算法的理论，提升算法的性能，且具有良好的应用前景。

基于增广拉格朗日函数的算法如ALM或ADMM是近年来流行的求解结构型凸规划问题的算法。为了提高算法中子问题的易解性，通常可在增广拉格朗日函数项后添加一个特殊的邻近项，从而可构造出一系列基于增广拉格朗日函数的改进算法，例如：线性ALM算法，线性ADMM算法，并行ADMM等。以往研究这类算法的文献中，大多要求或假定其附加的邻近项正则来分析算法或是构造新方法，而忽略了邻近项正则是否是收敛的必要条件这一重要科学问题。同时，计算实践表明邻近项非正则时，这类算法如果收敛数值效果会大幅提高。因此，不管从理论上或实践上，对非正则邻近ALM类算法的研究是有意义的。本项目主要针对邻近项非正则的增广拉格朗日算法展开研究，取得了如下结果：（1）证明增广拉格朗日类算法可以附加非正则的邻近项，从而设计了基于增广拉格朗日函数的非正则邻近算法，改进了麻省理工学院D. P. Bertsekas教授所提的并行交替方向法的收敛条件。（2）证明线性化ADMM算法可以附加非正则的邻近项，给出了非正则邻近项系数的取值下界，并给出反例证明这一下界的最优性，同时将这一结果推广到对称ADMM算法上。（3）指出在收敛性保证下，邻近ADMM算法与ALM算法中原始步长与对偶步长之间存在trade-off的关系，并给出了精确的函数表达式。（4）针对定制邻近点算法，提出了新的松弛策略来加快收敛，并给出了统一的刻画。以上研究结果既有收敛性分析，也有数值应用实例，丰富了对增广拉格朗日类算法的认识，可用于解决凸规划中的一些实际问题。