Convergence Analysis of the Symmetric Alternating Direction Method of Multipliers for Two-Block Separable Nonconvex Optimization Problems with Linear Constraints

What the paper says

(Communicated by Xinwei Liu) The alternating direction method of multipliers (ADMM) is one of the effective methods for solving two-block separable optimization problems with linear constraints, and has been widely applied in image processing, power systems, sparse learning, and other fields. Its essence is the application of the Douglas-Rachford splitting method to the dual problem. Classical ADMM updates the Lagrange multipliers only once per iteration, while symmetric ADMM achieves dual updates of the Lagrange multipliers in each iteration by introducing an additional multiplier update step, thereby significantly improving the convergence performance and numerical stability of the algorithm. In this paper, we propose a novel symmetric ADMM algorithmic framework for two-block separable nonconvex optimization problems with linear constraints, which introduces two distinct relaxation factors to enhance the flexibility and convergence efficiency of the algorithm. This method has been comprehensively studied for convex problems. However, for nonconvex problems, in the convergence analysis of symmetric alternating direction method of multipliers with two different relaxation factors without introducing Bregman distances or regularization terms, proving the monotonicity of the Lagrangian function remains a challenging problem. In terms of theoretical analysis, we establish the convergence theory of the proposed algorithm in this paper. Notably, our convergence proof does not rely on common technical assumptions such as Bregman distances or regularization terms. Specifically, by constructing a novel auxiliary function and under the mild condition that the Kurdyka–Łojasiewicz (KŁ) inequality is satisfied, we prove that the iterative sequence generated by the algorithm converges to a stationary point of the problem. The main contributions of this paper can be summarized as follows: First, we design a symmetric ADMM scheme with dual relaxation factors to solve two-block separable nonconvex and nonsmooth optimization problems with linear constraints, and the proposed method allows for a wider range of parameters, which can better adapt to the structural characteristics of different problems through flexible adjustment of relaxation parameters. Second, we establish a concise convergence analysis framework that does not depend on Bregman distances and regularization terms, reducing the complexity of theoretical analysis; moreover, it can degenerate into the classical ADMM. Finally, we validate the practical application effectiveness of the proposed algorithm through numerical experiments, and the experimental results demonstrate that the algorithm outperforms traditional ADMM and its variants in terms of convergence speed and solution accuracy.