大规模可分凸优化问题的非精确自适应步随机原始对偶算法
Inexact Adaptive Stochastic Primal-DualAlgorithm for Large Scale SeparableConvex Optimization Problems
摘要: 本文研究了可分优化问题，针对其目标函数的可分性，分裂算法将目标函数分解成更小、 更容易 处理的子问题, 如原始对偶混合梯度算法。 本文探讨了目标函数的邻近算子的非精确求解策略，并 基于此提出了一个非精确自适应步随机原始对偶算法。 我们分析了误差序列选取方式对算法收敛 速率的影响，发现不同的误差序列选择会导致算法在收敛速度和稳定性方面表现出显著的差异。 此外，该算法在实际应用中也展现出了更高的效率和灵活性。
Abstract: The separable optimization problem refers to optimizing an objective function with a separable structure. Splitting algorithms address this characteristic by breaking down the objective function into smaller, more manageable subproblems, such as the primal-dual hybrid gradient algorithm. We explore the approximate solution strat- egy of the objective function's proximal operator and propose an inexact adaptive stochastic primal-dual algorithm. We analyze the impact of the selection of error se- quences on the convergence rate of the algorithm and find that different selections of error sequences can lead to significant differences in convergence speed and stability. In addition, this algorithm has also demonstrated higher efficiency and exibility in practical applications.
文章引用：周晓艳. 大规模可分凸优化问题的非精确自适应步随机原始对偶算法[J]. 理论数学, 2024, 14(4): 399-415. https://doi.org/10.12677/PM.2024.144148

参考文献

[1] Chambolle, A. and Pock, T. (2011) A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging. Journal of Mathematical Imaging and Vision, 40, 120-145.
https://doi.org/10.1007/s10851-010-0251-1
[2] Chambolle, A. and Pock, T. (2016) An Introduction to Continuous Optimization for Imaging. Acta Numerica, 25, 161-319.
https://doi.org/10.1017/S096249291600009X
[3] Jiu, M. and Pustelnik, N. (2021) A Deep Primal-Dual Proximal Network for Image Restoration. IEEE Journal of Selected Topics in Signal Processing, 15, 190-203.
https://doi.org/10.1109/JSTSP.2021.3054506
[4] Chen, S., Halimi, A., Ren, X., et al. (2020) Learning Non-Local Spatial Correlations to Restore Sparse 3D Single-Photon Data. IEEE Transactions on Image Processing, 29, 3119-3131.
https://doi.org/10.1109/TIP.2019.2957918
[5] Goldstein, T., Li, M. and Yuan, X. (2015) Adaptive Primal-Dual Splitting Methods for Sta- tistical Learning and Image Processing. In: Cortes, C., Lawrence, N., Lee, D., Sugiyama, M. and Garnett, R., Eds., Advances in Neural Information Processing Systems, Vol. 28.
[6] Eckstein, J. and Bertsekas, D.P. (1992) On the Douglas|Rachford Splitting Method and the Proximal Point Algorithm for Maximal Monotone Operators. Mathematical Programming, 55, 293-318.
https://doi.org/10.1007/BF01581204
[7] Rasch, J. and Chambolle, A. (2020) Inexact First-Order Primal-Dual Algorithms. Computa- tional Optimization and Applications, 76, 381-430.
https://doi.org/10.1007/s10589-020-00186-y
[8] Ng, M.K., Wang, F. and Yuan, X. (2011) Inexact Alternating Direction Methods for Image Recovery. Siam Journal on Scientific Computing, 33, 1643-1668.
https://doi.org/10.1137/100807697
[9] Villa, S., Salzo, S., Baldassarre, L., et al. (2013) Accelerated and Inexact Forward-Backward Algorithms. Society for Industrial and Applied Mathematics, 23, 1607-1633.
https://doi.org/10.1137/110844805
[10] Salzo, S. and Villa, S. (2012) Inexact and Accelerated Proximal Point Algorithms. Journal of Convex Analysis, 19, 1167-1192.
[11] Lin, H., Mairal, J. and Harchaoui, Z.O. (2017) Catalyst Acceleration for First-Order Convex Optimization: From Theory to Practice. Machine Learning Research, 18, 7854-7907.
[12] Lin, H., Mairal, J. and Harchaoui, Z. (2015) A Universal Catalyst for First-Order Optimization. Advances in Neural Information Processing Systems, 28, 3384-3392.
[13] Xie, Z. (2017) A Primal-Dual Method with Linear Mapping for a Saddle Point Problem in Image Deblurring. Journal of Visual Communication and Image Representation, 42, 112-120.
https://doi.org/10.1016/j.jvcir.2016.11.011
[14] Schmidt, M., Roux, N.L. and Bach, F.R. (2011) Convergence Rates of Inexact Proximal- Gradient Methods for Convex Optimization. Curran Associates Inc., Red Hook, 1458-1466.
[15] Beck, A. (2017) First-Order Methods in Optimization. SIAM, Philadelphia, 269-304.
[16] Aujol, J.F. and Dossal, C. (2015) Stability of Over-Relaxations for the Forward-Backward Algorithm Application to FISTA. SIAM Journal on Optimization, 25, 2408-2433.
https://doi.org/10.1137/140994964
[17] Beck, A. and Teboulle, M. (2009) A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems. SIAM Journal on Imaging Sciences, 2, 183-202.
https://doi.org/10.1137/080716542

为你推荐