GLOBAL CONVERGENCE OF A CAUTIOUS PROJECTION BFGS ALGORITHM FOR NONCONVEX PROBLEMS WITHOUT GRADIENT LIPSCHITZ CONTINUITY*

doi:10.1007/s10473-024-0506-3

数学物理学报(英文版) ›› 2024, Vol. 44 ›› Issue (5): 1735-1746.doi: 10.1007/s10473-024-0506-3

GLOBAL CONVERGENCE OF A CAUTIOUS PROJECTION BFGS ALGORITHM FOR NONCONVEX PROBLEMS WITHOUT GRADIENT LIPSCHITZ CONTINUITY^*

Gonglin YUAN, Xiong ZHAO, Jiajia YU^†

School of Mathematics and Information Science, Center for Applied Mathematics of Guangxi (Guangxi University), Guangxi University, Nanning 530004, China

收稿日期:2023-02-16 修回日期:2024-06-16 出版日期:2024-10-25 发布日期:2024-10-22
通讯作者: †Jiajia YU, E-mail,: ; 8409855@qq.com
作者简介:Gonglin YUAN,E-mail,:glyuan@gxu.edu.cn; Xiong ZHAOE-mail,:chao18874188217@163.com
基金资助:
Yuan's research was supported by the Guangxi Science and Technology base and Talent Project (AD22080047), the National Natural Science Foundation of Guangxi Province (2023GXNFSBA 026063), the Innovation Funds of Chinese University (2021BCF03001), and the special foundation for Guangxi Ba Gui Scholars.

GLOBAL CONVERGENCE OF A CAUTIOUS PROJECTION BFGS ALGORITHM FOR NONCONVEX PROBLEMS WITHOUT GRADIENT LIPSCHITZ CONTINUITY^*

Gonglin YUAN, Xiong ZHAO, Jiajia YU^†

School of Mathematics and Information Science, Center for Applied Mathematics of Guangxi (Guangxi University), Guangxi University, Nanning 530004, China

Received:2023-02-16 Revised:2024-06-16 Online:2024-10-25 Published:2024-10-22
Contact: †Jiajia YU, E-mail,: ; 8409855@qq.com
About author:Gonglin YUAN,E-mail,:glyuan@gxu.edu.cn; Xiong ZHAOE-mail,:chao18874188217@163.com
Supported by:
Yuan's research was supported by the Guangxi Science and Technology base and Talent Project (AD22080047), the National Natural Science Foundation of Guangxi Province (2023GXNFSBA 026063), the Innovation Funds of Chinese University (2021BCF03001), and the special foundation for Guangxi Ba Gui Scholars.

摘要/Abstract

摘要： A cautious projection BFGS method is proposed for solving nonconvex unconstrained optimization problems. The global convergence of this method as well as a stronger general convergence result can be proven without a gradient Lipschitz continuity assumption, which is more in line with the actual problems than the existing modified BFGS methods and the traditional BFGS method. Under some additional conditions, the method presented has a superlinear convergence rate, which can be regarded as an extension and supplement of BFGS-type methods with the projection technique. Finally, the effectiveness and application prospects of the proposed method are verified by numerical experiments.

关键词: cautious BFGS, nonconvex problems, Lipschitz continuity, projection technique, global convergence

Abstract: A cautious projection BFGS method is proposed for solving nonconvex unconstrained optimization problems. The global convergence of this method as well as a stronger general convergence result can be proven without a gradient Lipschitz continuity assumption, which is more in line with the actual problems than the existing modified BFGS methods and the traditional BFGS method. Under some additional conditions, the method presented has a superlinear convergence rate, which can be regarded as an extension and supplement of BFGS-type methods with the projection technique. Finally, the effectiveness and application prospects of the proposed method are verified by numerical experiments.

Key words: cautious BFGS, nonconvex problems, Lipschitz continuity, projection technique, global convergence

中图分类号:

90C30

Gonglin YUAN, Xiong ZHAO, Jiajia YU. GLOBAL CONVERGENCE OF A CAUTIOUS PROJECTION BFGS ALGORITHM FOR NONCONVEX PROBLEMS WITHOUT GRADIENT LIPSCHITZ CONTINUITY^*[J]. 数学物理学报(英文版), 2024, 44(5): 1735-1746.

Gonglin YUAN, Xiong ZHAO, Jiajia YU. GLOBAL CONVERGENCE OF A CAUTIOUS PROJECTION BFGS ALGORITHM FOR NONCONVEX PROBLEMS WITHOUT GRADIENT LIPSCHITZ CONTINUITY^*[J]. Acta mathematica scientia,Series B, 2024, 44(5): 1735-1746.

参考文献

