American Institute of Mathematical Sciences

Advanced
March  2022, 18(2): 1295-1303. doi: 10.3934/jimo.2021020

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

Received  June 2020 Revised  October 2020 Published  March 2022 Early access  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.

Keywords: Nonlinear, equations, symmetry, BFGS, global convergence.
Mathematics Subject Classification: Primary: 90C30; Secondary: 65K05.
Citation: Weijun Zhou. A globally convergent BFGS method for symmetric nonlinear equations. Journal of Industrial and Management Optimization, 2022, 18 (2) : 1295-1303. 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.

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

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.

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

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
Table Options

Download as excel

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
Table Options

Download as excel

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]

Sven Jarohs, Tobias Weth. Asymptotic symmetry for a class of nonlinear fractional reaction-diffusion equations. Discrete and Continuous Dynamical Systems, 2014, 34 (6) : 2581-2615. doi: 10.3934/dcds.2014.34.2581
[2]

Chunlin Hao, Xinwei Liu. Global convergence of an SQP algorithm for nonlinear optimization with overdetermined constraints. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 19-29. doi: 10.3934/naco.2012.2.19
[3]

Zhong Tan, Qiuju Xu, Huaqiao Wang. Global existence and convergence rates for the compressible magnetohydrodynamic equations without heat conductivity. Discrete and Continuous Dynamical Systems, 2015, 35 (10) : 5083-5105. doi: 10.3934/dcds.2015.35.5083
[4]

Ruiying Wei, Yin Li, Zheng-an Yao. Global existence and convergence rates of solutions for the compressible Euler equations with damping. Discrete and Continuous Dynamical Systems - B, 2020, 25 (8) : 2949-2967. doi: 10.3934/dcdsb.2020047
[5]

Xingwen Hao, Yachun Li, Zejun Wang. Non-relativistic global limits to the three dimensional relativistic euler equations with spherical symmetry. Communications on Pure and Applied Analysis, 2010, 9 (2) : 365-386. doi: 10.3934/cpaa.2010.9.365
[6]

Walter Allegretto, Yanping Lin, Zhiyong Zhang. Convergence to convection-diffusion waves for solutions to dissipative nonlinear evolution equations. Conference Publications, 2009, 2009 (Special) : 11-23. doi: 10.3934/proc.2009.2009.11
[7]

Jiangxing Wang. Convergence analysis of an accurate and efficient method for nonlinear Maxwell's equations. Discrete and Continuous Dynamical Systems - B, 2021, 26 (5) : 2429-2440. doi: 10.3934/dcdsb.2020185
[8]

José A. Carrillo, Jean Dolbeault, Ivan Gentil, Ansgar Jüngel. Entropy-energy inequalities and improved convergence rates for nonlinear parabolic equations. Discrete and Continuous Dynamical Systems - B, 2006, 6 (5) : 1027-1050. doi: 10.3934/dcdsb.2006.6.1027
[9]

Matteo Novaga, Diego Pallara, Yannick Sire. A symmetry result for degenerate elliptic equations on the Wiener space with nonlinear boundary conditions and applications. Discrete and Continuous Dynamical Systems - S, 2016, 9 (3) : 815-831. doi: 10.3934/dcdss.2016030
[10]

Xavier Cabré, Eleonora Cinti. Energy estimates and 1-D symmetry for nonlinear equations involving the half-Laplacian. Discrete and Continuous Dynamical Systems, 2010, 28 (3) : 1179-1206. doi: 10.3934/dcds.2010.28.1179
[11]

Jeremy L. Marzuola, Michael I. Weinstein. Long time dynamics near the symmetry breaking bifurcation for nonlinear Schrödinger/Gross-Pitaevskii equations. Discrete and Continuous Dynamical Systems, 2010, 28 (4) : 1505-1554. doi: 10.3934/dcds.2010.28.1505
[12]

W. Wei, H. M. Yin. Global solvability for a singular nonlinear Maxwell's equations. Communications on Pure and Applied Analysis, 2005, 4 (2) : 431-444. doi: 10.3934/cpaa.2005.4.431
[13]

Daniela Giachetti, Maria Michaela Porzio. Global existence for nonlinear parabolic equations with a damping term. Communications on Pure and Applied Analysis, 2009, 8 (3) : 923-953. doi: 10.3934/cpaa.2009.8.923
[14]

Zuzana Došlá, Mauro Marini, Serena Matucci. Global Kneser solutions to nonlinear equations with indefinite weight. Discrete and Continuous Dynamical Systems - B, 2018, 23 (8) : 3297-3308. doi: 10.3934/dcdsb.2018252
[15]

Monica Conti, Elsa M. Marchini, V. Pata. Global attractors for nonlinear viscoelastic equations with memory. Communications on Pure and Applied Analysis, 2016, 15 (5) : 1893-1913. doi: 10.3934/cpaa.2016021
[16]

Huijiang Zhao, Yinchuan Zhao. Convergence to strong nonlinear rarefaction waves for global smooth solutions of $p-$system with relaxation. Discrete and Continuous Dynamical Systems, 2003, 9 (5) : 1243-1262. doi: 10.3934/dcds.2003.9.1243
[17]

Changlu Liu, Shuangli Qiao. Symmetry and monotonicity for a system of integral equations. Communications on Pure and Applied Analysis, 2009, 8 (6) : 1925-1932. doi: 10.3934/cpaa.2009.8.1925
[18]

Toshiko Ogiwara, Hiroshi Matano. Monotonicity and convergence results in order-preserving systems in the presence of symmetry. Discrete and Continuous Dynamical Systems, 1999, 5 (1) : 1-34. doi: 10.3934/dcds.1999.5.1
[19]

Stefano Scrobogna. Global existence and convergence of nondimensionalized incompressible Navier-Stokes equations in low Froude number regime. Discrete and Continuous Dynamical Systems, 2020, 40 (9) : 5471-5511. doi: 10.3934/dcds.2020235
[20]

Annie Raoult. Symmetry groups in nonlinear elasticity: an exercise in vintage mathematics. Communications on Pure and Applied Analysis, 2009, 8 (1) : 435-456. doi: 10.3934/cpaa.2009.8.435

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (383)
  • HTML views (505)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy