A survey of gradient methods for solving nonlinear optimization

  • Received: 01 October 2020 Revised: 01 November 2020 Published: 09 November 2020
  • Primary: 65K05, 90C30; Secondary: 90C06, 90C26

  • The paper surveys, classifies and investigates theoretically and numerically main classes of line search methods for unconstrained optimization. Quasi-Newton (QN) and conjugate gradient (CG) methods are considered as representative classes of effective numerical methods for solving large-scale unconstrained optimization problems. In this paper, we investigate, classify and compare main QN and CG methods to present a global overview of scientific advances in this field. Some of the most recent trends in this field are presented. A number of numerical experiments is performed with the aim to give an experimental and natural answer regarding the numerical one another comparison of different QN and CG methods.

    Citation: Predrag S. Stanimirović, Branislav Ivanov, Haifeng Ma, Dijana Mosić. A survey of gradient methods for solving nonlinear optimization[J]. Electronic Research Archive, 2020, 28(4): 1573-1624. doi: 10.3934/era.2020115

    Related Papers:

  • The paper surveys, classifies and investigates theoretically and numerically main classes of line search methods for unconstrained optimization. Quasi-Newton (QN) and conjugate gradient (CG) methods are considered as representative classes of effective numerical methods for solving large-scale unconstrained optimization problems. In this paper, we investigate, classify and compare main QN and CG methods to present a global overview of scientific advances in this field. Some of the most recent trends in this field are presented. A number of numerical experiments is performed with the aim to give an experimental and natural answer regarding the numerical one another comparison of different QN and CG methods.



    加载中


    [1] A new reprojection of the conjugate directions. Numer. Algebra Control Optim. (2019) 9: 157-171.
    [2] Descent property and global convergence of the Fletcher-Reeves method with inexact line search. IMA J. Numer. Anal. (1985) 5: 121-124.
    [3] An unconstrained optimization test functions collection. Adv. Model. Optim. (2008) 10: 147-161.
    [4] An acceleration of gradient descent algorithm with backtracking for unconstrained optimization. Numer. Algorithms (2006) 42: 63-73.
    [5] A Dai-Liao conjugate gradient algorithm with clustering of eigenvalues. Numer. Algorithms (2018) 77: 1273-1282.
    [6] N. Andrei, Relaxed gradient descent and a new gradient descent methods for unconstrained optimization, Visited August 19, (2018).
    [7] N. Andrei, Nonlinear Conjugate Gradient Methods for Unconstrained Optimization, 1st edition, Springer International Publishing, 2020. doi: 10.1007/978-3-030-42950-8
    [8] Minimization of functions having Lipschitz continuous first partial derivatives. Pacific J. Math. (1966) 16: 1-3.
    [9] The Dai-Liao nonlinear conjugate gradient method with optimal parameter choices. European J. Oper. Res. (2014) 234: 625-630.
    [10] B. Baluch, Z. Salleh, A. Alhawarat and U. A. M. Roslan, A new modified three-term conjugate gradient method with sufficient descent property and its global convergence, J. Math., 2017 (2017), Article ID 2715854, 12 pages. doi: 10.1155/2017/2715854
    [11] Two-point step-size gradient method. IMA J. Numer. Anal. (1988) 8: 141-148.
    [12] M. Bastani and D. K. Salkuyeh, On the GSOR iteration method for image restoration, Numerical Algebra, Control and Optimization, (2020). doi: 10.3934/naco.2020013
    [13] An evaluation of quasi-Newton methods for application to FSI problems involving free surface flow and solid body contact. Computers & Structures (2016) 173: 71-83.
    [14] CUTE: Constrained and unconstrained testing environments. ACM Trans. Math. Softw. (1995) 21: 123-160.
    [15] A classification of quasi-Newton methods. Numer. Algorithms (2003) 33: 123-135.
    [16] A conjugate gradient algorithm and its applications in image restoration. Appl. Numer. Math. (2020) 152: 243-252.
    [17] A two-term PRP-based descent method. Numer. Funct. Anal. Optim. (2007) 28: 1217-1230.
    [18] A sufficient descent conjugate gradient method and its global convergence. Optim. Methods Softw. (2016) 31: 577-590.
    [19] Stepsize analysis for descent methods. J. Optim. Theory Appl. (1981) 33: 187-205.
    [20] Convergence of quasi-Newton matrices generated by the symmetric rank one update. Math. Programming (1991) 50: 177-195.
    [21] Y.-H. Dai, Nonlinear Conjugate Gradient Methods, Wiley Encyclopedia of Operations Research and Management Science, (2011). doi: 10.1002/9780470400531.eorms0183
    [22] Y.-H. Dai, Alternate Step Gradient Method, Report AMSS–2001–041, Academy of Mathematics and Systems Sciences, Chinese Academy of Sciences, 2001.
    [23] A nonmonotone conjugate gradient algorithm for unconstrained optimization. J. Syst. Sci. Complex. (2002) 15: 139-145.
    [24] Y.-H. Dai and R. Fletcher, On the Asymptotic Behaviour of some New Gradient Methods, Numerical Analysis Report, NA/212, Dept. of Math. University of Dundee, Scotland, UK, 2003.
    [25] A nonlinear conjugate gradient algorithm with an optimal property and an improved wolfe line search. SIAM. J. Optim. (2013) 23: 296-320.
    [26] New conjugacy conditions and related nonlinear conjugate gradient methods. Appl. Math. Optim. (2001) 43: 87-101.
    [27] R-linear convergence of the Barzilai and Borwein gradient method. IMA J. Numer. Anal. (2002) 22: 1-10.
    [28] Testing different conjugate gradient methods for large-scale unconstrained optimization. J. Comput. Math. (2003) 21: 311-320.
    [29] Another improved Wei–Yao–Liu nonlinear conjugate gradient method with sufficient descent property. Appl. Math. Comput. (2012) 218: 7421-7430.
    [30] A nonlinear conjugate gradient method with a strong global convergence property. SIAM J. Optim. (1999) 10: 177-182.
    [31] An efficient hybrid conjugate gradient method for unconstrained optimization. Ann. Oper. Res. (2001) 103: 33-47.
    [32] Y. H. Dai and Y. Yuan, A class of Globally Convergent Conjugate Gradient Methods, Research report ICM-98-030, Institute of Computational Mathematics and Scientific/Engineering Computing, Chinese Academy of Sciences, 1998.
    [33] A class of globally convergent conjugate gradient methods. Sci. China Ser. A (2003) 46: 251-261.
    [34] Modified two-point step-size gradient methods for unconstrained optimization. Comput. Optim. Appl. (2002) 22: 103-109.
    [35] Alternate minimization gradient method. IMA J. Numer. Anal. (2003) 23: 377-393.
    [36] Analysis of monotone gradient methods. J. Ind. Manag. Optim. (2005) 1: 181-192.
    [37] Y.-H. Dai and H. Zhang, An Adaptive Two-Point Step-size gradient method, Research report, Institute of Computational Mathematics and Scientific/Engineering Computing, Chinese Academy of Sciences, 2001.
    [38] The conjugate gradient method for linear and nonlinear operator equations. SIAM J. Numer. Anal. (1967) 4: 10-26.
    [39] S. Delladji, M. Belloufi and B. Sellami, Behavior of the combination of PRP and HZ methods for unconstrained optimization, Numerical Algebra, Control and Optimization, (2020). doi: 10.3934/naco.2020032
    [40] Investigation of quasi-Newton methods for unconstrained optimization. International Journal of Computer Application (2010) 29: 48-58.
    [41] Two modifications of the method of the multiplicative parameters in descent gradient methods. Appl. Math, Comput. (2012) 218: 8672-8683.
    [42] S. S. Djordjević, Unconstrained Optimization Methods: Conjugate Gradient Methods and Trust-Region Methods, Book Chapter, 2019. doi: 10.5772/intechopen.84374
    [43] Benchmarking optimization software with performance profiles. Math. Program. (2002) 91: 201-213.
    [44] The application of quasi-Nnewton methods in fluid mechanics. Internat. J. Numer. Methods Engrg. (1981) 17: 707-718.
    [45] D. K. Faddeev and I. S. Sominskiǐ, Collection of Problems on Higher Algebra. Gostekhizdat, 2nd edition, Moscow, 1949.
    [46] A. G. Farizawani, M. Puteh, Y. Marina and A. Rivaie, A review of artificial neural network learning rule based on multiple variant of conjugate gradient approaches, Journal of Physics: Conference Series, 1529 (2020). doi: 10.1088/1742-6596/1529/2/022040
    [47] R. Fletcher, Practical Methods of Optimization, Unconstrained Optimization, 1st edition, Wiley, New York, 1987.
    [48] Function minimization by conjugate gradients. Comput. J. (1964) 7: 149-154.
    [49] Global convergence properties of conjugate gradient methods for optimization. SIAM J. Optim. (1992) 2: 21-42.
    [50] On steepest descent. J. SIAM Control Ser. A (1965) 3: 147-151.
    [51] A nonmonotone line search technique for Newton's method. SIAM J. Numer. ANAL. (1986) 23: 707-716.
    [52] A class of nonmonotone stability methods in unconstrained optimization. Numer. Math. (1991) 59: 779-805.
    [53] A truncated Newton method with nonmonotone line search for unconstrained optimization. J. Optim. Theory Appl. (1989) 60: 401-419.
    [54] Nonmonotone globalization techniques for the Barzilai-Borwein gradient method. Comput. Optim. Appl. (2002) 23: 143-169.
    [55] A new conjugate gradient method with guaranteed descent and an efficient line search. SIAM J. Optim. (2005) 16: 170-192.
    [56] Algorithm 851: CG_DESCENT, a conjugate gradient method with guaranteed descent. ACM Trans. Math. Software (2006) 32: 113-137.
    [57] A survey of nonlinear conjugate gradient methods. Pac. J. Optim. (2006) 2: 35-58.
    [58] Combining quasi-Newton and Cauchy directions. Int. J. Appl. Math. (2003) 12: 167-191.
    [59] A new type of quasi-Newton updating formulas based on the new quasi-Newton equation. Numer. Algebra Control Optim. (2020) 10: 227-235.
    [60] Methods of conjugate gradients for solving linear systems. J. Res. Nat. Bur. Standards (1952) 49: 409-436.
    [61] Global convergence result for conjugate gradient methods. J. Optim. Theory Appl. (1991) 71: 399-405.
    [62] Fixed points by a new iteration method. Proc. Am. Math. Soc. (1974) 44: 147-150.
    [63] B. Ivanov, P. S. Stanimirović, G. V. Milovanović, S. Djordjević and I. Brajević, Accelerated multiple step-size methods for solving unconstrained optimization problems, Optimization Methods and Software, (2019). doi: 10.1080/10556788.2019.1653868
    [64] Applications of the conjugate gradient method in optimal surface parameterizations. Int. J. Comput. Math. (2010) 87: 1032-1039.
    [65] A hybrid conjugate gradient method with descent property for unconstrained optimization. Appl. Math. Model. (2015) 39: 1281-1290.
    [66] S. H. Khan, A Picard-Mann hybrid iterative process, Fixed Point Theory Appl., 2013 (2013), Article number: 69, 10 pp. doi: 10.1186/1687-1812-2013-69
    [67] Novel hybrid algorithm in solving unconstrained optimizations problems. International Journal of Novel Research in Physics Chemistry & Mathematics (2017) 4: 36-42.
    [68] Implementation of gradient methods for optimization of underage costs in aviation industry. University Thought, Publication in Natural Sciences (2016) 6: 71-74.
    [69] A continuous-time approach to online optimization. J. Dyn. Games (2017) 4: 125-148.
    [70] On a two phase approximate greatest descent method for nonlinear optimization with equality constraints. Numer. Algebra Control Optim. (2018) 8: 315-326.
    [71] A modified BFGS method and its global convergence in nonconvex minimization. J. Comput. Appl. Math. (2001) 129: 15-35.
    [72] A modified PRP conjugate gradient algorithm with trust region for optimization problems. Numer. Funct. Anal. Optim. (2011) 32: 496-506.
    [73] A projected preconditioned conjugate gradient method for the linear response eigenvalue problem. Numer. Algebra Control Optim. (2018) 8: 389-412.
    [74] A modified Fletcher-Reeves-type derivative-free method for symmetric nonlinear equations. Numer. Algebra Control Optim. (2011) 1: 71-82.
    [75] Approximate greatest descent in neural network optimization. Numer. Algebra Control Optim. (2018) 8: 327-336.
    [76] J. Liu, S. Du and Y. Chen, A sufficient descent nonlinear conjugate gradient method for solving $M$-tensor equations, J. Comput. Appl. Math., 371 (2020), 112709, 11 pp. doi: 10.1016/j.cam.2019.112709
    [77] A projection method for convex constrained monotone nonlinear equations with applications. Comput. Math. Appl. (2015) 70: 2442-2453.
    [78] Efficient generalized conjugate gradient algorithms, part 1: Theory. J. Optim. Theory Appl. (1991) 69: 129-137.
    [79] A risk minimization problem for finite horizon semi-Markov decision processes with loss rates. J. Dyn. Games (2018) 5: 143-163.
    [80] I. E. Livieris and P. Pintelas, A descent Dai-Liao conjugate gradient method based on a modified secant equation and its global convergence, ISRN Computational Mathematics, 2012 (2012), Article ID 435495. doi: 10.5402/2012/435495
    [81] M. Lotfi and S. M. Hosseini, An efficient Dai-Liao type conjugate gradient method by reformulating the CG parameter in the search direction equation, J. Comput. Appl. Math., 371 (2020), 112708, 15 pp. doi: 10.1016/j.cam.2019.112708
    [82] Hybrid approach for solving systems of nonlinear equations using chaos optimization and quasi-Newton method. Applied Soft Computing (2008) 8: 1068-1073.
    [83] Mean value methods in iterations. Proc. Amer. Math. Soc. (1953) 4: 506-510.
    [84] Scalar correction method for solving large scale unconstrained minimization problems. J. Optim. Theory Appl. (2011) 151: 304-320.
    [85] S. K. Mishra and B. Ram, Introduction to Unconstrained Optimization with R, 1st edition, Springer Singapore, Springer Nature Singapore Pte Ltd., 2019. doi: 10.1007/978-981-15-0894-3
    [86] I. S. Mohammed, M. Mamat, I. Abdulkarim and F. S. Bt. Mohamad, A survey on recent modifications of conjugate gradient methods, Proceedings of the UniSZA Research Conference 2015 (URC 5), Universiti Sultan Zainal Abidin, 14–16 April 2015.
    [87] A brief survey of methods for solving nonlinear least-squares problems. Numer. Algebra Control Optim. (2019) 9: 1-13.
    [88] A survey of sufficient descent conjugate gradient methods for unconstrained optimization. SUT J. Math. (2014) 50: 167-203.
    [89] J. L. Nazareth, Conjugate-Gradient Methods, In: C. Floudas and P. Pardalos (eds), Encyclopedia of Optimization, 2$^nd$ edition, Springer, Boston, 2009. doi: 10.1007/978-0-387-74759-0
    [90] J. Nocedal and S. J. Wright, Numerical Optimization, Springer, New York, 1999. doi: 10.1007/b98874
    [91] W. F. H. W. Osman, M. A. H. Ibrahim and M. Mamat, Hybrid DFP-CG method for solving unconstrained optimization problems, Journal of Physics: Conf. Series, 890 (2017), 012033. doi: 10.1088/1742-6596/890/1/012033
    [92] Initial improvement of the hybrid accelerated gradient descent process. Bull. Aust. Math. Soc. (2018) 98: 331-338.
    [93] A modified conjugate gradient algorithm. Oper. Res. (1978) 26: 1073-1078.
    [94] An accelerated double step-size method in unconstrained optimization. Applied Math. Comput. (2015) 250: 309-319.
    [95] Determination of accelerated factors in gradient descent iterations based on Taylor's series. University Thought, Publication in Natural Sciences (2017) 7: 41-45.
    [96] Hybridization of accelerated gradient descent method. Numer. Algorithms (2018) 79: 769-786.
    [97] A note on hybridization process applied on transformed double step size model. Numerical Algorithms (2020) 85: 449-465.
    [98] M. J. Petrović and P. S. Stanimirović, Accelerated double direction method for solving unconstrained optimization problems, Math. Probl. Eng., 2014 (2014), Article ID 965104, 8 pages. doi: 10.1155/2014/965104
    [99] M. J. Petrović, P. S. Stanimirović, N. Kontrec and J. Mladenović, Hybrid modification of accelerated double direction method, Math. Probl. Eng., 2018 (2018), Article ID 1523267, 8 pages. doi: 10.1155/2018/1523267
    [100] A new class of efficient and globally convergent conjugate gradient methods in the Dai-Liao family. Optim. Methods Softw. (2015) 30: 843-863.
    [101] Memoire sur la theorie des equations aux derivees partielles et la methode des approximations successives. J. Math. Pures Appl. (1890) 6: 145-210.
    [102] E. Polak and G. Ribière, Note sur la convergence des méthodes de directions conjuguées, Rev. Française Imformat Recherche Opértionelle, 3 (1969), 35–43.
    [103] The conjugate gradient method in extreme problems. USSR Comput. Math. and Math. Phys. (1969) 9: 94-112.
    [104] Algorithms for nonlinear constraints that use Lagrangian functions. Math. Programming (1978) 14: 224-248.
    [105] On the Barzilai and Borwein choice of steplength for the gradient method. IMA J. Numer. Anal. (1993) 13: 321-326.
    [106] The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem. SIAM J. Optim. (1997) 7: 26-33.
    [107] Relaxed steepest descent and Cauchy-Barzilai-Borwein method. Comput. Optim. Appl. (2002) 21: 155-167.
    [108] A new family of conjugate gradient coefficient with application. International Journal of Engineering & Technology (2018) 7: 36-43.
    [109] Convergence of line search methods for unconstrained optimization. Appl. Math. Comput. (2004) 157: 393-405.
    [110] The application of new conjugate gradient methods in estimating data. International Journal of Engineering & Technology (2018) 7: 25-27.
    [111] Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numer. Algebra Control Optim. (2018) 8: 377-387.
    [112] New hybrid conjugate gradient and Broyden-Fletcher-Goldfarb-Shanno conjugate gradient methods. J. Optim. Theory Appl. (2018) 178: 860-884.
    [113] Computation of $\{2, 4\}$ and $\{2, 3\}$-inverses based on rank-one updates. Linear Multilinear Algebra (2018) 66: 147-166.
    [114] Computing $\{2, 4\}$ and $\{2, 3\}$-inverses by using the Sherman-Morrison formula. Appl. Math. Comput. (2015) 273: 584-603.
    [115] Accelerated gradient descent methods with line search. Numer. Algor. (2010) 54: 503-520.
    [116] P. S. Stanimirović, G. V. Milovanović, M. J. Petrović and N. Z. Kontrec, A transformation of accelerated double step-size method for unconstrained optimization, Math. Probl. Eng., 2015 (2015), Article ID 283679, 8 pages. doi: 10.1155/2015/283679
    [117] Global convergence of nonmonotone descent methods for unconstrained optimization problems. J. Comp. Appl. Math. (2002) 146: 89-98.
    [118] Identification of Hessian matrix in distributed gradient based multi agent coordination control systems. Numer. Algebra Control Optim. (2019) 9: 297-318.
    [119] W. Sun and Y.-X. Yuan, Optimization Theory and Methods: Nonlinear Programming, 1st edition, Springer, New York, 2006. doi: 10.1007/b106451
    [120] Non–monotone trust–region algorithm for nonlinear optimization subject to convex constraints. Math. Prog. (1997) 77: 69-94.
    [121] Efficient hybrid conjugate gradient techniques. J. Optim. Theory Appl. (1990) 64: 379-397.
    [122] A class of gradient unconstrained minimization algorithms with adaptive step-size. J. Comp. Appl. Math. (2000) 114: 367-386.
    [123] New quasi-Newton methods for unconstrained optimization problems. Appl. Math. Comput. (2006) 175: 1156-1188.
    [124] New nonlinear conjugate gradient formulas for large-scale unconstrained optimization problems. Appl. Math. Comput. (2006) 179: 407-430.
    [125] The convergence properties of some new conjugate gradient methods. Appl. Math. Comput. (2006) 183: 1341-1350.
    [126] Convergence conditions for ascent methods. SIAM Rev. (1969) 11: 226-235.
    [127] Survey of derivative-free optimization. Numer. Algebra Control Optim. (2020) 10: 537-555.
    [128] A conjugate gradient method to solve convex constrained monotone equations with applications in compressive sensing. J. Math. Anal. Appl. (2013) 405: 310-319.
    [129] Global convergence properties of nonlinear conjugate gradient methods with modified secant condition. Comput. Optim. Appl. (2004) 28: 203-225.
    [130] X. Yang, Z. Luo and X. Dai, A global convergence of LS-CD hybrid conjugate gradient method, Adv. Numer. Anal., 2013 (2013), Article ID 517452, 5 pp. doi: 10.1155/2013/517452
    [131] S. Yao, X. Lu and Z. Wei, A conjugate gradient method with global convergence for large-scale unconstrained optimization problems, J. Appl. Math., 2013 (2013), Article ID 730454, 9 pp. doi: 10.1155/2013/730454
    [132] Convergence analysis of a modified BFGS method on convex minimizations. Comp. Optim. Appl. (2010) 47: 237-255.
    [133] A notes about WYL's conjugate gradient method and its applications. Appl. Math. Comput. (2007) 191: 381-388.
    [134] A new stepsize for the steepest descent method. J. Comput. Math. (2006) 24: 149-156.
    [135] A conjugate gradient algorithm for large-scale nonlinear equations and image restoration problems. Appl. Numer. Math. (2020) 147: 129-141.
    [136] G. Yuan, T. Li and W. Hu, A conjugate gradient algorithm and its application in large-scale optimization problems and image restoration, J. Inequal. Appl., 2019 (2019), Article number: 247, 25 pp. doi: 10.1186/s13660-019-2192-6
    [137] Modified limited memory BFGS method with nonmonotone line search for unconstrained optimization. J. Korean Math. Soc. (2010) 47: 767-788.
    [138] An improved Wei-Yao-Liu nonlinear conjugate gradient method for optimization computation. Appl. Math. Comput. (2009) 215: 2269-2274.
    [139] Two new Dai-Liao-type conjugate gradient methods for unconstrained optimization problems. J. Optim. Theory Appl. (2017) 175: 502-509.
    [140] Semi-local convergence of the Newton-HSS method under the center Lipschitz condition. Numer. Algebra Control Optim. (2019) 9: 85-99.
    [141] A nonlinear conjugate gradient method based on the MBFGS secant condition. Optim. Methods Softw. (2006) 21: 707-714.
    [142] G. Zoutendijk, Nonlinear programming, computational methods, In: J. Abadie (eds.): Integer and Nonlinear Programming, North-Holland, Amsterdam, (1970), 37–86.
    [143] A new gradient method for solving linear regression model. International Journal of Recent Technology and Engineering (2019) 7: 624-630.
  • Reader Comments
  • © 2020 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(4392) PDF downloads(730) Cited by(11)

Article outline

Figures and Tables

Figures(18)  /  Tables(13)

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog