几类分块优化问题乘子交替方向法研究

The alternating direction method of multipliers (ADMM) is widely used in the engineering fields such as compressive sensing, machine learning, signal & image processing and so on. The classic ADMM is mainly used for solving the convex two-block optimization problem, which has been well studied. However, for convex multi-block problem, convex multi-block problem with inseparable structure and nonconvex block problem, the theory and algorithm of ADMM are still in the exploration and development stage. This project studies the theory and algorithm of ADMM for the three kinds of block optimization problems. The research contents and innovation are: 1) to propose convergent and new ADMM with good numerical results for solving convex multi-block problem by making use of correction technique, variable order adjustment technique, etc; 2) to weaken the conditions of convergence for the classical ADMM of convex two-block problem with inseparable structure by proposing new analysis techniques for compression of iterative sequence; to propose new ADMM with weak convergence condition for solving convex two-block problem with inseparable structure by the use of accelerating technique, subproblem simplification technique, etc； 3) to propose convergent and new ADMM for solving nonconvex block problem by the use of regularization technique, parameter adjustment technique, etc; and to remove the condition that at least one block function is Lipschitz continuously differentiable in the objective of the existing algorithms by developing a new dual variable sequence control technology.

乘子交替方向法(ADMM)广泛应用于实际工程领域，如压缩感知、机器学习、信号与图像处理等。经典的ADMM主要用于求解凸两分块优化问题，其研究已较完善。然而，对于凸多分块问题、带不可分结构的凸分块问题、非凸分块问题，ADMM的相关理论与算法的研究尚处于不断探索和发展阶段。本项目研究以上三类分块优化问题ADMM的新型算法构造与理论分析，研究内容与创新主要有：1）针对凸多分块问题，利用校正、变量次序调整等技术，提出收敛性可保证且数值效果好的新型ADMM。2）针对带不可分结构的凸两分块问题，通过提出新的迭代序列压缩性分析技巧，减弱已有经典ADMM收敛性分析的条件；利用加速、子问题简化等技术，提出收敛条件弱的新型ADMM。3）针对非凸分块问题，利用正则化、参数调整等技术，构造收敛性可保证的新型ADMM；发展新的对偶变量序列控制技术去掉现有算法要求目标函数中至少有一块函数Lipschitz可微的要求。

乘子交替方向法(ADMM)广泛应用于实际工程领域，如压缩感知、机器学习、信号与图像处理等。经典的ADMM主要用于求解凸两分块优化问题，其研究已较完善。然而，对于凸多分块问题、带不可分结构的凸分块问题、非凸分块问题，ADMM的相关理论与算法的研究尚处于不断探索和发展阶段。本项目研究以上三类分块优化问题ADMM的新型算法构造与理论分析。取得主要成果有:（1）针对目标函数的每个分块是光滑函数与非光滑函数和的凸多分块问题，在对光滑部分进行一阶近似的情形下构造了一个带校正近似乘子交替方向法，分析了算的收敛性，并通过数值实验验证了算法的有效性。(2) 针对非凸两分块问题，借助正则化技术，构造了一个外推正则化的乘子交替方向法；针对带不可分结构的非凸问题构造了一个Bregman ADMM；分析了上述两个算法的全局收敛性及强收敛性。(3) 针对非凸两分块问题，在其中一个分块函数可微、半凸的条件下，分析了经典Peaceman-Reachford(PR)分裂算法的全局及强收敛性；构造了一个外推正则化的PR分裂算法并分析了算法的全局收敛性及强收敛性。(4) 首先，将强斜率和全局斜率的概念推广到非下半连续函数。其次，利用这两个概念，给出了非下半连续函数存在全局误差界和局部误差界的刻画。特别，得到了非下半连续函数全局误差界的一个充要条件。(5) 考虑了带闭集约束的二次规划问题的凸性与解的存在性问题，给出了二次规划问题（严格）凸性和解的存在性的几个条件。