• Previous Article
    Celis-Dennis-Tapia based approach to quadratic fractional programming problems with two quadratic constraints
  • NACO Home
  • This Issue
  • Next Article
    Convergence analysis of sparse quasi-Newton updates with positive definite matrix completion for two-dimensional functions
2011, 1(1): 71-82. doi: 10.3934/naco.2011.1.71

A modified Fletcher-Reeves-Type derivative-free method for symmetric nonlinear equations

1. 

School of Mathematical Sciences, South China Normal University, Guangzhou, 510631, China

2. 

College of Mathematics and Econometrics, Hunan University, Changsha, 410082, China

Received  October 2010 Revised  October 2010 Published  February 2011

In this paper, we propose a descent derivative-free method for solving symmetric nonlinear equations. The method is an extension of the modified Fletcher-Reeves (MFR) method proposed by Zhang, Zhou and Li [25] to symmetric nonlinear equations. It can be applied to solve large-scale symmetric nonlinear equations due to lower storage requirement. An attractive property of the method is that the directions generated by the method are descent for the residual function. By the use of some backtracking line search technique, the generated sequence of function values is decreasing. Under appropriate conditions, we show that the proposed method is globally convergent. The preliminary numerical results show that the method is practically effective.
Citation: Dong-Hui Li, Xiao-Lin Wang. A modified Fletcher-Reeves-Type derivative-free method for symmetric nonlinear equations. Numerical Algebra, Control and Optimization, 2011, 1 (1) : 71-82. doi: 10.3934/naco.2011.1.71
References:
[1]

M. Al-Baali, Descent property and global convergence of the Fletcher-Reeves method with inexact line search, IMA Journal of Numerical Analysis, 5 (1985), 121-124. doi: 10.1093/imanum/5.1.121.

[2]

S. Bellavia and B. Morini, A globally convergent Newton-GMRES subspace method for systems of nonlinear equations, SIAM Journal on Scientific Computing, 23 (2001), 940-960. doi: 10.1137/S1064827599363976.

[3]

A. Griewank, The “global” convergence of Broyden-like methods with suitable line search, Journal of Australia Mathematical Society, Ser. B, 28 (1986), 75-92.

[4]

W. Cheng and D. H. Li, A derivative-free nonmonotone line search and its application to the spectral residual method, IMA Journal of Numerical Analysis, 29 (2009), 814-825. doi: 10.1093/imanum/drn019.

[5]

Y. H. Dai and Y. Yuan, Convergence of the Fletcher-Reeves method under a generalized Wolfe search, Journal of Computational Mathematics, 2 (1996), 142-148.

[6]

Y. H. Dai and Y. Yuan, Convergence properties of the Fletcher-Reeves method, IMA Journal of Numerical Analysis, 16 (1996), 155-164. doi: 10.1093/imanum/16.2.155.

[7]

Y. H. Dai and Y. Yuan, "Nonlinear Conjugate Gradient Methods," Shanghai Science and Technology Publisher, Shanghai, 2000.

[8]

R. Fletcher and C. Reeves, Function minimization by conjugate gradients, Computer Journal, 7 (1964), 149-154. doi: 10.1093/comjnl/7.2.149.

[9]

J. C. Gilbert and J. Nocedal, Global convergence properties of conjugate gradient methods for optimization, SIAM Journal on Optimization, 2 (1992), 21-42. doi: 10.1137/0802003.

[10]

G. Z. Gu, D. H. Li, L. Qi and S. Z. Zhou, Descent directions of Quasi-Newton methods for symmetric nonlinear equations, SIAM Journal on Numerical Analysis, 40 (2003), 1763-1774. doi: 10.1137/S0036142901397423.

[11]

J. Y. Han, G. H. Liu and H. X. Yin, Convergence properties of conjugate gradient methods with strong Wolfe linesearch, Systems Science and Mathematical Science, 11 (1998), 112-116.

[12]

W. W. Hager and H. Zhang, A survey of nonlinear conjugate gradient methods, Pacific Journal of Optimization, 2 (2006), 35-58.

[13]

Y. F. Hu and C. Storey, Global convergence result for conjugate gradient methods, Journal of Optimization Theory and Applications, 71 (1991), 399-405. doi: 10.1007/BF00939927.

[14]

W. La Cruz and M. Raydan, Nonmonotone spectral methods for large-scale nonlinear systems, Optimization Methods and Software, 18 (2003), 583-599. doi: 10.1080/10556780310001610493.

[15]

W. La Cruz, J.M. Martínez and M. Raydan, Spectral resdual method without gradient information for solving large-scale nonlinear systems of equations, Mathematics of Computation, 75 (2006), 1429-1448. doi: 10.1090/S0025-5718-06-01840-0.

