一种单位化的增量梯度算法

doi:10.15960/j.cnki.issn.1007-6093.2021.02.006

Abstract

Abstract:

A scaled incremental gradient algorithm for minimizing a sum of continuously differentiable functions is presented. At each iteration of the algorithm, the iterate is updated incrementally by a sequence of some steps, and each step is cyclically evaluates a normalized gradient of a single component function (or several component functions). Under some moderate assumptions, the convergence result of the algorithm employing the divergence step sizes is established. As applications, the new algorithm and the (unscaled) one proposed by Bertsekas D P, Tsitsikils J N are applied to solve the robust estimation problem and the source localization problem, respectively. Some numerical experiments show that the new algorithm is more effective and robust than the corresponding (unscaled) one.

Key words: separable optimization, scaled incremental gradient algorithm, incremental gradient algorithm, divergence step size rule

CLC Number:

O221.2

Xiaohui QIAN, Xiangmei WANG. A scaled incremental gradient method[J]. Operations Research Transactions, 2021, 25(2): 81-92.

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

URL: https://www.ort.shu.edu.cn/EN/10.15960/j.cnki.issn.1007-6093.2021.02.006

https://www.ort.shu.edu.cn/EN/Y2021/V25/I2/81

Figures/Tables 6

References 23

1	Bertsekas D P . Incremental least squares methods and the extended kalman filter[J]. SIAM Journal on Optimization, 1996, 6 (3): 807- 822. doi: 10.1137/S1052623494268522
2	Bertsekas D P . A new class of incremental gradient methods for least squares problems[J]. SIAM Journal on Optimization, 1997, 7 (4): 913- 926. doi: 10.1137/S1052623495287022
3	Moriyama H , Yamashita N , Fukushima M . The incremental Gauss-Newton algorithm with adaptive stepsize rule[J]. Computational Optimization and Applications, 2003, 26 (2): 107- 141. doi: 10.1023/A:1025703629626
4	Gurbuzbalaban M , Ozdaglar A , Parrilo P . A globally convergent incremental newton method[J]. Mathematical Programming, 2015, 151 (1): 283- 313. doi: 10.1007/s10107-015-0897-y
5	Blatt D , Hero A , Gauchman H . A convergent incremental gradient method with a constant stepsize[J]. SIAM Journal on Optimization, 2007, 18 (1): 29- 51. doi: 10.1137/040615961
6	Bottou L , Le Cun Y . On-line learning for very large data sets[J]. Applied Stochastic Models in Business and Industry, 2005, 21 (2): 137- 151. doi: 10.1002/asmb.538
7	Roux N L, Schmidt M, Bach F R. A stochastic gradient method with an exponential convergence rate for finite training sets [C]//ICONIP 2018 2018: 25th International Conference on Neural Information Processing Systems, 2018.
8	Grippo L . A class of unconstrained minimization methods for neural network training[J]. Optimization Methods and Software, 1994, 4 (2): 135- 150. doi: 10.1080/10556789408805583
9	Mangasarian O L , Solodov M V . Serial and parallel backpropagation convergence via nonmonotone perturbed minimization[J]. Optimization Methods and Software, 1994, 4 (2): 103- 116. doi: 10.1080/10556789408805581
10	Bertsekas D P , Tsitsiklis J N . Gradient convergence in gradient methods with errors[J]. SIAM Journal on Optimization, 2000, 10 (3): 627- 642. doi: 10.1137/S1052623497331063
11	BertsekasD P. 非线性规划[M]. 第2版北京: 清华大学出版社, 2013.
12	王宜举, 修乃华. 非线性最优化理论与方法[M]. 北京: 科学出版社, 2015.
13	袁亚湘, 孙文瑜. 最优化理论与方法[M]. 北京: 科学出版社, 2007.
14	陈宝林. 最优化理论与算法[M]. 北京: 清华大学出版社, 2005.
15	马昌凤, 柯艺芬, 谢亚君. 最优化计算方法及其MATLAB程序实现[M]. 北京: 国防教育出版社, 2017.
16	Trefethen . Spectral Methods in MATLAB[M]. New York: SIAM, 2000.
17	Rabbat M G, Nowak R D. Decentralized source localization and tracking[C]//2004 IEEE International Conference on Acoustics, Speech, and Signal Processing, New York: IEEE, 2004.
18	Sheng X , Hu Y H . Information Processing in Sensor Networks[M]. California: Springer, 2003.
19	Chen J C , Yao K , Hudson R E . Source localization and beamforming[J]. IEEE Signal Processing Magazine, 2002, 19, 30- 39. doi: 10.1109/79.985676
20	Huber P . Robust Statistics[M]. New York: John Wiley and Sons, 1981.
21	Polyak B T . Introduction to Optimization[M]. New York: Chapman & Hall, 1987.
22	Rey W J J . Introduction to Robust and Quasi-Robust Statistical Methods[M]. Berlin: SpringerVerlag, 1983.
23	Shor N Z . Minimization Methods for Non-differentiable Functions[M]. Kiev: Naukova Dumka, 1979.

算法	x_k	$ \\|{{\nabla}f(x_k)}\\| $
初始点x₀=(50, 50)
IGA^[10]	(53.345 6, 50.847 7)	0.323 7
SIGA	(60.872 6, 51.403 1)	0.179 6
初始点x₀=(60, 60)
IGA^[10]	(61.180 5, 58.552 6)	0.186 5
SIGA	(65.926 0, 52.011 7)	0.089 2
初始点x₀=(80, 80)
IGA^[10]	(76.527 4, 74.571 5)	0.557 4
SIGA	(69.774 5, 61.519 4)	0.210 6

