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

doi:10.1007/s10473-024-0506-3

Abstract

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

CLC Number:

90C30

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.

Trendmd

References

[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^*

Abstract

Cite this article

share this article

References

Related Articles 13

Metrics

Comments

Recommended 10

[1]	Zhenhai Liu, Nikolaos S. Papageorgiou. PERIODIC SYSTEMS WITH TIME DEPENDENT MAXIMAL MONOTONE OPERATORS [J]. Acta mathematica scientia,Series B, 2024, 44(4): 1280-1300.
[2]	Yongfu YANG, Qiangchang JU, Shuang ZHOU. THE GLOBAL COMBINED QUASI-NEUTRAL AND ZERO-ELECTRON-MASS LIMIT OF NON-ISENTROPIC EULER-POISSON SYSTEMS [J]. Acta mathematica scientia,Series B, 2022, 42(4): 1666-1680.
[3]	Deguang ZHONG, Fanning MENG, Wenjun YUAN. ON SCHWARZ-PICK TYPE INEQUALITY FOR MAPPINGS SATISFYING POISSON DIFFERENTIAL INEQUALITY [J]. Acta mathematica scientia,Series B, 2021, 41(3): 959-967.
[4]	Jinbao JIAN, Guodong MA. A GLOBALLY CONVERGENT QP-FREE ALGORITHM FOR INEQUALITY CONSTRAINED MINIMAX OPTIMIZATION [J]. Acta mathematica scientia,Series B, 2020, 40(6): 1723-1738.
[5]	Zhou SHENG, Gonglin YUAN, Zengru CUI. A NEW ADAPTIVE TRUST REGION ALGORITHM FOR OPTIMIZATION PROBLEMS [J]. Acta mathematica scientia,Series B, 2018, 38(2): 479-496.
[6]	Volker Elling. HÖLDER CONTINUITY AND DIFFERENTIABILITY ON CONVERGING SUBSEQUENCES [J]. Acta mathematica scientia,Series B, 2012, 32(1): 75-83.
[7]	Chi Xiaoni; Liu Sanyang. AN INFEASIBLE-INTERIOR-POINT PREDICTOR-CORRECTOR ALGORITHM FOR THE SECOND-ORDER CONE PROGRAM [J]. Acta mathematica scientia,Series B, 2008, 28(3): 551-559.
[8]	Zhang Liping. A GLOBAL LINEAR AND LOCAL QUADRATIC SINGLE--STEP NONINTERIOR#br# CONTINUATION METHOD FOR MONOTONE SEMIDEFINITE COMPLEMENTARITY PROBLEMS [J]. Acta mathematica scientia,Series B, 2007, 27(2): 243-253.
[9]	WANG Yi-Ju, ZHOU Hou-Chun, WANG Chang-Yu. A REGULARIZATION NEWTON METHOD FOR MIXED COMPLEMENTARITY PROBLEMS [J]. Acta mathematica scientia,Series B, 2004, 24(3): 376-384.
[10]	ZHANG Li-Ping, GAO Zi-You, LAI Yan-Lian. MERIT FUNCTION AND GLOBAL ALGORITHM FOR BOX CONSTRAINED VARIATIONAL INEQUALITIES [J]. Acta mathematica scientia,Series B, 2002, 22(1): 63-71.
[11]	TONG Xiao-Jiao, ZHOU Shu-Zi. GLOBAL CONVERGENCE OF A TRUST REGION ALGORITHM USING INEXACT GRADIENT FOR EQUALITY-CONSTRAINED OPTIMIZATION [J]. Acta mathematica scientia,Series B, 2000, 20(3): 365-373.
[12]	Chen Falai. BEST LIPSCHITZ CONSTANTS FOR THE BÉZIER NETS AND BERNSTEIN POLYNOMIALS OVER A SIMPLEX [J]. Acta mathematica scientia,Series B, 1998, 18(3): 262-270.
[13]	Liu Gnanghui, Han Jiye, Qi Honduo, Xu Zhongling. CONVERGENCE ANALYSIS ON A CLASS OF CONJUGATE GRADIENT METHODS WITHOUT SUFFICIENT DECREASE CONDITION [J]. Acta mathematica scientia,Series B, 1998, 18(1): 11-16.