• Previous Article
    Numerical simulation of two-fluid flow and meniscus interface movement in the electromagnetic continuous steel casting process
  • DCDS-B Home
  • This Issue
  • Next Article
    A class of nonlinear impulsive differential equation and optimal controls on time scales
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]

M. S. Lee, H. G. Harno, B. S. Goh, K. H. Lim. On the bang-bang control approach via a component-wise line search strategy for unconstrained optimization. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 45-61. doi: 10.3934/naco.2020014

[2]

Predrag S. Stanimirović, Branislav Ivanov, Haifeng Ma, Dijana Mosić. A survey of gradient methods for solving nonlinear optimization. Electronic Research Archive, 2020, 28 (4) : 1573-1624. doi: 10.3934/era.2020115

[3]

Thomas Frenzel, Matthias Liero. Effective diffusion in thin structures via generalized gradient systems and EDP-convergence. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 395-425. doi: 10.3934/dcdss.2020345

[4]

José Madrid, João P. G. Ramos. On optimal autocorrelation inequalities on the real line. Communications on Pure & Applied Analysis, 2021, 20 (1) : 369-388. doi: 10.3934/cpaa.2020271

[5]

Thierry Horsin, Mohamed Ali Jendoubi. On the convergence to equilibria of a sequence defined by an implicit scheme. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020465

[6]

Tommi Brander, Joonas Ilmavirta, Petteri Piiroinen, Teemu Tyni. Optimal recovery of a radiating source with multiple frequencies along one line. Inverse Problems & Imaging, 2020, 14 (6) : 967-983. doi: 10.3934/ipi.2020044

[7]

Martin Heida, Stefan Neukamm, Mario Varga. Stochastic homogenization of $ \Lambda $-convex gradient flows. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 427-453. doi: 10.3934/dcdss.2020328

[8]

Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020031

[9]

Parikshit Upadhyaya, Elias Jarlebring, Emanuel H. Rubensson. A density matrix approach to the convergence of the self-consistent field iteration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 99-115. doi: 10.3934/naco.2020018

[10]

Haiyu Liu, Rongmin Zhu, Yuxian Geng. Gorenstein global dimensions relative to balanced pairs. Electronic Research Archive, 2020, 28 (4) : 1563-1571. doi: 10.3934/era.2020082

[11]

Jianhua Huang, Yanbin Tang, Ming Wang. Singular support of the global attractor for a damped BBM equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020345

[12]

Bernold Fiedler. Global Hopf bifurcation in networks with fast feedback cycles. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 177-203. doi: 10.3934/dcdss.2020344

[13]

Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017

[14]

Yi-Long Luo, Yangjun Ma. Low Mach number limit for the compressible inertial Qian-Sheng model of liquid crystals: Convergence for classical solutions. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 921-966. doi: 10.3934/dcds.2020304

[15]

Cheng He, Changzheng Qu. Global weak solutions for the two-component Novikov equation. Electronic Research Archive, 2020, 28 (4) : 1545-1562. doi: 10.3934/era.2020081

[16]

Touria Karite, Ali Boutoulout. Global and regional constrained controllability for distributed parabolic linear systems: RHUM approach. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020055

[17]

Ahmad Z. Fino, Wenhui Chen. A global existence result for two-dimensional semilinear strongly damped wave equation with mixed nonlinearity in an exterior domain. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5387-5411. doi: 10.3934/cpaa.2020243

[18]

Mengni Li. Global regularity for a class of Monge-Ampère type equations with nonzero boundary conditions. Communications on Pure & Applied Analysis, 2021, 20 (1) : 301-317. doi: 10.3934/cpaa.2020267

[19]

Bo Chen, Youde Wang. Global weak solutions for Landau-Lifshitz flows and heat flows associated to micromagnetic energy functional. Communications on Pure & Applied Analysis, 2021, 20 (1) : 319-338. doi: 10.3934/cpaa.2020268

[20]

Karoline Disser. Global existence and uniqueness for a volume-surface reaction-nonlinear-diffusion system. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 321-330. doi: 10.3934/dcdss.2020326

2019 Impact Factor: 1.27

Metrics

  • PDF downloads (47)
  • HTML views (0)
  • Cited by (15)

Other articles
by authors

[Back to Top]