[16]

G. H. Liu, J. Y. Han and H. X. Yin, Global convergence of the Fletcher-Reeves algorithm with an inexact line search, Applied Mathematics, Journal of Chinese Universities, Ser. B, 10 (1995), 75-82.

[17]

D. H. Li and W. Cheng, Recent progress in the global convergence of quasi-Newton methods for nonlinear equations, Hokkaido Journal of Mathematics, 36 (2007), 729-743.

[18]

D. H. Li and M. Fukushima, A globally and superlinearly convergent Gauss-Newton based BFGS method for symmetric nonlinear equations, SIAM Journal on Numerical Analysis, 37 (1999), 152-172. doi: 10.1137/S0036142998335704.

[19]

D. H. Li and M. Fukushima, A derivative-free line search and global convergence of Broyden-like methods for nonlinear equations, Optimization Methods and Software, 13 (2000), 181-201. doi: 10.1080/10556780008805782.

[20]

Q. Li and D. H. Li, A class of derivative-free methods for large-scale nonlinear monotone equations,, IMA Journal of Numerical Analysis, (). 

[21]

M. J. D. Powell, Some convergence properties of the conjugate gradient method, Mathematical Programming, 11 (1976), 42-49. doi: 10.1007/BF01580369.

[22]

M. J . D. Powell, Restart procedures of the conjugate gradient method, Mathematical Programming, 2 (1977), 241-254. doi: 10.1007/BF01593790.

[23]

Q. Yan, X. Z. Peng and D. H. Li, A globally convergent derivative-free method for solving large-scale nonlinear monotone equations, Journal of Computational and Applied Mathematics, 234 (2010), 649-657. doi: 10.1016/j.cam.2010.01.001.

[24]

J. Zhang and D. H. Li, A norm descent BFGS method for solving KKT systems of symmetric variational inequality problems, Optimization Methods and Software, 22 (2007), 237-252. doi: 10.1080/10556780500397074.

[25]

L. Zhang, W. Zhou and D. H. Li, Global convergence of a modified Fletcher-Reeves conjugate gradient method with Armijo-type line search, Numerische Mathematik, 104 (2006), 561-572. doi: 10.1007/s00211-006-0028-z.

[26]

W. Zhou and D. H. Li, Limited memory BFGS method for nonlinear monotone equations, Journal of Computational Mathematics, 25 (2007), 89-96.

[27]

W. Zhou and D. H. Li, A globally convergent BFGS method for nonlinear monotone equations, Mathematics of Computation, 77 (2008), 2231-2240. doi: 10.1090/S0025-5718-08-02121-2.

[28]

G. Zoutendijk, Nonlinear Programming, Computational Methods, in "Integer and Nonlinear Programming" (eds. J. Abadie), North-Holland, Amsterdam, (1970), 37-86.

show all references

References:
[1]

M. Al-Baali, Descent property and global convergence of the Fletcher-Reeves method with inexact line search, IMA Journal of Numerical Analysis, 5 (1985), 121-124. doi: 10.1093/imanum/5.1.121.

[2]

S. Bellavia and B. Morini, A globally convergent Newton-GMRES subspace method for systems of nonlinear equations, SIAM Journal on Scientific Computing, 23 (2001), 940-960. doi: 10.1137/S1064827599363976.

[3]

A. Griewank, The “global” convergence of Broyden-like methods with suitable line search, Journal of Australia Mathematical Society, Ser. B, 28 (1986), 75-92.

[4]

W. Cheng and D. H. Li, A derivative-free nonmonotone line search and its application to the spectral residual method, IMA Journal of Numerical Analysis, 29 (2009), 814-825. doi: 10.1093/imanum/drn019.

[5]

Y. H. Dai and Y. Yuan, Convergence of the Fletcher-Reeves method under a generalized Wolfe search, Journal of Computational Mathematics, 2 (1996), 142-148.

[6]

Y. H. Dai and Y. Yuan, Convergence properties of the Fletcher-Reeves method, IMA Journal of Numerical Analysis, 16 (1996), 155-164. doi: 10.1093/imanum/16.2.155.

[7]

Y. H. Dai and Y. Yuan, "Nonlinear Conjugate Gradient Methods," Shanghai Science and Technology Publisher, Shanghai, 2000.

[8]

R. Fletcher and C. Reeves, Function minimization by conjugate gradients, Computer Journal, 7 (1964), 149-154. doi: 10.1093/comjnl/7.2.149.

[9]

