• 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
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.

[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.

[3]

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

[4]

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

[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.

[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.

[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.

[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.

[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.

[10]

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

[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.

[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.

[13]

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

[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.

[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.

[16]

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

[17]

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

[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.

[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.

[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).

[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.

[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.

[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.

[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.

[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.

[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.

show all references

References:
[1]

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

[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.

[3]

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

[4]

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

[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.

[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.

[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.

[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.

[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.

[10]

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

[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.

[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.

[13]

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

[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.

[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.

[16]

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

[17]

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

[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.

[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.

[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).

[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.

[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.

[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.

[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.

[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.

[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.

[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]

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

[15]

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

[16]

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

[17]

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

[18]

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

[19]

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

[20]

Lijuan Zhao, Wenyu Sun. Nonmonotone retrospective conic trust region method for unconstrained optimization. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 309-325. doi: 10.3934/naco.2013.3.309

2017 Impact Factor: 0.972

Metrics

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

Other articles
by authors

[Back to Top]