File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Convergence analysis of the direct extension of ADMM for multiple-block separable convex minimization

TitleConvergence analysis of the direct extension of ADMM for multiple-block separable convex minimization
Authors
KeywordsAlternating direction method of multipliers
Convergence analysis
Convex programming
Multiple-block separable models
Issue Date2017
Citation
Advances in Computational Mathematics, 2017, p. 1-41 How to Cite?
Abstract© 2017 Springer Science+Business Media, LLC Recently, the alternating direction method of multipliers (ADMM) has found many efficient applications in various areas; and it has been shown that the convergence is not guaranteed when it is directly extended to the multiple-block case of separable convex minimization problems where there are m ≥ 3 functions without coupled variables in the objective. This fact has given great impetus to investigate various conditions on both the model and the algorithm’s parameter that can ensure the convergence of the direct extension of ADMM (abbreviated as “e-ADMM”). Despite some results under very strong conditions (e.g., at least (m − 1) functions should be strongly convex) that are applicable to the generic case with a general m, some others concentrate on the special case of m = 3 under the relatively milder condition that only one function is assumed to be strongly convex. We focus on extending the convergence analysis from the case of m = 3 to the more general case of m ≥ 3. That is, we show the convergence of e-ADMM for the case of m ≥ 3 with the assumption of only (m − 2) functions being strongly convex; and establish its convergence rates in different scenarios such as the worst-case convergence rates measured by iteration complexity and the globally linear convergence rate under stronger assumptions. Thus the convergence of e-ADMM for the general case of m ≥ 4 is proved; this result seems to be still unknown even though it is intuitive given the known result of the case of m = 3. Even for the special case of m = 3, our convergence results turn out to be more general than the existing results that are derived specifically for the case of m = 3.
Persistent Identifierhttp://hdl.handle.net/10722/251247
ISSN
2023 Impact Factor: 1.7
2023 SCImago Journal Rankings: 0.995
ISI Accession Number ID

 

DC FieldValueLanguage
dc.contributor.authorTao, Min-
dc.contributor.authorYuan, Xiaoming-
dc.date.accessioned2018-02-01T01:55:00Z-
dc.date.available2018-02-01T01:55:00Z-
dc.date.issued2017-
dc.identifier.citationAdvances in Computational Mathematics, 2017, p. 1-41-
dc.identifier.issn1019-7168-
dc.identifier.urihttp://hdl.handle.net/10722/251247-
dc.description.abstract© 2017 Springer Science+Business Media, LLC Recently, the alternating direction method of multipliers (ADMM) has found many efficient applications in various areas; and it has been shown that the convergence is not guaranteed when it is directly extended to the multiple-block case of separable convex minimization problems where there are m ≥ 3 functions without coupled variables in the objective. This fact has given great impetus to investigate various conditions on both the model and the algorithm’s parameter that can ensure the convergence of the direct extension of ADMM (abbreviated as “e-ADMM”). Despite some results under very strong conditions (e.g., at least (m − 1) functions should be strongly convex) that are applicable to the generic case with a general m, some others concentrate on the special case of m = 3 under the relatively milder condition that only one function is assumed to be strongly convex. We focus on extending the convergence analysis from the case of m = 3 to the more general case of m ≥ 3. That is, we show the convergence of e-ADMM for the case of m ≥ 3 with the assumption of only (m − 2) functions being strongly convex; and establish its convergence rates in different scenarios such as the worst-case convergence rates measured by iteration complexity and the globally linear convergence rate under stronger assumptions. Thus the convergence of e-ADMM for the general case of m ≥ 4 is proved; this result seems to be still unknown even though it is intuitive given the known result of the case of m = 3. Even for the special case of m = 3, our convergence results turn out to be more general than the existing results that are derived specifically for the case of m = 3.-
dc.languageeng-
dc.relation.ispartofAdvances in Computational Mathematics-
dc.subjectAlternating direction method of multipliers-
dc.subjectConvergence analysis-
dc.subjectConvex programming-
dc.subjectMultiple-block separable models-
dc.titleConvergence analysis of the direct extension of ADMM for multiple-block separable convex minimization-
dc.typeArticle-
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1007/s10444-017-9560-x-
dc.identifier.scopuseid_2-s2.0-85031432456-
dc.identifier.spage1-
dc.identifier.epage41-
dc.identifier.eissn1572-9044-
dc.identifier.isiWOS:000435587000007-
dc.identifier.issnl1019-7168-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats