Title  A proximal alternating direction method of multiplier for linearly constrained nonconvex minimization 
Author (Name in English or Pinyin)  
Date Issued  2020 
Source Publication  SIAM Journal on Optimization 
ISSN  10526234 
EISSN  10957189 
Volume  30Issue:3Pages:22722302 
Abstract  Consider the minimization of a nonconvex differentiable function over a bounded polyhedron. A popular primaldual first order method for this problem is to perform a gradient projection iteration for the augmented Lagrangian function and then update the dual multiplier vector using the constraint residual. However, numerical examples show that this approach can exhibit oscillation and may not converge. In this paper, we propose a proximal alternating direction method of multipliers for the multiblock version of this problem. A distinctive feature of this method is the introduction of a smoothed (i.e., exponentially weighted) sequence of primal iterates and the inclusion, at each iteration, to the augmented Lagrangian function of a quadratic proximal term centered at the current smoothed primal iterate. The resulting proximal augmented Lagrangian function is inexactly minimized (via a gradient projection step) at each iteration while the dual multiplier vector is updated using the residual of the linear constraints. When the primal and dual stepsizes are chosen sufficiently small, we show that suitable smoothing can stabilize the oscillation, and the iterates of the new proximal ADMM algorithm converge to a stationary point under some mild regularity conditions. The iteration complexity of our algorithm for finding an estationary solution is O(1/epsilon(2)), which improves the best known complexity of o(1/epsilon(3)) for the problem under consideration. Furthermore, when the objective function is quadratic, we establish the linear convergence of the algorithm. Our proof is based on a new potential function and a novel use of error bounds. 
Keyword  nonconvex ADMM constrained 
DOI  10.1137/19M1242276 
Indexed By  SCIE 
language  英语 
Funding Project  NSFC [61731018, 61571384]; Peacock project of the Shenzhen Municipal Government 
WOS Research Area  Mathematics 
WOS Subject  Mathematics, Applied 
WOS ID  WOS:000576467300020 
Publisher  SIAM PUBLICATIONS 
Original Document Type  Article 
Firstlevel Discipline  信息科学与系统科学 
Education discipline  科技类 
Published range  国外学术期刊 
Volume Issue Pages  卷: 30 期: 3 页: 22722302 
References  [1] B. P. Ames and M. Hong, Alternating direction method of multipliers for sparse zerovariance discriminant analysis and principal component analysis, Comput. Optim. Appl., 64 (2016), pp. 725754. [2] D. P. Bertsekas, Nonlinear Programming, Athena Scientific, Belmont, MA, 1999. [3] R. I. Bot and D.K. Nguyen, The Proximal Alternating Direction Method of Multipliers in the Nonconvex Setting: Convergence Analysis and Rates, preprint, https://arxiv.org/abs/1801.01994, 2018. [4] S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, Distributed optimization and Statistical learning via the alternating direction method of multipliers, Found. Trends Mach. learn., 3 (2011), pp. 1122. [5] C. Chen, B. He, Y. Ye, and X. Yuan, The direct extension of ADMM for multiblock convex minimization problems is not necessarily convergent, Math. Program., 155 (2016), pp. 5779. [6] W. Deng and W. Yin, On the global and linear convergence of the generalized alternating direction method of multipliers, J. Sci. Comput., 66 (2016), pp. 889916. [7] J. Eckstein and D. P. Bertsekas, On the DouglasRachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program., 55 (1992), pp. 293318. [8] F. Facchinei and J.S. Pang, FiniteDimensional Variational Inequalities and Complementarity Problems, Springer, New York, 2007. [9] W. Gao, D. Goldfarb, and F. E. Curtis, ADMM for Multiaffine Constrained Optimization, preprint, https://arxiv.org/abs/1802.09592, 2018. [10] D. Hajinezhad, T.H. Chang, X. Wang, Q. Shi, and M. Hong, Nonnegative matrix factorization using admm: Algorithm and convergence analysis, in ICASSP, 2016, pp. 47424746. [11] M. Hong, D. Hajinezhad, and M.M. Zhao, ProxPDA: The proximal primaldual algorithm for fast distributed nonconvex optimization and learning over networks, in Proceedings of the ICML, 2017, pp. 15291538. [12] M. Hong and Z.Q. Luo, On the linear convergence of the alternating direction method of multipliers, Math. Program., 162 (2017), pp. 165199. [13] M. Hong, Z.Q. Luo, and M. Razaviyayn, Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems, SIAM J. Optim., 26 (2016), pp. 337364. [14] B. Jiang, T. Lin, S. Ma, and S. Zhang, Structured Nonconvex and Nonsmooth Optimization: Algorithms and Iteration Complexity Analysis, preprint, https://arxiv.org/abs/1605. 02408, 2016. [15] B. Jiang, S. Ma, and S. Zhang, Alternating direction method of multipliers for real and complex polynomial optimization models, Optimization, 63 (2014), pp. 883898. [16] W. Kong, J. G. Melo, and R. D. Monteiro, Complexity of a Quadratic Penalty Accelerated Inexact Proximal Point Method for Solving Linearly Constrained Nonconvex Composite Programs, preprint, https://arxiv.org/abs/1802.03504, 2018. [17] G. Li and T. K. Pong, Global convergence of splitting methods for nonconvex composite optimization, SIAM J. Optim., 25 (2015), pp. 24342460. [18] Q. Ling, Y. Xu, W. Yin, and Z. Wen, Decentralized lowrank matrix completion, in Proceedings of ICASSP, 2012, pp. 29252928. [19] Z.Q. Luo and P. Tseng, Error bounds and convergence analysis of feasible descent methods: A general approach, Ann. Oper. Res., 46 (1993), pp. 157178. [20] J.S. Pang, A posteriori error bounds for the linearlyconstrained variational inequality problem, Math. Oper. Res., 12 (1987), pp. 474484. [21] R. T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, NJ, 2015. [22] D. L. Sun and C. Fevotte, Alternating direction method of multipliers for nonnegative matrix factorization with the betadivergence, in Proceedings of ICASSP, 2014, pp. 62016205. [23] Z. Wen, X. Peng, X. Liu, X. Sun, and X. Bai, Asset Allocation Under the Basel Accord Risk Measures, preprint, https://arxiv.org/abs/1308.1321, 2013. [24] Z. Wen, C. Yang, X. Liu, and S. Marchesini, Alternating direction methods for classical and ptychographic phase retrieval, Inverse Problems, 28 (2012), 115010. [25] Y. Zhang, An Alternating Direction Algorithm for Nonnegative Matrix Factorization, preprint, 2010. 
Data Source  WOS 
Citation statistics 
Cited Times [WOS]:0
[WOS Record]
[Related Records in WOS]

Document Type  Journal article 
Identifier  https://irepository.cuhk.edu.cn/handle/3EPUXD0A/1914 
Collection  School of Science and Engineering Library 
Corresponding Author  LUO, Z.Q. 
Affiliation  [1] Shenzhen Research Institute of Big Data, Chinese University of Hong Kong, Shenzhen, Hong Kong 
First Author Affilication  Shenzhen Research Institute of Big Data 
Corresponding Author Affilication  Shenzhen Research Institute of Big Data 
Recommended Citation GB/T 7714  ZHANG, J.,LUO, Z.Q. A proximal alternating direction method of multiplier for linearly constrained nonconvex minimization[J]. SIAM Journal on Optimization,2020,30(3):22722302. 
APA  ZHANG, J., & LUO, Z.Q. (2020). A proximal alternating direction method of multiplier for linearly constrained nonconvex minimization. SIAM Journal on Optimization, 30(3), 22722302. 
MLA  ZHANG, J.,et al."A proximal alternating direction method of multiplier for linearly constrained nonconvex minimization".SIAM Journal on Optimization 30.3(2020):22722302. 
Files in This Item:  
There are no files associated with this item. 
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment