Friday , April 26 2024

Volume 17-Issue4-2008-ANDREI

A Hybrid Conjugate Gradient Algorithm with Modified Secant Condition for Unconstrained Optimization as a Convex Combination of Hestenes-Stiefel and Dai-Yuan Algorithms

Neculai ANDREI1,2
1 Center for Advanced Modeling and Optimization, National Institute for R&D in Informatics, (ICI)
8-10, Averescu Avenue, Bucharest 1, Romania
2 Academy of Romanian Scientists
54, Splaiul Independenţei, Bucharest 5, Romania

Abstract: Another hybrid conjugate gradient algorithm is suggested in this paper. The parameterImage152 is computed as a convex combination of Image153 (Hestenes-Stiefel) and Image154 (Dai-Yuan) formulae, i.e. Image155. The parameter Image156 in the convex combination is computed in such a way so that the direction corresponding to the conjugate gradient algorithm to be the Newton direction and the pair Image227 to satisfy the modified secant condition given by Zhang et al. [32] and Zhang and Xu [33], where Image789 and Image790 The algorithm uses the standard Wolfe line search conditions. Numerical comparisons with conjugate gradient algorithms show that this hybrid computational scheme outperforms a variant of the hybrid conjugate gradient algorithm given by Andrei [6], in which the pair Image227 satisfies the secant condition Image228, as well as the Hestenes-Stiefel, the Dai-Yuan conjugate gradient algorithms, and the hybrid conjugate gradient algorithms of Dai and Yuan. A set of 750 unconstrained optimization problems are used, some of them from the CUTE library.

MSC: 49M07, 49M10, 90C06, 65K.

Keywords: Unconstrained optimization, hybrid conjugate gradient method, Newton direction, numerical comparisons.

Neculai Andrei graduated in Mathematics, “A.I. Cuza” University – Iasi, and in Electrical Engineering from “Politehnica” University – Bucharest. He took his PhD degree for his contributions to Digraph Approach of Large-Scale Sparse Linear Dynamic Systems in 1984. He has been a senior scientific researcher at National Institute for R&D in Informatics – ICI, since 1973. He is author of 13 books and text books, as well as over 50 published papers and 300 Technical Reports in area of mathematical modeling optimization. He is the key architect of ALLO language and compiler for modeling in mathematical programming, as well as of some professional packages for linear programming and large-scale unconstrained optimization. His main current scientific interests centre on modeling for mathematical programming and on large-scale non-linear optimization, conjugate gradient, interior point methods, penalty and barrier approaches. Dr. Andrei is a founding member of the Operations Research Society of Romania; founding member of the Center for Advanced Modeling and Optimization; member of the Editorial Board of Computational Optimization and Applications – Springer Verlag (since 1992); member of Computational Optimization and Applications – Optimization Forum; member of the Editorial Board of Journal of Systems Science and Complexity – Science Press – China and Allerton Press – USA (since 2001). He is Editor-in-Chief to the Advanced Modeling and Optimization – An Electronic International Journal – ICI Press (since 1999). Dr. Andrei is an Alexander-von- Humboldt fellow, member ERCIM and of Academy of Romanian Scientists (since 2001).

>>Full text
CITE THIS PAPER AS:
Neculai ANDREI, A Hybrid Conjugate Gradient Algorithm with Modified Secant Condition for Unconstrained Optimization as a Convex Combination of Hestenes-Stiefel and Dai-Yuan Algorithms, Studies in Informatics and Control, ISSN 1220-1766, vol. 17 (4), pp. 373-392, 2008.

1. Introduction

Let us consider the nonlinear unconstrained optimization problem

Image26                                                                                                  (1)

whereImage27 is a continuously differentiable function, bounded from below. As we know, for solving this problem starting from an initial guess Image28 a nonlinear conjugate gradient method generates a sequence Image29 as

Image30,                                                                                                          (2)

where Image31 is obtained by line search and the directions Image32 are generated as

Image791, Image34.                                                                             (3)

In (3) Image35 is known as the conjugate gradient parameter, Image36 and Image37. Consider Image38 the Euclidean norm and defineImage39. The line search in the conjugate gradient algorithms is often based on the standard Wolfe conditions:

Image40                                                                     (4)

Image792,                                                                                     (5)

where Image42 is a descent direction and Image43 Different conjugate gradient algorithms correspond to different choices for the scalar parameter Image157 The methods of Fletcher and Reeves (FR) [19], of Dai and Yuan (DY) [13] and the Conjugate Descent (CD) proposed by Fletcher [18]:

Image158, Image159, Image160

have strong convergence properties, but they may have modest practical performance due to jamming. On the other hand, the methods of Polak – Ribière [27] and Polyak (PRP) [28], of Hestenes and Stiefel (HS) [23] or of Liu and Storey (LS) [25]:

Image161 Image162 Image793

may not always be convergent, but they often have better computational performances.

