求解结构型凸优化问题的一种算法改进
An Improved Algorithm for Solving Structural Convex Optimization Problems
摘要: 本文考虑一个求解结构型凸优化问题的新算法——带随机步长的并行分裂ADMM下降算法，它是基于并行分裂ADMM下降算法和改善步长的收缩算法产生的。新算法改变了步长和更新公式，同时利用服从独立同分布的随机数来扩张步长，提高了ADMM下降算法中因固定步长因子带来的收敛较慢的结果。然后在适当的条件下，证明了该方法是依概率收敛的。最后，通过对来自金融和统计中的一类问题进行的一系列数值实验，验证了新算法的高效性。
Abstract: This paper considers a new algorithm for solving structural convex optimization problems: parallel split ADMM descent algorithm with random step size, which is based on parallel split ADMM descent algorithm and shrinkage algorithm with improved step size. The new algorithm changes the step size and updates formula, and expands the step size by using random numbers subject to independent and identically distributed, which improves the slow convergence result caused by fixed step size factor in ADMM descent algorithm. Then, under appropriate conditions, it is proved that the method converges according to probability. Finally, a series of numerical experiments on a class of problems from finance and statistics verify the efficiency of the new algorithm.
文章引用：张宇婷, 李锋. 求解结构型凸优化问题的一种算法改进[J]. 应用数学进展, 2021, 10(12): 4352-4364. https://doi.org/10.12677/AAM.2021.1012463

参考文献

[1] Glowinski, R. and Marroco, A. (1975) Sur l’approximation, par éléments finis d’ordre un, et la résolution, par pénalisation-dualité d’une classe de problèmes de Dirichlet non linéaires. ESAIM: Mathematical Modelling and Numerical Analysis, 9, 41-76. [Google Scholar] [CrossRef] 
[2] Gabay, D. and Mercier, B. (1976) A Dual Algorithm for the Solution of Nonlinear Variational Problems via Finite Element Approximations. Computers and Mathematics with Applications, 2, 17-40. [Google Scholar] [CrossRef] 
[3] Li, G.Y. and Pong, T.K. (2015) Global Convergence of Splitting Methods for Nonconvex Composite Optimization. SIAM Journal on Optimization, 25, 2434-2460. [Google Scholar] [CrossRef] 
[4] Betts, J.T. (1978) A Gradient Projection-Multiplier Method for Nonlinear Programming. Journal of Optimization Theory and Applications, 24, 523-548. [Google Scholar] [CrossRef] 
[5] Root, R.R. and Ragsdell, K.M. (1980) On the Relationship between a Continuous Update Method of Multipliers and the Generalized Reduced Gradient Method. International Journal for Numerical Methods in Engineering, 15, 1735-1745. [Google Scholar] [CrossRef] 
[6] Hestenes, M.R. (1969) Multiplier and Gradient Methods. Journal of Optimization Theory & Applications, 4, 303-320. [Google Scholar] [CrossRef] 
[7] Cai, X.J., Gu, G.Y., He, B.S., et al. (2013) A Proximal Point Algorithm Revisit on the Alternating Direction Method of Multipliers. Science China Mathematics, 56, 2179-2186. [Google Scholar] [CrossRef] 
[8] Giselsson, P. and Boyd, S. (2014) Linear Convergence and Metric Selection for Douglas-Rachford Splitting and ADMM. IEEE Transactions on Automatic Control, 62, 532-544. [Google Scholar] [CrossRef] 
[9] Cai, X.J., Gu, G.Y., He, B.S., et al. (2011) A Relaxed Customized Proximal Point Algorithm for Separable Convex Programming. Optimization.
[10] He, B.S. and Yuan, X.M. (2012) On the O(1/n) Convergence Rate of the Douglas-Rachford Alternating Direction Method. SIAM Journal on Numerical Analysis, 50, 700-709. [Google Scholar] [CrossRef] 
[11] Boyd, S., Parikh, N., Chu, E., et al. (2011) Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers. Foundations and Trends® in Machine Learning, 3, 1-122. [Google Scholar] [CrossRef] 
[12] He, B.S. and Yuan, X.M. (2015) On Non-Ergodic Convergence Rate of Douglas-Rachford Alternating Direction Method of Multipliers. Numerische Mathematik, 130, 567-577. [Google Scholar] [CrossRef] 
[13] He, B.S., Yang, H. and Wang, S.L. (2000) Alternating Direction Method with Self-Adaptive Penalty Parameters for Monotone Variational Inequalities. Journal of Optimization Theory & Applications, 106, 337-356. [Google Scholar] [CrossRef] 
[14] Gabay, D. and Mercier, B. (1976) A Dual Algorithm for the Solution of Nonlinear Variational Problems via Finite Element Approximations. Computers and Mathematics with Applications, 2, 17-40. [Google Scholar] [CrossRef] 
[15] Shi, W., Ling, Q., Yuan, K., et al. (2014) On the Linear Convergence of the ADMM in Decentralized Consensus Optimization. IEEE Transactions on Signal Processing, 62, 1750-1761. [Google Scholar] [CrossRef] 
[16] Cao, J., Liu, S., Liu, H., et al. (2021) MRI Reconstruction Based on Bayesian Group Sparse Representation. Signal Processing, 187, Article ID: 108151. [Google Scholar] [CrossRef] 
[17] Du, S., Shi, Y., Hu, W., et al. (2020) Robust Tensor Factorization for Color Image and Grayscale Video Recovery. IEEE Access, 8, 174410-174423. [Google Scholar] [CrossRef] 
[18] Chan, S.H. (2019) Performance Analysis of Plug-and-Play ADMM: A Graph Signal Processing Perspective. IEEE Transactions on Computational Imaging, Volume number, 1-20.
[19] Bai, J., Liang, J., Guo, K., et al. (2021) Accelerated Symmetric ADMM and Its Applications in Large-Scale Signal Processing.
[20] Yue, H., Chi, E.C. and Allen, G.I. (2016) ADMM Algorithmic Regularization Paths for Sparse Statistical Machine Learning. Springer International Publishing, Berlin.
[21] Ye, C.H. and Yuan, X.M. (2007) A Descent Method for Structured Monotone Variational Inequalities. Optimization Methods and Software, 22, 329-338. [Google Scholar] [CrossRef] 
[22] He, B.S. (2009) Parallel Splitting Augmented Lagrangian Methods for Monotone Structured Variational Inequalities. Computational Optimization and Applications, 42, 195-212. [Google Scholar] [CrossRef] 
[23] Xu, H.W. (2011) A Contraction Method with Random Step Size for a Class of Variational Inequalities. Chinese Journal of Engineering Mathematics, 28, 461-469.
[24] He, B.S., Liao, L.Z., Han, D.R., et al. (2002) A New Inexact Alternating Directions Method for Monotone Variational Inequalities. Mathematical Programming, 92, 103-118. [Google Scholar] [CrossRef] 
[25] He, B.S., Liao, L.Z. and Wang, X.F. (2012) Proximal-Like Contraction Methods for Monotone Variational Inequalities in a Unified Framework I: Effective Quadruplet and Primary Methods. Computational Optimization and Applications, 51, 649-679. [Google Scholar] [CrossRef] 
[26] Tao, M. and Yuan, X.M. (2012) On the O(1/t) Convergence Rate of Alternating Direction Method with Logarithmic-Quadratic Proximal Regularization. SIAM Journal on Optimization, 22, 1431-1448. [Google Scholar] [CrossRef] 
[27] 林正炎, 等. 概率极限理论基础[M]. 北京: 高等教育出版社, 2003.
[28] 何炳生. 凸优化的一阶分裂算法——变分不等式为工具的统一框架[EB/OL]. http://math.nju.edu.cn/-hebma

为你推荐