Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

Erschienen in: Calcolo 4/2020

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
share
TEILEN

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.
Zurück zum Zitat 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) MathSciNetCrossRef 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) MathSciNetCrossRef
2.
Zurück zum Zitat 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) MathSciNetCrossRef 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) MathSciNetCrossRef
3.
Zurück zum Zitat Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201–213 (2002) MathSciNetCrossRef Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201–213 (2002) MathSciNetCrossRef
4.
Zurück zum Zitat Jr, Dennis J.E., Moré, J.J.: Quasi-Newton Methods, Motivation and Theory. SIAM Rev. 19, 46–89 (1977) Jr, Dennis J.E., Moré, J.J.: Quasi-Newton Methods, Motivation and Theory. SIAM Rev. 19, 46–89 (1977)
5.
Zurück zum Zitat 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) MathSciNetCrossRef 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) MathSciNetCrossRef
6.
Zurück zum Zitat 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) MathSciNetCrossRef 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) MathSciNetCrossRef
7.
Zurück zum Zitat Dai, Y.: Conjugate gradient methods with Armijo-type line searches. Acta Math. Appl. Sinica, English Series 18, 123–130 (2002) MathSciNetCrossRef Dai, Y.: Conjugate gradient methods with Armijo-type line searches. Acta Math. Appl. Sinica, English Series 18, 123–130 (2002) MathSciNetCrossRef
8.
Zurück zum Zitat Fletcher, R.: Practical Methods of Optimization, 2nd edn. John Wiley and Sons, New York (1987) MATH Fletcher, R.: Practical Methods of Optimization, 2nd edn. John Wiley and Sons, New York (1987) MATH
9.
Zurück zum Zitat Geem, Z.W.: Parameter estimation for the nonlinear Muskingum model using the BFGS technique. J. Irrig. Drain. Eng. 132(5), 474–478 (2006) CrossRef 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.
Zurück zum Zitat Griewank, A., Toint, P.L.: Local convergence analysis for partitioned quasi-Newton updates. Numer. Math. 39, 429–448 (1982) MathSciNetCrossRef Griewank, A., Toint, P.L.: Local convergence analysis for partitioned quasi-Newton updates. Numer. Math. 39, 429–448 (1982) MathSciNetCrossRef
11.
Zurück zum Zitat Grippo, L., Lucidi, S.: A globally convergent version of the Polak-Ribière conjugate gradient method. Math. Program. 78, 375–391 (1997) MATH Grippo, L., Lucidi, S.: A globally convergent version of the Polak-Ribière conjugate gradient method. Math. Program. 78, 375–391 (1997) MATH
12.
Zurück zum Zitat Huang, Y., Liu, C.: Dai-Kou type conjugate gradient methods with a line search only using gradient. J. Inequal Appl. 2017, 66 (2017) MathSciNetCrossRef Huang, Y., Liu, C.: Dai-Kou type conjugate gradient methods with a line search only using gradient. J. Inequal Appl. 2017, 66 (2017) MathSciNetCrossRef
13.
Zurück zum Zitat Kou, C.: An improved nonlinear conjugate gradient method with an optimal property. Sci. China Math. 57, 635–648 (2014) MathSciNetCrossRef Kou, C.: An improved nonlinear conjugate gradient method with an optimal property. Sci. China Math. 57, 635–648 (2014) MathSciNetCrossRef
14.
Zurück zum Zitat Nocedal, J., Wright, S.J.: Numerical Optimization. Springer, New York (2006) MATH Nocedal, J., Wright, S.J.: Numerical Optimization. Springer, New York (2006) MATH
15.
Zurück zum Zitat 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) MathSciNetMATH 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) MathSciNetMATH
16.
Zurück zum Zitat 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 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.
18.
Zurück zum Zitat 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) 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)
20.
Zurück zum Zitat 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) 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.
Zurück zum Zitat Stachurski, A.: Superlinear convergence of Broyden’s bounded \(\theta\)-class of methods. Math. Program. 20, 196–212 (1981) MathSciNetCrossRef Stachurski, A.: Superlinear convergence of Broyden’s bounded \(\theta\)-class of methods. Math. Program. 20, 196–212 (1981) MathSciNetCrossRef
22.
Zurück zum Zitat Werner, J.: Über die globale Konvergenz von Variable-Metrik-Verfahren mit nicht-exakter Schrittweitenbestimmung[in German]. J. Numer. Math. 31, 321–334 (1978) CrossRef 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.
Zurück zum Zitat Wan, Z., Huang, S., Zheng, X.: New cautious BFGS algorithm based on modified Armijo-type line search. J. Inequal Appl. 2012, 241 (2012) MathSciNetCrossRef Wan, Z., Huang, S., Zheng, X.: New cautious BFGS algorithm based on modified Armijo-type line search. J. Inequal Appl. 2012, 241 (2012) MathSciNetCrossRef
24.
Zurück zum Zitat 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) MathSciNetCrossRef 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) MathSciNetCrossRef
25.
Zurück zum Zitat 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) MathSciNetMATH 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) MathSciNetMATH
26.
Zurück zum Zitat 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) MathSciNetCrossRef 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) MathSciNetCrossRef
27.
Zurück zum Zitat 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) MathSciNetCrossRef 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) MathSciNetCrossRef
28.
Zurück zum Zitat Yuan, Y., Sun, W.: Theory and Methods of Optimization. Science Press of China, Beijing (1999) Yuan, Y., Sun, W.: Theory and Methods of Optimization. Science Press of China, Beijing (1999)
29.
Zurück zum Zitat 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) MathSciNetCrossRef 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) MathSciNetCrossRef
30.
Zurück zum Zitat Zhou, W.: A short note on the global convergence of the unmodified PRP method. Optim. Lett. 7, 1367–1372 (2013) MathSciNetCrossRef Zhou, W.: A short note on the global convergence of the unmodified PRP method. Optim. Lett. 7, 1367–1372 (2013) MathSciNetCrossRef
Metadaten
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

Weitere Artikel der Ausgabe 4/2020

Calcolo 4/2020 Zur Ausgabe

Premium Partner