非凸多分块优化部分对称正则化交替方向乘子法
A Partially Symmetric Regularized Alternating Direction Method of Multipliers for Nonconvex Multi-block Optimization
交替方向乘子法求解两分块优化的研究已逐渐成熟和完善,但对于非凸多分块优化的研究相对较少.本文提出带线性约束的非凸多分块优化的部分对称正则化交替方向乘子法.首先,在适当的假设条件下,包括部分对称乘子修正中参数的估值区域,证明了算法的全局收敛性.其次,当增广拉格朗日函数满足Kurdyka-Lojasiewicz(KL)性质时,证明了算法的强收敛性.当KL性质关联函数具有特殊结构时,保证了算法的次线性和线性收敛率.最后,对算法进行了初步数值试验,结果表明算法的数值有效性.
The researches on the alternating direction method of multiplier method (ADMM) for solving two-block optimization have been gradually mature and perfect. However, the studies on ADMM for solving nonconvex multi-block optimization are relatively few. In this paper, we first propose a partially symmetric regularized ADMM for nonconvex multi-block optimization with linear constraints. Second, under appropriate assumptions including the region of the two parameters in the updating formulas for the multiplier, the global convergence of the proposed method is proved. Third, when the augmented Lagrangian function satisfies the Kurdyka-Lojasiewicz (KL) property, the strong convergence of the method is proved. Furthermore, when the associated KL property function has a special structure, the sublinear and linear convergence rate of the method are obtained. Finally, some preliminary numerical experiments are carried out, and this shows that the proposed method is numerically effective.
多分块优化 / 非凸优化 / 交替方向乘子法 / Kurdyka-Lojasiewicz性质 / 收敛率 {{custom_keyword}} /
multi-block optimization / nonconvex optimization / alternating direction method of multipliers / Kurdyka-Lojasiewicz property / convergence rate {{custom_keyword}} /
[1] Attouch H., Bolte J., On the convergence of the proximal algorithm for nonsmooth functions involving analytic features, Math. Program., 2009, 116(1-2):5-16.
[2] Bai J., Liang J., Guo K., et al., Accelerated symmetric ADMM and its applications in signal processing, arXiv:1906.12015, 2019.
[3] Bolte J., Daniilidis A., Lewis A., The Lojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems, SIAM J. Optim., 2007, 17(4):1205-1223.
[4] 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, 31:1-122.
[5] Candès E., Li X., Ma Y., et al., Robust principal component analysis? J. ACM, 2011, 58(3):1-37.
[6] Chao M., Cheng C., Zhang H., A linearized alternating direction method of multipliers with substitution procedure, Asia Pac. J. Oper. Res., 2015, 32(3):1550011.
[7] Chao M., Deng Z., Jian J., Convergence of linear Bregman ADMM for nonconvex and nonsmooth problems with nonseparable structure, Complexity, 2020, 6237942.
[8] Chao M., Zhang Y., Jian J., An inertial proximal alternating direction method of multipliers for nonconvex optimization, Int. J. Comput. Math., https://doi.org/10.1080/00207160.2020.1812585, 2020.
[9] Chen C., He B., Ye Y., et al., The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent, Math. Program., 2016, 155(1-2):57-79.
[10] Chen C., Some notes on the divergence example for multi-block alternating direction method of multipliers (in Chinese), Oper. Res. Trans., 2019, 23(3):135-140.
[11] Daubechies I., Defrise M., De Mol C., An iterative thresholding algorithm for linear inverse problems with a sparsity constraint, Commun. Pure Appl. Math., 2003, 57(11):1413-1457.
[12] Douglas J., Rachford Jr.H.H., On the numerical solution of the heat conduction problem in two and three space variables, Trans. Amer. Math. Soc., 1956, 82(2):421-439.
[13] Glowinski R., Numerical Methods for Nonlinear Variational Problems, Springer-Verlag, New York, 1984.
[14] Gu Y., Jiang B., Han D., A semi-proximal-based strictly contractive Peaceman-Rachford splitting method, arXiv:1506.02221, 2015.
[15] Guo K., Han D., Wang D., et al., Convergence of ADMM for multi-block nonconvex separable optimization models, Front. Math. China, 2017, 12(5):1139-1162.
[16] Guo K., Han D., Wu T., Convergence of alternating direction method for minimizing sum of two nonconvex functions with linear constraints, Int. J. Comput. Math., 2017, 94(8):1653-1669.
[17] Han D., Yuan X., A note on the alternating direction method of multipliers, J. Optim. Theory Appl., 2012, 155(1):227-238.
[18] Han D., Yuan X., Local linear convergence of the alternating direction method of multipliers for quadratic programs, SIAM J. Numer. Anal., 2013, 51(6):3446-3457.
[19] He B., Parallel splitting augmented Lagrangian methods for monotone structured variational inequalities, Comput. Optim. Appl., 2009, 42(2):195-212.
[20] He B., Ma F., Yuan X., Convergence study on the symmetric version of ADMM with larger step sizes, SIAM J. Imaging Sci., 2016, 9(3):1467-1501.
[21] He B., Tao M., Yuan X., Alternating direction method with Gaussian back substitution for separable convex programming, SIAM J. Optim., 2012, 22(2):313-340.
[22] He B., Tao M., Yuan X., A splitting method for separable convex programming, IMA J. Numer. Anal., 2015, 35(1):394-426.
[23] He B., Yuan X., Linearized alternating direction method with Gaussian back substitution for separable convex programming, Numer. Algebr. Control Optim., 2013, 3(2):247-260.
[24] Jian J., Zhang Y., Chao M., A regularized alternating direction method of multipliers for a class of nonconvex problems, J. Inequal. Appl., 2019, 2019(1):193.
[25] Li Z., Dai Y., Optimal beamformer design in the reverberant environment (in Chinese), Sci. Sin. Math., 2016, 46(06):877-892.
[26] Liu M., Jian J., An ADMM-based SQP method for separably smooth nonconvex optimization, J. Inequal. Appl., 2020, 2020:81.
[27] Lions P., Mercier B., Splitting algorithms for the sum of two nonlinear operators, SIAM J. Numer. Anal., 1979, 16(6):964-979
[28] Nesterov Y., Introductory Lectures on Convex Optimization:A Basic Course, Springer Science & Business Media, Boston, 2013.
[29] Peaceman D., Rachford H., The numerical solution of parabolic and elliptic differential equations, J. Soci. Ind. Appl. Math., 1955, 3(1):28-41.
[30] Rockafellar R., Wets R., Variational Analysis, Springer Science & Business Media, Berlin, 2009.
[31] Wang F., Cao W., Xu Z., Convergence of multi-block Bregman ADMM for nonconvex composite problems, Sci. China Inform. Sci., 2018, 61(12):122101.
[32] Wang F., Xu Z., Xu H., Convergence of Bregman alternating direction method with multipliers for nonconvex composite problems, arXiv:1410.8625, 2014.
[33] Wang Y., Fan S., Weighted l1-norm constrained sparse regularization and alternating directions method of multipliers for seismic time-frequency analysis (in Chinese), Sci. Sin. Math., 2018, 48(03):457-470.
[34] Wu Z., Li M., Wang D., Han D., A symmetric alternating direction method of multipliers for separable nonconvex minimization problems, Asia Pac. J. Oper. Res., 2017, 34(06):1750030.
[35] Xu Z., Chang X., Xu F., et al., l1/2 regularization:a thresholding representation theory and a fast solver, IEEE T. Neur. Net. Lear., 2012, 23(7):1013-1027.
[36] Yang L., Luo J., Xu Y., et al., A distributed dual consensus ADMM based on partition for DC-DOPF with carbon emission trading, IEEE T. Ind. Inform., 2020, 16(3):1858-1872.
[37] Yang W., Han D., Linear convergence of the alternating direction method of multipliers for a class of convex optimization problems, SIAM J. Numer. Anal., 2016, 54(2):625-640.
[38] Zeng J., Fang J., Xu Z., Sparse SAR imaging based on l1/2 regularization, Sci. China Inform. Sci., 2012, 55:1755-1775.
[39] Zhu M., Mihic K., Ye Y., On a randomized multi-block ADMM for solving selected machine learning problems, arXiv:1907.01995, 2019.
国家自然科学基金(11771383);广西自然科学基金(2020GXNSFDA238017,2018GXNSFFA281007)
/
〈 | 〉 |