算法	x_k	迭代次数k	运行时间t/s
初始点x₀=(50, 50), 精度ε=0.3
IGA^[10]	(54.525 5, 51.111 2)	476 813	109.72
SIGA	(54.526 9, 51.115 8)	59	0.10
初始点x₀=(60, 60), 精度ε=0.185
IGA^[10]	(61.383 7, 58.300 0)	57 280	13.10
SIGA	(61.253 2, 58.022 0)	5	0.01
初始点x₀=(80, 80), 精度ε=0.5
IGA^[10]	(75.710 9, 73.123 5)	233 133	54.12
SIGA	(75.566 1, 73.220 3)	11	0.02

算法	迭代次数^k	平均$ \\|\nabla f(x_k)\\| $	平均运行时间/s
IGA^[10]	10⁴	0.329 2	2.29
	10⁵	0.313 7	22.69
	10⁶	0.298 9	227.04
SIGA	10⁴	0.170 2	13.77

算法	x_k	$ \\|{{\nabla}f(x_k)}\\| $	迭代次数k
初始点x₀=-5
IGA^[10]	9.775 6	0.056 6	10 000
SIGA	9.846 5	9.389 4×10^-5	340
初始点x₀=0
IGA^[10]	9.812 4	0.027 2	10 000
SIGA	9.846 5	9.905 0×10^-5	244
初始点x₀=20
IGA^[10]	9.876 1	0.023 9	10 000
SIGA	9.846 2	9.776 2×10^-5	55

算法	x_k	迭代次数k	运行时间/s
初始点x₀=-5
IGA^[10]	9.833 9	87 427	16.67
SIGA	9.835 2	249	0.20
初始点x₀=0
IGA^[10]	9.833 9	34 933	6.33
SIGA	9.840 5	121	0.09
初始点x₀=20
IGA^[10]	9.858 8	29 622	5.70
SIGA	9.846 9	19	0.07

A scaled incremental gradient method

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 6

References 23

Related Articles 15

Recommended Articles

Metrics

Comments

算法	平均迭代次数k	平均运行时间/s
IGA^[10]	67 370	12.46
SIGA	97	0.16

[1]	WANG Xiangfeng, ZENG Shangzhi, ZHANG Jin, ZHOU Jinchuan. Proximal-based methods can guarantee blunt local minimizer for nonconvex nonsmooth optimization problem [J]. Operations Research Transactions, 2026, 30(2): 1-23.
[2]	MEN Yanchao, LI Xudong. Fast algorithm for OWL1 norm constrained regression model [J]. Operations Research Transactions, 2026, 30(2): 24-44.
[3]	ZENG Jing, XIANG Yao, ZHANG Wenyan. The well-posedness of traffic equilibrium problems [J]. Operations Research Transactions, 2026, 30(2): 58-68.
[4]	WANG Feng, HANG Bo, HUANG Jinzhou, XU Degang, ZHANG Zeyu, LIU Jiamou. Research of touring route planning based on spatio-temporal awareness [J]. Operations Research Transactions, 2026, 30(2): 69-78.
[5]	WU Xiaoyu, SHAO Hu, LIU Pengjie, ZHOU Jincheng. Two RMIL-type conjugate gradient methods with sufficient descent property and applications in image restoration [J]. Operations Research Transactions, 2026, 30(2): 79-92.
[6]	CUI Hengxin, JIANG Fan. Inexact proximal point algorithms and projection methods for monotone variational inequalities [J]. Operations Research Transactions, 2026, 30(2): 194-208.
[7]	ZHANG Xuefeng, PENG Xiao, CHEN Liangyu, YANG Zhengfeng, ZENG Zhenbing. A review of intelligent branch and bound algorithms for mixed integer linear programming problems [J]. Operations Research Transactions, 2026, 30(2): 237-270.
[8]	WEI Jiazhen, BIAN Wei. A survey on research advances in consensus-based optimization algorithm [J]. Operations Research Transactions, 2026, 30(1): 1-23.
[9]	ZHOU Yunxu, YAO Fanjun, GAO Hongwei. Blockchain empowering the digital transformation: Study on the coordination strategies of supply chain [J]. Operations Research Transactions, 2026, 30(1): 61-74.
[10]	ZHAO Hongxin, KONG Lingchen. Research on diversification portfolio optimization model and method [J]. Operations Research Transactions, 2026, 30(1): 75-92.
[11]	SUN Ke, WANG Jinting, WANG Zhongbin. The economics of waiting-area entertainment [J]. Operations Research Transactions, 2026, 30(1): 93-107.
[12]	XU Ke, JI Lanping, GONG Hua, LIU Peng, SUN Wenjuan. A coordinated multi-agent production and transportation scheduling on parallel machines based on auction algorithm [J]. Operations Research Transactions, 2026, 30(1): 121-136.
[13]	WANG Ziqi, WANG Junlin, XU Zi. A variance reduced gradient descent ascent algorithm for a class of nonconvex-nonconcave minimax problems [J]. Operations Research Transactions, 2026, 30(1): 197-206.
[14]	YANG Jinji, SHEN Chungen, YU Zhensheng. Convergence analysis of an adaptive proximal gradient-subgradient algorithm for square-root-loss regression problems [J]. Operations Research Transactions, 2026, 30(1): 217-234.
[15]	Ruiqing SUN, Rui ZHANG, Yan LAN, Weidong LI. LPT algorithm for early work maximization problem [J]. Operations Research Transactions, 2025, 29(4): 249-254.