求解大型最小二乘问题的混合贪婪随机坐标下降法

doi:10.12286/jssx.j2022-0943

计算数学 ›› 2023, Vol. 45 ›› Issue (2): 230-239.DOI: 10.12286/jssx.j2022-0943

求解大型最小二乘问题的混合贪婪随机坐标下降法

谢亚君

福州外语外贸学院, 大数据学院 & 数据科学与智能计算重点实验室, 福州, 350202

收稿日期:2022-05-10 出版日期:2023-05-14 发布日期:2023-05-13
基金资助:
福建省自然科学基金面上项目(2022J01378)和福建省重大教改项目 (FBJG20200310)资助.

PDF ( 92 ) 引用

谢亚君. 求解大型最小二乘问题的混合贪婪随机坐标下降法[J]. 计算数学, 2023, 45(2): 230-239.

Xie Yajun. HYBRID GREEDY RANDOMIZED COORDINATE DESCENT METHOD FOR SOLVING LARGE-SCALE LINEAR LEAST SQUARE PROBLEM[J]. Mathematica Numerica Sinica, 2023, 45(2): 230-239.

HYBRID GREEDY RANDOMIZED COORDINATE DESCENT METHOD FOR SOLVING LARGE-SCALE LINEAR LEAST SQUARE PROBLEM

Xie Yajun

School of Big Data & Key Laboratory of Data Science and Intelligent Computing, Fuzhou University of International Studies and Trade, Fuzhou 350202, China

Received:2022-05-10 Online:2023-05-14 Published:2023-05-13

线性最小二乘问题是科学计算与工程领域普遍存在的问题, 有着广泛的应用背景. 本文提出了两个新的贪婪随机坐标下降算法来求解大规模的线性最小二乘问题. 理论上分析了算法的收敛性. 数值实验结果进一步表明了算法的可行性和有效性.

关键词： 线性最小二乘问题, 贪婪随机坐标下降法, 两步混合加速策略, 数值实验

Linear least square problem is a universal problem in scientific computing and engineering field which has a wide application background. In this paper, two new greedy random coordinate descent algorithms are proposed to solve large-scale linear least square problem. The convergence of algorithm is analyzed theoretically in details. Numerical tests further verify the feasibility and efficiency of the two algorithms.

Key words: linear least square problem, greedy randomized coordinate descent, strategy of two-step hybrid accelerated version, numerical tests

MR(2010)主题分类:

33F99

分享此文:

[1] Bai Z Z, Wu W T. On greedy randomized coordinate descent methods for solving large linear least-squares problems[J]. Numer. Linear Algebra Appl., 2019, 26:e2237.
[2] Bai Z Z, Wu W T. On greedy randomized Kaczmarz method for solving large sparse linear systems[J]. SIAM J. Sci. Comput., 2018, 40(1):592-606.
[3] Bai Z Z, Wu W T. On partially randomized extended Kaczmarz method for solving large sparse overdetermined inconsistent linear systems[J]. Linear Algebra Appl., 2019, 578:225-250.
[4] Bai Z Z, Wu W T. On relaxed greedy randomized Kaczmarz methods for solving large sparse linear systems[J]. Appl. Math. Lett., 2018, 83:21-26.
[5] Bai Z Z, Wu W T. On convergence rate of the randomized Kaczmarz method[J]. Linear Algebra Appl., 2018, 553:252-269.
[6] Bertsekas D P, Tsitsiklis J N. Parallel and Distributed Computation:Numerical Methods[M]. Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 1989.
[7] Breheny P, Huang J. Coordinate descent algorithms for nonconvex penalized regression, with applications to biological feature selection[J]. Ann. Appl. Stat., 2011, 5(1):232-253.
[8] Canutescu A A, Dunbrack J R. Cyclic coordinate descent:A robotics algorithm for protein loop closure[J]. Protein Sci., 2003, 12(5):963-972.
[9] Chang K W, Hsieh C J, Lin C J. Coordinate descent method for large-scale L2-loss linear support vector machines[J]. J. Mach. Learn Res., 2008, 9:1369-1398.
[10] Leventhal D, Lewis A S. Randomized methods for linear constraints:Convergence rates and conditioning[J]. Math. Oper. Res., 2010, 35(3):641-654.
[11] Lu Z, Xiao L. On the complexity analysis of randomized block-coordinate descent methods[J]. Math. Program., 2015, 152(2):615-642.
[12] Luo Z Q, Tseng P. On the convergence of the coordinate descent method for convex differentiable minimization[J]. J. Optim. Theory Appl., 1992, 72(1):7-35.
[13] Luo, Z.Q., Tseng, P. Error bounds and convergence analysis of feasible descent methods:a general approach[J]. Annals of Operations Research, 1993, 46:157-178.
[14] Ma A, Needell D, Ramdas A. Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods[J]. SIAM J. Matrix Anal. Appl., 2015, 36(4):1590-1604.
[15] Necoara I, Nesterov Y, Glineur F. Random block coordinate descent methods for linearly constrained optimization over networks[J]. J. Optim. Theory Appl., 2017, 173(1):227-254.
[16] Nesterov Y. Efficiency of coordinate descent methods on huge-scale optimization problems[J]. SIAM J. Optim., 2012, 22(2):341-362.
[17] Strohmer T, Vershynin R. A randomized Kaczmarz algorithm with exponential convergence[J]. J. Fourier Anal. Appl., 2009, 15:262-278.
[18] Tseng P. Convergence of a block coordinate descent method for nondifferentiable minimization[J]. J. Optim. Theory Appl., 2001, 109(3):475-494.
[19] Wright S J. Coordinate descent algorithms[J]. Math. Program., 2015, 151(1):3-34.
[20] Xie Y J, Ke Y F. Finite iterative (R,S)-conjugate solutions of the generalized complex coupled Sylvester-transpose equations[J]. J. Appl. Anal. Comput., 2021, 11(1):309-332.
[21] Xie Y J, Ke Y F. Neural network approaches based on new NCP-functions for solving tensor complementarity problem[J]. J. Appl. Math. Comput., 2021, 67:833-853.

[1]	缪树鑫. 关于“求解加权线性最小二乘问题的一类预处理GAOR方法”一文的注记[J]. 计算数学, 2022, 44(1): 89-96.
[2]	甘小艇. 状态转换下欧式Merton跳扩散期权定价的拟合有限体积方法[J]. 计算数学, 2021, 43(3): 337-353.
[3]	王丽, 罗玉花, 王广彬. 求解加权线性最小二乘问题的一类预处理GAOR方法[J]. 计算数学, 2020, 42(1): 63-79.
[4]	闫熙, 马昌凤. 求解矩阵方程AXB+CXD=F参数迭代法的最优参数分析[J]. 计算数学, 2019, 41(1): 37-51.
[5]	黄娜, 马昌凤, 谢亚君. 求解非对称代数Riccati 方程几个新的预估-校正法[J]. 计算数学, 2013, 35(4): 401-418.
[6]	范斌, 马昌凤, 谢亚君. 求解非线性互补问题的一类光滑Broyden-like方法[J]. 计算数学, 2013, 35(2): 181-194.
[7]	陈争, 马昌凤. 求解非线性互补问题一个新的 Jacobian 光滑化方法[J]. 计算数学, 2010, 32(4): 361-372.
[8]	孙清滢, 付小燕, 桑兆阳, 刘秋, 王长钰. 基于简单二次函数模型的带线搜索的信赖域算法[J]. 计算数学, 2010, 32(3): 265-274.
[9]	杨大地,刘冬兵,. 一类A(α)稳定的k阶线性k步法公式[J]. 计算数学, 2008, 30(2): 143-146.
[10]	刘新国,王卫国. 关于结构KKT方程组的扰动分析[J]. 计算数学, 2004, 26(2): 179-188.
[11]	刘晓青,曹礼群,崔俊芝. 复合材料弹性结构的高精度多尺度算法与数值模拟[J]. 计算数学, 2001, 23(3): 369-384.

阅读次数

全文

摘要

求解大型最小二乘问题的混合贪婪随机坐标下降法

HYBRID GREEDY RANDOMIZED COORDINATE DESCENT METHOD FOR SOLVING LARGE-SCALE LINEAR LEAST SQUARE PROBLEM

扫码分享