求解结构型优化问题的随机步长ADMM下降算法

本文考虑求解带有两块变量的结构型凸优化问题．ADMM算法是求解该问题的一种经典算法，主要思想是在増广拉格朗日乘子算法的基础上，利用目标函数关于两块变量的可分性，降低了子问题的计算难度．ADMM下降算法是ADMM算法的一种改进，对部分变量利用最优步长外加一个固定的延长因子进行延长，以加快ADMM算法的收敛速度．数值实验结果表明，ADMM下降算法比ADMM算法收敛速度更快．根据徐海文提出的随机步长收缩算法的思想，我们在ADMM下降算法的基础上，将延长因子改为利用随机数生成，提出了带随机步长的ADMM下降算法，并证明了新算法的收敛性．初步数值实验结果，表明新算法的计算效率优于经典ADMM算法和ADMM下降算法，且新算法的计算效率对问题规模的增长有更好的尺度适应性．

A Descent Alternating Direction Method of Multipliers with Random Step Size for Structured Optimization Problem

In this paper, we consider the structured convex optimization problem with two blocks of variables. The alternating direction method of multipliers (ADMM) is a classical method for solving this problem, which is based on the augmented Lagrange algorithm and it utilizes the separability of two blocks of variables in the objective function to simplify the computation of subproblems. The descent alternating direction method of multipliers (DADMM) is an improved version of ADMM, which applies an optimal step as well as a fixed factor to do extension on part of the variables. The DADMM is reported to be faster than the classical ADMM in numerical simulations. According to the idea of SC-Method proposed by Xu which allows the extension factor to be randomly generated, we propose a new DADMM with random step size. The convergence of the new algorithm can be derived under mild assumptions. Preliminary experiments demonstrate the promising performance and dimensional scalability of the new method.