A globally convergent BFGS method for symmetric nonlinear equations

Weijun Zhou

doi:10.3934/jimo.2021020

Article Contents

2022, Volume 18, Issue 2: 1295-1303. Doi: 10.3934/jimo.2021020

This issue Previous Article Optimality conditions of fenchel-lagrange duality and farkas-type results for composite dc infinite programs Next Article On the optimal control problems with characteristic time control constraints

A globally convergent BFGS method for symmetric nonlinear equations

Weijun Zhou^,

Department of Mathematics and Statistics, Changsha University of Science and Technology, Changsha 410114, China

^* Corresponding author: Weijun Zhou
^* Corresponding author: Weijun Zhou

Received: May 31, 2020

Revised: September 30, 2020

Early access: January 2021

Published: March 2022

The author is supported by National Natural Science Foundation of China (11371073 and 61972055)

Abstract Full Text(HTML) Figure(0) / Table(2) Related Papers Cited by

Abstract

A BFGS type method is presented to solve symmetric nonlinear equations, which is shown to be globally convergent under suitable conditions. Compared with some existing Gauss-Newton-based BFGS methods whose iterative matrix approximates the Gauss-Newton matrix, an important feature of the proposed method lies in that the iterative matrix is an approximation of the Jacobian, which greatly reduces condition number of the iterative matrix. Numerical results are reported to support the theory.

Keywords:

Mathematics Subject Classification: Primary: 90C30; Secondary: 65K05.

Citation:

Full Text(HTML)

Table 1. Test results on Problem 1 with initial point $ x_0 = \beta\hat{x} $

		GN-BFGS				Algorithm 2.1
$ \beta $	$ n $	$ N_{iter} $	$ N_F $	$ \\|F_k\\| $	$ C_{B_k} $	$ N_{iter} $	$ N_F $	$ \\|F_k\\| $	$ C_{B_k} $
0.01	9	22	63	1.9e-007	1578	17	33	1.27e-008	46
	49	288	2041	7.85e-007	1117816	135	626	9.47e-007	1419
	99	1000	8307	3.2e-006	18348874	1000	8072	0.000741	8672
0.1	9	22	64	4.36e-007	1663	17	36	5.04e-007	42
	49	298	2130	8.31e-007	1137498	118	487	8.26e-007	969
	99	1000	8144	0.000850	1642370	1000	7800	0.000692	10814
1	9	23	67	4.76e-007	1787	19	40	2.31e-007	45
	49	191	947	1.13e-007	1061079	160	697	4.13e-007	1255
	99	1000	9113	0.000756	6266525	1000	7474	0.000590	10730
10	9	24	69	7.03e-007	1781	20	39	1.73e-007	45
	49	181	861	2.21e-007	1110234	148	609	4.41e-007	1292
	99	1000	8591	0.000122	1664830	1000	6719	5.27e-005	5989
50	9	25	71	2.51e-007	1713	20	39	4.5e-007	43
	49	185	883	1.11e-007	1098144	133	531	8.71e-007	1217
	99	823	6041	4.55e-008	18835000	548	3361	8.72e-007	4638

| Show Table

DownLoad: CSV

Table 2. Test results on Problem 2 with initial point $ x_0 = \beta\hat{x} $

		GN-BFGS				Algorithm 2.1
$ \beta $	$ n $	$ N_{iter} $	$ N_F $	$ \\|F_k\\| $	$ C_{B_k} $	$ N_{iter} $	$ N_F $	$ \\|F_k\\| $	$ C_{B_k} $
0.01	50	4	37	NaN	Inf	60	235	8.9382e-007	14
	100	5	53	NaN	NaN	79	321	8.7896e-007	28
	200	5	53	NaN	Inf	91	362	8.363e-007	29
0.1	50	67	306	7.6196e-007	72	59	234	5.3211e-007	13
	100	132	623	6.1482e-007	133	83	341	6.9712e-007	29
	200	170	879	8.2061e-007	356	88	358	8.8805e-007	51
1	50	69	312	9.7115e-007	618	59	225	7.0356e-007	13
	100	134	619	9.3146e-007	458	79	322	9.6653e-007	33
	200	186	956	8.5496e-007	595	101	401	9.152e-007	43
10	50	18	241	NaN	NaN	65	265	7.7764e-007	15
	100	15	194	NaN	NaN	88	385	9.7307e-007	49
	200	15	188	NaN	NaN	111	461	7.7243e-007	50