J. C. Gilbert and J. Nocedal, Global convergence properties of conjugate gradient methods for optimization, SIAM Journal on Optimization, 2 (1992), 21-42. doi: 10.1137/0802003.

[10]

G. Z. Gu, D. H. Li, L. Qi and S. Z. Zhou, Descent directions of Quasi-Newton methods for symmetric nonlinear equations, SIAM Journal on Numerical Analysis, 40 (2003), 1763-1774. doi: 10.1137/S0036142901397423.

[11]

J. Y. Han, G. H. Liu and H. X. Yin, Convergence properties of conjugate gradient methods with strong Wolfe linesearch, Systems Science and Mathematical Science, 11 (1998), 112-116.

[12]

W. W. Hager and H. Zhang, A survey of nonlinear conjugate gradient methods, Pacific Journal of Optimization, 2 (2006), 35-58.

[13]

Y. F. Hu and C. Storey, Global convergence result for conjugate gradient methods, Journal of Optimization Theory and Applications, 71 (1991), 399-405. doi: 10.1007/BF00939927.

[14]

W. La Cruz and M. Raydan, Nonmonotone spectral methods for large-scale nonlinear systems, Optimization Methods and Software, 18 (2003), 583-599. doi: 10.1080/10556780310001610493.

[15]

W. La Cruz, J.M. Martínez and M. Raydan, Spectral resdual method without gradient information for solving large-scale nonlinear systems of equations, Mathematics of Computation, 75 (2006), 1429-1448. doi: 10.1090/S0025-5718-06-01840-0.

[16]

G. H. Liu, J. Y. Han and H. X. Yin, Global convergence of the Fletcher-Reeves algorithm with an inexact line search, Applied Mathematics, Journal of Chinese Universities, Ser. B, 10 (1995), 75-82.

[17]

D. H. Li and W. Cheng, Recent progress in the global convergence of quasi-Newton methods for nonlinear equations, Hokkaido Journal of Mathematics, 36 (2007), 729-743.

[18]

D. H. Li and M. Fukushima, A globally and superlinearly convergent Gauss-Newton based BFGS method for symmetric nonlinear equations, SIAM Journal on Numerical Analysis, 37 (1999), 152-172. doi: 10.1137/S0036142998335704.

[19]

D. H. Li and M. Fukushima, A derivative-free line search and global convergence of Broyden-like methods for nonlinear equations, Optimization Methods and Software, 13 (2000), 181-201. doi: 10.1080/10556780008805782.

[20]

Q. Li and D. H. Li, A class of derivative-free methods for large-scale nonlinear monotone equations,, IMA Journal of Numerical Analysis, (). 

[21]

M. J. D. Powell, Some convergence properties of the conjugate gradient method, Mathematical Programming, 11 (1976), 42-49. doi: 10.1007/BF01580369.

[22]

M. J . D. Powell, Restart procedures of the conjugate gradient method, Mathematical Programming, 2 (1977), 241-254. doi: 10.1007/BF01593790.

[23]

Q. Yan, X. Z. Peng and D. H. Li, A globally convergent derivative-free method for solving large-scale nonlinear monotone equations, Journal of Computational and Applied Mathematics, 234 (2010), 649-657. doi: 10.1016/j.cam.2010.01.001.

[24]

J. Zhang and D. H. Li, A norm descent BFGS method for solving KKT systems of symmetric variational inequality problems, Optimization Methods and Software, 22 (2007), 237-252. doi: 10.1080/10556780500397074.

[25]

L. Zhang, W. Zhou and D. H. Li, Global convergence of a modified Fletcher-Reeves conjugate gradient method with Armijo-type line search, Numerische Mathematik, 104 (2006), 561-572. doi: 10.1007/s00211-006-0028-z.

[26]

W. Zhou and D. H. Li, Limited memory BFGS method for nonlinear monotone equations, Journal of Computational Mathematics, 25 (2007), 89-96.

[27]

W. Zhou and D. H. Li, A globally convergent BFGS method for nonlinear monotone equations, Mathematics of Computation, 77 (2008), 2231-2240. doi: 10.1090/S0025-5718-08-02121-2.

[28]

G. Zoutendijk, Nonlinear Programming, Computational Methods, in "Integer and Nonlinear Programming" (eds. J. Abadie), North-Holland, Amsterdam, (1970), 37-86.

[1]

Wei-Zhe Gu, Li-Yong Lu. The linear convergence of a derivative-free descent method for nonlinear complementarity problems. Journal of Industrial and Management Optimization, 2017, 13 (2) : 531-548. doi: 10.3934/jimo.2016030

[2]