[1] Fu Z J, Ren K, Shu J G, et al. Enabling personalized search over encrypted outsourced data with efficiency improvement. J IEEE Trans Parall Distr Syst, 2016, 27(9): 2546-2559
[2] Fu Z J, Wu X L, Guan C W, et al. Toward efficient multi-keyword fuzzy search over encrypted outsourced data with accuracy improvement. J IEEE Trans Inf Foren Sec, 2017, 11(12): 2706-2716
[3] Gu B, Sun X M, Sheng V S. Structural minimax probability machine. J IEEE Trans Neur Net Lear, 2017, 28(7): 1646-1656
[4] Pan Z Q, Lei J J, Zhang Y, et al. Fast motion estimation based on content property for low-complexity H.265/HEVC encoder. J IEEE Trans Broadcast, 2016, 62(3): 675-684
[5] Pan Z Q, Zhang Y, Kwong S. Efficient motion and disparity estimation optimization for low complexity multiview video coding. J IEEE Trans Broadcast, 2015, 61(2): 166-176
[6] Broyden C G. The convergence of a class of double-rank minimization algorithms 1. general considerations. SIMA J Appl Math, 1970, 6(1): 76-90
[7] Fletcher R. A new approach to variable metric algorithms. Comput J, 1970, 13(3): 317-322
[8] Goldfarb D. A family of variable-metric methods derived by variational means. Math Comp, 1970, 24(109): 23-26
[9] Shanno D F. Conditioning of quasi-Newton methods for function minimization. Math Comp, 1970, 24(111): 647-656
[10] Powell M J D. Some global convergence properties of a variable metric algorithm for minimization without exact line searches. Nonlinear Programming, SIAM-AMS Proceedings.1976, 9(1): 53-72
[11] Byrd R H, Nocedal J, Yuan Y X. Global convergence of a cass of quasi-Newton methods on convex problems. SIAM J Numer Anal, 1987, 24(5): 1171-1190
[12] Byrd R H, Nocedal J. A tool for the analysis of quasi-Newton methods with application to unconstrained minimization. SIAM J Numer Anal, 1989, 26(3): 727-739
[13] Dixon L C W. Variable metric algorithms: Necessary and sufficient conditions for identical behavior of nonquadratic functions. J Optim Theory Appl, 1972, 10(1): 34-40
[14] Griewank A. The global convergence of partitioned BFGS on problems with convex decompositions and Lipschitzian gradients. Math Program, 1991, 50(1): 141-175
[15] Powell M J D. On the convergence of the variable metric algorithm. IMA J Appl Math, 1971, 7(1): 21-36
[16] Powell M J D. Updating conjugate directions by the BFGS formula. Math Program, 1987, 38(1): 29-46
[17] Biggs M C. Minimization algorithms making use of non-quadratic properties of the objective function. IMA J Numer Anal, 1971, 8(3): 123-123
[18] Nocedal J, Yuan Y X. Analysis of a self-scaling quasi-Newton method. Math Program, 1993, 61: 19-37
[19] Oren S S, Luenberger D G. Self-scaling variable metric (ssvm) algorithms: Part i: Criteria and sufficient conditions for scaling a class of algorithms. Manag Sci, 1974, 20(5): 845-862
[20] Yuan Y X. A modified bfgs algorithm for unconstrained optimization. IMA J Numer Anal, 1991, 3: 325-332
[21] Cheng W Y, Li D H. Spectral scaling BFGS method. J Optim Theory Appl, 2010, 146(2): 305-319
[22] Sheng Z, Yuan G L, Cui Z R. A new adaptive trust region algorithm for optimization problems. Acta Math Sci, 2018, 38B(2): 479-496
[23] Yuan G L, Wei Z X. The superlinear convergence analysis of a nonmonotone BFGS algorithm on convex objective functions. Acta Math Sci, 2008, 24B: 35-42
[24] Dai Y H. Convergence properties of the BFGS algoritm. SIAM J Optim, 2002, 13(3): 693-701
[25] Yuan G L, Sheng Z, Wang B P, et al. The global convergence of a modified BFGS method for nonconvex functions. J Comput Appl Math, 2017, 327: 274-294
[26] Li D H, Fukushima M. A modified BFGS method and its global convergence in nonconvex minimization. J Comput Appl Math, 2001, 129(1/2): 15-35
[27] Li D H, Fukushima M. On the global convergence of BFGS method for nonconvex unconstrained optimization problems. SIAM J Optim, 2001, 11(4): 1054-1064
[28] Yuan G L, Wang X L, Sheng Z. The projection technique for two open problems of unconstrained optimization problems. J Optim Theory Appl, 2020, 186(2): 590-619
[29] Yuan G L, Wei Z X, Lu X W. Global convergence of BFGS and PRP methods under a modified weak Wolfe-Powell line search. Appl Math Model, 2017, 47: 811-825
[30] Bongartz I, Conn A R, Gould N, et al. CUTE: Constrained and unconstrained testing environment. ACM Trans Math Software, 1995, 21(1): 123-160
[31] Moré J J, Garbow B S, Hillstrom K E. Testing unconstrained optimization software. ACM Trans Math Software, 1981, 7(1): 17-41
[32] Andrei N. An unconstrained optimization test functions collection. Adv Model Optim, 2008, 10(1): 147-161
[33] Dolan E D, Moré, Jorge J. Benchmarking optimization software with performance profiles. Math Program, 2002, 91(2): 201-213
[34] Zhou W J, Zhang L. A nonlinear conjugate gradient method based on the MBFGS secant condition. Optim Methods Softw, 2006, 21(5): 707-714
[35] Yang Y G. A robust BFGS algorithm for unconstrained nonlinear optimization problems. Optim, 2022, 73(3): 851-873
[36] Yuan G L, Zhao X, Liu K Jun, et al. An adaptive projection BFGS method for nonconvex unconstrained optimization problems. Numer Algorithms, 2024, 95(4): 1747-1767
[37] Yuan G L, Li P Y, Lu J Y. The global convergence of the BFGS method with a modified WWP line search for nonconvex functions. Numer Algorithms, 2022, 91(1): 353-365
[38] Yuan G L, Zhang M X, Zhou Y J. Adaptive scaling damped BFGS method without gradient Lipschitz continuity. Appl Math Lett, 2022, 124: Art 107634
[39] Tits A L, Yang Y. Globally convergent algorithms for robust pole assignment by state feedback. IEEE Trans Automat Contr, 1996, 41(10): 1432-1452

