Convergence of the augmented decomposition algorithm

Hongsheng Liu () and Shu Lu ()
Additional contact information
Hongsheng Liu: University of North Carolina at Chapel Hill
Shu Lu: University of North Carolina at Chapel Hill

Computational Optimization and Applications, 2019, vol. 72, issue 1, No 6, 179-213

Abstract: Abstract We study the convergence of the augmented decomposition algorithm (ADA) proposed in Rockafellar et al. (Problem decomposition in block-separable convex optimization: ideas old and new, https://www.washington.edu/ , 2017) for solving multi-block separable convex minimization problems subject to linear constraints. We show that the global convergence rate of the exact ADA is $$o(1/\nu )$$ o ( 1 / ν ) under the assumption that there exists a saddle point. We consider the inexact augmented decomposition algorithm and establish global and local convergence results under some mild assumptions, by providing a stability result for the maximal monotone operator $$\mathcal {T}$$ T associated with the perturbation from both primal and dual perspectives. This result implies the local linear convergence of the inexact ADA for many applications such as the lasso, total variation reconstruction, exchange problem and many other problems from statistics, machine learning and engineering with $$\ell _1$$ ℓ 1 regularization.

Keywords: Separable convex minimization; Convergence rate; Augmented decomposition algorithm; Distributed computing (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10589-018-0039-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:72:y:2019:i:1:d:10.1007_s10589-018-0039-6

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-018-0039-6

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().