Advances in Applied Mathematics
Vol.
11
No.
08
(
2022
), Article ID:
54881
,
10
pages
10.12677/AAM.2022.118607
凸约束优化问题的杂交三阶投影HS-PRP方法
周姣利
长沙理工大学数学与统计学院,湖南 长沙
收稿日期:2022年7月15日;录用日期:2022年8月9日;发布日期:2022年8月18日
摘要
本文提出了一种杂交三阶投影HS-PRP共轭梯度法求解凸约束优化问题并证明了该算法的全局收敛性,该方法是求解无约束优化问题的三阶HS共轭梯度法的推广。数值实验结果表明,该算法是有效的。
关键词
投影,共轭梯度法,线搜索,全局收敛
A Hybrid Three-Term Projected HS-PRP Method for Optimization with Convex Constraint
Jiaoli Zhou
School of Mathematics and Statistics, Changsha University of Science and Technology, Changsha Hunan
Received: Jul. 15th, 2022; accepted: Aug. 9th, 2022; published: Aug. 18th, 2022
ABSTRACT
In this paper, we propose a hybrid third-term projected HS-PRP conjugate gradient method for solving convex constrained optimization problems and establish its global convergence, which is a generalization of the third-term HS conjugate gradient method for unconstrained optimization. Numerical experimental results show that the algorithm is effective.
Keywords:Projected, Conjugate Gradient Method, Line Search, Global Convergence
Copyright © 2022 by author(s) and Hans Publishers Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).
http://creativecommons.org/licenses/by/4.0/
1. 引言
自共轭梯度法被提出以来,因其具有良好的收敛性质,且所需存储量小,因此被广泛用于求解大规模无约束优化问题。
共轭梯度法的基本迭代格式如下:
,
,
其中 为步长因子,由某种线搜索确定; 为搜索方向, 为共轭参数, 。
共轭参数 的经典选取方式有Fletcher-Reeves [1],Polak-Ribière-Polyak [2],Hestenes-Stiefel [3],Dai-Yuan [4],Conjugate Descent [5],Liu-Storey [6] 六种,其具体表达式如下:
,,,
,,.
其中 表示Euclidean范数, 。由于分子不同,可将这六种经典的共轭梯度法分为两类。第一类如FR、CD和DY方法,其共轭参数 有共同的分子 ,虽然它们具有良好的全局收敛性,但数值表现一般;第二类如PRP、HS和LS方法,其共轭参数 有共同的分子 ,虽然它们拥有良好的数值表现,但对全局收敛的条件要求较强。为得到数值实验和理论结果都较好的共轭梯度法,许多学者对这些经典方法做了修正 [7] [8] [9] [10]。
2007年,Zhang等人在 [11] [12] [13] 的基础上,提出了三阶HS共轭梯度法 [14],即TTHS方法,搜索方向 的取法如下:
,.
该方法的优点在于:生成的搜索方向 总满足 ,即不依赖任何线搜索而具有充分下降性。为了得到TTHS方法在标准Wolf线搜索下的全局收敛性,Zhang等人提出了以下两种算法。一种是截断TTHS方法(CTTHS方法):
其中 和 是任意正常数。另一种是改进的TTHS方法(MTTHS方法):
其中
,,.
t和 为任意正常数, ,。
为保证MTTHS方法在修改的Armijo线搜索下的全局收敛性,考虑做如下修改:
其中
,,,
其中
,,,.
1990年,Touati-Ahmed和Storey首次引入了杂交共轭梯度法 [15],其共轭参数 的取法为: ,杂交共轭梯度法的提出,使得共轭梯度法的理论性质和数值试验都表现得更佳。随后,许多学者对杂交共轭梯度法做了进一步研究,见文献 [16] [17]。
在杂交共轭梯度法的启发下,本文考虑杂交三项HS-PRP共轭梯度法:
其中
,,.
其中
,,, 为任意正常数。
我们注意到,上述共轭梯度法旨在求解无约束优化问题,该方法并不适合直接用于求解约束优化问题。2021年,Zhou提出了一种求解凸约束优化问题的投影PRP方法 [18],利用投影的性质证明了该算法在修改的Armijo线搜索下具有全局收敛性。本文的目的是推广杂交三阶HS-PRP共轭梯度法求解凸约束优化问题,并证明该算法在修改的Armijo线搜索下的全局收敛性。
本文其余部分组织如下:第二部分详细介绍了求解凸约束优化问题的杂交三阶投影HS-PRP共轭梯度法;第三部分证明该算法的全局收敛性;第四部分给出数值实验结果。
2. 杂交三阶投影HS-PRP共轭梯度法
本文的目的是推广求解无约束优化问题的杂交三阶HS-PRP共轭梯度法用于求解以下凸约束优化问题:
. (1)
其中 是闭凸集, 为 的光滑函数。显然,若 是问题(1)的局部极小点,那么 一定是满足定义2.1的稳定点。
定义2.1. 是问题(1)的稳定点当且仅当: ,。
定义2.2. 从 到闭凸集 的投影算子为:
. (2)
令
. (3)
显然, 是问题(1)的稳定点当且仅当 。
算法1. (杂交三阶投影HS-PRP方法)
步0. 取初始点 ,,,,。选取一个正序列 满足: 。令
,. (4)
步1. 若 , 则停止计算;否则,转步2。
步2. 按如下公式计算
(5)
其中
,,. (6)
其中
,,. (7)
步3. 计算 满足:
, (8)
其中 。
步4. 令 ,,,转步1。
注2.2.
1) 由(3)可知,若 ,则 ,则 是问题(1)的稳定点;
2) 若 ,则 ,这也就意味着 是问题(1)的稳定点;
3) 由 的定义可知:
; (9)
4) 由投影算子的连续性和 可知线搜索(8)对任意充分小的 都成立。线搜索(8)来自文献 [19]。
接下来我们将介绍投影算子的一些重要性质,这些性质对我们后面证明该算法的全局收敛性非常有用。引理2.3和引理2.4来自文献 [20]。
引理2.3. 若 ,则有:
, (10)
, (11)
引理2.4. 对任意 , 在 上非增。
引理2.5. 对任意 。有:
, (12)
证明:由(10)和 可知:
证毕。
3. 全局收敛性
在这一部分,我们将讨论算法1在以下假设条件下的全局收敛性。首先,我们定义水平集:
, (13)
其中 满足(4)。显然 对任意 都成立。
假设A.
1) 由(13)定义的水平集 是有界的;
2) 存在 的某些凸邻域N,使得梯度函数 在 上Lipschitz连续,即存在常数 ,使得:
(14)
由假设A可知存在常数 ,使得:
(15)
显然,由线搜索(8)和(4)我们可以得到:
(16)
引理3.1. 设 是由算法1产生的序列且假设A成立,则对任意的 ,有:
. (17)
. (18)
由(18)可知: 。
引理3.2. 若假设A成立,则存在常数 使得:
. (19)
证明:由(5)、(6)、(15)、(17)、(18)可知:
令 即得(19),证毕。
定理3.3. 设 是由算法1产生的序列且假设A成立,则有:
. (20)
证明:反证法,假设结论不成立,则存在常数 使得:
. (21)
由(21)可知存在常数 ,使得:
. (22)
否则存在无限子集 使得:
. (23)
最后一个不等式由(11)和 可得,因此上式与(21)矛盾,即(22)成立。
1) 若 ,由(9)和(16)可得: 。这与(22)式矛盾。
2) 若 ,则存在 不满足不等式(8),即:
. (24)
由拉格朗日中值定理和引理2.5可得:
其中 介于 和 之间。上述不等式结合(24)可得:
. (25)
由(11)和(15)可得:
由(5)、(6)、(11)、(15)、(17)、(22)以及 可得:
(26)
因此,由 的连续性和 以及(26)可知: 。
由(3)、(19)、(25),引理2.4以及 ,我们可以得到:
.
这与(21)矛盾,证毕。
4. 数值实验
在这一部分我们将通过数值实验来验证本文所提出算法的有效性。实验测试在PC机上完成,PC机配置:联想,Intel(R) Core(TM) i7-8700 CPU @ 3.20GHz 3.19GHz,8Gb内存,Windows10操作系统,所有代码用Matlab R2016b编写并运行。
测试对象:函数来自文献 [18],表达式如下:
.
约束集 ,其中 为任意常数。
令 。
测试参数: ,,,,。
初始点: 。
终止条件:迭代次数 或 ,其中 表示迭代终止时 的无穷范数。
采用本文提出的算法与Zhou在文献 [18] 中提出的投影PRP算法求解上述测试问题,分别记为算法1和算法2,测试结果见表1和表2。
Table 1. Test function with γ = ( 1 , 2 , ⋯ , n − 1 ) T
表1. 测试函数中
Table 2. Test function with γ = 1 n ( 1 2 , 2 2 , ⋯ , ( n − 1 ) 2 ) T
表2. 测试函数中
由表1和表2的数据我们可以知道,在迭代次数和运行时间两个方面,本文提出的算法优于 [18] 提出的投影PRP方法。
5. 结束语
本文提出了一种求解凸约束优化问题的杂交三阶投影HS-PRP共轭梯度法,它是求解无约束优化问题的共轭梯度法的推广。利用投影的相关性质,我们证明了该算法在修改的Armijo线搜索下的全局收敛性。数值结果表明,本文所提出的算法较投影PRP算法更优。
文章引用
周姣利. 凸约束优化问题的杂交三阶投影HS-PRP方法
A Hybrid Three-Term Projected HS-PRP Method for Optimization with Convex Constraint[J]. 应用数学进展, 2022, 11(08): 5750-5759. https://doi.org/10.12677/AAM.2022.118607
参考文献
- 1. Fletcher. R. and Reeves, C.M. (1964) Function Minimization by Conjugate Gradients. The Computer Journal, 7, 149-154. https://doi.org/10.1093/comjnl/7.2.149
- 2. Polyak, B.T. (1969) The Conjugate Gradient Method in Ex-treme problems. USSR Computational Mathematics and Mathematical Physics, 9, 94-112. https://doi.org/10.1016/0041-5553(69)90035-4
- 3. Hestenes, M.R. and Stiefel, E. (1952) Method of Conjugate Gradient for Solving Linear System. Journal of Research of the National Bureau of Standards, 49, 409-436. https://doi.org/10.6028/jres.049.044
- 4. Dai, Y.H. and Yuan, Y. (1999) A Nonlinear Conjugate Gradient Method with a Strong Global Convergence Property. SIAM Journal on Optimization, 10, 177-182. https://doi.org/10.1137/S1052623497318992
- 5. Fletcher, R. (1987) Practical Methods of Optimization, Vol. 1: Unconstrained Optimization. Wiley & Sons, New York.
- 6. Liu, Y. and Storey, C. (1991) Efficient Generalized Con-jugate Gradient Algorithms, Part 1: Theory. Journal of Optimization Theory and Applications, 69, 129-137. https://doi.org/10.1007/BF00940464
- 7. Zhou, W. and Li, D. (2014) On the Convergence Properties of the Un-modified PRP Method with a Non-Descent Line Search. Optimization Methods Software, 29, 484-496. https://doi.org/10.1080/10556788.2013.811241
- 8. Hager, W.W. and Zhang, H. (2005) A New Conjugate Gra-dient Method with Guaranteed Descent and an Efficient Line Search. SIAM Journal on Optimization, 16, 170-192. https://doi.org/10.1137/030601880
- 9. Gilbert, J.C. (1994) Convergence Properties of Conjugate Descent Method for Optimization. SIAM Journal on Optimization, 2, 24-32.
- 10. 杨萌, 王祥玲. 修正HS共轭梯度法的全局收敛性[J]. 桂林电子科技大学学报, 2009, 29(4): 300-302.
- 11. Zhang, L., Zhou, W. and Li, D. (2006) A Descent Modified Polak-Ribière-Polyak Conjugate Gradient Method and Its Global Convergence. IMA J Numerical Analysis, 26, 629-640. https://doi.org/10.1093/imanum/drl016
- 12. Zhang, L., Zhou, W. and Li, D. (2006) Global Convergence of a Modi-fied Fletcher Reeves Conjugate Gradient Method with Armijo-Type Line Search. Numerische Mathematik, 104, 561-572. https://doi.org/10.1007/s00211-006-0028-z
- 13. Li, D.H. and Fukushima, M. (2001) A Modified BFGS Method and Its Global Convergence in Nonconvex Minimization. Journal of Computational and Applied Mathematics, 129, 15-35. https://doi.org/10.1016/S0377-0427(00)00540-9
- 14. Zhang, L., Zhou, W. and Li, D. (2007) Some Descent Three-Term Conjugate Gradient Methods and Their Global Convergence. Optimization Methods and Software, 22, 697-711. https://doi.org/10.1080/10556780701223293
- 15. Touati-Ahmed, D. and Story, C. (1990) Global Con-vergent Hybrid Conjugate Gradient Method. Journal of Optimization Theory and Applications, 64, 379-397. https://doi.org/10.1007/BF00939455
- 16. Dai, Y.H. and Yuan, Y. (2001) An Efficient Hybrid Conjugate Method for Unconstrained Optimization. Annals of Operations Research, 103, 33-47. https://doi.org/10.1023/A:1012930416777
- 17. Dai, Z.F. and Wen, F.H. (2015) Comments on Another Hybrid Conjugate Gradient Algorithm for Unconstrained Optimization by Andrei. Numerical Algorithms, 69, 337-341. https://doi.org/10.1007/s11075-014-9899-8
- 18. Zhou, W. (2021) A Projected PRP Method for Optimization with Convex Constraint. Pacilici Journal of Optimization, 17, 47-55.
- 19. Zhou W. (2013) A Short Note on the Global Con-vergence of the Unmodified PRP Method. Optimization Letters, 7, 1367-1372. https://doi.org/10.1007/s11590-012-0511-7
- 20. Calamai, P.H. and Moré, J.J. (1987) Projected Gradient Methods for Linearly Constrained Problems. Mathematical Programming, 39, 93-116. https://doi.org/10.1007/BF02592073