• Previous Article
    Modeling and computation of mean field game with compound carbon abatement mechanisms
  • JIMO Home
  • This Issue
  • Next Article
    Dynamic discrete-time portfolio selection for defined contribution pension funds with inflation risk
doi: 10.3934/jimo.2021020

A globally convergent BFGS method for symmetric nonlinear equations

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

* Corresponding author: Weijun Zhou

Received  June 2020 Revised  October 2020 Published  January 2021

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

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.

Citation: Weijun Zhou. A globally convergent BFGS method for symmetric nonlinear equations. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2021020
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.  Google Scholar

[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.  Google Scholar

[3]

H. Cao and D. Li, Adjoint Broyden methods for symmetric nonlinear equations, Pac. J. Optim., 13 (2017), 645-663.   Google Scholar

[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.  Google Scholar

[5]

Y.-H. Dai, Convergence properties of the BFGS algorithm, SIAM J. Optim., 13 (2002), 693-701.  doi: 10.1137/S1052623401383455.  Google Scholar

[6]

G. GuD. LiL. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[11]

W. Sun and Y. Yuan, Optimization Theory and Methods, Springer Science and Business Media, LLC, New York, 2006.  Google Scholar

[12]

Z. WangY. ChenS. 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.  Google Scholar

[13]

Z. WanK. TeoX. 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.  Google Scholar

[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.  Google Scholar

[15]

G. YuanZ. ShengB. WangW. 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.  Google Scholar

[16]

G. YuanZ. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[20]

W. Zhou, A Gauss-Newton-based BFGS method for symmetric nonlinear least squares problems, Pac. J. Optim., 9 (2013), 373-389.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

show all references

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.  Google Scholar

[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.  Google Scholar

[3]

H. Cao and D. Li, Adjoint Broyden methods for symmetric nonlinear equations, Pac. J. Optim., 13 (2017), 645-663.   Google Scholar

[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.  Google Scholar

[5]

Y.-H. Dai, Convergence properties of the BFGS algorithm, SIAM J. Optim., 13 (2002), 693-701.  doi: 10.1137/S1052623401383455.  Google Scholar

[6]

G. GuD. LiL. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[11]

W. Sun and Y. Yuan, Optimization Theory and Methods, Springer Science and Business Media, LLC, New York, 2006.  Google Scholar

[12]

Z. WangY. ChenS. 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.  Google Scholar

[13]

Z. WanK. TeoX. 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.  Google Scholar

[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.  Google Scholar

[15]

G. YuanZ. ShengB. WangW. 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.  Google Scholar

[16]

G. YuanZ. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[20]

W. Zhou, A Gauss-Newton-based BFGS method for symmetric nonlinear least squares problems, Pac. J. Optim., 9 (2013), 373-389.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

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
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
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
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
[1]

Irena PawŃow, Wojciech M. Zajączkowski. Global regular solutions to three-dimensional thermo-visco-elasticity with nonlinear temperature-dependent specific heat. Communications on Pure & Applied Analysis, 2017, 16 (4) : 1331-1372. doi: 10.3934/cpaa.2017065

[2]

Bernold Fiedler, Carlos Rocha, Matthias Wolfrum. Sturm global attractors for $S^1$-equivariant parabolic equations. Networks & Heterogeneous Media, 2012, 7 (4) : 617-659. doi: 10.3934/nhm.2012.7.617

[3]

Hirofumi Notsu, Masato Kimura. Symmetry and positive definiteness of the tensor-valued spring constant derived from P1-FEM for the equations of linear elasticity. Networks & Heterogeneous Media, 2014, 9 (4) : 617-634. doi: 10.3934/nhm.2014.9.617

[4]

Xiaoming Wang. Quasi-periodic solutions for a class of second order differential equations with a nonlinear damping term. Discrete & Continuous Dynamical Systems - S, 2017, 10 (3) : 543-556. doi: 10.3934/dcdss.2017027

[5]

Bin Pei, Yong Xu, Yuzhen Bai. Convergence of p-th mean in an averaging principle for stochastic partial differential equations driven by fractional Brownian motion. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1141-1158. doi: 10.3934/dcdsb.2019213

[6]

Rafael Luís, Sandra Mendonça. A note on global stability in the periodic logistic map. Discrete & Continuous Dynamical Systems - B, 2020, 25 (11) : 4211-4220. doi: 10.3934/dcdsb.2020094

[7]

Lakmi Niwanthi Wadippuli, Ivan Gudoshnikov, Oleg Makarenkov. Global asymptotic stability of nonconvex sweeping processes. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1129-1139. doi: 10.3934/dcdsb.2019212

[8]

J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008

[9]

Fernando P. da Costa, João T. Pinto, Rafael Sasportes. On the convergence to critical scaling profiles in submonolayer deposition models. Kinetic & Related Models, 2018, 11 (6) : 1359-1376. doi: 10.3934/krm.2018053

[10]

Alberto Bressan, Carlotta Donadello. On the convergence of viscous approximations after shock interactions. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 29-48. doi: 10.3934/dcds.2009.23.29

[11]

Caifang Wang, Tie Zhou. The order of convergence for Landweber Scheme with $\alpha,\beta$-rule. Inverse Problems & Imaging, 2012, 6 (1) : 133-146. doi: 10.3934/ipi.2012.6.133

[12]

Min Li. A three term Polak-Ribière-Polyak conjugate gradient method close to the memoryless BFGS quasi-Newton method. Journal of Industrial & Management Optimization, 2020, 16 (1) : 245-260. doi: 10.3934/jimo.2018149

[13]

Alexey Yulin, Alan Champneys. Snake-to-isola transition and moving solitons via symmetry-breaking in discrete optical cavities. Discrete & Continuous Dynamical Systems - S, 2011, 4 (5) : 1341-1357. doi: 10.3934/dcdss.2011.4.1341

[14]

Yanqin Fang, Jihui Zhang. Multiplicity of solutions for the nonlinear Schrödinger-Maxwell system. Communications on Pure & Applied Analysis, 2011, 10 (4) : 1267-1279. doi: 10.3934/cpaa.2011.10.1267

[15]

Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017

[16]

Carlos Gutierrez, Nguyen Van Chau. A remark on an eigenvalue condition for the global injectivity of differentiable maps of $R^2$. Discrete & Continuous Dynamical Systems - A, 2007, 17 (2) : 397-402. doi: 10.3934/dcds.2007.17.397

[17]

Olena Naboka. On synchronization of oscillations of two coupled Berger plates with nonlinear interior damping. Communications on Pure & Applied Analysis, 2009, 8 (6) : 1933-1956. doi: 10.3934/cpaa.2009.8.1933

[18]

Sergi Simon. Linearised higher variational equations. Discrete & Continuous Dynamical Systems - A, 2014, 34 (11) : 4827-4854. doi: 10.3934/dcds.2014.34.4827

[19]

Haibo Cui, Haiyan Yin. Convergence rate of solutions toward stationary solutions to the isentropic micropolar fluid model in a half line. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020210

[20]

Jaume Llibre, Luci Any Roberto. On the periodic solutions of a class of Duffing differential equations. Discrete & Continuous Dynamical Systems - A, 2013, 33 (1) : 277-282. doi: 10.3934/dcds.2013.33.277

2019 Impact Factor: 1.366

Article outline

Figures and Tables

[Back to Top]