logo

SCIENCE CHINA Information Sciences, Volume 61, Issue 12: 122101(2018) https://doi.org/10.1007/s11432-017-9367-6

Convergence of multi-blockBregman ADMM for nonconvex composite problems

More info
  • ReceivedSep 12, 2017
  • AcceptedFeb 26, 2018
  • PublishedJun 21, 2018

Abstract

The alternating direction method with multipliers (ADMM) isone of the most powerful and successful methods for solving variouscomposite problems. The convergence of the conventional ADMM (i.e.,2-block) for convex objective functions has been stated for along time, and its convergence for nonconvex objective functionshas, however, been established very recently. The multi-block ADMM,a natural extension of ADMM, is a widely used scheme and has alsobeen found very useful in solving various nonconvex optimizationproblems. It is thus expected to establish the convergence ofthe multi-block ADMM under nonconvex frameworks. In this paper, wefirst justify the convergence of 3-block Bregman ADMM.We next extend these results to the $N$-block case ($N~\geq~3$),which underlines the feasibility of multi-block ADMM applications innonconvex settings. Finally, we present a simulation study and areal-world application to support the correctness of the obtainedtheoretical assertions.


Acknowledgment

This work was supported by National Natural Science Foundation of China (Grant No. 61603235), and Program for Science and Technology Innovation Talents in Universities of Henan Province (Grant No. 15HASTIT013). We thank all anonymous reviewers for their thoughtful and constructive comments that greatly improve the analysis and writing of the manuscript.


References

[1] Boyd S, Parikh N, Chu E, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers. Found Trends Mach Learn, 2011, 3: 1--122. Google Scholar

[2] Wang H, Banerjee A. Bregman alternating direction method of multipliers. In: Proceedings of Advances in Neural Information Processing Systems (NIPS), Montréal, 2014. 2816--2824. Google Scholar

[3] Gabay D, Mercier B. A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Comput Math Appl, 1976, 2: 17-40 CrossRef Google Scholar

[4] Alcouffe A, Enjalbert M, Muratet G. Méthodes de résolution du problème de transport et de production d'une entreprise à établissements multiples en présence de co?ts fixes. RAIRO Recherche opérationnelle, 1975, 9: 41-55 CrossRef Google Scholar

[5] He B, Yuan X. On the $O(1/n)$ Convergence Rate of the Douglas-Rachford Alternating Direction Method. SIAM J Numer Anal, 2012, 50: 700-709 CrossRef Google Scholar

[6] Goldstein T, O'Donoghue B, Setzer S. Fast Alternating Direction Optimization Methods. SIAM J Imag Sci, 2014, 7: 1588-1623 CrossRef Google Scholar

[7] Xu Y, Yin W, Wen Z. An alternating direction algorithm for matrix completion with nonnegative factors. Front Math China, 2012, 7: 365-384 CrossRef Google Scholar

[8] Bolte J, Sabach S, Teboulle M. Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Math Program, 2014, 146: 459-494 CrossRef Google Scholar

[9] Xu Y, Yin W. A Block Coordinate Descent Method for Regularized Multiconvex Optimization with Applications to Nonnegative Tensor Factorization and Completion. SIAM J Imag Sci, 2013, 6: 1758-1789 CrossRef Google Scholar

[10] Hong M, Luo Z Q, Razaviyayn M. Convergence Analysis of Alternating Direction Method of Multipliers for a Family of Nonconvex Problems. SIAM J Optim, 2016, 26: 337-364 CrossRef Google Scholar

[11] Li G, Pong T K. Global Convergence of Splitting Methods for Nonconvex Composite Optimization. SIAM J Optim, 2015, 25: 2434-2460 CrossRef Google Scholar

[12] Wang F, Xu Z, Xu H. Convergence of bregman alternating direction method with multipliers for nonconvex composite problems,. arXiv Google Scholar

[13] Chen C, He B, Ye Y. The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent. Math Program, 2016, 155: 57-79 CrossRef Google Scholar

[14] Han D, Yuan X. A Note on the Alternating Direction Method of Multipliers. J Optim Theor Appl, 2012, 155: 227-238 CrossRef Google Scholar

