main-content

Erschienen in:

01.12.2020

# A modified Broyden family algorithm with global convergence under a weak Wolfe-Powell line search for unconstrained nonconvex problems

verfasst von: Gonglin Yuan, Zhan Wang, Pengyuan Li

Erschienen in: Calcolo | Ausgabe 4/2020

Einloggen, um Zugang zu erhalten

## Abstract

The Quasi-Newton method is one of the most effective methods using the first derivative for solving all unconstrained optimization problems. The Broyden family method plays an important role among the quasi-Newton algorithms. However, the study of the convergence of the classical Broyden family method is still not enough. While in the special case, BFGS method, there have been abundant achievements. Yuan et al. (Appl Math Model. 47:811–825, (2017)) presented a modified weak Wolfe-Powell line search and obtained the convergence of BFGS method for general functions under this line search. Motivated by their works, a new modified weak Wolfe-Powell line search technique is proposed for unconstrained problems. We assume that the objective function is nonconvex and the global convergence of the restricted Broyden family method is established. Preliminary numerical results including the classical optimization problems and the Muskingum model show that the presented algorithm is promising.
Literatur
1.
Byrd, R., Nocedal, J., Yuan, Y.: Global convergence of a class of quasi-newton methods on convex problems. SIAM J. Numer. Anal. 24, 1171–1189 (1987)
2.
Byrd, R., Nocedal, J.: A tool for the analysis of quasi-Newton methods with application to unconstrained minimization. SIAM J. Numer. Anal. 26, 727–739 (1989)
3.
Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201–213 (2002)
4.
Jr, Dennis J.E., Moré, J.J.: Quasi-Newton Methods, Motivation and Theory. SIAM Rev. 19, 46–89 (1977)
5.
Dixon, L.C.W.: Variable metric algorithms: Nessary and sufficient conditions for identical behavior on nonquadratic functions. J. Optim. Theory Appl. 10, 34–40 (1972)
6.
Dai, Y., Kou, C.: A nonlinear conjugate gradient algorithm with an optimal property and an improved Wolfe line search. SIAM J. Optim. 23, 296–320 (2013)
7.
Dai, Y.: Conjugate gradient methods with Armijo-type line searches. Acta Math. Appl. Sinica, English Series 18, 123–130 (2002)
8.
Fletcher, R.: Practical Methods of Optimization, 2nd edn. John Wiley and Sons, New York (1987) MATH
9.
Geem, Z.W.: Parameter estimation for the nonlinear Muskingum model using the BFGS technique. J. Irrig. Drain. Eng. 132(5), 474–478 (2006) CrossRef
10.
Griewank, A., Toint, P.L.: Local convergence analysis for partitioned quasi-Newton updates. Numer. Math. 39, 429–448 (1982)
11.
Grippo, L., Lucidi, S.: A globally convergent version of the Polak-Ribière conjugate gradient method. Math. Program. 78, 375–391 (1997) MATH
12.
Huang, Y., Liu, C.: Dai-Kou type conjugate gradient methods with a line search only using gradient. J. Inequal Appl. 2017, 66 (2017)
13.
Kou, C.: An improved nonlinear conjugate gradient method with an optimal property. Sci. China Math. 57, 635–648 (2014)
14.
Nocedal, J., Wright, S.J.: Numerical Optimization. Springer, New York (2006) MATH
15.
Ouyang, A., Liu, L., Sheng, Z., Wu, F.: A class of parameter estimation methods for nonlinear Muskingum model using hybrid invasive weed optimization algorithm. Math. Problems Eng. 2015, 573894 (2015)
16.
Ouyang, A., Tang, Z., Li, K., Sallam, A., Sha, E.: Estimating parameters of Muskingum model using an adaptive hybrid PSO algorithm. Int. J. Pattern Recognit. Artif. Intell. 28, 1–29 (2014) CrossRef
17.
Powell, M.J.D.: On the convergence of the variable metric algorithm. IMA J. Appl. Math. 7, 21–36 (1971)
18.
Powell, M.J.D.: Some global convergence properties of a variable metric algorithm for minimization without exact line searches. In: Cottle, R.W., Lemke, C.E. (eds.) Nonlinear Programming, SIAM-AMS Proceedings, vol. IX. SIAM, Philadelphia (1976)
19.
Pearson, J.D.: Variable metric methods of minimization. Comput. J. 12, 171–178 (1969)
20.
Ritter, K.: Global and superlinear convergence of a class of variable metric methods. In: König, H., Korte, B., Ritter, K. (eds.) Mathematical Programming at Oberwolfach. Mathematical Programming Studies, vol. 14. Springer, Berlin (1981)
21.
Stachurski, A.: Superlinear convergence of Broyden’s bounded $$\theta$$-class of methods. Math. Program. 20, 196–212 (1981)
22.
Werner, J.: Über die globale Konvergenz von Variable-Metrik-Verfahren mit nicht-exakter Schrittweitenbestimmung[in German]. J. Numer. Math. 31, 321–334 (1978) CrossRef
23.
Wan, Z., Huang, S., Zheng, X.: New cautious BFGS algorithm based on modified Armijo-type line search. J. Inequal Appl. 2012, 241 (2012)
24.
Wan, Z., Teo, K.L., Shen, X., et al.: New BFGS method for unconstrained optimization problem based on modified Armijo line search. Optimization 63, 285–304 (2014)
25.
Yu, G., Guan, L., Wei, Z.: Globally convergent Polak-Ribière-Polyak conjugate gradient methods under a modified Wolfe line search. Appl. Math. Comput. 215(8), 3082–3090 (2009)
26.
Yuan, G., Sheng, Z., Wang, B., Hu, W., Li, C.: The global convergence of a modified BFGS method for nonconvex functions. J. Comput. Appl. Math. 327, 274–294 (2018)
27.
Yuan, G., Wei, Z., Lu, X.: Global convergence of the BFGS method and the PRP method for general functions under a modified weak Wolfe-Powell line search. Appl. Math. Model. 47, 811–825 (2017)
28.
Yuan, Y., Sun, W.: Theory and Methods of Optimization. Science Press of China, Beijing (1999)
29.
Zhou, W., Li, D.: On the convergence properties of the unmodified PRP method with a non-descent line search. Optim. Methods Softw. 29, 484–496 (2014)
30.
Zhou, W.: A short note on the global convergence of the unmodified PRP method. Optim. Lett. 7, 1367–1372 (2013)
Titel
A modified Broyden family algorithm with global convergence under a weak Wolfe-Powell line search for unconstrained nonconvex problems
verfasst von
Gonglin Yuan
Zhan Wang
Pengyuan Li
Publikationsdatum
01.12.2020
Verlag
Springer International Publishing
Erschienen in
Calcolo / Ausgabe 4/2020
Print ISSN: 0008-0624
Elektronische ISSN: 1126-5434
DOI
https://doi.org/10.1007/s10092-020-00383-5

Zur Ausgabe