• Previous Article
    A class of nonlinear impulsive differential equation and optimal controls on time scales
  • DCDS-B Home
  • This Issue
  • Next Article
    Numerical simulation of two-fluid flow and meniscus interface movement in the electromagnetic continuous steel casting process
November  2011, 16(4): 1157-1169. doi: 10.3934/dcdsb.2011.16.1157

A spectral PRP conjugate gradient methods for nonconvex optimization problem based on modified line search

1. 

School of Mathematics Sciences and Computing Technology, Central South University, Hunan Changsha, 410083, China, China

Received  August 2010 Revised  February 2011 Published  August 2011

In this paper, a new spectral PRP conjugate gradient algorithm is developed for solving nonconvex unconstrained optimization problems. The search direction in this algorithm is proved to be a sufficient descent direction of the objective function independent of line search. To rule out possible unacceptably short step in the Armijo line search, a modified Armijo line search strategy is presented. The obtained step length is improved by employing the properties of the approximate Wolfe conditions. Under some suitable assumptions, the global convergence of the developed algorithm is established. Numerical experiments demonstrate that this algorithm is promising.
Citation: Zhong Wan, Chaoming Hu, Zhanlu Yang. A spectral PRP conjugate gradient methods for nonconvex optimization problem based on modified line search. Discrete & Continuous Dynamical Systems - B, 2011, 16 (4) : 1157-1169. doi: 10.3934/dcdsb.2011.16.1157
References:
[1]

N. Andrei, Numerical comparison of conjugate gradient algorithms for unconstrained optimization,, Studies in Informatics and Control, 16 (2007), 333. Google Scholar

[2]

N. Andrei, Acceleration of conjugate gradient algorithms for unconstrained optimization,, Applied Mathematics and Computation, 213 (2009), 361. doi: 10.1016/j.amc.2009.03.020. Google Scholar

[3]

N. Andrei, Open problems in conjugate gradient algorithms for unconstrained optimization,, Bulletin of the Malaysian Mathematical Sciences Society, (2011). Google Scholar

[4]

A. Antoniou and W. S. Lu, "Practical Optimization: Algorithms and Engineering Applications,'', Springer, (2007). Google Scholar

[5]

E. Birgin and J. M. Martínez, A spectral conjugate gradient method for unconstrained optimization,, Appl. Math. Optim., 43 (2001), 117. doi: 10.1007/s00245-001-0003-0. Google Scholar

[6]

E. Feireisl, F. Issard-Roch and H. Petzeltová, Long-time behaviour and convergence towards equilibria for a conserved phase field model. Partial differential equations and applications,, Discrete Contin. Dyn. Syst., 10 (2004), 239. Google Scholar

[7]

J. C. Gilbert and J. Nocedal, Global convergence properties of conjugate gradient methods for optimization,, SIAM J. Optim., 2 (1992), 21. doi: 10.1137/0802003. Google Scholar

[8]

L. Grippo and S. Lucidi, A globally convergent version of the Polak-Ribière conjugate gradient method,, Math. Prog., 78 (1997), 375. doi: 10.1007/BF02614362. Google Scholar

[9]

M. Gunzburger, S. D. Yang and W. X. Zhu, Analysis and discretization of an optimal control problem for the forced Fisher equation,, Discrete and Continuous Dynamical Systems-Series B, 8 (2007), 569. doi: 10.3934/dcdsb.2007.8.569. Google Scholar

[10]

W. W. Hager and H. C. Zhang, A survey of nonlinear conjugate gradient methods,, Pracific J Optim., 2 (2006), 35. Google Scholar

[11]

Z. Huang and S. Li, Guaranteed descent conjugate gradient methods with modified secant condition,, J. Industrial and Management Optim., 4 (2008), 739. doi: 10.3934/jimo.2008.4.739. Google Scholar

[12]

G. Li, L. Guan and G. Yu, Global convergence of modified Polak-Ribière-Polyak conjugate gradient methods with sufficient descent property,, J. Industrial and Management Optim., 4 (2008), 565. doi: 10.3934/jimo.2008.4.565. Google Scholar

[13]

J. Nocedal and J. S. Wright, "Numerical Optimization,'', Springer Series in Operations Research, (1999). doi: 10.1007/b98874. Google Scholar

[14]

E. Polak and G. Ribiére, Note sur la convergence de méthodes de directions conjuguées,, Rev. Française Infomat. Recherche Opérationnelle, 3 (1969), 35. Google Scholar

[15]

B. T. Polyak, The conjugate gradient method in extreme problems,, USSR Comput. Math. Math. Phys., 9 (1969), 94. doi: 10.1016/0041-5553(69)90035-4. Google Scholar

[16]

M. J. D. Powell, Restart procedures of the conjugate gradient method,, Math. Program., 12 (1977), 241. doi: 10.1007/BF01593790. Google Scholar

[17]

M. J. D. Powell, Nonconvex minimization calculations and the conjugate gradient method,, in, 1066 (1984), 122. Google Scholar

[18]

Z. J. Shi and J. Shen, Convergence of the Polak-Ribiére-Polyak conjugate gradient method,, Nonlinear Analysis, 66 (2007), 1428. doi: 10.1016/j.na.2006.02.001. Google Scholar

[19]

J. Sun and J. P. Zhang, Global convergence of conjugate gradient methods without line search,, Annals of Operations Research, 103 (2001), 161. doi: 10.1023/A:1012903105391. Google Scholar

[20]

Z. Wan, X. D. Zheng and Y. Y. Fei, Hybrid Armijo-Wolfe line search strategy and its applications in newton method for unconstrained optimization,, working paper, (2010). Google Scholar

[21]

Z. Wan, Z. L. Yang and Y. L. Wang, New spectral PRP conjugate gradient method for unconstrained optimization,, Appl. Math. Letter, 24 (2011), 16. doi: 10.1016/j.aml.2010.08.002. Google Scholar

[22]

C. Wang, Y. Chen and S. Du, Further insight into the Shamanskii modification of Newton method,, Appl. Math. Comput., 180 (2006), 46. doi: 10.1016/j.amc.2005.11.167. Google Scholar

[23]

G. H. Yu, L. T. Guan and Z. X. Wei, Globally convergent Polak-Ribiére-Polyak conjugate gradient methods under a modified Wolfe line search,, Applied Mathematics and Computation, 215 (2009), 3082. Google Scholar

[24]

G. L. Yuan, X. W. Lu and Z. X. Wei, A conjugate gradient method with descent direction for unconstrained optimization,, Journal of Computational and Applied Mathematics, 233 (2009), 519. doi: 10.1016/j.cam.2009.08.001. Google Scholar

[25]

L. Zhang, W. J. Zhou and D. H. Li, Global convergence of a modified Fletcher-Reeves conjugate gradient method with Armijo-type line search,, Numer. Math., 104 (2006), 561. doi: 10.1007/s00211-006-0028-z. Google Scholar

[26]

L. Zhang, W. J. Zhou and D. H. Li, A descent modified Polak-Ribière-Polyak conjugate gradient method and its global convergence,, IMA J. Numer. Anal., 26 (2006), 629. doi: 10.1093/imanum/drl016. Google Scholar

show all references

References:
[1]

N. Andrei, Numerical comparison of conjugate gradient algorithms for unconstrained optimization,, Studies in Informatics and Control, 16 (2007), 333. Google Scholar

[2]

N. Andrei, Acceleration of conjugate gradient algorithms for unconstrained optimization,, Applied Mathematics and Computation, 213 (2009), 361. doi: 10.1016/j.amc.2009.03.020. Google Scholar

[3]

N. Andrei, Open problems in conjugate gradient algorithms for unconstrained optimization,, Bulletin of the Malaysian Mathematical Sciences Society, (2011). Google Scholar

[4]

A. Antoniou and W. S. Lu, "Practical Optimization: Algorithms and Engineering Applications,'', Springer, (2007). Google Scholar

[5]

E. Birgin and J. M. Martínez, A spectral conjugate gradient method for unconstrained optimization,, Appl. Math. Optim., 43 (2001), 117. doi: 10.1007/s00245-001-0003-0. Google Scholar

[6]

E. Feireisl, F. Issard-Roch and H. Petzeltová, Long-time behaviour and convergence towards equilibria for a conserved phase field model. Partial differential equations and applications,, Discrete Contin. Dyn. Syst., 10 (2004), 239. Google Scholar

[7]

J. C. Gilbert and J. Nocedal, Global convergence properties of conjugate gradient methods for optimization,, SIAM J. Optim., 2 (1992), 21. doi: 10.1137/0802003. Google Scholar

[8]

L. Grippo and S. Lucidi, A globally convergent version of the Polak-Ribière conjugate gradient method,, Math. Prog., 78 (1997), 375. doi: 10.1007/BF02614362. Google Scholar

[9]

M. Gunzburger, S. D. Yang and W. X. Zhu, Analysis and discretization of an optimal control problem for the forced Fisher equation,, Discrete and Continuous Dynamical Systems-Series B, 8 (2007), 569. doi: 10.3934/dcdsb.2007.8.569. Google Scholar

[10]

W. W. Hager and H. C. Zhang, A survey of nonlinear conjugate gradient methods,, Pracific J Optim., 2 (2006), 35. Google Scholar

[11]

Z. Huang and S. Li, Guaranteed descent conjugate gradient methods with modified secant condition,, J. Industrial and Management Optim., 4 (2008), 739. doi: 10.3934/jimo.2008.4.739. Google Scholar

[12]

G. Li, L. Guan and G. Yu, Global convergence of modified Polak-Ribière-Polyak conjugate gradient methods with sufficient descent property,, J. Industrial and Management Optim., 4 (2008), 565. doi: 10.3934/jimo.2008.4.565. Google Scholar

[13]

J. Nocedal and J. S. Wright, "Numerical Optimization,'', Springer Series in Operations Research, (1999). doi: 10.1007/b98874. Google Scholar

[14]

E. Polak and G. Ribiére, Note sur la convergence de méthodes de directions conjuguées,, Rev. Française Infomat. Recherche Opérationnelle, 3 (1969), 35. Google Scholar

[15]

B. T. Polyak, The conjugate gradient method in extreme problems,, USSR Comput. Math. Math. Phys., 9 (1969), 94. doi: 10.1016/0041-5553(69)90035-4. Google Scholar

[16]

M. J. D. Powell, Restart procedures of the conjugate gradient method,, Math. Program., 12 (1977), 241. doi: 10.1007/BF01593790. Google Scholar

[17]

M. J. D. Powell, Nonconvex minimization calculations and the conjugate gradient method,, in, 1066 (1984), 122. Google Scholar

[18]

Z. J. Shi and J. Shen, Convergence of the Polak-Ribiére-Polyak conjugate gradient method,, Nonlinear Analysis, 66 (2007), 1428. doi: 10.1016/j.na.2006.02.001. Google Scholar

[19]

J. Sun and J. P. Zhang, Global convergence of conjugate gradient methods without line search,, Annals of Operations Research, 103 (2001), 161. doi: 10.1023/A:1012903105391. Google Scholar

[20]

Z. Wan, X. D. Zheng and Y. Y. Fei, Hybrid Armijo-Wolfe line search strategy and its applications in newton method for unconstrained optimization,, working paper, (2010). Google Scholar

[21]

Z. Wan, Z. L. Yang and Y. L. Wang, New spectral PRP conjugate gradient method for unconstrained optimization,, Appl. Math. Letter, 24 (2011), 16. doi: 10.1016/j.aml.2010.08.002. Google Scholar

[22]

C. Wang, Y. Chen and S. Du, Further insight into the Shamanskii modification of Newton method,, Appl. Math. Comput., 180 (2006), 46. doi: 10.1016/j.amc.2005.11.167. Google Scholar

[23]

G. H. Yu, L. T. Guan and Z. X. Wei, Globally convergent Polak-Ribiére-Polyak conjugate gradient methods under a modified Wolfe line search,, Applied Mathematics and Computation, 215 (2009), 3082. Google Scholar

[24]

G. L. Yuan, X. W. Lu and Z. X. Wei, A conjugate gradient method with descent direction for unconstrained optimization,, Journal of Computational and Applied Mathematics, 233 (2009), 519. doi: 10.1016/j.cam.2009.08.001. Google Scholar

[25]

L. Zhang, W. J. Zhou and D. H. Li, Global convergence of a modified Fletcher-Reeves conjugate gradient method with Armijo-type line search,, Numer. Math., 104 (2006), 561. doi: 10.1007/s00211-006-0028-z. Google Scholar

[26]

L. Zhang, W. J. Zhou and D. H. Li, A descent modified Polak-Ribière-Polyak conjugate gradient method and its global convergence,, IMA J. Numer. Anal., 26 (2006), 629. doi: 10.1093/imanum/drl016. Google Scholar

[1]

Wataru Nakamura, Yasushi Narushima, Hiroshi Yabe. Nonlinear conjugate gradient methods with sufficient descent properties for unconstrained optimization. Journal of Industrial & Management Optimization, 2013, 9 (3) : 595-619. doi: 10.3934/jimo.2013.9.595

[2]

Gaohang Yu, Lutai Guan, Guoyin Li. Global convergence of modified Polak-Ribière-Polyak conjugate gradient methods with sufficient descent property. Journal of Industrial & Management Optimization, 2008, 4 (3) : 565-579. doi: 10.3934/jimo.2008.4.565

[3]

Guanghui Zhou, Qin Ni, Meilan Zeng. A scaled conjugate gradient method with moving asymptotes for unconstrained optimization problems. Journal of Industrial & Management Optimization, 2017, 13 (2) : 595-608. doi: 10.3934/jimo.2016034

[4]

Shishun Li, Zhengda Huang. Guaranteed descent conjugate gradient methods with modified secant condition. Journal of Industrial & Management Optimization, 2008, 4 (4) : 739-755. doi: 10.3934/jimo.2008.4.739

[5]

Saman Babaie–Kafaki, Reza Ghanbari. 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, 2017, 13 (2) : 649-658. doi: 10.3934/jimo.2016038

[6]

C.Y. Wang, M.X. Li. Convergence property of the Fletcher-Reeves conjugate gradient method with errors. Journal of Industrial & Management Optimization, 2005, 1 (2) : 193-200. doi: 10.3934/jimo.2005.1.193

[7]

El-Sayed M.E. Mostafa. A nonlinear conjugate gradient method for a special class of matrix optimization problems. Journal of Industrial & Management Optimization, 2014, 10 (3) : 883-903. doi: 10.3934/jimo.2014.10.883

[8]

Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024

[9]

Yigui Ou, Xin Zhou. A modified scaled memoryless BFGS preconditioned conjugate gradient algorithm for nonsmooth convex optimization. Journal of Industrial & Management Optimization, 2018, 14 (2) : 785-801. doi: 10.3934/jimo.2017075

[10]

Mohamed Aly Tawhid. Nonsmooth generalized complementarity as unconstrained optimization. Journal of Industrial & Management Optimization, 2010, 6 (2) : 411-423. doi: 10.3934/jimo.2010.6.411

[11]

King Hann Lim, Hong Hui Tan, Hendra G. Harno. Approximate greatest descent in neural network optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 327-336. doi: 10.3934/naco.2018021

[12]

Chunlin Hao, Xinwei Liu. Global convergence of an SQP algorithm for nonlinear optimization with overdetermined constraints. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 19-29. doi: 10.3934/naco.2012.2.19

[13]

Anulekha Dhara, Aparna Mehra. Conjugate duality for generalized convex optimization problems. Journal of Industrial & Management Optimization, 2007, 3 (3) : 415-427. doi: 10.3934/jimo.2007.3.415

[14]

Xiaming Chen. Kernel-based online gradient descent using distributed approach. Mathematical Foundations of Computing, 2019, 2 (1) : 1-9. doi: 10.3934/mfc.2019001

[15]

Jianjun Liu, Min Zeng, Yifan Ge, Changzhi Wu, Xiangyu Wang. Improved Cuckoo Search algorithm for numerical function optimization. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-13. doi: 10.3934/jimo.2018142

[16]

Nora Merabet. Global convergence of a memory gradient method with closed-form step size formula. Conference Publications, 2007, 2007 (Special) : 721-730. doi: 10.3934/proc.2007.2007.721

[17]

Nam-Yong Lee, Bradley J. Lucier. Preconditioned conjugate gradient method for boundary artifact-free image deblurring. Inverse Problems & Imaging, 2016, 10 (1) : 195-225. doi: 10.3934/ipi.2016.10.195

[18]

Xing Li, Chungen Shen, Lei-Hong Zhang. A projected preconditioned conjugate gradient method for the linear response eigenvalue problem. Numerical Algebra, Control & Optimization, 2018, 8 (4) : 389-412. doi: 10.3934/naco.2018025

[19]

Wei-Zhe Gu, Li-Yong Lu. The linear convergence of a derivative-free descent method for nonlinear complementarity problems. Journal of Industrial & Management Optimization, 2017, 13 (2) : 531-548. doi: 10.3934/jimo.2016030

[20]

Jun Chen, Wenyu Sun, Zhenghao Yang. A non-monotone retrospective trust-region method for unconstrained optimization. Journal of Industrial & Management Optimization, 2013, 9 (4) : 919-944. doi: 10.3934/jimo.2013.9.919

2018 Impact Factor: 1.008

Metrics

  • PDF downloads (11)
  • HTML views (0)
  • Cited by (10)

Other articles
by authors

[Back to Top]