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.
References
[1]
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
[2]
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
[3]
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
[4]
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
[5]
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
[6]
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
[7]
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
[8]
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
[9]
Hager, W.W. and Zhang, H. (2006) A Survey of Nonlinear Conjugate Gradient Methods. Pacific Journal of Optimization, 2, 35-58.
[10]
Sun, W.Y. and Yuan, Y.X. (2006) Optimization Theory and Methods: Nonlinear Programming. Springer, New York.
[11]
Nocedal, J. (1992) Theory of Algorithms for Unconstrained Optimization. Acta Numerica, 1, 199-242. https://doi.org/10.1017/S0962492900002270
[12]
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
[13]
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
[14]
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
[15]
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
[16]
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
[17]
Dai, Y.H. (2002) Convergence Properties of the BFGS Algorithm. SIAM Journal on Optimization, 13, 693-701. https://doi.org/10.1137/S1052623401383455
[18]
Wolfe, P. (1969) Convergence Conditions for Ascent Methods. SIAM Review, 11, 226-235. https://doi.org/10.1137/1011036
[19]
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
[20]
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
[21]
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
[22]
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
[23]
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
[24]
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
[25]
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
[26]
Su, K. and Rong, Z. (2015) A Spectral Conjugate Gradient Method under Modified Nonmonotone Line Search Technique. Mathematica Aeterna, 5, 537-549.
[27]
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
[28]
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
[29]
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
[30]
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
[31]
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
[32]
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
[33]
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
[34]
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
[35]
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
[36]
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
[37]
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
[38]
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
[39]
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
[40]
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
[41]
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
[42]
Qi, L. and Sun, J. (1993) A Nonsmooth Version of Newton’s Method. Mathematical Programming, 58, 353-367. https://doi.org/10.1007/BF01581275
[43]
Miffin, R. (1996) A Quasi-Second-Order Proximal Bundle Algorithm. Mathematical Programming, 73, 51-72. https://doi.org/10.1007/BF02592098
[44]
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
[45]
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
[46]
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
[47]
Conn, A.R., Gould, N.I.M. and Toint, P.L. (2000) Trust Region Methods. SIAM, Philadelphia. https://doi.org/10.1137/1.9780898719857
[48]
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
[49]
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
[50]
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
