On the Sublinear Convergence Rate of Multi-block ADMM
- PDF / 592,518 Bytes
- 24 Pages / 439.37 x 666.142 pts Page_size
- 0 Downloads / 191 Views
On the Sublinear Convergence Rate of Multi-block ADMM Tian-Yi Lin1 · Shi-Qian Ma1 · Shu-Zhong Zhang2
Received: 8 May 2015 / Revised: 7 June 2015 / Accepted: 19 June 2015 © Operations Research Society of China, Periodicals Agency of Shanghai University, Science Press, and Springer-Verlag Berlin Heidelberg 2015
Abstract The alternating direction method of multipliers (ADMM) is widely used in solving structured convex optimization problems. Despite its success in practice, the convergence of the standard ADMM for minimizing the sum of N (N 3) convex functions, whose variables are linked by linear constraints, has remained unclear for a very long time. Recently, Chen et al. (Math Program, doi:10.1007/ s10107-014-0826-5, 2014) provided a counter-example showing that the ADMM for N 3 may fail to converge without further conditions. Since the ADMM for N 3 has been very successful when applied to many problems arising from real practice, it is worth further investigating under what kind of sufficient conditions it can be guaranteed to converge. In this paper, we present such sufficient conditions that can guarantee the sublinear convergence rate for the ADMM for N 3. Specifically, we show that if one of the functions is convex (not necessarily strongly convex) and the other N -1 functions are strongly convex, and the penalty parameter lies in a certain region, the ADMM converges with rate O(1/t) in a certain ergodic sense and o(1/t) in a certain
The research of S.-Q. Ma was supported in part by the Hong Kong Research Grants Council General Research Fund Early Career Scheme (No. CUHK 439513). The research of S.-Z. Zhang was supported in part by the National Natural Science Foundation (No. CMMI 1161242).
B
Shi-Qian Ma [email protected] Tian-Yi Lin [email protected] Shu-Zhong Zhang [email protected]
1
Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Shatin, New Territories, Hong Kong, China
2
Department of Industrial and Systems Engineering, University of Minnesota, Minneapolis, MN 55455, USA
123
T.-Y. Lin et al.
non-ergodic sense, where t denotes the number of iterations. As a by-product, we also provide a simple proof for the O(1/t) convergence rate of two-block ADMM in terms of both objective error and constraint violation, without assuming any condition on the penalty parameter and strong convexity on the functions. Keywords Alternating direction method of multipliers · Sublinear convergence rate · Convex optimization 90C25 · 90C30
Mathematics Subject Classification
1 Introduction We consider solving the following multi-block convex minimization problem: min f 1 (x1 ) + f 2 (x2 ) + · · · + f N (x N ) s.t. A1 x1 + A2 x2 + · · · + A N x N = b xi ∈ Xi , i = 1, · · · , N ,
(1.1)
where Ai ∈ R p×n i , b ∈ R p , Xi ⊂ Rn i are closed convex sets and f i : Rn i → R p are closed convex functions. One recently popular way to solve (1.1), when the functions f i are of special structures, is to apply the alternating direction method of multipliers (ADMM) [1,2
Data Loading...
