Details of Research Outputs

TitleA proximal alternating direction method of multiplier for linearly constrained nonconvex minimization
Author (Name in English or Pinyin)
Date Issued2020
Source PublicationSIAM Journal on Optimization
ISSN10526234
EISSN1095-7189
Volume30Issue:3Pages:2272-2302
AbstractConsider the minimization of a nonconvex differentiable function over a bounded polyhedron. A popular primal-dual 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.
Keywordnonconvex ADMM constrained
DOI10.1137/19M1242276
Indexed BySCIE
language英语
Funding ProjectNSFC [61731018, 61571384]; Peacock project of the Shenzhen Municipal Government
WOS Research AreaMathematics
WOS SubjectMathematics, Applied
WOS IDWOS:000576467300020
PublisherSIAM PUBLICATIONS
Original Document TypeArticle
Firstlevel Discipline信息科学与系统科学
Education discipline科技类
Published range国外学术期刊
Volume Issue Pages卷: 30 期: 3 页: 2272-2302
References
[1] B. P. Ames and M. Hong, Alternating direction method of multipliers for sparse zero-variance discriminant analysis and principal component analysis, Comput. Optim. Appl., 64 (2016), pp. 725-754.
[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. 1-122.
[5] C. Chen, B. He, Y. Ye, and X. Yuan, The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent, Math. Program., 155 (2016), pp. 57-79.
[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. 889-916.
[7] J. Eckstein and D. P. Bertsekas, On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program., 55 (1992), pp. 293-318.
[8] F. Facchinei and J.-S. Pang, Finite-Dimensional 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. 4742-4746.
[11] M. Hong, D. Hajinezhad, and M.-M. Zhao, Prox-PDA: The proximal primal-dual algorithm for fast distributed nonconvex optimization and learning over networks, in Proceedings of the ICML, 2017, pp. 1529-1538.
[12] M. Hong and Z.-Q. Luo, On the linear convergence of the alternating direction method of multipliers, Math. Program., 162 (2017), pp. 165-199.
[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. 337-364.
[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. 883-898.
[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. 2434-2460.
[18] Q. Ling, Y. Xu, W. Yin, and Z. Wen, Decentralized low-rank matrix completion, in Proceedings of ICASSP, 2012, pp. 2925-2928.
[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. 157-178.
[20] J.-S. Pang, A posteriori error bounds for the linearly-constrained variational inequality problem, Math. Oper. Res., 12 (1987), pp. 474-484.
[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 non-negative matrix factorization with the beta-divergence, in Proceedings of ICASSP, 2014, pp. 6201-6205.
[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 SourceWOS
Citation statistics
Cited Times [WOS]:0   [WOS Record]     [Related Records in WOS]
Document TypeJournal article
Identifierhttps://irepository.cuhk.edu.cn/handle/3EPUXD0A/1914
CollectionSchool of Science and Engineering
Library
Corresponding AuthorLUO, Z.-Q.
Affiliation
[1] Shenzhen Research Institute of Big Data, Chinese University of Hong Kong, Shenzhen, Hong Kong
First Author AffilicationShenzhen Research Institute of Big Data
Corresponding Author AffilicationShenzhen 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):2272-2302.
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), 2272-2302.
MLA ZHANG, J.,et al."A proximal alternating direction method of multiplier for linearly constrained nonconvex minimization".SIAM Journal on Optimization 30.3(2020):2272-2302.
Files in This Item:
There are no files associated with this item.
Related Services
Usage statistics
Google Scholar
Similar articles in Google Scholar
[ZHANG, J.]'s Articles
[LUO, Z.-Q.]'s Articles
Baidu academic
Similar articles in Baidu academic
[ZHANG, J.]'s Articles
[LUO, Z.-Q.]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[ZHANG, J.]'s Articles
[LUO, Z.-Q.]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.