Convergence study on the proximal alternating direction method with larger step size
- PDF / 1,027,445 Bytes
- 27 Pages / 439.642 x 666.49 pts Page_size
- 75 Downloads / 196 Views
Convergence study on the proximal alternating direction method with larger step size Feng Ma1 Received: 5 December 2018 / Accepted: 24 September 2019 / © Springer Science+Business Media, LLC, part of Springer Nature 2019
Abstract The alternating direction method of multipliers (ADMM) is a popular method for solving separable convex programs with linear constraints, and its proximal version is an important variant. In the literature, Fortin and Glowinski proved that the step size for updating the Lagrange multiplier of the ADMM can be chosen in the open interval of zero to the golden ratio, and subsequently this result has been proved to be also valid for the proximal ADMM. In this paper, we demonstrate that the dual step size can be larger than the golden ratio when the proximal regularization is positive definite. Thus, the feasible interval of the dual step size can be further enlarged for the proximal ADMM. Moreover, we establish the exact relationship between the dual step size and the proximal parameter. We also prove global convergence and establish a worst case convergence rate in the ergodic sense for this proximal scheme with the enlarged step size. Finally, we present numerical results to demonstrate the practical performance of the method. Keywords Alternating direction method of multipliers · Convex programming · Proximal regularization · Convergence analysis Mathematics Subject Classification (2010) 65K10 · 90C25 · 90C30
1 Introduction In this paper, we restrict our discussion to the canonical convex minimization model with a separable structure in the generic setting: min{θ1 (x) + θ2 (y) | Ax + By = b, x ∈ X , y ∈ Y }, This author was supported by the NSFC Grant 11701564 and 11871029. Feng Ma
[email protected] 1
Xi’an Research Institute of High Technology, Xi’an, 710025, Shaanxi, China
(1)
Numerical Algorithms
where A ∈ Rm×n1 , B ∈ Rm×n2 , and b ∈ Rm ; X ⊂ Rn1 and Y ⊂ Rn2 are closed and convex sets; θ1 : Rn1 → R and θ2 : Rn2 → R are closed (that is, lower semicontinuous) proper convex functions (not necessarily smooth). The augmented Lagrangian function associated with (1) is Lβ (x, y, λ) = θ1 (x) + θ2 (y) − λT (Ax + By − b) +
β Ax + By − b2 , 2
(2)
where λ is the Lagrange multiplier and β > 0 is a penalty parameter for the linear constraints. The augmented Lagrangian method (ALM) initially introduced in [1, 2] serves as a fundamental algorithm for solving (1). It reads as
Note that the ALM requires to minimize the augmented Lagrangian with respect to (x, y) jointly, and this minimization can be prohibitively expensive when the problem data is large and dense. On the other hand, we have encountered many problems arising in sparse and low-rank optimization, in which the functions θ1 and θ2 usually have some specific properties; and a natural idea is to exploit these underling structures in the algorithmic implementation. The alternating direction method of multipliers (ADMM) proposed in [3, 4] is well suited for this purpose. Given an initial iterate (y 0 , λ0 ) ∈ Y × Rm , ADMM generat
Data Loading...
