Local Linear Convergence of the Alternating Direction Method of Multipliers for Nonconvex Separable Optimization Problems

In this paper, we consider the convergence rate of the alternating direction method of multipliers for solving the nonconvex separable optimization problems. Based on the error bound condition, we prove that the sequence generated by the alternating direction method of multipliers converges locally to a critical point of the nonconvex optimization problem in a linear convergence rate, and the corresponding sequence of the augmented Lagrangian function value converges in a linear convergence rate. We illustrate the analysis by applying the alternating direction method of multipliers to solving the nonconvex quadratic programming problems with simplex constraint, and comparing it with some state-of-the-art algorithms, the proximal gradient algorithm, the proximal gradient algorithm with extrapolation, and the fast iterative shrinkage-thresholding algorithm.

Automated summary

In this paper, the convergence rate of the alternating direction method of multipliers for solving nonconvex separable optimization problems is considered. It is proven that the sequence generated by this method converges locally to a critical point of the nonconvex optimization problem with a linear convergence rate. Results are illustrated through the application of this method to nonconvex quadratic programming problems and comparison with other state-of-the-art algorithms.