American Institute of Mathematical Sciences

Advanced
doi: 10.3934/naco.2019049

A new type of quasi-Newton updating formulas based on the new quasi-Newton equation

Basim A. Hassan ,

Department of Mathematics, College of Computers Sciences and Mathematics, University of Mosul, Iraq

* Corresponding author: Basim A. Hassan

Received  February 2019 Revised  July 2019 Published  September 2019

The quasi-Newton equation is the very foundation of an assortment of the quasi-Newton methods. Therefore, by using the offered alternative equation, we derive the modified BFGS quasi-Newton updating formulas. In this paper, a new y-technique has been introduced to modify the secant equation of the quasi-Newton methods. Prove the global convergence of this algorithm is associated with a line search rule. The numerical results explain that the offered method is effectual for the known test problems.

Keywords: Quasi-Newton equations, quasi-Newton methods, convergence properties.
Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.
Citation: Basim A. Hassan. A new type of quasi-Newton updating formulas based on the new quasi-Newton equation. Numerical Algebra, Control & Optimization, doi: 10.3934/naco.2019049
References:
[1]

R. Byrd and J. Nocedal, A tool for the analysis of quasi-Newton methods with application to unconstrained minimization, SIAM J. Numer., 26 (1989), 727-739.  doi: 10.1137/0726042.  Google Scholar

[2]

X. W. Fang, Q. Ni and M. L. Zeng, A modified quasi-Newton method for nonlinear equation, Journal of Computational and Applied Mathematics, 328 (2018), 44-58.  doi: 10.1016/j.cam.2017.06.024.  Google Scholar

[3]

R. Fletcher, Practical Methods of Optimization, John Wiley and Sons, ChiChester, New York, 1987.  Google Scholar

[4]

A. R. M. Issam, A new limited memory Quasi-Newton method for unconstrained optimization, J. KSIAM, 7 (2003), 7-14.   Google Scholar

[5]

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

[6]

J. More, B. Garbow and K. Hillstrome, Testing unconstrained optimization software, ACM Trans. Math. Software, 7 (1981), 17-41.  doi: 10.1145/355934.355936.  Google Scholar

[7]

J. Nocedal and J. Wright, Numerical Optimization, Springer Series in Operations Research, Springer Verlag, New York, USA. doi: 10.1007/b98874.  Google Scholar

[8]

M. J. D. Powell, Algorithms for nonlinear constraints that use Lagrange functions, Math. Programming, 14 (1978), 224-248.  doi: 10.1007/BF01588967.  Google Scholar

[9]

Z. Wei, G. Li and L. Qi, New quasi-Newton methods for unconstrained optimization problems, Math Program. Applied Mathematics and Computation, 175 (2006), 1156-1188.  doi: 10.1016/j.amc.2005.08.027.  Google Scholar

[10]

Z. Wei, G. Li and L. Qi, 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.  Google Scholar

[11]

P. Wolfe, Convergence conditions for ascent methods, (II): Some corrections, SIAM Review, 13 (1971), 185-188.  doi: 10.1137/1013035.  Google Scholar

[12]

Y. H. Xiao, Z. X. Wei and L. Zhang, A modified BFGS method without line searches for nonconvex unconstrained optimization, Advances in Theoretical and Applied Mathematics, 1 (2006), 149-162.   Google Scholar

[13]

Y. Yuan and W. Sun, Theory and Methods of Optimization, Science Press of China, 1999.  Google Scholar

[14]

G. Yuan and Z. Wei, Convergence analysis of a modified BFGS method on convex minimizations, Comp. Optim. Appl., 47 (2010), 237-255.  doi: 10.1007/s10589-008-9219-0.  Google Scholar

[15]

G. Yuan, Z. Wei and X. Lu, Global convergence of BFGS and PRP methods under a modified weak Wolfe-Powell line search, Applied Mathematical Modelling, 47 (2017), 811-825.  doi: 10.1016/j.apm.2017.02.008.  Google Scholar

[16]