GLOBAL CONVERGENCE OF A CAUTIOUS PROJECTION BFGS ALGORITHM FOR NONCONVEX PROBLEMS WITHOUT GRADIENT LIPSCHITZ CONTINUITY^*

GLOBAL CONVERGENCE OF A CAUTIOUS PROJECTION BFGS ALGORITHM FOR NONCONVEX PROBLEMS WITHOUT GRADIENT LIPSCHITZ CONTINUITY^*

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 12

Metrics

本文评价

推荐阅读 10

[1]	Zhenhai Liu, Nikolaos S. Papageorgiou. PERIODIC SYSTEMS WITH TIME DEPENDENT MAXIMAL MONOTONE OPERATORS[J]. 数学物理学报(英文版), 2024, 44(4): 1280-1300.
[2]	杨永富, 琚强昌, 周爽. THE GLOBAL COMBINED QUASI-NEUTRAL AND ZERO-ELECTRON-MASS LIMIT OF NON-ISENTROPIC EULER-POISSON SYSTEMS[J]. 数学物理学报(英文版), 2022, 42(4): 1666-1680.
[3]	钟德光, 孟凡宁, 袁文俊. ON SCHWARZ-PICK TYPE INEQUALITY FOR MAPPINGS SATISFYING POISSON DIFFERENTIAL INEQUALITY[J]. 数学物理学报(英文版), 2021, 41(3): 959-967.
[4]	简金宝, 马国栋. A GLOBALLY CONVERGENT QP-FREE ALGORITHM FOR INEQUALITY CONSTRAINED MINIMAX OPTIMIZATION[J]. 数学物理学报(英文版), 2020, 40(6): 1723-1738.
[5]	盛洲, 袁功林, 崔曾如. A NEW ADAPTIVE TRUST REGION ALGORITHM FOR OPTIMIZATION PROBLEMS[J]. 数学物理学报(英文版), 2018, 38(2): 479-496.
[6]	Volker Elling. HÖLDER CONTINUITY AND DIFFERENTIABILITY ON CONVERGING SUBSEQUENCES[J]. 数学物理学报(英文版), 2012, 32(1): 75-83.
[7]	迟晓妮; 刘三阳. AN INFEASIBLE-INTERIOR-POINT PREDICTOR-CORRECTOR ALGORITHM FOR THE SECOND-ORDER CONE PROGRAM[J]. 数学物理学报(英文版), 2008, 28(3): 551-559.
[8]	张立平. A GLOBAL LINEAR AND LOCAL QUADRATIC SINGLE--STEP NONINTERIOR#br# CONTINUATION METHOD FOR MONOTONE SEMIDEFINITE COMPLEMENTARITY PROBLEMS[J]. 数学物理学报(英文版), 2007, 27(2): 243-253.
[9]	张立平, 高自友, 赖炎连. MERIT FUNCTION AND GLOBAL ALGORITHM FOR BOX CONSTRAINED VARIATIONAL INEQUALITIES[J]. 数学物理学报(英文版), 2002, 22(1): 63-71.
[10]	童小娇, 周叔子. GLOBAL CONVERGENCE OF A TRUST REGION ALGORITHM USING INEXACT GRADIENT FOR EQUALITY-CONSTRAINED OPTIMIZATION[J]. 数学物理学报(英文版), 2000, 20(3): 365-373.
[11]	陈发来. BEST LIPSCHITZ CONSTANTS FOR THE BÉZIER NETS AND BERNSTEIN POLYNOMIALS OVER A SIMPLEX[J]. 数学物理学报(英文版), 1998, 18(3): 262-270.
[12]	刘光辉, 韩继业, 戚厚铎, 徐中玲. CONVERGENCE ANALYSIS ON A CLASS OF CONJUGATE GRADIENT METHODS WITHOUT SUFFICIENT DECREASE CONDITION[J]. 数学物理学报(英文版), 1998, 18(1): 11-16.