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

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.

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]	XU Zi, ZHANG Huiling. Optimization algorithms and their complexity analysis for non-convex minimax problems [J]. Operations Research Transactions, 2021, 25(3): 74-86.
[2]	KE Rongzhu, ZHANG Jin. On the first order approach for bilevel programming: moral hazard case [J]. Operations Research Transactions, 2021, 25(3): 87-104.
[3]	Fusheng BAI, Dan FENG, Ke ZHANG. Combined response surface method with adaptive sampling for expensive black-box global optimization [J]. Operations Research Transactions, 2021, 25(2): 1-14.
[4]	Deqiang QU, Youlin SHANG, Yue ZHAN, Dan WU. A new parameterless filled function for global optimization problems [J]. Operations Research Transactions, 2021, 25(1): 89-95.
[5]	Jiali CHEN, Ying ZHANG, Shenggang WANG, Xiaoying XIE. A new filled function and its application in data fitting problems [J]. Operations Research Transactions, 2021, 25(1): 81-88.
[6]	MIAO Xiaonan, GU Jian, XIAO Xiantao. A cubic regularization method for solving nonsmooth equations [J]. Operations Research Transactions, 2019, 23(2): 17-30.
[7]	LIANG Renli, BAI Yanqin. A splitting augmented Lagrangian method embedding in the BB method for solving the sparse logistic problem [J]. Operations Research Transactions, 2019, 23(2): 86-94.
[8]	TANG Liping, YANG Xinmin. Characterizations of two classes of cone generalized pseudoinvexity [J]. Operations Research Transactions, 2015, 19(1): 1-8.
[9]	ZENG Youfang, TANG Chunming. A non-interior-point continuous algorithm with superlinear convergence for second-order cone programming [J]. Operations Research Transactions, 2015, 19(1): 18-30.
[10]	LIU Shuixia, CHEN Guoqing. A multiplier relaxation method for solving mathematical programs with complementarity constraints [J]. Operations Research Transactions, 2014, 18(4): 119-130.
[11]	YANG Yun, PENG Zheng. An inexact parallel splitting method for separable convex optimization problem [J]. Operations Research Transactions, 2014, 18(3): 33-46.
[12]	FENG Zengzhe, ZHANG Xixue, LIU Jianbo$, FANG Liang. A new wide neighborhood infeasible interior-point algorithm for semidefinite programming [J]. Operations Research Transactions, 2014, 18(2): 49-58.
[13]	DAI Yuhong, LIU Xinwei. Advances in linear and nonlinear programming [J]. Operations Research Transactions, 2014, 18(1): 69-92.
[14]	LIU Yuanyuan, OU Yigui. An ODE-based hybrid method based on the nonmonotone technique [J]. Operations Research Transactions, 2013, 17(3): 11-22.
[15]	HAN Yingwei, XIA Yong. A dual method for the pose estimation problem [J]. Operations Research Transactions, 2013, 17(3): 86-92.