G. Yuan, Z. Sheng, B. Wang, W. Hu and C. Li, The global convergence of a modified BFGS method for nonconvex functions, Journal of Computational and Applied Mathematics, 327 (2018), 274-294.  doi: 10.1016/j.cam.2017.05.030.  Google Scholar

[17]

G. Yuan, Z. Wei and Y. Wu, Modified limited memory BFGS method with nonmonotone line search for unconstrained optimization, J. Korean Math. Soc., 47 (2010), 767-788.  doi: 10.4134/JKMS.2010.47.4.767.  Google Scholar

[18]

J. Z. Zhang, N. Y. Deng and L. H. Chen, Quasi-Newton equation and related methods for unconstrained optimization, JOTA, 102 (1999), 147-167.  doi: 10.1023/A:1021898630001.  Google Scholar

show all references

References:
[1]

R. Byrd and J. Nocedal, A tool for the analysis of quasi-Newton methods with application to unconstrained minimization, SIAM J. Numer., 26 (1989), 727-739.  doi: 10.1137/0726042.  Google Scholar

[2]

X. W. Fang, Q. Ni and M. L. Zeng, A modified quasi-Newton method for nonlinear equation, Journal of Computational and Applied Mathematics, 328 (2018), 44-58.  doi: 10.1016/j.cam.2017.06.024.  Google Scholar

[3]

R. Fletcher, Practical Methods of Optimization, John Wiley and Sons, ChiChester, New York, 1987.  Google Scholar

[4]

A. R. M. Issam, A new limited memory Quasi-Newton method for unconstrained optimization, J. KSIAM, 7 (2003), 7-14.   Google Scholar

[5]

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

[6]

J. More, B. Garbow and K. Hillstrome, Testing unconstrained optimization software, ACM Trans. Math. Software, 7 (1981), 17-41.  doi: 10.1145/355934.355936.  Google Scholar

[7]

J. Nocedal and J. Wright, Numerical Optimization, Springer Series in Operations Research, Springer Verlag, New York, USA. doi: 10.1007/b98874.  Google Scholar

[8]

M. J. D. Powell, Algorithms for nonlinear constraints that use Lagrange functions, Math. Programming, 14 (1978), 224-248.  doi: 10.1007/BF01588967.  Google Scholar

[9]

Z. Wei, G. Li and L. Qi, New quasi-Newton methods for unconstrained optimization problems, Math Program. Applied Mathematics and Computation, 175 (2006), 1156-1188.  doi: 10.1016/j.amc.2005.08.027.  Google Scholar

[10]

Z. Wei, G. Li and L. Qi, 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.  Google Scholar

[11]

P. Wolfe, Convergence conditions for ascent methods, (II): Some corrections, SIAM Review, 13 (1971), 185-188.  doi: 10.1137/1013035.  Google Scholar

[12]

Y. H. Xiao, Z. X. Wei and L. Zhang, A modified BFGS method without line searches for nonconvex unconstrained optimization, Advances in Theoretical and Applied Mathematics, 1 (2006), 149-162.   Google Scholar

[13]

Y. Yuan and W. Sun, Theory and Methods of Optimization, Science Press of China, 1999.  Google Scholar

[14]

G. Yuan and Z. Wei, Convergence analysis of a modified BFGS method on convex minimizations, Comp. Optim. Appl., 47 (2010), 237-255.  doi: 10.1007/s10589-008-9219-0.  Google Scholar

[15]

G. Yuan, Z. Wei and X. Lu, Global convergence of BFGS and PRP methods under a modified weak Wolfe-Powell line search, Applied Mathematical Modelling, 47 (2017), 811-825.  doi: 10.1016/j.apm.2017.02.008.  Google Scholar

[16]

G. Yuan, Z. Sheng, B. Wang, W. Hu and C. Li, The global convergence of a modified BFGS method for nonconvex functions, Journal of Computational and Applied Mathematics, 327 (2018), 274-294.  doi: 10.1016/j.cam.2017.05.030.  Google Scholar

[17]

