Abstract: 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.

Key words: variational inequalities, alternating direction method of multipliers, proximal point algorithm, random step size, structured optimization