An inexact proximal generalized alternating direction method of multipliers
- PDF / 3,771,732 Bytes
- 27 Pages / 439.37 x 666.142 pts Page_size
- 73 Downloads / 197 Views
An inexact proximal generalized alternating direction method of multipliers V. A. Adona1 · M. L. N. Gonçalves1 · J. G. Melo1 Received: 8 December 2018 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract This paper proposes and analyzes an inexact variant of the proximal generalized alternating direction method of multipliers (ADMM) for solving separable linearly constrained convex optimization problems. In this variant, the first subproblem is approximately solved using a relative error condition whereas the second one is assumed to be easy to solve. In many ADMM applications, one of the subproblems has a closed-form solution; for instance, 𝓁1 regularized convex composite optimization problems. The proposed method possesses iteration-complexity bounds similar to its exact version. More specifically, it is shown that, for a given tolerance 𝜌 > 0 , an approximate solution of the Lagrangian system associated to the problem under consideration is obtained in at most O(1∕𝜌2 ) (resp. O(1∕𝜌) in the ergodic case) iterations. Numerical experiments are presented to illustrate the performance of the proposed scheme. Keywords Generalized alternating direction method of multipliers · Convex program · Relative error criterion · Pointwise iteration-complexity · Ergodic iteration-complexity Mathematics Subject Classification 47H05 · 49M27 · 90C25 · 90C60 · 65K10
The work of these authors was supported in part by CAPES, FAPEG/GO, and CNPq Grants 302666/2017-6, 312559/2019-4 and 408123/2018-4. * J. G. Melo [email protected] V. A. Adona [email protected] M. L. N. Gonçalves [email protected] 1
IME, Universidade Federal de Goias, Campus II, Caixa Postal 131, Goiânia, GO CEP 74001‑970, Brazil
13
Vol.:(0123456789)
V. A. Adona et al.
1 Introduction Recently, there has been a growing interest in the study of the alternating direction method of multipliers (ADMM) and its variants for solving the separable linearly constrained optimization problem
min{f (x) + g(y) ∶ Ax + By = b},
(1)
where f ∶ ℝn → (−∞, ∞] and g ∶ ℝp → (−∞, ∞] are proper, closed and convex functions, A ∈ ℝm×n , B ∈ ℝm×p , and b ∈ ℝm . The ADMM is an augmented Lagrangian type method that explores the separable structure of problem (1) in such a way that the augmented Lagrangian subproblem is solved alternately. The first ones to consider this scheme were Glowinski and Marroco in [17] and Gabay and Mercier in [16]. An important class of problems that can be fit into the above setting is the following composite convex optimization problem
min f (x) + g(Qx),
x∈ℝn
(2)
where Q ∈ ℝn×n . Indeed, this can be done by considering an artificial variable y = Qx and setting A = −Q , B = In , and b = 0 . A special instance of (2) consists of Q = In and g as the 𝓁1 regularization g(⋅) = 𝜇‖ ⋅ ‖1 , where 𝜇 is a regularization parameter. The latter instance with f (x) = ‖Dx − d‖2 , where D ∈ ℝm×n , corresponds to the popular LASSO problem. Problems such as (2) and, more generally, (1) have found many applications in different areas; see, for examp
Data Loading...
