Global convergence of a modified Broyden family method for nonconvex functions

Gonglin Yuan; Zhan Wang; Pengyuan Li

doi:10.3934/jimo.2021164

Article Contents

2022, Volume 18, Issue 6: 4393-4407. Doi: 10.3934/jimo.2021164

This issue Previous Article Synchronized abandonment in discrete-time renewal input queues with vacations Next Article Effect of service quality on software sales and coordination mechanism in IT service supply chain

Global convergence of a modified Broyden family method for nonconvex functions

College of Mathematics and Information Science, Guangxi University, Center for Applied Mathematics of Guangxi, Nanning, Guangxi 530004, China

^*Corresponding author: Zhan Wang (zhanwxd@126.com)
^*Corresponding author: Zhan Wang (zhanwxd@126.com)

Received: July 31, 2020

Revised: March 31, 2021

Early access: September 2021

Published: September 2022

This work is supported by the National Natural Science Foundation of China (Grant No. 11661009), the High Level Innovation Teams and Excellent Scholars Program in Guangxi institutions of higher education (Grant No.[2019]52), the Guangxi Natural Science Key Fund (No. 2017GXNSFDA198046), the Special Funds for Local Science and Technology Development Guided by the Central Government (No. ZY20198003), and the special foundation for Guangxi Ba Gui Scholars

Abstract Full Text(HTML) Figure(4) / Table(1) Related Papers Cited by

Abstract

The Broyden family method is one of the most effective methods for solving unconstrained optimization problems. However, the study of the global convergence of the Broyden family method is not sufficient. In this paper, a new Broyden family method is proposed based on the BFGS formula of Yuan and Wei (Comput. Optim. Appl. 47: 237-255, 2010). The following approaches are used in the designed algorithm: (1) a modified Broyden family formula is given, (2) every matrix sequence $ \{B_k\} $ generated by the new algorithm possesses positive-definiteness, and (3) the global convergence of the new presented Broyden family algorithm with the Y-W-L inexact line search is obtained for general functions. Numerical performance shows that the modified Broyden family method is competitive with the classical Broyden family method.

Keywords:

Mathematics Subject Classification: Primary: 90C53.

Citation:

Full Text(HTML)

Figure 1. Performance profiles of the algorithm MBroyden with different $ \phi $

Download: Full-size image PowerPoint slide

Figure 2. Performance profiles of these methods(CPU)

Download: Full-size image PowerPoint slide

Figure 3. Performance profiles of these methods(NI)

Download: Full-size image PowerPoint slide

Figure 4. Performance profiles of these methods(NFG)

Download: Full-size image PowerPoint slide

Table 1. Test problems

