以交替方向法为代表的分裂算法的深入研究

From the point of view of “numerical optimization”, the iterative algorithm consists of two parts: “direction” and “step length”. The Newton method for nonlinear programming does not adopt the “ideal” unit step, and the “interior point methods” do not adopt the theoretical short step. In recent years, the first order splitting algorithms, represented by Alternating Direction Method of Multipliers (ADMM), are widely applied to solve computer vision, image processing, machine learning and other fields, and play an increasingly important role. In the past, the study of these algorithms circles from operator splitting point of view, focus on how to split the original problem into several sub-problems, reduce the difficulty of the original problems, but most algorithms lack the characteristics of numerical optimization and the iterative process uses the uniform steps. This project reexamines the split algorithm represented by ADMM from the perspective of numerical optimization, trying to integrate the advantages of the operator splitting method and the numerical optimization. The research contents include: (1) Improve the various splitting algorithms by considering the both direction and step length. (2) Study the convergence of the direct extension of ADMM with three operators whose constraints matrices including a unit matrix. (3) Promote the application of ADMM-like splitting contraction methods in engineering areas. The research of this project will further enrich the theory of ADMM class splitting and contraction algorithm, optimize the performance of the algorithm, and broaden the new application field.

从数值优化的角度看，迭代算法由方向和步长两要素组成。非线性规划的牛顿法并不采用理想的单位步长，内点法也不采用理论结果好的短步长。近年来，以交替方向法(ADMM)为代表的一阶分裂算法被广泛用于求解计算机视觉、图像处理、机器学习等领域的问题，起着日益重要作用。以往，学界对这些算法的研究多从算子分裂角度考虑，注重于将原始问题分裂成若干子问题，降低原问题的求解难度，但多数算法缺乏数值优化的特征，迭代过程中采用千篇一律的步长。本项目从数值优化的角度重新审视以ADMM为代表的分裂算法，力图整合算子分裂方法与数值优化的优点。研究内容包括：（1）为多类分裂算法设计考虑方向与步长的改进算法。（2）研究直接推广的ADMM方法对三个算子问题含单位约束矩阵的收敛性。（3）推广ADMM类分裂方法在工程领域的应用。本项目的研究将进一步丰富ADMM类分裂算法的理论，优化算法性能，和拓宽新的应用领域。

本项目开展以交替方向法(ADMM)为代表的分裂收缩算法的深入研究。最近十多年来，以ADMM为代表的一阶分裂收缩算法被广泛用于求解图像处理、计算机视觉、机器学习等领域出现的凸优化问题。本项目主要做了以下四个方面的工作：（1）对图像处理领域常用的一类求解鞍点问题的Primal-Dual方法，进行深入研究，指出Arrow-Hurwicz方法求解一般Convex-Concave问题并不保证收敛；对 Chambolle-Pock 提出的同类算法，略加改造，放松了收敛条件，增大了步长因子，切实提高了算法效率，并举例说明若因子继续扩大就不能保证在所有情况下收敛，在理论上给出了最优的界。（2）对线性化的增广拉格朗日乘子法，线性化的 ADMM 方法给出了最优线性化因子，提高了算法效率; 对三个可分离块凸优化问题的平行正则化方法，给出了最优正则化因子。（3）对多个可分离块的凸优化问题，分别给出了采用平行预测和ADMM类预测的迭代方法，不管线性约束是等式的还是不等式的，预测中处理的是系列的单个小问题，校正的形式又非常简单，容易被工程技术界掌握。（4）对先前相关项提出的分裂收缩算法的预测-校正统一框架做进一步的分析，得到了新的等价形式。对于同一个合格的预测，以前是好不容易地凑出一个方法，利用这个等价形式，如今并不费力地构造一簇算法，为算法设计开辟了新的局面。我们在凸优化分裂收缩算法方面的系统独立的工作，已经被认为一个“独立的流派”，并得到欧美学者“Very Simple yet Powerful”的赞誉。本项目的研究ADMM类分裂收缩算法，进一步丰富了理论、优化了算法性能和拓宽了新的应用领域。