A new family of conjugate gradient methods. (English) Zbl 1155.65049
The conjugate gradient method is commonly used for solving large scale minimization problems due to its decreased storage requirements and simple computation. The global convergence of some conjugate gradient algorithms under certain line searches are not proved since the methods cannot guarantee the descent of objective function values at each iteration. This paper seeks some new line search approaches to overcome this drawback.
The authors propose a new class of conjugate gradient methods for minimizing functions that have Lipschitz continuous partial derivatives. This new class contains the Polak-Ribière-Polyak and the Liu-Storey methods as its special cases. A new nonmonotone line search is proposed for guaranteeing the global convergence. By estimating the local Lipschitz constant of the derivative of objective functions, an adequate initial step size and a suitable step size can be chosen at each iteration which decreases the function evaluations and improves the efficiency of the conjugate gradient methods. Numerical results are reported to demonstrate the effectiveness of the proposed method.
The authors propose a new class of conjugate gradient methods for minimizing functions that have Lipschitz continuous partial derivatives. This new class contains the Polak-Ribière-Polyak and the Liu-Storey methods as its special cases. A new nonmonotone line search is proposed for guaranteeing the global convergence. By estimating the local Lipschitz constant of the derivative of objective functions, an adequate initial step size and a suitable step size can be chosen at each iteration which decreases the function evaluations and improves the efficiency of the conjugate gradient methods. Numerical results are reported to demonstrate the effectiveness of the proposed method.
Reviewer: Hang Lau (Montréal)
MSC:
| 65K05 | Numerical mathematical programming methods |
| 90C30 | Nonlinear programming |
| 49M37 | Numerical methods based on nonlinear programming |
References:
| [1] | Armijo, L., Minimization of fuctions having Lipschits continuous partial derivatives, Pacific J. Math., 16, 1-3 (1966) · Zbl 0202.46105 |
| [2] | Al-Baali, M., New property and global convergence of the Fletcher-Reeves method with inexact line searches, IMA J. Numer. Anal., 5, 122-124 (1985) · Zbl 0578.65063 |
| [3] | Bongartz, I.; Conn, A. R.; Gould, N. I.M.; Toint, P. L., CUTE: Constrained and unconstrained testing environments, ACM Trans. Math. Softw., 21, 123-160 (1995) · Zbl 0886.65058 |
| [4] | Chen, X. D.; Sun, J., Global convergence of a two-parameter family of conjugate gradient methods without line search, J. Comput. Appl. Math., 146, 37-45 (2002) · Zbl 1018.65081 |
| [5] | Dai, Y. H., New properties of a nonlinear conjugate gradient method, Numer. Math., 89, 83-98 (2001) · Zbl 1006.65063 |
| [6] | Dai, Y. H., On the nonmonotone line search, J. Optim. Theory Appl., 112, 2, 315-330 (2002) · Zbl 1049.90087 |
| [7] | Dai, Y. H.; Yuan, Y., Convergence properties of the conjugate descent method, Adv. Math., 25, 552-562 (1996) · Zbl 0871.49028 |
| [8] | Dai, Y. H.; Yuan, Y., Convergence properties of the Fletcher-Reeves method, IMA J. Numer. Anal., 16, 155-164 (1996) · Zbl 0851.65049 |
| [9] | Dai, Y. H.; Yuan, Y., A nonlinear conjugate gradient method with a strong global convergence property, SIAM J. Optim., 10, 177-182 (1999) · Zbl 0957.65061 |
| [10] | Dai, Y. H.; Han, J. Y.; Liu, G. H.; Sun, D. F.; Yin, H. X.; Yuan, Y. X., Convergence properties of nonlinear conjugate gradient methods, SIAM J. Optim., 10, 345-358 (1999) · Zbl 0957.65062 |
| [11] | Dai, Y. H., A family of hybrid conjugate gradient methods for unconstrained optimization, Math. Comp., 72, 1317-1328 (2003) · Zbl 1014.49024 |
| [12] | Fletcher, R., (Practical Method of Optimization. Practical Method of Optimization, Unconstrained Optimization, vol. I (1987), Wiley: Wiley New York) · Zbl 0905.65002 |
| [13] | Fletcher, R.; Reeves, C., Function minimization by conjugate gradients, Comput. J., 7, 149-154 (1964) · Zbl 0132.11701 |
| [14] | Fasano, G., Planar conjugate gradient algorithm for large-scale unconstrained optimization, Part 1: Theory, J. Optim. Theory Appl., 125, 523-541 (2005) · Zbl 1079.90162 |
| [15] | Fasano, G., Planar conjugate gradient algorithm for large-scale unconstrained optimization, Part 2: Applications, J. Optim. Theory Appl., 125, 543-558 (2005) · Zbl 1079.90163 |
| [16] | Grippo, L.; Lucidi, S., A globally convergent version of the Polak-Ribière conjugate gradient method, Math. Program, 78, 375-391 (1997) · Zbl 0887.90157 |
| [17] | Grippo, L.; Lampariello, F.; Lucidi, S., A nonmonotone line search technique for Newton’s method, SIAM J. Numer. Anal., 23, 707-716 (1986) · Zbl 0616.65067 |
| [18] | Grippo, L.; Lampariello, F.; Lucidi, S., A truncated Newton method with nonmonotone line search for unconstrained optimization, J. Optim. Theory Appl., 60, 401-419 (1989) · Zbl 0632.90059 |
| [19] | Grippo, L.; Sciandrone, M., Nonmonotone globalization techniques for the Barzilai-Borwein gradient gethod, Comput Optim. Appl., 23, 143-169 (2002) · Zbl 1028.90061 |
| [20] | Gilbert, J. C.; Nocedal, J., Global convergence properties of conjugate gradient methods for optimization, SIAM J. Optim., 2, 1, 21-42 (1992) · Zbl 0767.90082 |
| [21] | Hager, W. W.; Zhang, H. C., A new conjugate gradient method with guaranteed descent and an efficient line search, SIAM J. Optim., 16, 170-192 (2005) · Zbl 1093.90085 |
| [22] | Hager, W. W.; Zhang, H. C., Algorithm 851: CG_DESCENT, A conjugate gradient method with guaranteed descent, ACM Trans. Math. Softw., 32, 113-137 (2006) · Zbl 1346.90816 |
| [23] | Hestenes, M. R.; Stiefel, E., Method of conjugate gradient for solving linear systems, J. Res. Natl. Bur. Stand., 49, 409-436 (1952) · Zbl 0048.09901 |
| [24] | Hu, Y. F.; Storey, C., Global convergence result for conjugate gradient methods, J. Optim. Theory Appl., 71, 399-405 (1991) · Zbl 0794.90063 |
| [25] | Liu, Y.; Storey, C., Efficient generalized conjugate gradient algorithms, part 1: theory, J. Optim. Theory Appl., 69, 129-137 (1991) · Zbl 0702.90077 |
| [26] | Nocedal, J.; Wright, J. S., Numerical Optimization (1999), Springer-Verlag New York, Inc. · Zbl 0930.65067 |
| [27] | Polak, E.; Ribiére, G., Note sur la convergence de directions conjuguées, Rev. Francaise Infomat Recherche Operatonelle, 3e Année, 16, 35-43 (1969) · Zbl 0174.48001 |
| [28] | Polyak, B. T., The conjugate gradient method in extreme problems, USSR Comp. Math. Math. Phys., 9, 94-112 (1969) · Zbl 0229.49023 |
| [29] | Raydan, M., The Barzilai and Borwein gradient method for the large-scale unconstrained minimization problem, SIAM J. Optim., 7, 26-33 (1997) · Zbl 0898.90119 |
| [30] | Sun, J.; Zhang, J. P., Convergence of conjugate gradient methods without line search, Ann. Oper. Res., 103, 161-173 (2001) · Zbl 1014.90071 |
| [31] | Sun, J.; Yang, X. Q.; Chen, X. D., Quadratic cost flow and the conjugate gradient method, European J. Oper. Res., 164, 104-114 (2005) · Zbl 1132.90374 |
| [32] | Shanno, D. F., On the convergence of a new conjugate gradient algorithm, SIAM J. Numer. Anal., 15, 1247-1257 (1978) · Zbl 0408.90071 |
| [33] | Sun, W. Y.; Han, J. Y.; Sun, J., Global convergence of nonmonotone descent methods for unconstrained optimization problems, J. Comput. Appl. Math., 146, 89-98 (2002) · Zbl 1007.65044 |
| [34] | Shi, Z. J., Restricted PR conjugate gradient method and its global convergence, Adv. in Math., 31, 1, 47-55 (2002), (in Chinese) · Zbl 1264.90179 |
| [35] | Shi, Z. J., Modified HS conjugate gradient method and its global convergence, Math. Numer. Sin., 23, 383-406 (2001), (in Chinese) · Zbl 1495.90234 |
| [36] | Shi, Z. J.; Shen, J., Convergence of Polak-Rebiére-Polyak conjugate gradient method, Nonlinear Anal., 66, 1428-1441 (2007) · Zbl 1120.49027 |
| [37] | Shi, Z. J.; Shen, J., Convergence of descent method without line search, Appl. Math. Comput., 167, 94-107 (2005) · Zbl 1084.65064 |
| [38] | Shi, Z. J.; Shen, J., Step-size estimation for unconstrained optimization methods, Comput. Appli. Math., 24, 3, 399-416 (2005) · Zbl 1213.90232 |
| [39] | Shi, Z. J.; Shen, J., New inexact line search method for unconstrained optimization, J. Optim. Theory Appl., 127, 2, 425-446 (2005) · Zbl 1116.90097 |
| [40] | Shi, Z. J.; Shen, J., Convergence of nonmonotone line search methods, J. Comput. Appl. Math., 193, 397-412 (2006) · Zbl 1136.90477 |
| [41] | Toint, P. L., A nonmonotone trust-region algorithm for nonlinear optimization subject to convex constraints, Math. Prog., 77, 69-94 (1997) · Zbl 0891.90153 |
| [42] | Toint, P. L., An assessment of nonmonotone line search techniques for unconstrained optimization, SIAM J. Sci. Comput., 17, 725-739 (1996) · Zbl 0849.90113 |
| [43] | Yuan, Y., Numerical Methods for Nonlinear Programming (1993), Shanghai Science and Technology Publisher |
| [44] | Yuan, Y., Analysis on the conjugate gradient method, Optim. Methods Softw., 2, 19-29 (1993) |
| [45] | Zhang, H. C.; Hager, W. W., A nonmonotone line search technique and its application to unconstrained optimization, SIAM J. Optim., 14, 1043-1056 (2004) · Zbl 1073.90024 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
