IDEAS home Printed from https://ideas.repec.org/a/spr/joptap/v172y2017i3d10.1007_s10957-017-1061-z.html
   My bibliography  Save this article

Local Convergence Properties of Douglas–Rachford and Alternating Direction Method of Multipliers

Author

Listed:
  • Jingwei Liang

    (Normandie Univ)

  • Jalal Fadili

    (Normandie Univ)

  • Gabriel Peyré

    (DMA, ENS Paris)

Abstract

The Douglas–Rachford and alternating direction method of multipliers are two proximal splitting algorithms designed to minimize the sum of two proper lower semi-continuous convex functions whose proximity operators are easy to compute. The goal of this work is to understand the local linear convergence behaviour of Douglas–Rachford (resp. alternating direction method of multipliers) when the involved functions (resp. their Legendre–Fenchel conjugates) are moreover partly smooth. More precisely, when the two functions (resp. their conjugates) are partly smooth relative to their respective smooth submanifolds, we show that Douglas–Rachford (resp. alternating direction method of multipliers) (i) identifies these manifolds in finite time; (ii) enters a local linear convergence regime. When both functions are locally polyhedral, we show that the optimal convergence radius is given in terms of the cosine of the Friedrichs angle between the tangent spaces of the identified submanifolds. Under polyhedrality of both functions, we also provide conditions sufficient for finite convergence. The obtained results are illustrated by several concrete examples and supported by numerical experiments.

Suggested Citation

  • Jingwei Liang & Jalal Fadili & Gabriel Peyré, 2017. "Local Convergence Properties of Douglas–Rachford and Alternating Direction Method of Multipliers," Journal of Optimization Theory and Applications, Springer, vol. 172(3), pages 874-913, March.
    • Handle: RePEc:spr:joptap:v:172:y:2017:i:3:d:10.1007_s10957-017-1061-z
    DOI: 10.1007/s10957-017-1061-z
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10957-017-1061-z
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10957-017-1061-z?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Walaa M. Moursi & Lieven Vandenberghe, 2019. "Douglas–Rachford Splitting for the Sum of a Lipschitz Continuous and a Strongly Monotone Operator," Journal of Optimization Theory and Applications, Springer, vol. 183(1), pages 179-198, October.
    2. Cesare Molinari & Jingwei Liang & Jalal Fadili, 2019. "Convergence Rates of Forward–Douglas–Rachford Splitting Method," Journal of Optimization Theory and Applications, Springer, vol. 182(2), pages 606-639, August.
    3. Dirk A. Lorenz & Quoc Tran-Dinh, 2019. "Non-stationary Douglas–Rachford and alternating direction method of multipliers: adaptive step-sizes and convergence," Computational Optimization and Applications, Springer, vol. 74(1), pages 67-92, September.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:joptap:v:172:y:2017:i:3:d:10.1007_s10957-017-1061-z. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.