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

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

摘要/Abstract

摘要：

研究目标函数是若干光滑函数和的可分离优化问题，提出了一种单位化增量梯度算法。该算法每次子迭代只需要计算一个（或几个）分量函数的单位负梯度方向作为迭代方向。在一定条件下，证明了采用发散步长的单位化增量梯度算法的收敛性。作为应用，新算法和Bertsekas D P，Tsitsikils J N提出的（没有单位化）增量梯度算法分别用来求解稳健估计问题和源定位问题。数值例子表明，新算法优于（没有单位化）增量梯度算法。

关键词: 可分离优化, 单位化增量梯度算法, 增量梯度法, 发散步长准则

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

中图分类号:

O221.2

钱晓慧, 王湘美. 一种单位化的增量梯度算法[J]. 运筹学学报, 2021, 25(2): 81-92.

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

图/表 6

表1

表2

表3

表4

表5

表6

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