Hostname: page-component-78c5997874-s2hrs Total loading time: 0 Render date: 2024-11-19T20:31:30.198Z Has data issue: false hasContentIssue false
  • English
  • Français

NEW ADAPTIVE BARZILAI–BORWEIN STEP SIZE AND ITS APPLICATION IN SOLVING LARGE-SCALE OPTIMIZATION PROBLEMS

Part of: Artificial intelligence (68Txx) Design of experiments

Published online by Cambridge University Press:  03 December 2018

TING LI  and
ZHONG WAN Open the ORCID record for ZHONG WAN [Opens in a new window]
TING LI
Affiliation:
School of Mathematics and Statistics, Central South University, Hunan Changsha, China email [email protected], [email protected]
ZHONG WAN*
Affiliation:
School of Mathematics and Statistics, Central South University, Hunan Changsha, China email [email protected], [email protected]
*
✉[email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We propose a new adaptive and composite Barzilai–Borwein (BB) step size by integrating the advantages of such existing step sizes. Particularly, the proposed step size is an optimal weighted mean of two classical BB step sizes and the weights are updated at each iteration in accordance with the quality of the classical BB step sizes. Combined with the steepest descent direction, the adaptive and composite BB step size is incorporated into the development of an algorithm such that it is efficient to solve large-scale optimization problems. We prove that the developed algorithm is globally convergent and it R-linearly converges when applied to solve strictly convex quadratic minimization problems. Compared with the state-of-the-art algorithms available in the literature, the proposed step size is more efficient in solving ill-posed or large-scale benchmark test problems.

Keywords

nonlinear programstep sizealgorithmconvergencelarge-scale optimization

MSC classification

Primary: 90C30: Nonlinear programming
Secondary: 62K05: Optimal designs 68T37: Reasoning under uncertainty
Type
Research Article
Information
The ANZIAM Journal , Volume 61 , Issue 1 , January 2019 , pp. 76 - 98
Copyright
© 2018 Australian Mathematical Society 

References

Andrei, N., “An unconstrained optimization test functions collection”, Adv. Model. Optim. 10 (2008) 147–161; doi:10.1021/es702781x.Google Scholar
Barzilai, J. and Borwein, J. M., “Two-point step size gradient methods”, IMA J. Numer. Anal. 8 (1988) 141–148; doi:10.1093/imanum/8.1.141.Google Scholar
Birgin, E. G., Martínez, J. M. and Raydan, M., “Nonmonotone spectral projected gradient methods on convex sets”, SIAM J. Optim. 10 (2000) 1196–1211; doi:10.1137/S1052623497330963.Google Scholar
Bonettini, S., Zanella, R. and Zanni, L., “A scaled gradient projection method for constrained image deblurring”, Inverse Problems 25 (2009) 015002; doi:10.1088/0266-5611/25/1/015002.Google Scholar
Chen, X. R., Liu, Y. M. and Wan, Z., “Optimal decision-making for the online and offline retailers under BOPS model”, ANZIAM J. 58 (2016) 187–208; doi:10.1017/S1446181116000201.Google Scholar
Cheng, W. and Li, D. H., “A derivative-free nonmonotone line search and its application to the spectral residual method”, IMA J. Numer. Anal. 29 (2009) 814–825; doi:10.1093/imanum/drn019.Google Scholar
Dai, Y. H., “Alternate step gradient method”, Optimization 52 (2003) 395–415; doi:10.1080/02331930310001611547.Google Scholar
Dai, Y. H., Al-Baali, M. and Yang, X., “A positive Barzilai–Borwein-like stepsize and an extension for symmetric linear systems”, in: Numerical Analysis and Optimization, Volume 431 of Springer Proceedings in Mathematics and Statistics Series (Springer, Cham, 2015) 59–75.Google Scholar
Dai, Y. H. and Fletcher, R., “Projected Barzilai–Borwein methods for large-scale box-constrained quadratic programming”, Numer. Math. 100 (2005) 21–47; doi:10.1007/s00211-004-0569-y.Google Scholar
Dai, Y. H. and Liao, L. Z., “R-linear convergence of the Barzilai and Borwein gradient method”, IMA J. Numer. Anal. 22 (2002) 1–10; doi:10.1093/imanum/22.1.1.Google Scholar
Deng, S. and Wan, Z., “A three-term conjugate gradient algorithm for large-scale unconstrained optimization problems”, Appl. Numer. Math. 92 (2015) 70–81; doi:10.1016/j.apnum.2015.01.008.Google Scholar
Dennis, J. E. and Moré, J. J., “Quasi-Newton methods, motivation and theory”, Siam Rev. 19 (1977) 46–89; doi:10.1137/1019005.Google Scholar
Dolan, E. D. and Moré, J. J., “Benchmarking optimization software with performance profiles”, Math. Program. 91 (2002) 201–213; doi:10.1007/s101070100263.Google Scholar
Figueiredo, M. A., Nowak, R. D. and Wright, S. J., “Gradient projection for sparse reconstruction: application to compressed sensing and other inverse problems”, IEEE J. Sel. Top. Signal Process. 1 (2007) 586–597; doi:10.1109/jstsp.2007.910281.Google Scholar
Huang, Y., Liu, H. and Zhou, S., “Quadratic regularization projected Barzilai–Borwein method for nonnegative matrix factorization”, Data Min. Knowl. Discov. 29 (2014) 1665–1684; doi:10.1007/s10618-014-0390-x.Google Scholar
Huang, Y., Liu, H. and Zhou, S., “An efficient monotone projected Barzilai–Borwein method for nonnegative matrix factorization”, Appl. Math. Lett. 45 (2015) 12–17; doi:10.1016/j.aml.2015.01.003.Google Scholar
Huang, S. and Wan, Z., “A new nonmonotone spectral residual method for nonsmooth nonlinear equations”, J. Comput. Appl. Math. 313 (2017) 82–101; doi:10.1016/j.cam.2016.09.014.Google Scholar
Huang, S., Wan, Z. and Zhang, J., “An extended nonmonotone line search technique for large-scale unconstrained optimization”, J. Comput. Appl. Math. 330 (2018) 586–604; doi:10.1016/j.cam.2017.09.026.Google Scholar
La Cruz, W., Martínez, J. M. and Raydan, M., “Spectral residual method without gradient information for solving large-scale nonlinear systems of equations”, Math. Comput. 75 (2006) 1429–1448; doi:10.1090/s0025-5718-06-01840-0.Google Scholar
Li, Y. X. and Wan, Z., “Bi-level programming approach to optimal strategy for VMI problems under random demand”, ANZIAM J. 59 (2017) 247–270; doi:10.1017/S1446181117000384.Google Scholar
Raydan, M., “On the Barzilai and Borwein choice of steplength for the gradient method”, IMA J. Numer. Anal. 13 (1993) 321–326; doi:10.1093/imanum/13.3.321.Google Scholar
Sopyła, K. and Drozda, P., “Stochastic gradient descent with Barzilai–Borwein update step for SVM”, Inform. Sci. 316 (2015) 218–233; doi:10.1016/j.ins.2015.03.073.Google Scholar
Sun, W. and Yuan, Y. X., Optimization theory and methods: nonlinear programming (Springer, New York, 2006); doi:10.1007/b106451.Google Scholar
Wan, Z., Chen, Y., Huang, S. and Feng, D., “A modified nonmonotone BFGS algorithm for solving smooth nonlinear equations”, Optim. Lett. 8 (2014) 1845–1860; doi:10.1007/s11590-013-0678-6.Google Scholar
Wan, Z., Guo, J., Liu, J. and Liu, W., “A modified spectral conjugate gradient projection method for signal recovery”, Signal Image Video Process. 12 (2018) 1455–1462; doi:10.1007/s11760-018-1300-2.Google Scholar
Wu, H. and Wan, Z., “A multiobjective optimization model and an orthogonal design-based hybrid heuristic algorithm for regional urban mining management problems”, J. Air Waste Manag. Assoc. 68 (2017) 146–169; doi:10.1080/10962247.2017.1386141.Google Scholar
Yuan, Y., “Gradient methods for large scale convex quadratic functions”, in: Optimization and regularization for computational inverse problems and applications (Springer, Berlin, Heidelberg, 2010) 141–155; doi:10.1007/978-3-642-13742-6_7.Google Scholar
Zhang, X. B., Huang, S. and Wan, Z., “Optimal pricing and ordering in global supply chain management with constraints under random demand”, Appl. Math. Model. 40 (2016) 10105–10130; doi:10.1016/j.apm.2016.06.054.Google Scholar
Zhang, X. B., Huang, S. and Wan, Z., “Stochastic programming approach to global supply chain management under random additive demand”, Oper. Res. 18 (2018) 389–420; doi:10.1007/s12351-016-0269-2.Google Scholar
Zhou, B., Gao, L. and Dai, Y. H., “Gradient methods with adaptive step-sizes”, Comput. Optim. Appl. 35 (2006) 69–86; doi:10.1007/s10589-006-6446-0.Google Scholar