G. Yuan, Z. Wei and Y. Wu, Modified limited memory BFGS method with nonmonotone line search for unconstrained optimization, J. Korean Math. Soc., 47 (2010), 767-788.  doi: 10.4134/JKMS.2010.47.4.767.  Google Scholar

[18]

J. Z. Zhang, N. Y. Deng and L. H. Chen, Quasi-Newton equation and related methods for unconstrained optimization, JOTA, 102 (1999), 147-167.  doi: 10.1023/A:1021898630001.  Google Scholar

Table 1.  Some modifications of QN-equations
Author(s) QN conditions Ref.
Powell $ B_{k+1}s_k=\tilde{y}_k= \varphi_k y_k +(1-\varphi_k)B_ks_k $ [8]
Li and Fukushima $ B_{k+1}s_k=\tilde{y}_k= y_k +t_ks_k, t_k \le 10^{-6} $ [5]
Wei, Li, and Qi $ B_{k+1}s_k=\tilde{y}_k= y_k +\frac{2(f_k-f_{k+1})+(g_{k+1}+g_k)^Ts_k}{\Vert s_k \Vert^2} s_k $ [9]
Zhang, Deng, and Chen $ B_{k+1}s_k=\tilde{y}_k= y_k +\frac{6(f_k-f_{k+1})+3(g_{k+1}+g_k)^Ts_k}{\Vert s_k \Vert^2} s_k $ [18]
Yuan and Wei $ B_{k+1}s_k=\tilde{y}_k= y_k +\frac{max(0,2(f_k-f_{k+1})+(g_{k+1}+g_k)^Ts_k}{\Vert s_k \Vert^2} s_k $ [14]
Yuan, Wei and Wu $ B_{k+1}s_k=\tilde{y}_k= y_k +\frac{max(0,6(f_k-f_{k+1})+3(g_{k+1}+g_k)^Ts_k}{\Vert s_k \Vert^2} s_k $ [17]
Table Options

Download as excel

Author(s) QN conditions Ref.
Powell $ B_{k+1}s_k=\tilde{y}_k= \varphi_k y_k +(1-\varphi_k)B_ks_k $ [8]
Li and Fukushima $ B_{k+1}s_k=\tilde{y}_k= y_k +t_ks_k, t_k \le 10^{-6} $ [5]
Wei, Li, and Qi $ B_{k+1}s_k=\tilde{y}_k= y_k +\frac{2(f_k-f_{k+1})+(g_{k+1}+g_k)^Ts_k}{\Vert s_k \Vert^2} s_k $ [9]
Zhang, Deng, and Chen $ B_{k+1}s_k=\tilde{y}_k= y_k +\frac{6(f_k-f_{k+1})+3(g_{k+1}+g_k)^Ts_k}{\Vert s_k \Vert^2} s_k $ [18]
Yuan and Wei $ B_{k+1}s_k=\tilde{y}_k= y_k +\frac{max(0,2(f_k-f_{k+1})+(g_{k+1}+g_k)^Ts_k}{\Vert s_k \Vert^2} s_k $ [14]
Yuan, Wei and Wu $ B_{k+1}s_k=\tilde{y}_k= y_k +\frac{max(0,6(f_k-f_{k+1})+3(g_{k+1}+g_k)^Ts_k}{\Vert s_k \Vert^2} s_k $ [17]
Table 2.  Comparison of different BFGS-algorithms with different test functions and different dimensions
P.No. n BFGS algorithm BBFGS with $ u_k=y_k $ BBFGS with $ u_k=g_{k+1} $
NI NF NI NF NI NF
1 2 35 140 36 124 8 29
2 2 9 26 8 23 5 16
3 2 43 166 34 123 3 12
4 2 3 30 3 30 3 30
5 2 15 50 15 48 5 17
6 2 2 27 2 27 2 27
7 3 34 113 26 86 7 20
8 3 16 54 15 51 6 18
9 3 2 4 2 4 2 4
10 3 2 27 2 27 2 27
11 3 2 27 2 27 2 27
12 4 20 60 20 60 5 17
13 4 19 61 24 73 4 13
14 4 21 65 23 72 4 10
15 4 17 54 16 49 5 17
16 5 2 27 2 27 2 27
17 6 25 72 33 101 4 12
18 11 3 31 3 31 3 31
19 20 31 102 33 103 4 13
20 400 64 209 91 297 5 17
21 400 2 27 2 27 2 27
22 200 2 5 2 5 2 5
23 100 2 27 2 27 2 27
24 500 9 33 8 28 10 31
25 500 2 4 2 4 2 4
26 500 6 16 7 19 5 14
27 500 57 281 16 114 5 17
28 500 2 4 2 4 2 4
29 500 3 7 3 7 3 7
30 500 3 7 3 7 3 7
Total 453 1756 437 1625 117 527
Table Options

Download as excel

P.No. n BFGS algorithm BBFGS with $ u_k=y_k $ BBFGS with $ u_k=g_{k+1} $
NI NF NI NF NI NF
1 2 35 140 36 124 8 29
2 2 9 26 8 23 5 16
3 2 43 166 34 123 3 12
4 2 3 30 3 30 3 30
5 2 15 50 15 48 5 17
6 2 2 27 2 27 2 27
7 3 34 113 26 86 7 20
8 3 16 54 15 51 6 18
9 3 2 4 2 4 2 4
10 3 2 27 2 27 2 27
11 3 2 27 2 27 2 27
12 4 20 60 20 60 5 17
13 4 19 61 24 73 4 13
14 4 21 65 23 72 4 10
15 4 17 54 16 49 5 17
16 5 2 27 2 27 2 27
17 6 25 72 33 101 4 12
18 11 3 31 3 31 3 31
19 20 31 102 33 103 4 13
20 400 64 209 91 297 5 17
21 400 2 27 2 27 2 27
22 200 2 5 2 5 2 5
23 100 2 27 2 27 2 27
24 500 9 33 8 28 10 31
25 500 2 4 2 4 2 4
26 500 6 16 7 19 5 14
27 500 57 281 16 114 5 17
28 500 2 4 2 4 2 4
29 500 3 7 3 7 3 7
30 500 3 7 3 7 3 7
Total 453 1756 437 1625 117 527
Table 3.  Relative efficiency of the new Algorithms
BFGS algorithm BBFGS with $ u_k=y_k $ BBFGS with $ u_k=g_{k+1} $
NI 100% 96.70% 25.82%
NF 100% 92.53% 30.01%
Table Options

Download as excel

BFGS algorithm BBFGS with $ u_k=y_k $ BBFGS with $ u_k=g_{k+1} $
NI 100% 96.70% 25.82%
NF 100% 92.53% 30.01%
[1]

Shummin Nakayama, Yasushi Narushima, Hiroshi Yabe. Memoryless quasi-Newton methods based on spectral-scaling Broyden family for unconstrained optimization. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1773-1793. doi: 10.3934/jimo.2018122
[2]

Yuhong Dai, Nobuo Yamashita. Convergence analysis of sparse quasi-Newton updates with positive definite matrix completion for two-dimensional functions. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 61-69. doi: 10.3934/naco.2011.1.61
[3]

Honglan Zhu, Qin Ni, Meilan Zeng. A quasi-Newton trust region method based on a new fractional model. Numerical Algebra, Control & Optimization, 2015, 5 (3) : 237-249. doi: 10.3934/naco.2015.5.237
[4]

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

B. S. Goh, W. J. Leong, Z. Siri. Partial Newton methods for a system of equations. Numerical Algebra, Control & Optimization, 2013, 3 (3) : 463-469. doi: 10.3934/naco.2013.3.463
[6]

Cheng-Dar Liou. Note on "Cost analysis of the M/M/R machine repair problem with second optional repair: Newton-Quasi method". Journal of Industrial & Management Optimization, 2012, 8 (3) : 727-732. doi: 10.3934/jimo.2012.8.727
[7]

Kuo-Hsiung Wang, Chuen-Wen Liao, Tseng-Chang Yen. Cost analysis of the M/M/R machine repair problem with second optional repair: Newton-Quasi method. Journal of Industrial & Management Optimization, 2010, 6 (1) : 197-207. doi: 10.3934/jimo.2010.6.197
[8]

Wei Ouyang, Li Li. Hölder strong metric subregularity and its applications to convergence analysis of inexact Newton methods. Journal of Industrial & Management Optimization, 2017, 13 (5) : 0-0. doi: 10.3934/jimo.2019105
[9]

Ai-Li Yang, Yu-Jiang Wu. Newton-MHSS methods for solving systems of nonlinear equations with complex symmetric Jacobian matrices. Numerical Algebra, Control & Optimization, 2012, 2 (4) : 839-853. doi: 10.3934/naco.2012.2.839
[10]

Enrique Fernández-Cara, Arnaud Münch. Numerical null controllability of semi-linear 1-D heat equations: Fixed point, least squares and Newton methods. Mathematical Control & Related Fields, 2012, 2 (3) : 217-246. doi: 10.3934/mcrf.2012.2.217
[11]

Lori Badea. Multigrid methods for some quasi-variational inequalities. Discrete & Continuous Dynamical Systems - S, 2013, 6 (6) : 1457-1471. doi: 10.3934/dcdss.2013.6.1457
[12]

Qiumei Huang, Xiuxiu Xu, Hermann Brunner. Continuous Galerkin methods on quasi-geometric meshes for delay differential equations of pantograph type. Discrete & Continuous Dynamical Systems - A, 2016, 36 (10) : 5423-5443. doi: 10.3934/dcds.2016039
[13]

Ugo Locatelli, Letizia Stefanelli. Quasi-periodic motions in a special class of dynamical equations with dissipative effects: A pair of detection methods. Discrete & Continuous Dynamical Systems - B, 2015, 20 (4) : 1155-1187. doi: 10.3934/dcdsb.2015.20.1155
[14]

Zhengguang Guo, Sadek Gala. Regularity criterion of the Newton-Boussinesq equations in $R^3$. Communications on Pure & Applied Analysis, 2012, 11 (2) : 443-451. doi: 10.3934/cpaa.2012.11.443
[15]

Xiaojiao Tong, Shuzi Zhou. A smoothing projected Newton-type method for semismooth equations with bound constraints. Journal of Industrial & Management Optimization, 2005, 1 (2) : 235-250. doi: 10.3934/jimo.2005.1.235
[16]

Saeed Ketabchi, Hossein Moosaei, M. Parandegan, Hamidreza Navidi. Computing minimum norm solution of linear systems of equations by the generalized Newton method. Numerical Algebra, Control & Optimization, 2017, 7 (2) : 113-119. doi: 10.3934/naco.2017008
[17]

Li-Xia Liu, Sanyang Liu, Chun-Feng Wang. Smoothing Newton methods for symmetric cone linear complementarity problem with the Cartesian $P$/$P_0$-property. Journal of Industrial & Management Optimization, 2011, 7 (1) : 53-66. doi: 10.3934/jimo.2011.7.53
[18]

Liping Zhang, Soon-Yi Wu, Shu-Cherng Fang. Convergence and error bound of a D-gap function based Newton-type algorithm for equilibrium problems. Journal of Industrial & Management Optimization, 2010, 6 (2) : 333-346. doi: 10.3934/jimo.2010.6.333
[19]

Hongxiu Zhong, Guoliang Chen, Xueping Guo. Semi-local convergence of the Newton-HSS method under the center Lipschitz condition. Numerical Algebra, Control & Optimization, 2019, 9 (1) : 85-99. doi: 10.3934/naco.2019007
[20]

Masahiro Kubo. Quasi-subdifferential operators and evolution equations. Conference Publications, 2013, 2013 (special) : 447-456. doi: 10.3934/proc.2013.2013.447

 Impact Factor: 

Tools

Metrics

  • PDF downloads (47)
  • HTML views (118)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences