In this paper, we provide and analyze a new scaled conjugate gradient method and its performance, based on the modified secant equation of the Broyden-Fletcher-Goldfarb-Shanno (BFGS) method and on a new modified nonmonotone line search technique. The method incorporates the modified BFGS secant equation in an effort to include the second order information of the objective function. The new secant equation has both gradient and function value information, and its update formula inherits the positive definiteness of Hessian approximation for general convex function. In order to improve the likelihood of finding a global optimal solution, we introduce a new modified nonmonotone line search technique. It is shown that, for nonsmooth convex problems, the proposed algorithm is globally convergent. Numerical results show that this new scaled conjugate gradient algorithm is promising and efficient for solving not only convex but also some large scale nonsmooth nonconvex problems in the sense of the Dolan-Moré performance profiles.
KeywordsConjugate Gradient MethodBFGS MethodModified Secant EquationNonmonotone Line SearchNonsmooth Optimization
Broyden, C.G. (1970) The Convergence of a Class of Double-Rank Minimization Algorithms: I. General Considerations. Journal of the Institute of Mathematics and Its Applications, 6, 76-90. https://doi.org/10.1093/imamat/6.1.76
Fletcher, R. (1970) A New Approach to Variable Metric Algorithms. The Computer Journal, 13, 317-322. https://doi.org/10.1093/comjnl/13.3.317
Goldfarb, D. (1970) A Family of Variable Metric Methods Derived by Variation Mean. Mathematics of Computation, 23, 23-26. https://doi.org/10.1090/S0025-5718-1970-0258249-6
Shanno, D.F. (1970) Conditioning of Quasi-Newton Methods for Function Minimization. Mathematics of Computation, 24, 647-656. https://doi.org/10.1090/S0025-5718-1970-0274029-X
Hestenes, M.R. and Stiefel, E. (1952) Methods of Conjugate Gradients for Solving Linear Systems. Journal of Research of the National Bureau of Standards, 49, 409-436. https://doi.org/10.6028/jres.049.044
Fletcher, R. and Reeves, C.M. (1964) Function Minimization by Conjugate Gradients. The Computer Journal, 7, 149-154. https://doi.org/10.1093/comjnl/7.2.149
Polak, H. (1969) The Conjugate Gradient Method in Extreme Problems. USSR Computational Mathematics and Mathematical Physics, 9, 94-112. https://doi.org/10.1016/0041-5553(69)90035-4
Dai, Y.H. and Yuan, Y. (1999) A Nonlinear Conjugate Gradient Method with a Strong Global Convergence Property. SIAM Journal on Optimization, 10, 177-182. https://doi.org/10.1137/S1052623497318992
Hager, W.W. and Zhang, H. (2006) A Survey of Nonlinear Conjugate Gradient Methods. Pacific Journal of Optimization, 2, 35-58.
Sun, W.Y. and Yuan, Y.X. (2006) Optimization Theory and Methods: Nonlinear Programming. Springer, New York.
Nocedal, J. (1992) Theory of Algorithms for Unconstrained Optimization. Acta Numerica, 1, 199-242. https://doi.org/10.1017/S0962492900002270
Dennis, J.E. and Moré, J.J. (1974) A Characterization of Superlinear Convergence and Its Application to Quasi-Newton Methods. Mathematics of Computation, 28, 549-560. https://doi.org/10.1090/S0025-5718-1974-0343581-1
Byrd, R., Nocedal, J. and Yuan, Y. (1987) Global Convergence of a Class of Quasi-Newton Methods on Convex Problems. SIAM Journal on Numerical Analysis, 24, 1171-1189. https://doi.org/10.1137/0724077
Byrd, R. and Nocedal, J. (1989) A Tool for the Analysis of Quasi-Newton Methods with Application to Unconstrained Minimization. SIAM Journal on Numerical Analysis, 26, 727-739. https://doi.org/10.1137/0726042
Griewank, A. (1991) The Global Convergence of Partitioned BFGS on Problems with Convex Decompositions and Lipschitzian Gradients. Mathematical Programming, 50, 141-175. https://doi.org/10.1007/BF01594933
Mascarenhas, W.F. (2004) The BFGS Method with Exact Line Searches Fails for Non-Convex Objective Functions. Mathematical Programming, 99, 49-61. https://doi.org/10.1007/s10107-003-0421-7
Dai, Y.H. (2002) Convergence Properties of the BFGS Algorithm. SIAM Journal on Optimization, 13, 693-701. https://doi.org/10.1137/S1052623401383455
Wolfe, P. (1969) Convergence Conditions for Ascent Methods. SIAM Review, 11, 226-235. https://doi.org/10.1137/1011036
Grippo, L., Lampariello, F. and Lucidi, S. (1986) A Nonmonotone Line Search Technique for Newton’s Method. SIAM Journal on Scientific Computing, 23, 707-716. https://doi.org/10.1137/0723046
Toint, P.L. (1996) An Assessment of Nonmonotone Line Search Technique for Unconstrained Optimization. SIAM Journal on Scientific Computing, 17, 725-739. https://doi.org/10.1137/S106482759427021X
Toint, P.L. (1997) A Nonmonotone Trust Region Algorithm for Nonlinear Programming Subject to Convex Constraints. Mathematical Programming, 77, 69-94. https://doi.org/10.1007/BF02614518
Panier, E.R. and Tits, A.L. (1991) Avoiding Maratos Effect by Means of Nonmonotone Line Search Constrained Problems. SIAM Journal on Numerical Analysis, 28, 1183-1190. https://doi.org/10.1137/0728063
Yu, Z. and Pu, D. (2008) A New Nonmonotone Line Search Technique for Unconstrained Optimization. Journal of Computational and Applied Mathematics, 219, 134-144. https://doi.org/10.1016/j.cam.2007.07.008
Yuan, G., Wei, Z. and Wu, Y. (2010) Modified Limited Memory BFGS Method with Nonmonotone Line Search for Unconstrained Optimization Problems. Journal of the Korean Mathematical Society, 47, 767-788. https://doi.org/10.4134/JKMS.2010.47.4.767
Li, X., Wang, B. and Hu, W. (2017) A Modified Nonmonotone BFGS Algorithm for Unconstrained Optimization. Journal of Inequalities and Applications, 183, 1-18. https://doi.org/10.1186/s13660-017-1453-5
Su, K. and Rong, Z. (2015) A Spectral Conjugate Gradient Method under Modified Nonmonotone Line Search Technique. Mathematica Aeterna, 5, 537-549.
Andrei, A. (2007) Scaled Conjugate Gradient Algorithms for Unconstrained Optimization. Computational Optimization and Applications, 38, 401-416. https://doi.org/10.1007/s10589-007-9055-7
Babaie-Kafaki, S. (2013) A Modified Scaled Memoryless BFGS Preconditioned Conjugate Gradient Method for Unconstrained Optimization. 4OR, 11, 361-374. https://doi.org/10.1007/s10288-013-0233-4
Babaie-Kafaki, S. and Chanbari, R. (2017) A Class of Descent Four-Term Extension of the Dai-Liao Conjugate Gradient Method Based on the Scaled Memoryless BFGS Update. Journal of Industrial & Management Optimization, 13, 649-658. https://doi.org/10.3934/jimo.2016038
Yuan, G., Wei, Z. and Li, G. (2014) A Modified Polak-Ribière-Polyak Conjugate Gradient Algorithm for Nonsmooth Convex Programs. Journal of Computational and Applied Mathematics, 255, 86-96. https://doi.org/10.1016/j.cam.2013.04.032
Yuan, G., Wei, Z. and Li, Y. (2015) A Modified Hestenes and Stiefel Conjugate Gradient Algorithm for Large-Scale Nonsmooth Minimizations and Nonlinear Equations. Journal of Optimization Theory and Applications, 168, 129-152. https://doi.org/10.1007/s10957-015-0781-1
Yuan, G. and Wei, Z. (2015) A Modified PRP Conjugate Gradient Algorithm with Nonmonotone Line Search for Nonsmooth Convex Optimization Problems. Journal of Applied Mathematics and Computing, 51, 397-412. https://doi.org/10.1007/s12190-015-0912-8
Yuan, G., Sheng, Z. and Liu, W. (2016) The Modified HZ Conjugate Gradient Algorithm for Large-Scale Nonsmooth Optimization. PLoS ONE, 11, e0164289. https://doi.org/10.1371/journal.pone.0164289
Yuan, G. and Wei, Z. (2012) The Barzilai and Browein Gradient Method with Nonmonotone Line Search for Nonsmooth Convex Optimization Problems. Mathematical Modelling and Analysis, 17, 203-216. https://doi.org/10.3846/13926292.2012.661375
Cui, Z., Yuan, G., Sheng, Z., Liu, W., Wang, X. and Duan, X. (2015) A Modified BFGS Formula Using a Trust Region Model for Nonsmooth Convex Minimizations. PLoS ONE, 10, e0140606. https://doi.org/10.1371/journal.pone.0140606
Burke, J.V. and Qian, M. (2000) On the Superlinear Convergence of the Variable Metric Proximal Point Algorithm Using Broyden and BFGS Matrix Secant Updating. Mathematical Programming, 88, 157-181. https://doi.org/10.1007/PL00011373
Chen, X. and Fukushima, M. (1999) Proximal Quasi-Newton Methods for Nondifferentiale Convex Optimization. Mathematical Programming, 85, 313-334. https://doi.org/10.1007/s101070050059
Sagara, N. and Fukushima, M. (2005) A Trust Region Method for Nonsmooth Convex Optimization. Journal of Industrial & Management Optimization, 1, 171-180. https://doi.org/10.3934/jimo.2005.1.171
Ou, Y. and Zhou, X. (2018) A Modified Scaled Memoryless BFGS Preconditioned Conjugate Gradient Algorithm for Nonsmooth Convex Optimization. Journal of Industrial & Management Optimization, 14, 785-801. https://doi.org/10.3934/jimo.2017075
Hiriart-Urruty, J.B. and Lemaréchal, C. (1993) Convex Analysis and Minimization Algorithms. Springer, Berlin. https://doi.org/10.1007/978-3-662-02796-7
Fukushima, M. and Qi, L. (1996) A Global and Superlinearly Convergent Algorithm for Nonsmooth Convex Minimization. SIAM Journal on Optimization, 6, 1106-1120. https://doi.org/10.1137/S1052623494278839
Qi, L. and Sun, J. (1993) A Nonsmooth Version of Newton’s Method. Mathematical Programming, 58, 353-367. https://doi.org/10.1007/BF01581275
Miffin, R. (1996) A Quasi-Second-Order Proximal Bundle Algorithm. Mathematical Programming, 73, 51-72. https://doi.org/10.1007/BF02592098
Bonnans, J.F., Gilbert, J.C., Lemaréchal, C. and Sagastizábal, C. (1995) A Family of Variable-Metric Proximal Methods. Mathematical Programming, 68, 15-47. https://doi.org/10.1007/BF01585756
Lemaréchal, C. and Sagastizábal, C. (1997) Practical Aspects of the Moreu-Yosida Regularization: Theoretical Preliminaries. SIAM Journal on Optimization, 7, 367-385. https://doi.org/10.1137/S1052623494267127
Rauf, A.I. and Fukushima, M. (2000) A Globally Convergent BFGS Method for Nonsmooth Convex Optimization. Journal of Optimization Theory and Applications, 104, 539-558. https://doi.org/10.1023/A:1004633524446
Conn, A.R., Gould, N.I.M. and Toint, P.L. (2000) Trust Region Methods. SIAM, Philadelphia. https://doi.org/10.1137/1.9780898719857
Li, D.H. and Fukushima, M. (1999) On the Global Convergence of BFGS Method for Nonconvex Unconstrained Optimization Problems. SIAM Journal on Optimization, 11, 1054-1064. https://doi.org/10.1137/S1052623499354242
Haarala, M. and Mäkelä, M.M. (2004) New Limited Memory Bundle Method for Large-Scale Nonsmooth Optimization. Optimization Methods and Software, 19, 673-692. https://doi.org/10.1080/10556780410001689225
Dolan, E.D. and Moré, J.J. (2002) Benchmarking Optimization Software with Performance Profiles. Mathematical Programming, 91, 201-213. https://doi.org/10.1007/s101070100263