[15] Cai X, Han D, Yuan X. On the convergence of the direct extension of ADMM for three-block separable convex minimization models with one strongly convex function. Comput Optim Appl, 2017, 66: 39-73 CrossRef Google Scholar

[16] Li M, Sun D, Toh K C. A Convergent 3-Block Semi-Proximal ADMM for Convex Minimization Problems with One Strongly Convex Block. Asia Pac J Oper Res, 2015, 32: 1550024 CrossRef Google Scholar

[17] Mordukhovich B. Variational Analysis And Generalized Differentiation I: Basic Theory. Berlin: Springer, 2006. 30--35. Google Scholar

[18] Lojasiewicz S. Une propriété topologique des sous-ensembles analytiques réels. Les équations aux dérivées partielles, 1963, 117: 87--89. Google Scholar

[19] Kurdyka K. On gradients of functions definable in o-minimal structures. Annales de l'institut Fourier, 1998, 48: 769-783 CrossRef Google Scholar

[20] Attouch H, Bolte J, Svaiter B F. Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods. Math Program, 2013, 137: 91-129 CrossRef Google Scholar

[21] Si Si , Dacheng Tao , Bo Geng . Bregman Divergence-Based Regularization for Transfer Subspace Learning. IEEE Trans Knowl Data Eng, 2010, 22: 929-942 CrossRef Google Scholar

[22] Wu L, Hoi S C H, Jin R. Learning Bregman Distance Functions for Semi-Supervised Clustering. IEEE Trans Knowl Data Eng, 2012, 24: 478-491 CrossRef Google Scholar

[23] Zongben Xu , Xiangyu Chang , Fengmin Xu . L1/2 regularization: a thresholding representation theory and a fast solver.. IEEE Trans Neural Netw Learning Syst, 2012, 23: 1013-1027 CrossRef PubMed Google Scholar

[24] Behmardi B, Raich R. On provable exact low-rank recovery in topic models. In: Proceedings of IEEE Statistical Signal Processing Workshop (SSP), Nice, 2011. 265--268. Google Scholar

[25] Xu H, Caramanis C, Mannor S. Outlier-Robust PCA: The High-Dimensional Case. IEEE Trans Inform Theor, 2013, 59: 546-572 CrossRef Google Scholar

[26] Zeng J, Xu Z, Zhang B. Accelerated regularization based SAR imaging via BCR and reduced Newton skills. Signal Processing, 2013, 93: 1831-1844 CrossRef Google Scholar

  • Figure 1

    (Color online) Convergence results for (a) the noiseless case and (b) Gaussian noise with the standard deviation $\sigma=0.01$.

  • Figure 2

    Background subtraction results in the real-world video clips. (a) Lobby; (b) Bootstrap; (c) Hall; (d) ShoppingMall.

  •   
    (ttr ttspr $\text{RelErr}$ $\text{Rank}({L}^{*})$ $\text{Rank}(\hat{L})$ $\|{S}^{*}\|_0$ $\|\hat{S}\|_0$
    Noiseless case ($\sigma=~0$)(1, 0.05) 4.8674E$-$06 1 1500500
    (1, 0.1) 5.0446E$-$06 1 1 10001000
    (5, 0.05) 2.2342E$-$06 5 5500500
    (5, 0.1) 2.4366E$-$0655 1000 1000
    (10, 0.05) 1.5039E$-$06 1010 500 500
    (10, 0.1) 1.8572E$-$0610 10 10001000
    (20, 0.05) 1.2889E$-$06 20 20500500
    (20, 0.1) 1.6974E$-$0620 20 10001000
    Gauss noise $(\sigma=~0.01)$(1, 0.05) 0.0049 1 15001723
    (1, 0.1) 0.0060 1 1 10003797
    (5, 0.05) 0.00255 55001541
    (5, 0.1) 0.0033 55 1000 3551
    (10, 0.05) 0.0022 1010 500 1318
    (10, 0.1) 0.0024 10 10 10003183
    (20, 0.05) 0.0020 20 205001110
    (20, 0.1) 0.0024 20 20 10003612

Copyright 2019 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1