• 论文 • 上一篇    下一篇

复合凸优化问题的一个非精确多层梯度镜面下降算法

肖斌, 周芷娟, 胡清洁   

  1. 桂林电子科技大学数学与计算科学学院, 桂林 541004
  • 收稿日期:2020-09-02 出版日期:2021-12-15 发布日期:2021-12-07
  • 通讯作者: 胡清洁,Email:hqj0715@126.com.cn
  • 基金资助:
    国家自然科学基金(11461015,11761014,11961011),广西自然科学基金(2015GXNSFAA139010,2017GXNSFAA198243)资助.

肖斌, 周芷娟, 胡清洁. 复合凸优化问题的一个非精确多层梯度镜面下降算法[J]. 数值计算与计算机应用, 2021, 42(4): 361-378.

Xiao Bin, Zhou Zhijuan, Hu QingJie. AN INEXACT GRADIENT MIRROR DESCENT ALGORITHM FOR COMPOSITE CONVEX OPTIMIZATION[J]. Journal on Numerica Methods and Computer Applications, 2021, 42(4): 361-378.

AN INEXACT GRADIENT MIRROR DESCENT ALGORITHM FOR COMPOSITE CONVEX OPTIMIZATION

Xiao Bin, Zhou Zhijuan, Hu QingJie   

  1. School of Mathematics and Computational Science, Guilin University of Electronic Technology, Guilin 541004, China
  • Received:2020-09-02 Online:2021-12-15 Published:2021-12-07
本文提出一个求解复合凸优化问题的非精确多层梯度镜面下降算法.该算法允许目标函数中光滑部分梯度计算和非光滑部分邻近算子计算都存在误差,在适当条件下分析了该算法函数值误差序列的O(1/k2)收敛速度,这里k表示迭代次数.最后关于Lasso问题和Logistic问题的数值结果表明该算法是有效的.
In this paper, we present an inexact multilevel gradient mirror descent algorithm for composite convex optimization problem under the presence of the errors of gradient calculations of smooth terms and proximity operator calculations of non-smooth terms. The convergence rate of the proposed algorithm is analyzed under mild conditions. Finally, the algorithm is used to solve the lasso and logistic problems, numerical results show the efficiency of the proposed algorithm.

MR(2010)主题分类: 

()
[1] Candès E J. Compressive sampling[C]. Proceedings of the International Congress of Mathematicians, 2006, 3:1433-1452.
[2] Donoho D L. Compressed sensing[J]. IEEE Transactions on Information Theory, 2006, 52(4):1289-1306.
[3] Wright J, Ma Y, Mairal J, et al. Sparse representation for computer vision and pattern recognition[J]. Proceedings of the IEEE, 2010, 98(6):1031-1044.
[4] Wright J, Yang A Y, Ganesh A, et al. Robust face recognition via sparse representation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2008, 31(2):210-227.
[5] Candès E J, Romberg J, Tao T. Robust uncertainty principles:Exact signal reconstruction from highly incomplete frequency information[J]. IEEE Transactions on Information Theory, 2006, 52(2):489-509.
[6] Engl H W, Hanke M, Neubauer A. Regularization of inverse problems[M]. Springer Science and Business Media, 1996.
[7] Chen P, Huang J, Zhang X. A primal dual fixed point algorithm for convex separable minimization with applications to image restoration[J]. Inverse Problems, http://dx.doi.org/10.1088/0266-5611/29/2/025011,2013,29(2).
[8] Hovhannisyan V, Parpas P, Zafeiriou S. MAGMA:Multilevel accelerated gradient mirror descent algorithm for large-scale convex composite minimization[J]. SIAM Journal on Imaging Sciences, 2016, 9(4):1829-1857.
[9] Dong Q, Liu X, Wen Z W, et al. A parallel line search subspace correction method for composite convex optimization[J]. Journal of the Operations Research Society of China, 2015, 3(2):163-187.
[10] Machart P, Anthoine S, Baldassarre L. Optimal computational trade-off of inexact proximal methods[J]. https://arxiv.xilesou.top/pdf/1210.5034.pdf,2012.
[11] Schmidt M, Roux N L, Bach F R. Convergence rates of inexact proximal-gradient methods for convex optimization[C]. Advances in Neural Information Processing Systems, 2011:1458-1466.
[12] Richtárik P, Takáč M. Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function[J]. Mathematical Programming, 2014, 144(1-2):1-38.
[13] Tseng P, Yun S. Block-coordinate gradient descent method for linearly constrained nonsmooth separable optimization[J]. Journal of Optimization Theory and Applications, 2009, 140(3):513-535.
[14] Saha A, Tewari A. On the finite time convergence of cyclic coordinate descent methods[J]. Computer Science, 2010, 23(1):576-601.
[15] Salzo S. The variable metric forward-backward splitting algorithm under mild differentiability assumptions[J]. SIAM Journal on Optimization, 2017, 27(4):2153-2181.
[16] Beck A, Teboulle M. A fast iterative shrinkage-thresholding algorithm for linear inverse problems[J]. SIAM Journal on Imaging Sciences, 2009, 2(1):183-202.
[17] Jiang K, Sun D, Toh K C. An inexact accelerated proximal gradient method for large scale linearly constrained convex SDP[J]. SIAM Journal on Optimization, 2012, 22(3):1042-1064.
[18] Allen-Zhu Z, Orecchia L. Linear coupling:An ultimate unification of gradient and mirror descent[J]. Mathematics, 2014.
[19] Bonettini S, Rebegoldi S, Ruggiero V. Inertial Variable Metric Techniques for the Inexact Forward-Backward Algorithm[J]. SIAM Journal on Scientific Computing, 2018, 40(5):A3180-A3210.
[20] Gu B, Wang D, Huo Z, et al. Inexact proximal gradient methods for non-convex and non-smooth optimization[C]. Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
[21] Nesterov Y. Introductory lectures on convex optimization:A basic course[M]. Springer Science Business Media, 2013.
[22] Daubechies I, Defrise M, De Mol C, et al. An iterative thresholding algorithm for linear inverse problems with a sparsity constraint[J]. Communications on Pure and Applied Mathematics, 2004, 57(11):1413-1457.
[23] Briggs W L. Van Emden Henson, and Steve F. McCormick[J]. A Multigrid Tutorial, 2nd ed., SIAM, Philadelphia.
[24] Tibshirani R. Regression shrinkage and selection via the lasso[J]. Journal of the Royal Statistical Society, 2011, 58(1):267-288.
[25] Fadili J, Peyŕe G. Total variation projection with first order schemes[J]. IEEE Transactions on Image Processing, 2011, 20(3):657-669.
[26] Cai J F, Candès E J and Shen Z. A singular value thresholding algorithm for matrix compeletion[J]. SIAM Journal on Optimization, 2010, 20(4):1956-1982.
[27] Nash S G. A multigrid approach to discretized optimization problems[J]. Optimization Methods and Software, 2000, 14(1):99-116.
[28] Wen Z. Goldfarb D., A line search multigrid method for large-scale nonlinear optimization[J]. SIAM Journal on Optimization, 2009, 20(3):1478-1503.
[29] Panos P. A Multilevel Proximal Gradient Algorithm for a Class of Composite Optimization Problems[J]. SIAM Journal on Scientific Computing, 2017, 39(5):S681-S701.
[1] 刘紫娟, 李慧云, 刘新为. 外推系数带参数的加速邻近梯度算法[J]. 数值计算与计算机应用, 2016, 37(3): 211-222.
阅读次数
全文


摘要