A New Hybrid Conjugate Gradient Method Based on Eigenvalue Analysis for Unconstrained Optimization Problems

Document Type: بنیادی - نظری

Authors

1 Department of Mathematics, Payame Noor University, PO BOX 19395-3697, Tehran, Iran

2 Young Researchers and Elite Club‎, ‎Hamedan Branch‎, ‎Islamic Azad University‎, ‎Hamedan‎, ‎Iran

10.30473/coam.2019.44564.1108

Abstract

In this paper‎, ‎two extended three-term conjugate gradient methods based on the Liu-Storey ({\tt LS})‎
‎conjugate gradient method are presented to solve unconstrained optimization problems‎. ‎A remarkable property of the proposed methods is that the search direction always satisfies‎ ‎the sufficient descent condition independent of line search method‎, ‎based on eigenvalue analysis‎. ‎The global convergence of proposed algorithms is established under suitable conditions‎. ‎Preliminary numerical results show that the proposed methods are efficient and robust‎ ‎to solve the unconstrained optimization problems.

Keywords

Main Subjects


bibitem{AhoAP} Ahookhosh M.‎, ‎Amini K.‎, ‎Peyghami M.R‎. ‎(2012)‎. ‎``A nonmonotone trust--region line search method for large-scale unconstrained optimization"‎, ‎Applied Mathematical Modelling‎, ‎36(1)‎, ‎478--487‎.

‎bibitem{A15} Andrei N‎. ‎(2015)‎. ‎``A new three--term conjugate gradient algorithm for unconstrained optimization"‎, ‎Applied Mathematical Modelling‎, ‎68‎, ‎305--321‎.

‎bibitem{B72} Beale E.M.L‎. ‎(1972)‎. ‎``A derivative of conjugate gradients‎, ‎in‎: ‎Lootsma F A‎, ‎eds‎. ‎Numerical methods for nonlinear optimization"‎, ‎London‎, ‎Academic Press‎, ‎39--43‎.

‎bibitem{CUTEST} Conn A‎. ‎R.‎, ‎Gould N‎. ‎I‎. ‎M.‎, ‎Toint Ph‎. ‎L‎. ‎(1995)‎. ‎``CUTE‎: ‎constrained and unconstrained testing environment"‎, ‎ACM T‎. ‎Math‎. ‎Software‎, ‎21‎, ‎123--160‎.

‎bibitem{DY99} Dai Y.‎, ‎Yuan Y‎. ‎(1999)‎. ‎``A nonlinear conjugate gradient method with a strong global convergence property"‎, ‎SIAM Journal on Optimization‎, ‎10(1)‎, ‎177--182‎.

‎bibitem{D19} Djordjevic S.S‎. ‎(2019)‎. ‎``New hybrid conjugate gradient method as a convex combination of LS and FR methods"‎,

‎Acta Mathematica Scientia‎, ‎39B(1)‎, ‎214--228‎.

‎bibitem{DM} Dolan E.D.‎, ‎Mor'{e} J‎. ‎(2012)‎. ‎``Benchmarking optimization software with performance profiles"‎, ‎Mathematical Programming Ser A‎, ‎91(2)‎, ‎201--213‎.

‎bibitem{EM} Edelman A.‎, ‎Mith T.S‎. ‎(1996)‎. ‎``On conjugate gradient--like methods for eigen--like problems"‎, ‎BIT Numerical Mathematics‎,

‎36(1)‎, ‎1--16‎.

‎bibitem{EK14} Esmaeili H.‎, ‎Kimiaei M‎. ‎(2014)‎. ‎``An improved adaptive trust--region method for unconstrained optimization"‎,

‎Mathematical Modelling and Analysis‎, ‎19(4)‎, ‎469--490‎.

‎bibitem{ERK} Esmaeili H.‎, ‎Rostami M.‎, ‎Kimiaei M‎. ‎(2018)‎. ‎``Extended Dai--Yuan conjugate gradient strategy for large--scale unconstrained optimization with applications to compressive sensing"‎, ‎Filomat‎, ‎32(6)‎, ‎323--337‎.

‎bibitem{F} Fletcher R‎. ‎(1987)‎. ‎``{em Practical methods of optimization‎, ‎in‎: ‎Unconstrained Optimization}"‎, ‎John Wiley & Sons‎, ‎New York‎.

‎bibitem{FR64} Fletcher R.‎, ‎Reeves C‎. ‎(1964)‎. ‎``Function minimization by conjugate gradients"‎, ‎Computer Journal‎, ‎72(2)‎, ‎149--154‎.

‎bibitem{GL01} Gill P.‎, ‎Leonard M.W‎. ‎(2001)‎. ‎``Reduced--Hessian Quasi--Newton methods for unconstrained optimization"‎, ‎SIAM Journal on Optimization‎, ‎12(1)‎, ‎209--237‎.

‎bibitem{GM72} Gill P.‎, ‎Murry W‎. ‎(1972)‎. ‎``Quasi--Newton Methods for Unconstrained Optimization"‎, ‎IMA Journal of Applied Mathematics‎,

‎9(1)‎, ‎91--108‎.

‎bibitem{GLL86} Grippo L.‎, ‎Lamparillo F.‎, ‎Lucidi S‎. ‎(1986)‎. ‎``A nonmonotone line search technique for Newtons method"‎,

‎SIAM Journal on Numerical Analysis‎, ‎23‎, ‎707--716‎.

‎bibitem{HZ06} Hager W.W.‎, ‎Zhang H‎. ‎(2006)‎. ‎``A survey of nonlinear conjugate gradient methods"‎,

‎Pacific journal of Optimization‎, ‎2(1)‎, ‎35--58‎.

‎bibitem{HS} Hestenes M.R.‎, ‎Stiefel E.L‎. ‎(1952)‎. ‎``Methods of conjugate gradients for solving linear systems"‎,

‎Journal of Research of the National Bureau of Standards‎, ‎49‎, ‎409--436‎.

‎bibitem{KGH17} Kimiaei M.‎, ‎Ghaderi S‎. ‎(2017)‎. ‎``A new restarting adaptive trust--region method for unconstrained optimization"‎,

‎Journal of the Operations Research Society of China‎, ‎5(4)‎, ‎487--507‎.

‎bibitem{KR16} Kimiaei M.‎, ‎Rostami M‎. ‎(2016)‎. ‎``Impulse noise removal based on new hybrid conjugate gradient approach"‎,

‎Kybernetika‎, ‎52(5)‎, ‎791--823‎.

‎bibitem{LCD97} Li Z.F.‎, ‎Chen J.‎, ‎Deng N.Y‎. ‎(1997)‎. ‎``A New Conjugate Gradient Method and Its Global Convergence Properties"‎,

‎Mathematical Programming‎, ‎78‎, ‎375--391‎.

‎bibitem{LF11} Li M.‎, ‎Feng H‎. ‎(2011)‎. ‎``A sufficient descent LS conjugate gradient method for unconstrained optimization problems"‎,

‎Applied Mathematics and Computation‎, ‎218‎, ‎1577--1586‎.

‎bibitem{LS91} Liu Y.L.‎, ‎Storey C‎. ‎(1991)‎. ‎``Efficient generalized conjugate gradient algorithms"‎,

‎part1‎: ‎Journal of Optimization Theory and Applications‎, ‎69(1)‎, ‎129--137‎.

‎bibitem{NYF} Narushima Y.‎, ‎Yabe H.‎, ‎Ford J.A‎. ‎(2011)‎. ‎``A three--term conjugate gradient method with sufficient descent property for unconstrained optimization"‎, ‎SIAM Journal on Optimization‎, ‎21‎, ‎212--230‎.

‎bibitem{NW} Nocedal J‎, ‎Wright S‎. ‎(2006)‎. ‎``{em Numerical Optimization}"‎, ‎Springer‎, ‎New York‎.

‎bibitem{PR} Polak E.‎, ‎Ribi`{e}re G‎. ‎(1969)‎. ‎``Note sur la convergence de directions conjugu'{e}e"‎, ‎Rev‎. ‎Francaise Informat Recherche Operationelle‎, ‎3e Ann'{e}e‎, ‎16‎, ‎35--43‎.

‎bibitem{P} Polyak B.T‎. ‎(1969)‎. ‎``The conjugate gradient method in extreme problems"‎, ‎USSR Computational Mathematics and Mathematical Physics‎, ‎9‎, ‎94--112‎.

‎bibitem{P84} Powell M.J.D‎. ‎(1984)‎. ‎``Nonconvex minimization calculations and the conjugate gradient method"‎, ‎in‎: ‎Numerical Analysis (Dundee‎, ‎1983)‎, ‎Lecture Notes in Mathematics‎. ‎1066‎, ‎Springer‎, ‎Berlin‎, ‎122--141‎.

‎bibitem{GS} Strang G‎. ‎(2016)‎. ‎`` {em Introduction to Linear Algebra}"‎, ‎Springer‎, ‎Fifth Edition‎, ‎New York‎.

‎bibitem{WZW08} Wang F.‎, ‎Zhang K.‎, ‎Wang C.‎, ‎Wang L‎. ‎(2008)‎. ‎``A variant of trust--region methods for unconstrained optimization"‎, ‎Applied Mathematics and Computation‎, ‎203‎, ‎297--307‎.

‎bibitem{YH18} Yuan G.‎, ‎Hu W‎. ‎(2018)‎. ‎``A conjugate gradient algorithm for large--scale unconstrained optimization problems and nonlinear equations"‎, ‎Journal of Inequalities and Applications‎, ‎113‎, ‎https://doi.org/10.1186/s13660--018--1703--1‎.

‎bibitem{YLD13} Yang X.‎, ‎Luo Z.‎, ‎Dai X‎. ‎(2013)‎. ‎``A global convergence of LS--CD hybrid conjugate gradient method"‎,

‎Advances in Numerical Analysis‎, ‎517--452‎.

‎bibitem{YSA} Yang X.‎, ‎Sarkar T‎. ‎P.‎, ‎Arvas E‎. ‎(1989)‎. ‎``A survey of conjugate gradient algorithms for solution of extreme eigenproblems of a symmetric matrix"‎, ‎IEEE Trans‎. ‎Acoust‎. ‎Speech Signal Processing‎, ‎37‎, ‎1550--1556‎.

‎bibitem{Z09} Zhang L‎. ‎(2009)‎. ‎``A new Liu--Storey type nonlinear conjugate gradient method for unconstrained optimization problems"‎,

‎J‎. ‎Comput‎. ‎Appl‎. ‎Math‎, ‎225‎, ‎146--157‎.

‎bibitem{ZH14} Zhang H.‎, ‎Hager W.W‎. ‎(2014)‎. ‎``A nonmonotone line search technique and its application to nuconstrained optimization"‎,

‎SIAM Journal on Optimization‎, ‎14( 4)‎, ‎1043--1056‎.

‎bibitem{ZZL} Zhang L.‎, ‎Zhou W.‎, ‎Li D.H‎. ‎(2006)‎. ‎``A descent modified Polak-Ribi`{e}re-Polyak conjugate gradient method and its global convergence"‎, ‎IMA Journal of Numerical Analysis‎, ‎26(4)‎, ‎629--640‎.

‎bibitem{ZZL07} Zhang L.‎, ‎Zhou W.‎, ‎Li D‎. ‎(2007)‎. ‎``Some descent three--term conjugate‎

‎gradient methods and their global convergence"‎, ‎Optim Methods Software‎,

‎22(4)‎, ‎697--711‎.

‎bibitem{ZhSh18} Zheng X.‎, ‎Shi J‎. ‎(2018)‎. ‎``A Modified Sufficient Descent Polak–Ribiére–Polyak Type Conjugate Gradient Method for Unconstrained Optimization Problems"‎, ‎Algorithms‎, ‎11(9)‎, ‎https://doi.org/10.3390/a11090133‎.

‎bibitem{ZZC13} Zhou Q.‎, ‎Zhou F.‎, ‎Cao F‎. ‎(2013)‎. ‎``A nonmonotone trust--region method based on simple conic models for unconstrained optimization"‎, ‎Applied Mathematics and Computation‎, ‎225‎, ‎295--305‎.