-0.1	50	77	341	4.4278e-007	59	60	236	9.0422e-007	26
	100	120	585	9.5748e-007	136	73	305	9.8125e-007	39
	200	221	1011	8.6068e-007	456	90	366	8.6948e-007	40
	500	296	1684	9.1214e-007	1095	88	359	9.9204e-007	79

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	S. Bojari and M. R. Eslahchi, Global convergence of a family of modified BFGS methods under a modified weak Wolfe-Powell line search for nonconvex functions, 4OR, 18 (2020), 219-244. doi: 10.1007/s10288-019-00412-2.
[2]	R. H. 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.
[3]	H. Cao and D. Li, Adjoint Broyden methods for symmetric nonlinear equations, Pac. J. Optim., 13 (2017), 645-663.
[4]	J. E. Dennis and J. J. Moré, A characterization of superlinear convergence and its applications to quasi-Newton methods, Math. Comput., 28 (1974), 549-560. doi: 10.1090/S0025-5718-1974-0343581-1.
[5]	Y.-H. Dai, Convergence properties of the BFGS algorithm, SIAM J. Optim., 13 (2002), 693-701. doi: 10.1137/S1052623401383455.
[6]	G. Gu, D. Li, L. Qi and S. Zhou, Descent directions of quasi-Newton method for symmetric nonlinear equations, SIAM J. Numer. Anal., 40 (2002), 1763-1774. doi: 10.1137/S0036142901397423.
[7]	D. Li and M. Fukushima, A globally and superlinearly convergent Gauss-Newton-based BFGS method for symmetric nonlinear equations, SIAM J. Numer. Anal., 37 (1999), 152-172. doi: 10.1137/S0036142998335704.
[8]	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.
[9]	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.
[10]	W. F. Mascarenhas, The BFGS method with exact line searches fails for nonconvex objective functions, Math. Program., 99 (2004), 49-61. doi: 10.1007/s10107-003-0421-7.
[11]	W. Sun and Y. Yuan, Optimization Theory and Methods, Springer Science and Business Media, LLC, New York, 2006.
[12]	Z. Wang, Y. Chen, S. Huang and D. Feng, A modified nonmonotone BFGS algorithm for solving smooth nonlinear equations, Optim. Lett., 8 (2014), 1845-1860. doi: 10.1007/s11590-013-0678-6.
[13]	Z. Wan, K. Teo, X. Chen and C. Hu, New BFGS method for unconstrained optimization problem based on modified Armijo line search, Optimization, 63 (2014), 285-304. doi: 10.1080/02331934.2011.644284.
[14]	G. Yuan and X. Lu, A new backtracking inexact BFGS method for symmetric nonlinear equations, Comput. Math. Appl., 55 (2008), 116-129. doi: 10.1016/j.camwa.2006.12.081.
[15]	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.
[16]	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.
[17]	G. Yuan and S. Yao, A BFGS algorithm for solving symmetric nonlinear equations, Optimization, 62 (2013), 85-99. doi: 10.1080/02331934.2011.564621.
[18]	L. Zhang, A derivative-free conjugate residual method using secant condition for general large-scale nonlinear equations, Numer. Algo., 83 (2020), 1277-1293. doi: 10.1007/s11075-019-00725-7.
[19]	L. Zhang and H. Tang, A hybrid MBFGS and CBFGS method for nonconvex minimization with a global complexity bound, Pac. J. Optim., 14 (2018), 693-702.
[20]	W. Zhou, A Gauss-Newton-based BFGS method for symmetric nonlinear least squares problems, Pac. J. Optim., 9 (2013), 373-389.
[21]	W. Zhou, A modified BFGS type quasi-Newton method with line search for symmetric nonlinear equations problems, J. Comput. Appl. Math., 367 (2020), 112454, 8 pp. doi: 10.1016/j.cam.2019.112454.
[22]	W. Zhou and X. Chen, Global convergence of a new hybrid Gauss-Newton structured BFGS methods for nonlinear least squares problems, SIAM J. Optim., 20 (2010), 2422-2441. doi: 10.1137/090748470.
[23]	W. Zhou and D. Li, On the Q-linear convergence rate of a class of methods for monotone nonlinear equations, Pac. J. Optim., 14 (2018), 723-737.
[24]	W. Zhou and D. Shen, Convergence properties of an iterative method for solving symmetric nonlinear equations, J. Optim. Theory Appl., 164 (2015), 277-289. doi: 10.1007/s10957-014-0547-1.
[25]	W. Zhou and D. Shen, An inexact PRP conjugate gradient method for symmetric nonlinear equations, Numer. Funct. Anal. Optim., 35 (2014), 370-388. doi: 10.1080/01630563.2013.871290.
[26]	W. Zhou and F. Wang, A PRP-based residual method for large-scale monotone nonlinear equations, Appl. Math. Comput., 261 (2015), 1-7. doi: 10.1016/j.amc.2015.03.069.
[27]	W. Zhou and L. Zhang, A modified Broyden-like quasi-Newton method for nonlinear equations, J. Comput. Appl. Math., 372 (2020), 112744, 10 pp. doi: 10.1016/j.cam.2020.112744.