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

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

Lixing Han. An unconstrained optimization approach for finding real eigenvalues of even order symmetric tensors. Numerical Algebra, Control & Optimization, 2013, 3 (3) : 583-599. doi: 10.3934/naco.2013.3.583

[17]

Xin Zhang, Jie Wen, Qin Ni. Subspace trust-region algorithm with conic model for unconstrained optimization. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 223-234. doi: 10.3934/naco.2013.3.223

[18]

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

[19]

Leong-Kwan Li, Sally Shao. Convergence analysis of the weighted state space search algorithm for recurrent neural networks. Numerical Algebra, Control & Optimization, 2014, 4 (3) : 193-207. doi: 10.3934/naco.2014.4.193

[20]

Foxiang Liu, Lingling Xu, Yuehong Sun, Deren Han. A proximal alternating direction method for multi-block coupled convex optimization. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-15. doi: 10.3934/jimo.2018067

2016 Impact Factor: 0.994

Metrics

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

Other articles
by authors

[Back to Top]