It is widely accepted that the stepsize is of great significance to gradient method. An efficient gradient method with approximately optimal stepsizes mainly based on regularization models is proposed for unconstrained optimization. More specifically, if the objective function is not close to a quadratic function on the line segment between the current and latest iterates, regularization model is exploited carefully to generate approximately optimal stepsize. Otherwise, quadratic approximation model is used. In addition, when the curvature is non-positive, special regularization model is developed. The convergence of the proposed method is established under some weak conditions. Extensive numerical experiments indicated the proposed method is very promising. Due to the surprising efficiency, we believe that gradient methods with approximately optimal stepsizes can become strong candidates for large-scale unconstrained optimization.
Keywords: Approximately optimal stepsize, gradient method, regularization method, Barzilai–Borwein (BB) method, global convergence
@article{RO_2022__56_4_2403_0,
author = {Liu, Zexian and Chu, Wangli and Liu, Hongwei},
title = {An efficient gradient method with approximately optimal stepsizes based on regularization models for unconstrained optimization},
journal = {RAIRO. Operations Research},
pages = {2403--2424},
year = {2022},
publisher = {EDP-Sciences},
volume = {56},
number = {4},
doi = {10.1051/ro/2022107},
mrnumber = {4458848},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2022107/}
}
TY - JOUR AU - Liu, Zexian AU - Chu, Wangli AU - Liu, Hongwei TI - An efficient gradient method with approximately optimal stepsizes based on regularization models for unconstrained optimization JO - RAIRO. Operations Research PY - 2022 SP - 2403 EP - 2424 VL - 56 IS - 4 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2022107/ DO - 10.1051/ro/2022107 LA - en ID - RO_2022__56_4_2403_0 ER -
%0 Journal Article %A Liu, Zexian %A Chu, Wangli %A Liu, Hongwei %T An efficient gradient method with approximately optimal stepsizes based on regularization models for unconstrained optimization %J RAIRO. Operations Research %D 2022 %P 2403-2424 %V 56 %N 4 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2022107/ %R 10.1051/ro/2022107 %G en %F RO_2022__56_4_2403_0
Liu, Zexian; Chu, Wangli; Liu, Hongwei. An efficient gradient method with approximately optimal stepsizes based on regularization models for unconstrained optimization. RAIRO. Operations Research, Tome 56 (2022) no. 4, pp. 2403-2424. doi: 10.1051/ro/2022107
[1] , On a successive transformation of probability distribution and its application to the analysis of the optimum gradient method. Ann. Inst. Statist. Math. 11 (1959) 1–17. | MR | DOI
[2] , An unconstrained optimization test functions collection. Adv. Model. Optim. 10 (2008) 147–161. | MR
[3] and , Two-point step size gradient methods. IMA J. Numer. Anal. 8 (1988) 141–148. | MR | DOI
[4] and , A cubic regularization algorithm for unconstrained optimization using line search and nonmonotone techniques. Optim. Methods Softw. 31 (2016) 1008–1035. | MR | DOI
[5] , and , On the use of iterative methods in cubic regularization for unconstrained optimization. Comput. Optim. Appl. 60 (2015) 35–57. | MR | DOI
[6] and , Scaling on the spectral gradient method. J. Optim. Theory Appl. 158 (2013) 626–635. | MR | DOI
[7] , and , Nonmonotone spectral projected gradient methods for convex sets. SIAM J. Optim. 10 (2000) 1196–1211. | MR | DOI
[8] , and , Adaptive cubic regularisation methods for unconstrained optimization. Part I: motivation, convergence and numerical results. Math. Program. 127 (2011) 245–295. | MR | DOI
[9] , and , Adaptive cubic regularisation methods for unconstrained optimization. Part II: worst-case function-and derivative-evaluation complexity. Math. Program. 130 (2011) 295–319. | MR | DOI
[10] , Méthode générale pour la résolution des systéms déquations simultanées. Comput. Rend. Sci. Paris 25 (1847) 46–89.
[11] and , A nonlinear conjugate gradient algorithm with an optimal property and an improved Wolfe line search. SIAM J. Optim. 23 (2013) 296–320. | MR | DOI
[12] and , -linear convergence of the Barzilai and Borwein gradient method. IMA J. Numer. Anal. 22 (2002) 1–10. | MR | DOI
[13] and , An adaptive two-point stepsize gradient algorithm. Numer. Algorithms 27 (2001) 377–385. | MR | DOI
[14] , and , Modified two-point stepsize gradient methods for unconstrained optimization. Comput. Optim. Appl. 22 (2002) 103–109. | MR | DOI
[15] , , and , The cyclic Barzilai-Borwein method for unconstrained optimization. IMA J. Numer. Anal. 26 (2006) 604–627. | MR | DOI
[16] and , Benchmarking optimization software with performance profiles. Math. Program. 91 (2002) 201–213. | MR | DOI
[17] and , Updating the regularization parameter in the adaptive cubic regularization algorithm. Comput. Optim. Appl. 53 (2012) 1–22. | MR | DOI
[18] , and , CUTEr and SifDec: a constrained and unconstrained testing environment, revisited. ACM Trans. Math. Softw. 29 (2003) 373–394. | DOI
[19] , and , A nonmonotone line search technique for Newton’s method. SIAM J. Numer. Anal. 23 (1986) 707–716. | MR | DOI
[20] and , A new conjugate gradient method with guaranteed descent and an efficient line search. SIAM J. Optim. 16 (2005) 170–192. | MR | DOI
[21] and , Algorithm 851: CG_DESCENT, a conjugate gradient method with guaranteed descent. ACM Trans. Math. Softw. 32 (2006) 113–137. | MR | DOI
[22] , and , Equipping Barzilai-Borwein method with two dimensional quadratic termination property. SIAM J. Optim. 31 (2021) 3068–3096. | MR | DOI
[23] and , On a faster R-linear convergence rate of the Barzilai-Borwein method (2020). Preprint . | arXiv
[24] and , Several efficient gradient methods with approximate optimal stepsizes for large scale unconstrained optimization. J. Comput. Appl. Math. 328 (2018) 400–413. | MR | DOI
[25] and , An efficient gradient method with approximate optimal stepsize for large-scale unconstrained optimization. Numer. Algorithms 78 (2018) 21–39. | MR | DOI
[26] , and , An efficient gradient method with approximate optimal stepsize for the strictly convex quadratic minimization problem. Optimization 67 (2018) 427–440. | MR | DOI
[27] and , Gradient method with dynamical retards for large-scale optimization problems. Electron. Trans. Numer. Anal. 16 (2003) 186–193. | MR
[28] , and , Scalar correction method for solving large scale unconstrained minimization problems. J. Optim. Theory Appl. 151 (2011) 304–320. | MR | DOI
[29] , and , An adaptive nonmonotone global Barzilai-Borwein gradient method for unconstrained optimization. Optimization 66 (2017) 641–655. | MR | DOI
[30] and On the Barzilai and Borwein choice of steplength for the gradient method. IMA J. Numer. Anal. 13 (1993) 321–326. | MR | DOI
[31] , The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem. SIAM J. Optim. 7 (1997) 26–33. | MR | DOI
[32] , Optimization methods for non-quadratic model. Asia-Pac. J. Oper. Res. 13 (1996) 43–63. | MR
[33] and , A filter-trust-region method based on conic model for unconstrained optimization. Sci. Sin. Math. 55 (2012) 527–543.
[34] , A non-monotone trust-region algorithm for nonlinear optimization subject to convex constraints. Math. Program. 77 (1997) 69–94. | MR | DOI
[35] , and , Notes on the Dai-Yuan-Yuan modified spectral gradient method. J. Comput. Appl. Math. 234 (2010) 2986–2992. | MR | DOI
[36] , A new stepsize for the steepest descent method. J. Comput. Math. 24 (2006) 149–156. | MR
[37] and , A nonmonotone line search technique and its application to unconstrained optimization. SIAM J. Optim. 14 (2004) 1043–1056. | MR | DOI
[38] , and , New quasi-Newton equation and related methods for unconstrained optimization. J. Optim. Theory Appl. 102 (1999) 147–167. | MR | DOI
Cité par Sources :
