skip to main content
Language:
Search Limited to: Search Limited to: Resource type Show Results with: Show Results with: Search type Index

On the Global and Linear Convergence of the Generalized Alternating Direction Method of Multipliers

Journal of scientific computing, 2016-03, Vol.66 (3), p.889-916 [Peer Reviewed Journal]

Springer Science+Business Media New York 2015 ;Springer Science+Business Media New York 2015. ;ISSN: 0885-7474 ;EISSN: 1573-7691 ;DOI: 10.1007/s10915-015-0048-x

Full text available

Citations Cited by
  • Title:
    On the Global and Linear Convergence of the Generalized Alternating Direction Method of Multipliers
  • Author: Deng, Wei ; Yin, Wotao
  • Subjects: Algorithms ; Computational Mathematics and Numerical Analysis ; Convergence ; Convex analysis ; Convexity ; Fourier transforms ; Image processing ; Machine learning ; Mathematical analysis ; Mathematical and Computational Engineering ; Mathematical and Computational Physics ; Mathematical models ; Mathematics ; Mathematics and Statistics ; Multipliers ; Optimization ; Splitting ; Statistics ; Theoretical
  • Is Part Of: Journal of scientific computing, 2016-03, Vol.66 (3), p.889-916
  • Description: The formulation min x , y f ( x ) + g ( y ) , subject to A x + B y = b , where f and g are extended-value convex functions, arises in many application areas such as signal processing, imaging and image processing, statistics, and machine learning either naturally or after variable splitting. In many common problems, one of the two objective functions is strictly convex and has Lipschitz continuous gradient. On this kind of problem, a very effective approach is the alternating direction method of multipliers (ADM or ADMM), which solves a sequence of f / g -decoupled subproblems. However, its effectiveness has not been matched by a provably fast rate of convergence; only sublinear rates such as O (1 /  k ) and O ( 1 / k 2 ) were recently established in the literature, though the O (1 /  k ) rates do not require strong convexity. This paper shows that global linear convergence can be guaranteed under the assumptions of strong convexity and Lipschitz gradient on one of the two functions, along with certain rank assumptions on A and B . The result applies to various generalizations of ADM that allow the subproblems to be solved faster and less exactly in certain manners. The derived rate of convergence also provides some theoretical guidance for optimizing the ADM parameters. In addition, this paper makes meaningful extensions to the existing global convergence theory of ADM generalizations.
  • Publisher: New York: Springer US
  • Language: English
  • Identifier: ISSN: 0885-7474
    EISSN: 1573-7691
    DOI: 10.1007/s10915-015-0048-x
  • Source: ProQuest Central
Back to results list
INSPIRE LIBRARY - TON DUC THANG UNIVERSITY (84-028) 37 755 057 Feedback
19 Nguyen Huu Tho St. Dist.7, HCM thuvien@tdtu.edu.vn

Copyright © 2017 INSPIRE LIBRARY - TON DUC THANG UNIVERSITY

Searching Remote Databases, Please Wait