Gaohang Yu. A derivative-free method for solving large-scale nonlinear systems of equations. Journal of Industrial and Management Optimization, 2010, 6 (1) : 149-160. doi: 10.3934/jimo.2010.6.149

[3]

Yigui Ou, Wenjie Xu. A unified derivative-free projection method model for large-scale nonlinear equations with convex constraints. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021125

[4]

A. M. Bagirov, Moumita Ghosh, Dean Webb. A derivative-free method for linearly constrained nonsmooth optimization. Journal of Industrial and Management Optimization, 2006, 2 (3) : 319-338. doi: 10.3934/jimo.2006.2.319

[5]

Min Xi, Wenyu Sun, Jun Chen. Survey of derivative-free optimization. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 537-555. doi: 10.3934/naco.2020050

[6]

Liang Zhang, Wenyu Sun, Raimundo J. B. de Sampaio, Jinyun Yuan. A wedge trust region method with self-correcting geometry for derivative-free optimization. Numerical Algebra, Control and Optimization, 2015, 5 (2) : 169-184. doi: 10.3934/naco.2015.5.169

[7]

Herbert Gajewski, Jens A. Griepentrog. A descent method for the free energy of multicomponent systems. Discrete and Continuous Dynamical Systems, 2006, 15 (2) : 505-528. doi: 10.3934/dcds.2006.15.505

[8]

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

[9]

Jun Takaki, Nobuo Yamashita. A derivative-free trust-region algorithm for unconstrained optimization with controlled error. Numerical Algebra, Control and Optimization, 2011, 1 (1) : 117-145. doi: 10.3934/naco.2011.1.117

[10]

Abdulkarim Hassan Ibrahim, Jitsupa Deepho, Auwal Bala Abubakar, Kazeem Olalekan Aremu. A modified Liu-Storey-Conjugate descent hybrid projection method for convex constrained nonlinear equations and image restoration. Numerical Algebra, Control and Optimization, 2021  doi: 10.3934/naco.2021022

[11]

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

[12]

Jie-Wen He, Chi-Chon Lei, Chen-Yang Shi, Seak-Weng Vong. An inexact alternating direction method of multipliers for a kind of nonlinear complementarity problems. Numerical Algebra, Control and Optimization, 2021, 11 (3) : 353-362. doi: 10.3934/naco.2020030

[13]

Ugur G. Abdulla. On the optimal control of the free boundary problems for the second order parabolic equations. II. Convergence of the method of finite differences. Inverse Problems and Imaging, 2016, 10 (4) : 869-898. doi: 10.3934/ipi.2016025

[14]

Gaohang Yu, Lutai Guan, Guoyin Li. Global convergence of modified Polak-Ribière-Polyak conjugate gradient methods with sufficient descent property. Journal of Industrial and Management Optimization, 2008, 4 (3) : 565-579. doi: 10.3934/jimo.2008.4.565

[15]

Ugur G. Abdulla. On the optimal control of the free boundary problems for the second order parabolic equations. I. Well-posedness and convergence of the method of lines. Inverse Problems and Imaging, 2013, 7 (2) : 307-340. doi: 10.3934/ipi.2013.7.307

[16]

Gang Luo, Qingzhi Yang. The point-wise convergence of shifted symmetric higher order power method. Journal of Industrial and Management Optimization, 2021, 17 (1) : 357-368. doi: 10.3934/jimo.2019115

[17]

M. S. Lee, B. S. Goh, H. G. Harno, K. H. Lim. On a two-phase approximate greatest descent method for nonlinear optimization with equality constraints. Numerical Algebra, Control and Optimization, 2018, 8 (3) : 315-326. doi: 10.3934/naco.2018020

[18]

Jahnabi Chakravarty, Ashiho Athikho, Manideepa Saha. Convergence of interval AOR method for linear interval equations. Numerical Algebra, Control and Optimization, 2022, 12 (2) : 293-308. doi: 10.3934/naco.2021006

[19]

Paola Mannucci. The Dirichlet problem for fully nonlinear elliptic equations non-degenerate in a fixed direction. Communications on Pure and Applied Analysis, 2014, 13 (1) : 119-133. doi: 10.3934/cpaa.2014.13.119

[20]

Aimin Huang, Roger Temam. The nonlinear 2D subcritical inviscid shallow water equations with periodicity in one direction. Communications on Pure and Applied Analysis, 2014, 13 (5) : 2005-2038. doi: 10.3934/cpaa.2014.13.2005

 Impact Factor: 

Metrics

  • PDF downloads (200)
  • HTML views (0)
  • Cited by (24)

Other articles
by authors

[Back to Top]