Abstract
This paper gives a modified PRP method which possesses the global convergence of nonconvex function and the R-linear convergence rate of uniformly convex function. Furthermore, the presented method has sufficiently descent property and characteristic of automatically being in a trust region without carrying out any line search technique. Numerical results indicate that the new method is interesting for the given test problems.
Similar content being viewed by others
References
Al-baali, A. (1985). Descent property and global convergence of the Fletcher-Reeves method with inexact line search. IMA Journal of Numerical Analysis, 5, 121–124.
Armijo, L. (1966). Minimization of functions having Lipschitz conditions partial derivatives. Pacific Journal of Mathematics, 16, 1–3.
Chen, X., & Sun, J. (2002). Global convergence of a two-parameter family of conjugate gradient methods without line search. Journal of Computational and Applied Mathematics, 146(1), 37–45.
Dai, Y. (2001). Convergence of nonlinear conjugate methods. Journal of Computational Mathematics, 19, 539–549.
Dai, Y. (2002). A nonmonotone conjugate gradient algorithm for unconstrained optimization. Journal of Systems Science and Complexity, 15, 139–145.
Dai, Y., & Ni, Q. (2003). Testing different conjugate gradient methods for large-scale unconstrained optimization. Journal of Computational Mathematics, 21(3), 311–320.
Dai, Y., & Yuan, Y. (1995). Further studies on the Polak-Ribière-Polyak method. Research report ICM-95-040, Institute of Computational Mathematics and Scientific/Engineering computing, Chinese Academy of Sciences.
Dai, Y., & Yuan, Y. (1996). Convergence properties of the conjugate descent method. Advances in Mathematics, 6, 552–562.
Dai, Y., & Yuan, Y. (2000a). A nonlinear conjugate gradient with a strong global convergence properties. SIAM Journal on Optimization, 10, 177–182.
Dai, Y., & Yuan, Y. (2000b). Nonlinear conjugate gradient methods. Shanghai: Science Press of Shanghai.
Dai, Y., & Yuan, Y. (2001). An efficient hybrid conjugate gradient method for unconstrained optimization. Annals of Operations Research, 103, 33–47.
Dai, Y., Han, J., Liu, G., Sun, D., Yin, H., & Yan, Y. (1999). Convergence properties of the nonlinear conjugate methods. SIAM Journal on Optimization, 2, 345–358.
Dolan, E. D., & Moré, J. J. (2002). Benchmarking optimization software with performance profiles. Mathematical Programming, 91, 201–213.
Fletcher, R. (1997). Practical method of optimization, Vol I: Unconstrained optimization (2nd ed.). New York: Wiley.
Fletcher, R., & Reeves, C. (1964). Function minimization by conjugate gradients. Computer Journal, 7, 149–154.
Gibert, J. C., & Nocedal, J. (1992). Global convergence properties of conjugate gradient methods for optimization. SIAM Journal on Optimization, 2, 21–42.
Gould, N. I. M., Orban, D., Toint, P. L., & CUTEr(and SifDec) (2003). A constrained and unconstrained testing environment, revisited. ACM Transactions on Mathematical Software, 29, 373–394.
Griewank, A. (1989). On automatic differentiation. In M. Iri & K. Tanabe (Eds.), Mathematical programming: Recent developments and applications (pp. 84–108). Dordrecht: Kluwer Academic.
Grippo, L., & Lucidi, S. (1997). A globally convergent version of the Polak-Ribière gradient method. Mathematical Programming, 78, 375–391.
Grippo, L., Lampariello, F., & Lucidi, S. (1986). A nonmonotone line search technique for Newton’s method. SIAM Journal on Numerical Analysis, 23, 707–716.
Han, J., Liu, G., Sun, D., & Yin, H. (2001). Two fundamental convergence theorems for nonlinear conjugate gradient methods and their applications. Acta Mathematicae Applicatae Sinica, 1, 38–46.
Hestenes, M. R., & Stiefel, E. (1952). Method of conjugate gradient for solving linear equations. Journal of Research of National Bureau of Standards, 49, 409–436.
Liu, G., & Han, J. (1995). On the global convergence of conjugate gradient methods with inexact line search. Numerical Mathematics. A Journal of Chinese Universities, 2, 147–153.
Liu, Y., & Storey, C. (1992). Efficient generalized conjugate gradient algorithms, part 1: theory. Journal of Optimization Theory and Application, 69, 17–41.
Liu, G., Han, J., & Yin, H. (1995). Global convergence of the Fletcher-Reeves algorithm with inexact line search. Applied Mathematics. Journal of Chinese Universities Series B, 10, 75–82.
McCormick, G. (1977). A modification of Armijo’s step-size rule for negative curvature. Mathematical Programming, 13, 111–115.
Moré, J. J., Garbow, B. S., & Hillstrome, K. E. (1981). Testing unconstrained optimization software. ACM Transactions on Mathematical Software, 7, 17–41.
Nocedal, J. (1992). Theorem of algorithms for unconstrained optimization. In Acta Numerica (pp. 199–242). Cambridge: Cambridge University Press.
Nocedal, J. (1995). Conjugate gradient methods and nonlinear optimization. In L. Adams & J. L. Nazareth (Eds.), Linear and nonlinear conjugate gradient related methods (pp. 9–23). Philadelphia: SIAM.
Polak, E. (1997). Optimization: Algorithms and consistent approximations. New York: Springer.
Polak, E., & Ribière, G. (1969). Note sur la convergence de directions conjugèes. Rev. Francaise Inform. Recherche Operationelle, 16(3), 35–43.
Polyak, B. T. (1969). The conjugate gradient method in extreme problems. USSR Computational Mathematics and Mathematical Physics, 9, 94–112.
Powell, M. J. D. (1977). Restart procedures for the conjugate gradient method. Mathematical Programming, 12, 241–254.
Powell, M. J. D. (1984). Nonconvex minimization calculations and the conjugate gradient method. In Lecture notes in mathematics (vol. 1066, pp. 122–141). Berlin: Springer.
Powell, M. J. D. (1986). Convergence properties of algorithms for nonlinear optimization. SIAM Review, 28, 487–500.
Qi, H., Han, J., & Liu, G. (1996). A modification of Hestenes-Stiefel conjugate gradient method. Chinese Annals of Mathematics, 3, 177–184.
Shi, Z. J. (2004). Convergence of line search methods for unconstrained optimization. Applied Mathematics and Computation, 157, 393–405.
Sun, J., & Zhang, J. (2001). Convergence of conjugate gradient methods without line search. Annals of Operations Research, 103, 161–173.
Wei, Z., Li, G., & Qi, L. (2006a). New nonlinear conjugate gradient formulas for large-scale unconstrained optimization problems. Applied Mathematics and Computation, 179, 407–430.
Wei, Z., Yao, S., & Liu, L. (2006b). The convergence properties of some new conjugate gradient methods. Applied Mathematics and Computation, 183, 1341–1350.
Yuan, Y. (1993). Analysis on the conjugate gradient method. Optimization Methods and Software, 2, 19–29.
Zhang et al. (2006). A descent modified Polak-Ribière-Polyak conjugate method and its global convergence. IMA Journal on Numerical Analysis, 26, 629–649.
Zoutendijk, G. (1970). Nonlinear programming computational methods. In J. Abadie (Ed.), Integer and nonlinear programming (pp. 37–86). Amsterdam: North-Holland.
Author information
Authors and Affiliations
Corresponding author
Additional information
This work is supported by Guangxi University SF grands X061041 and China NSF grands 10761001.
Rights and permissions
About this article
Cite this article
Yuan, G., Lu, X. A modified PRP conjugate gradient method. Ann Oper Res 166, 73–90 (2009). https://doi.org/10.1007/s10479-008-0420-4
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-008-0420-4