一种求解低秩矩阵最小化问题的非凸分式模型的对称 AＤmm 算法研究

Research on a Symmetric ADMM Algorithm for Solving Nonconvex Fractional Model of Low Rank Matrix Minimization Problems

摘要

鉴于低秩矩阵最小化问题的非凸非连续，本文考虑了一种近似秩函数的非凸分式模型。凭借非凸分式模型的可分性特点，设计了一种对称 AＤmm 算法来求解该模型。区别于传统的 AＤmm，该方法在乘子更新项 Λ^k+1/2 中添加了松弛系数 α，该系数有利于加速算法收敛。在适当的假设条件下，给出了新算法的子序列收敛性和全局收敛性。最后，通过数值实验验证该方法的有效性。

Abstract

Due to the nonconvex and discontinuous properties of the low rank matrix minimization problem, this paper considers a nonconvex fractional model that approximates the rank function. By exploiting the separability structure of the nonconvex fractional model, a symmetric ADMM algorithm is developed to solve this model. Compared to traditional ADMM, this method incorporates a relaxation coefficient α into the multiplier update term Λ^k+1/2, which allows to speed up the convergence of the algorithm. Under suitable assumptions, the subsequential and global convergence of the new algorithm are established. Finally, numerical experiments are performed to verify the effectiveness of the proposed method.

关键词

非凸分式模型 / 对称 AＤmm / 收敛性

Key words

nonconvex fractional model / symmetric ADMM / convergence

参考文献

[1] Cai J F, Candès E J, Shen Z W. A singular value thresholding algorithm for matrix completion[J]. SIAM Journal on Optimization, 2010, 20(4): 1956–1982.

[2] Nie F P, Huang H, Ding C. Low-rank matrix recovery via efficient schatten p-norm minimization[C]//Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence. Toronto, Ontario, Canada, 2012, 26(1): 655–661

[3] Malek-Mohammadi M, Babaie-Zadeh M, Skoglund M. Iterative concave rank approximation for recovering low-rank matrices[J]. IEEE Transactions on Signal Processing, 2014, 62(20): 5213–5226.

[4] Lu C Y, Tang J H, Yan S C, et al. Nonconvex nonsmooth low rank minimization via iteratively reweighted nuclear norm[J]. IEEE Transactions on Image Processing, 2016, 25(2): 829–839.

[5] Li G R, Guo G, Peng S C, et al. Matrix completion via schatten capped p norm[J]. IEEE Transactions on Knowledge and Data Engineering, 2022, 34(1): 394–404.

[6] Xiong Z K, Wei Y M, Xu R J, et al. Low-rank traffic matrix completion with marginal information[J]. Journal of Computational and Applied Mathematics, 2022, 410: 114219.

[7] Fazel M. Matrix rank minimization with applications[D]. Stanford: Stanford University, 2002.

[8] Ma S Q, Goldfarb D, Chen L F. Fixed point and Bregman iterative methods for matrix rank minimization[J]. Mathematical Programming, 2011, 128: 321–353.

[9] Toh K C, Yun S. An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems[J]. Pacific Journal of Optimization, 2010, 6(3): 615–640.

[10] Kuang S F, Chao H Y, Li Q. Majorized proximal alternating imputation for regularized rank constrained matrix completion[J]. Journal of Computational and Applied Mathematics, 2020, 371: 112679.

[11] Candès E J, Recht B. Exact matrix completion via convex optimization[J]. Foundations of Computational Mathematics, 2009, 9(6): 717–772.

[12] Li Y F, Zhang Y J, Huang Z H. A reweighted nuclear norm minimization algorithm for low rank matrix recovery[J]. Journal of Computational and Applied Mathematics, 2014, 263: 338–350.

[13] Phan D N, Nguyen T N. An accelerated IRNN-Iteratively Reweighted Nuclear Norm algorithm for nonconvex nonsmooth low-rank minimization problems [J]. Journal of Computational and Applied Mathematics, 2021, 396: 113602.

[14] Gao K X, Huang Z H, Guo L L. Low-rank matrix recovery problem minimizing a new ratio of two norms approximating the rank function then using an ADMM-type solver with applications [J]. Journal of Computational and Applied Mathematics, 2024, 438: 115564.

[15] 彭建文，雷宏旺. 非凸两分块优化问题的一类惯性对称正则化交替方向乘子法[J].运筹学学报，2023, 27 (3): 37–52

[16] Guo K, Han D R, Wu T T. Convergence of alternating direction method for minimizing sum of two nonconvex functions with linear constraints [J]. International Journal of Computational Mathematics, 2017, 94 (8): 1653–1669.

[17] Bot R I, Nguyen D K. The proximal alternating direction method of multipliers in the non-convex setting: convergence analysis and rates [J]. Mathematics of Operations Research, 2020, 45 (2): 682–712.

[18] Wu Z M, Li M, Wang D Z W, et al. A symmetric alternating direction method of multipliers for separable nonconvex minimization problems [J]. Asia-Pacific Journal of Operational Research, 2017, 34 (6): 1750030.

[19] Wang Y, Yin W T, Zeng J S. Global convergence of ADMM in nonconvex nonsmooth optimization [J]. Journal of Scientific Computing, 2019, 78 (1): 29–63.

[20] Rahimi Y, Wang C, Dong H B, et al. A scale-invariant approach for sparse signal recovery [J]. SIAM Journal on Scientific Computing, 2019, 41 (6): A3649–A3672.

[21] Beck A. First-Order methods in optimization [M]. Philadelphia: SIAM Society for Industrial and Applied Mathematics, 2017.

[22] Wu Z M, Sun K X, Ge Z L, et al. Sparse portfolio optimization l1 via l2 over regularization [J]. European Journal of Operational Research, 2024, 319 (3): 820–833.

[23] Tao M, Zhang X P. Study on over minimization for nonnegative signal recovery [J]. Journal of Scientific Computing, 2023, 95: 94–118.

基金资助

国家自然科学基金资助项目(120081、12471290)

江苏省青蓝工程和大规模复杂系统数值模拟教育部重点实验室开放课题基金资助项目()