Optimally linearizing the alternating direction method of multipliers for convex programming

He，Bingsheng1,2; Ma，Feng3; Yuan，Xiaoming4

2019

10.1007/s10589-019-00152-3

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS   影响因子和分区

0926-6003

1573-2894

The alternating direction method of multipliers (ADMM) is being widely used in a variety of areas; its different variants tailored for different application scenarios have also been deeply researched in the literature. Among them, the linearized ADMM has received particularly wide attention in many areas because of its efficiency and easy implementation. To theoretically guarantee convergence of the linearized ADMM, the step size for the linearized subproblems, or the reciprocal of the linearization parameter, should be sufficiently small. On the other hand, small step sizes decelerate the convergence numerically. Hence, it is interesting to probe the optimal (largest) value of the step size that guarantees convergence of the linearized ADMM. This analysis is lacked in the literature. In this paper, we provide a rigorous mathematical analysis for finding this optimal step size of the linearized ADMM and accordingly set up the optimal version of the linearized ADMM in the convex programming context. The global convergence and worst-case convergence rate measured by the iteration complexity of the optimal version of linearized ADMM are proved as well.

Alternating direction method of multipliers Convergence rate Convex programming Linearized Optimal step size Proximal regularization

SCI ; EI

英语

第一

National Natural Science Foundation of China[11471156] ; National Natural Science Foundation of China[11701564] ; Research Grants Council, University Grants Committee[12300317] ; National Natural Science Foundation of China[91530115]

Operations Research & Management Science ; Mathematics

Operations Research & Management Science ; Mathematics, Applied

WOS:000513353000002

Springer

20194807745552

Convex optimization ; Iterative methods

Numerical Methods:921.6

ENGINEERING

2-s2.0-85075189794

Scopus

1.Department of Mathematics,Southern University of Science and Technology of China,Shenzhen,China
2.Department of Mathematics,Nanjing University,Nanjing,China
3.High-Tech Institute of Xi’an,Xi’an,710025,China
4.Department of Mathematics,The University of Hong Kong,Hong Kong

He，Bingsheng,Ma，Feng,Yuan，Xiaoming. Optimally linearizing the alternating direction method of multipliers for convex programming[J]. COMPUTATIONAL OPTIMIZATION AND APPLICATIONS,2019,75(2):361-388.

He，Bingsheng,Ma，Feng,&Yuan，Xiaoming.(2019).Optimally linearizing the alternating direction method of multipliers for convex programming.COMPUTATIONAL OPTIMIZATION AND APPLICATIONS,75(2),361-388.

He，Bingsheng,et al."Optimally linearizing the alternating direction method of multipliers for convex programming".COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 75.2(2019):361-388.