In this paper we focus on hybrid conjugate gradient methods. These algorithms have been devised to use the attractive features of the above conjugate gradient algorithms. They are defined by (2) and (3) where the parameter Image794 is computed as projections or as convex combinations of different conjugate gradient algorithms, as in Table 1.

Table 1. Hybrid conjugate gradient algorithms.

Nr. Formula Author(s)
1. Image795,
Image180		 Hybrid Dai-Yuan [14] (hDY)
2. Image796 Hybrid Dai-Yuan zero [14] (hDYz)
3. Image797 Gilbert and Nocedal [20] (GN)
4. Image798 Hu and Storey [24] (HuS)
5. Image799 Touati-Ahmed and Storey [31] (TaS)
6. Image800 Hybrid Liu-Storey, Conjugate-Descent (LS-CD)
7. Image155,
Image240,
Image229		 Andrei [6]Newton direction. Secant condition.
8. Image801,
Image240,
Image802		 Andrei [7]Conjugacy condition
9. Image803,
Image240,
Image804		 Andrei [8]Newton direction

The hybrid computational schemes perform better than the classical conjugate gradient algorithms [5]. In [6] we presented another hybrid conjugate gradient algorithm as a convex combination of the Hestenes-Stiefel and the Dai-Yuan algorithms, where the parameter in convex combination is computed in such a way so that the direction corresponding to the conjugate gradient algorithm to be the Newton direction and the pair Image805 to satisfy the secant condition. Numerical experiments with this computational scheme proved to outperform the Hestenes-Stiefel and the Dai-Yuan conjugate gradient algorithms, as well as some other hybrid conjugate gradient algorithms [6]. In this paper, motivated by a result given by Zhang, Deng and Chen [32] and Zhang and Xu [33] concerning a better approximation of Image806 using the modified secant condition, we present another variant of the hybrid conjugate gradient algorithm for unconstrained optimization which performs much better and it is more robust than the variant using the secant condition.

The structure of the paper is as follows. Section 2 introduces our hybrid conjugate gradient algorithm, HYBRIDM as a convex combination of HS and DY algorithms with modified secant condition. Section 3 presents the algorithm and in section 4 its convergence analysis both for uniformly convex functions and general functions is shown. In section 5 some numerical experiments and performance profiles of Dolan-Moré [17] corresponding to this new hybrid conjugate gradient algorithm are given. The performance profiles correspond to a set of 750 unconstrained optimization problems in the CUTE test problem library [10] as well as some other ones presented in [1]. It is shown that this hybrid conjugate gradient algorithm outperforms the classical HS and DY conjugate gradient algorithms and also the hybrid variants hDY and hDYz.

6. Conclusion

A large variety of conjugate gradient algorithms is well known. In this paper we have presented a new hybrid conjugate gradient algorithm in which the parameter Image409 is computed as a convex combination of Image410 and Image807 The parameter in convex combination is computed in such a way so that the direction corresponding to this algorithm to be the Newton direction. Using the modified secant condition we get an algorithm which proved to be more efficient than the algorithm based on secant condition. For uniformly convex function our algorithm is globally convergent. For general nonlinear functions we proved the global convergence of a variant of the algorithm using the strong Wolfe line search.

The performance profile of our algorithm was higher than those of the well established conjugate gradient algorithms HS and DY and also of the hybrid variants hDY and hDYz, for a set of 750 unconstrained optimization problems. Additionally the proposed hybrid conjugate gradient algorithm is more robust than the HS and DY conjugate gradient algorithms.