No.	Test problems	No.	Test problems
1	Extended Freudenstein and Roth Function	38	ARWHEAD Function (CUTE)
2	Extended Trigonometric Function	39	ARWHEAD Function (CUTE)
3	Extended Rosenbrock Function	40	NONDQUAR Function (CUTE)
4	Extended White and Holst Function	41	DQDRTIC Function (CUTE)
5	Extended Beale Function	42	EG2 Function (CUTE)
6	Extended Penalty Function	43	DIXMAANA Function (CUTE)
7	Perturbed Quadratic Function	44	DIXMAANB Function (CUTE)
8	Raydan 1 Function	45	DIXMAANC Function (CUTE)
9	Raydan 2 Function	46	DIXMAANE Function (CUTE)
10	Diagonal 1 Function	47	Partial Perturbed Quadratic Function
11	Diagonal 2 Function	48	Broyden Tridiagonal Function
12	Diagonal 3 Function	49	Almost Perturbed Quadratic Function
13	Hager Function	50	Tridiagonal Perturbed Quadratic Function
14	Generalized Tridiagonal 1 Function	51	EDENSCH Function (CUTE)
15	Extended Tridiagonal 1 Function	52	VARDIM Function (CUTE)
16	Extended Three Exponential Terms Function	53	STAIRCASE S1 Function
17	Generalized Tridiagonal 2 Function	54	LIARWHD Function (CUTE)
18	Diagonal 4 Function	55	DIAGONAL 6 Function
19	Diagonal 5 Function	56	DIXON3DQ Function (CUTE)
20	Extended Himmelblau Function	57	DIXMAANF Function (CUTE)
21	Generalized PSC1 Function	58	DIXMAANG Function (CUTE)
22	Extended PSC1 Function	59	DIXMAANH Function (CUTE)
23	Extended Powell Function	60	DIXMAANI Function (CUTE)
24	Extended Block Diagonal BD1 Function	61	DIXMAANJ Function (CUTE)
25	Extended Maratos Function	62	DIXMAANK Function (CUTE)
26	Extended Cliff Function	63	DIXMAANL Function (CUTE)
27	Quadratic Diagonal Perturbed Function	64	DIXMAAND Function (CUTE)
28	Extended Wood Function	65	ENGVAL1 Function (CUTE)
29	Extended Hiebert Function	66	FLETCHCR Function (CUTE)
30	Quadratic Function QF1 Function	67	COSINE Function (CUTE)
31	Extended Quadratic Penalty QP1 Function	68	Extended DENSCHNB Function (CUTE)
32	Extended Quadratic Penalty QP2 Function	69	DENSCHNF Function (CUTE)
33	A Quadratic Function QF2 Function	70	SINQUAD Function (CUTE)
34	Extended EP1 Function	71	BIGGSB1 Function (CUTE)
35	Extended Tridiagonal-2 Function	72	Partial Perturbed Quadratic PPQ2 Function
36	BDQRTIC Function (CUTE)	73	Scaled Quadratic SQ1 Function
37	TRIDIA Function (CUTE)

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	M. Al-Baali and H. Khalfan, A combined class of self-scaling and modified quasi-Newton methods, Comput. Optim. Appl., 52 (2012), 393-408. doi: 10.1007/s10589-011-9415-1.
[2]	C. G. Broyden, J. E. Dennis and J. J. Mor$\acute{e}$, On the local and superlinear convergence of quasi-Newton methods, J. Inst. Math. Appl., 12 (1973), 223-245. doi: 10.1093/imamat/12.3.223.
[3]	R. Byrd, J. Nocedal and Y. Yuan, Global convergence of a class of quasi-Newton methods on convex problems, SIAM J. Numer. Anal., 24 (1987), 1171-1189. doi: 10.1137/0724077.
[4]	R. Byrd and J. Nocedal, A tool for the analysis of quasi-Newton methods with application to unconstrained minimization, SIAM J. Numer. Anal., 26 (1989), 727-739. doi: 10.1137/0726042.
[5]	E. D. Dolan and J. J. Mor$\acute{e}$, Benchmarking optimization software with performance profiles, Math. Program., 91 (2002), 201-213. doi: 10.1007/s101070100263.
[6]	L. C. W. Dixon, Variable metric algorithms: Nessary and sufficient conditions for identical behavior on nonquadratic functions, J. Optimiz. Theory. App., 10 (1972), 34-40. doi: 10.1007/BF00934961.
[7]	J. E. Dennis Jr and J. J. Mor$\acute{e}$, Quasi-Newton methods, motivation and theory, SIAM Rev., 19 (1977), 46-89. doi: 10.1137/1019005.
[8]	J. E. Dennis and R. B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Prentice Hall, Inc., Englewood Cliffs, NJ, 1983.
[9]	Y. Dai, Convergence properties of the BFGS algoritm, SIAM J. Optim., 13 (2003), 693-701. doi: 10.1137/S1052623401383455.
[10]	R. Fletcher, Practical Methods of Optimization, 2$^nd$ edition, A Wiley-Interscience Publication. John Wiley & Sons, Ltd., Chichester, 1987.
[11]	A. Griewank, The global convergence of partitioned BFGS on problems with convex decompositions and Lipschitzian gradients, Math. Program., 50 (1991), 141-175. doi: 10.1007/BF01594933.
[12]	A. Griewank, The "global" convergence of Broyden-like methods with suitable line search, J. Austral. Math. Soc. Ser., 28 (1986), 75-92. doi: 10.1017/S0334270000005208.
[13]	Z. W. Geem, Parameter estimation for the nonlinear Muskingum model using the BFGS technique, J. Irrig. Drain. Eng., 132 (2006), 474-478. doi: 10.1061/(ASCE)0733-9437(2006)132:5(474).
[14]	D. Li and M. Fukushima, A modified BFGS method and its global convergence in nonconvex minimization, J. Comput. Appl. Math., 129 (2001), 15-35. doi: 10.1016/S0377-0427(00)00540-9.
[15]	D. Li and M. Fukushima, On the global convergence of the BFGS method for nonconvex unconstrained optimization problems, SIAM J. Optim., 11 (2001), 1054-1064. doi: 10.1137/S1052623499354242.
[16]	A. Ouyang, L. Liu, Z. Sheng and F. Wu, A class of parameter estimation methods for nonlinear Muskingum model using hybrid invasive weed optimization algorithm, Math. Probl. Eng., 2015 (2015), 1-15. doi: 10.1155/2015/573894.
[17]	A. Ouyang, Z. Tang, K. Li, A. Sallam and E. Sha, Estimating parameters of Muskingum model using an adaptive hybrid PSO algorithm, Int. J. Pattern. Recogn., 28 (2014), 1-29. doi: 10.1142/S0218001414590034.
[18]	M. J. D. Powell, On the convergence of the variable metric algorithm, J. Inst. Math. Appl., 7 (1971), 21-36. doi: 10.1093/imamat/7.1.21.
[19]	M. J. D. Powell, Some global convergence properties of a variable metric algorithm for minimization without exact line searches, Nonlinear Programming, SIAM-AMS Proc., Amer. Math. Soc., Providence, R. I., 9 (1976), 53–72.
[20]	J. D. Pearson, Variable metric methods of minimization, Comput. J., 12 (1969/70), 171-178. doi: 10.1093/comjnl/12.2.171.
[21]	J. Schropp, A note on minimization problems and multistep methods, Numer. Math., 78 (1997), 87-101. doi: 10.1007/s002110050305.
[22]	J. Schropp, One-step and multistep procedures for constrained minimization problems, IMA J. Numer. Anal., 20 (2000), 135-152. doi: 10.1093/imanum/20.1.135.
[23]	P. L. Toint, Global convergence of the partitioned BFGS algorithm for convex partially separable optimization, Math. Program., 36 (1986), 290-306. doi: 10.1007/BF02592063.
[24]	D. J. Van Wyk, Differential optimization techniques, Appl. Math. Model., 8 (1984), 419-424. doi: 10.1016/0307-904X(84)90048-9.
[25]	M. N. Vrahatis, G. S. Androulakis and J. N. Lambrinos, et al., A class of gradient unconstrained minimization algorithms with adaptive stepsize, J. Comput. Appl. Math., 114 (2000), 367-386. doi: 10.1016/S0377-0427(99)00276-9.
[26]	Z. Wei, G. Li and L. Qi, New quasi-Newton methods for unconstrained optimization problems, Appl. Math. Comput., 175 (2006), 1156-1188. doi: 10.1016/j.amc.2005.08.027.
[27]	Z. Wei, G. Yu, G. Yuan and Z. Lian, The superlinear convergence of a modified BFGS-type method for unconstrained optimization, Comput. Optim. Appl., 29 (2004), 315-332. doi: 10.1023/B:COAP.0000044184.25410.39.
[28]	H. Yabe, H. Ogasawara and M. Yoshino, Local and superlinear convergence of quasi-Newton methods based on modified secant conditions, J. Comput. Appl. Math., 205 (2007), 617-632. doi: 10.1016/j.cam.2006.05.018.
[29]	G. Yuan and X. Lu, A new line search method with trust region for unconstrained optimization, Comm. Appl. Nonlinear Anal., 15 (2008), 35-49.
[30]	G. Yuan, Z. Sheng, B. Wang, W. Hu and C. Li, The global convergence of a modified BFGS method for nonconvex functions, J. Comput. Appl. Math., 327 (2018), 274-294. doi: 10.1016/j.cam.2017.05.030.
[31]	G. Yuan, Z. Wang and P. Li, A modifed Broyden family algorithm with global convergence under a weak Wolfe-Powell line search for unconstrained nonconvex problems, Calcolo., 57 (2020), 21pp. doi: 10.1007/s10092-020-00383-5.
[32]	G. Yuan, Z. Wei and X. Lu, Global convergence of BFGS and PRP methods under a modified weak Wolfe-Powell line search, Appl. Math. Model., 47 (2017), 811-825. doi: 10.1016/j.apm.2017.02.008.
[33]	G. Yuan and Z. Wei, Convergence analysis of a modified BFGS method on convex minimizations, Comput. Optim. Appl., 47 (2010), 237-255. doi: 10.1007/s10589-008-9219-0.
[34]	G. Yuan and Z. Wei, New line search methods for unconstrained optimization, J. Korean Statist. Soc., 38 (2009), 29-39. doi: 10.1016/j.jkss.2008.05.004.
[35]	G. Yuan, Modified nonlinear conjugate gradient methods with sufficient descent property for large-scale optimization problems, Optim. Lett., 3 (2009), 11-21. doi: 10.1007/s11590-008-0086-5.
[36]	Y. Yuan and W. Sun, Theory and Methods of Optimization, Science Press of China, Beijing, 1999.