Two-step conjugate gradient method for unconstrained optimization. (English) Zbl 1463.49049
Summary: Using Taylor’s series, we propose a modified secant relation to get a more accurate approximation of the second curvature of the objective function. Then, using this relation and an approach introduced by Y. H. Dai and L. Z. Liao [Appl. Math. Optim. 43, No. 1, 87–101 (2001; Zbl 0973.65050)], we present a conjugate gradient algorithm to solve unconstrained optimization problems. The proposed method makes use of both gradient and function values, and utilizes information from the two most recent steps, while the usual secant relation uses only the latest step information. Under appropriate conditions, we show that the proposed method is globally convergent without needing convexity assumption on the objective function. Comparative results show computational efficiency of the proposed method in the sense of the Dolan-Moré performance profiles.
MSC:
| 49M37 | Numerical methods based on nonlinear programming |
| 65K10 | Numerical optimization and variational techniques |
| 90C30 | Nonlinear programming |
Keywords:
unconstrained optimization; two-step secant relation; conjugate gradients; global convergenceCitations:
Zbl 0973.65050Software:
CUTEstReferences:
| [1] | Al-Baali, M., Descent property and global convergence of the Fletcher- Reeves method with inexact linesearch, IMA J. Numer. Anal., 5, 121-124 (1985) · Zbl 0578.65063 · doi:10.1093/imanum/5.1.121 |
| [2] | Babaie-Kafaki, S.; Ghanbari, R., The Dai-Liao nonlinear conjugate gradient method with optimal parameter choices, Eur. J. Oper. Res., 234, 625-630 (2014) · Zbl 1304.90216 · doi:10.1016/j.ejor.2013.11.012 |
| [3] | Babaie-Kafaki, S.; Ghanbari, R.; Mahdavi-Amiri, N., Two new conjugate gradient methods based on modified secant relations, J. Comput. Appl. Math., 234, 1374-1386 (2010) · Zbl 1202.65071 · doi:10.1016/j.cam.2010.01.052 |
| [4] | Dai, YH; Han, JY; Liu, GH; Sun, DF; Yin, HX; Yuan, YX, Convergence properties of nonlinear conjugate gradient methods, SIAM J. Optim., 10, 348-358 (1999) · Zbl 0957.65061 · doi:10.1137/S1052623497318992 |
| [5] | Dai, YH; Liao, LZ, New conjugacy conditions and related nonlinear conjugate gradient methods, Appl. Math. Optim., 43, 87-101 (2001) · Zbl 0973.65050 · doi:10.1007/s002450010019 |
| [6] | Dolan, ED; Moré, JJ, Benchmarking optimization software with performance profiles, Math. Program., 91, 201-213 (2002) · Zbl 1049.90004 · doi:10.1007/s101070100263 |
| [7] | Fletcher, R.; Revees, CM, Function minimization by conjugate gradients, Comput. J., 7, 149-154 (1964) · Zbl 0132.11701 · doi:10.1093/comjnl/7.2.149 |
| [8] | Ford, JA; Moghrabi, IA, Alternating multi-step quasi-Newton methods for unconstrained optimization, J. Comput. Appl. Math., 82, 105-116 (1997) · Zbl 0886.65064 · doi:10.1016/S0377-0427(97)00075-7 |
| [9] | Ford, JA; Moghrabi, IA, Alternative parameter choices for multi-step quasi-Newton methods, Optim. Methods Softw., 2, 357-370 (1993) · doi:10.1080/10556789308805550 |
| [10] | Ford, JA; Moghrabi, IA, Multi-step quasi-Newton methods for optimization, J. Comput. Appl. Math., 50, 305-323 (1994) · Zbl 0807.65062 · doi:10.1016/0377-0427(94)90309-3 |
| [11] | Ford, JA; Narushima, Y.; Yabe, H., Multi-step nonlinear conjugate gradient methods for unconstrained minimization, Comput. Opt. Appl., 40, 191-216 (2008) · Zbl 1181.90221 · doi:10.1007/s10589-007-9087-z |
| [12] | Gould, NI; Orban, D.; Toint, PhL, CUTEst: a constrained and unconstrained testing environment with safe threads for mathematical optimization, Comput. Opt. Appl., 60, 545-557 (2015) · Zbl 1325.90004 · doi:10.1007/s10589-014-9687-3 |
| [13] | Hestenes, MR; Stiefel, EL, Methods of conjugate gradients for solving linear systems, J. Res. Nat. Bur. Stand., 49, 409-436 (1952) · Zbl 0048.09901 · doi:10.6028/jres.049.044 |
| [14] | Li, G.; Tang, C.; Wei, Z., New conjugacy condition and related new conjugate gradient methods for unconstrained optimization, J. Comput. Appl. Math., 202, 523-539 (2007) · Zbl 1116.65069 · doi:10.1016/j.cam.2006.03.005 |
| [15] | Moré, JJ; Thuente, DJ, Line search algorithms with guaranteed sufficient decrease, ACM Trans. Math. Softw., 20, 286-307 (1994) · Zbl 0888.65072 · doi:10.1145/192115.192132 |
| [16] | Moghrabi, IA, A new preconditioned conjugate gradient method for optimization, IAENG Int. J. Appl. Math., 49, 1, 1-8 (2019) · Zbl 1512.90244 |
| [17] | Nocedal, J.; Wright, SJ, Numerical Optimization (2006), New York: Springer, New York · Zbl 1104.65059 |
| [18] | Polak, E.; Ribiére, G., Note Sur la Convergence de Directions Conjuguée, Francaise Informat Recherche Operationelle, 16, 35-43 (1969) · Zbl 0174.48001 |
| [19] | Polyak, BT, The conjugate gradient method in extreme problems, USSR Comput. Math. Math. Phys., 9, 94-112 (1969) · Zbl 0229.49023 · doi:10.1016/0041-5553(69)90035-4 |
| [20] | Powell, MJD, Restart procedures of the conjugate gradient method, Math. Program., 2, 241-254 (1977) · Zbl 0396.90072 · doi:10.1007/BF01593790 |
| [21] | Powell, MJD, Nonconvex minimization calculations and the conjugate gradient method, Numerical Analysis (Dundee, 1983) Lecture Notes in Mathematics, 122-141 (1984), Berlin: Springer, Berlin · Zbl 0531.65035 |
| [22] | Wei, Z.; Li, G.; Qi, L., New quasi-Newton methods for unconstrained optimization problems, Appl. Math. Comput., 175, 1156-1188 (2006) · Zbl 1100.65054 |
| [23] | Yuan, G.; Wei, Z., Convergence analysis of a modified BFGS method on convex minimizations, Comput. Opt. Appl., 47, 237-255 (2010) · Zbl 1228.90077 · doi:10.1007/s10589-008-9219-0 |
| [24] | Yabe, H.; Takano, M., Global convergence properties of nonlinear conjugate gradient methods with modified secant relation, Comput. Optim. Appl., 28, 203-225 (2004) · Zbl 1056.90130 · doi:10.1023/B:COAP.0000026885.81997.88 |
| [25] | Zhang, JZ; Xu, CX, Properties and numerical performance of quasi-Newton methods with modified quasi-Newton equation, J. Comput. Appl. Math., 137, 269-278 (2001) · Zbl 1001.65065 · doi:10.1016/S0377-0427(00)00713-5 |
| [26] | Zoutendijk, G.; Abadie, J., Nonlinear programming, computational methods, Integer and nonlinear programming, 37-86 (1970), Amsterdam: North-holland, Amsterdam · Zbl 0336.90057 |
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.