REFERENCES

  1. ANDREI, N., An unconstrained optimization test functions collection, Advanced Modeling and Optimization, 10 (2008), pp.147-161.
  2. ANDREI, N., Scaled conjugate gradient algorithms for unconstrained optimization, Computational Optimization and Applications, 38 (2007), pp. 401-416.
  3. ANDREI, N., Scaled memoryless BFGS preconditioned conjugate gradient algorithm for unconstrained optimization, Optimization Methods and Software, 22(2007), pp. 561-571.
  4. ANDREI, N., A scaled BFGS preconditioned conjugate gradient algorithm for unconstrained optimization, Applied Mathematics Letters, 20 (2007), pp. 645-650.
  5. ANDREI, N., Numerical comparison of conjugate gradient algorithms for unconstrained optimization, Studies in Informatics and Control, 16 (2007), pp. 333-352.
  6. ANDREI, N., Another hybrid conjugate gradient algorithm for unconstrained optimization, Numerical Algorithms, 47 (2008), pp. 143-156.
  7. ANDREI, N., A hybrid conjugate gradient algorithm for unconstrained optimization. JOTA, Accepted.
  8. ANDREI, N., New hybrid conjugate gradient algorithms as a convex combination of PRP and DY for unconstrained optimization, ICI Technical Report, October 1, 2007.
  9. BIRGIN, E. and J.M. MARTÍNEZ, A spectral conjugate gradient method for unconstrained optimization, Applied Math. and Optimization, 43, 2001, pp. 117-128.
  10. BONGARTZ, I., A.R. CONN, N.I.M. GOULD, and P.L. TOINT, CUTE: constrained and unconstrained testing environments, ACM Trans. Math. Software, 21, 1995, pp. 123-160.
  11. DAI, Y.H., New properties of a nonlinear conjugate gradient method, Numer. Math., 89 (2001), pp. 83-98.
  12. DAI, Y.H. and L.Z. LIAO, New conjugacy conditions and related nonlinear conjugate gradient methods, Appl. Math. Optim., 43 (2001), pp. 87-101.
  13. DAI, Y.H., and Y. YUAN, A nonlinear conjugate gradient method with a strong global convergence property, SIAM J. Optim., 10 (1999), pp. 177-182.
  14. DAI, Y.H., and Y. YUAN, An efficient hybrid conjugate gradient method for unconstrained optimization, Ann. Oper. Res., 103 (2001), pp. 33-47.
  15. DAI, Y.H., J.Y. HAN, G.H. LIU, D.F. SUN, X. YIN, and Y. YUAN, Convergence properties of nonlinear conjugate gradient methods, SIAM Journal on Optimization 10 (1999), pp. 348-358.
  16. DANIEL, J.W., The conjugate gradient method for linear and nonlinear operator equations, SIAM J. Numer. Anal., 4 (1967), pp. 10-26.
  17. DOLAN, E.D., and J.J. MORÉ, Benchmarking optimization software with performance profiles, Math. Programming, 91 (2002), pp. 201-213.
  18. FLETCHER, R., Practical Methods of Optimization, vol. 1: Unconstrained Optimization, John Wiley & Sons, New York, 1987.
  19. FLETCHER, R., and C. REEVES, Function minimization by conjugate gradients, Comput. J., 7 (1964), pp. 149-154.
  20. GILBERT, J.C., and J. NOCEDAL, Global convergence properties of conjugate gradient methods for optimization, SIAM J. Optim., 2 (1992), pp. 21-42.
  21. HAGER, W.W., and H. ZHANG, A new conjugate gradient method with guaranteed descent and an efficient line search, SIAM Journal on Optimization, 16(2005), pp. 170-192.
  22. HAGER, W.W., and H. ZHANG, A survey of nonlinear conjugate gradient methods, Pacific journal of Optimization, 2 (2006), pp. 35-58.
  23. HESTENES, M.R., and E.L. STIEFEL, Methods of conjugate gradients for solving linear systems, J. Research Nat. Bur. Standards, 49 (1952), pp. 409-436.
  24. HU, Y.F. and C. STOREY, Global convergence result for conjugate gradient methods. J. Optim. Theory Appl., 71 (1991), pp. 399-405.
  25. LIU, Y., and C. STOREY, Efficient generalized conjugate gradient algorithms, Part 1: Theory, JOTA, 69 (1991), pp. 129-137.
  26. PERRY, A., A modified conjugate gradient algorithm, Discussion Paper no. 229, Center for Mathematical Studies in Economics and Management Science, Northwestern University, (1976).
  27. POLAK, E., and G. RIBIERE, Note sur la convergence de directions conjuguée, Rev. Francaise Informat Recherche Operationelle, 3e Année 16 (1969), pp. 35-43.
  28. POLYAK, B.T., The conjugate gradient method in extreme problems, USSR Comp. Math. Math. Phys., 9 (1969), pp. 94-112.
  29. POWELL, M.J.D., Nonconvex minimization calculations and the conjugate gradient method, in Numerical Analysis (Dundee, 1983), Lecture Notes in Mathematics, vol. 1066, Springer-Verlag, Berlin, 1984, pp. 122-141.
  30. SHANNO, D.F., and K.H. PHUA, Algorithm 500, Minimization of unconstrained multivariate functions, ACM Trans. on Math. Soft., 2, 1976, pp. 87-94.
  31. TOUATI-AHMED, D., and C. STOREY, Efficient hybrid conjugate gradient techniques, J. Optim. Theory Appl., 64 (1990), pp. 379-397.
  32. ZHANG, J.Z., N.Y. DENG, and L.H. CHEN, New quasi-Newton equation and related methods for unconstrained optimization, J. Optim. Theory Appl., 102(1999), pp. 147-167.
  33. ZHANG, J.Z., C.X. XU, Properties and numerical performance of quasi-Newton methods with modified quasi-Newton equations, Journal of Computational and Applied Mathematics, 137 (2001), pp. 269-278.
  34. YABE, H., and M. TAKANO, Global convergence properties of nonlinear conjugate gradient methods with modified secant condition, Computational Optimization and Applications, 28 (2004), pp. 203-225.
Designed by | ICI Bucharest
© Copyright 2024, All Rights Reserved