Two modified Dai-Yuan nonlinear conjugate gradient methods. (English) Zbl 1173.65046

Zhang, Li

Numer. Algorithms 50, No. 1, 1-16 (2009).

The author improves the iterative method
\[ x_{k+1}=x_k+\alpha_k d_k;\;d_0=-g_k,\;d_k=-g_k+\beta_k d_{k-1},\;k>0;\;g(x)=f^{\prime}(x),\;g_k=g(x_k) \]
for solving smooth unconstrained optimization problems \(\min_{x \in\mathbb R^n} f(x)\). In the original version of the method,
\[ \beta_k=\| g_k \|^2/d^T_{k-1}y_{k-1},\;y_{k-1}=g_k-g_{k-1}, \]
and the stepsize \(\alpha_k>0\) satisfies
\[ f(x_k+\alpha_k d_k) \leq f(x_k)+\delta \alpha_k g_k^T d_k,\;d^T_k g(x_k+\alpha_k d_k) \geq \sigma d^T_k g_k, \]
where \(0<\delta<\sigma<1\). The modified method converges globally for nonconvex functions such that the level set \(\Omega=\{ x\in \mathbb R^n: f(x) \leq f(x_0) \}\) is bounded and \(\| g(x)-g(y)\| \leq L\| x-y \|\) for all \(x,y\) from a neighborhood of \(\Omega\).

Reviewer: Mikhail Yu. Kokurin (Yoshkar-Ola)

MSC:

65K05	Numerical mathematical programming methods
90C30	Nonlinear programming

Keywords:

nonlinear conjugate gradient method; global convergence

Software:

CUTEr; CUTE

References:

[1]	Andrei, N.: A Dai-Yuan conjugate gradient algorithm with sufficient descent and conjugacy conditions for unconstrained optimization. Appl. Math. Lett. 21, 165–171 (2008) · Zbl 1165.90683
[2]	Bongartz, K.E., 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
[3]	Byrd, R., Nocedal, J.: A tool for analysis of quasi-Newton methods with application to unconstrained minimization. SIAM J. Numer. Anal. 26, 727–739 (1989) · Zbl 0676.65061
[4]	Dai, Y.H.: New properties of a nonlinear conjugate gradient method. Numer. Math. 89, 83–98 (2001) · Zbl 1006.65063
[5]	Dai, Y.H.: A nonmonotone conjugate gradient algorithm for unconstrained optimization. J. Syst. Sci. Complex. 15, 139–145 (2002) · Zbl 1019.90039
[6]	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
[7]	Dai, Y.H., Yuan, Y.: An efficient hybrid conjugate gradient method for unconstrained optimization. Ann. Oper. Res. 103, 33–47 (2001) · Zbl 1007.90065
[8]	Dai, Y.H., Yuan, Y.: Nonlinear Conjugate Gradient Methods. Shanghai Science and Technology, Shanghai (2000)
[9]	Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201–213 (2002) · Zbl 1049.90004
[10]	Fletcher, R., Reeves, C.: Function minimization by conjugate gradients. Comput. J. 7, 149–154 (1964) · Zbl 0132.11701
[11]	Gilbert, J.C., Nocedal, J.: Global convergence properties of conjugate gradient methods for optimization. SIAM. J. Optim. 2, 21–42 (1992) · Zbl 0767.90082
[12]	Hager, W.W., Zhang, H.: A new conjugate gradient method with guaranteed descent and an efficient line search. SIAM J. Optim. 16, 170–192 (2005) · Zbl 1093.90085
[13]	Hager, W.W., Zhang, H.: A survey of nonlinear conjugate gradient methods. Pac. J. Optim. 2, 35–58 (2006) · Zbl 1117.90048
[14]	Hestenes, M.R., Stiefel, E.L.: Methods of conjugate gradients for solving linear systems. J. Res. Natl. Bur. Stand. B 49, 409–432 (1952) · Zbl 0048.09901
[15]	Li, D.H., Fukushima, M.: A modified BFGS method and its global convergence in nonconvex minimization. J. Comput. Appl. Math. 129, 15–35 (2001) · Zbl 0984.65055
[16]	Moré, J.J., Thuente, D.J.: Line search algorithms with guaranted sufficient decrease. ACM Trans. Math. Softw. 20, 286–307 (1994) · Zbl 0888.65072
[17]	Polak, B., Ribiere, G.: Note surla convergence des méthodes de directions conjuguées. Rev. Francaise Imformat Recherche Opertionelle 16, 35–43 (1969)
[18]	Polyak, B.T.: The conjugate gradient method in extreme problems. USSR Comp. Math. Math. Phys. 9, 94–112 (1969) · Zbl 0229.49023
[19]	Wei, Z., Yao, S., Liu, L.: The convergence properties of some new conjugate gradient methods. Appl. Math. Comput. 183, 1341–1350 (2006) · Zbl 1116.65073
[20]	Zhang, L., Zhou, W., Li, D.: Global convergence of the DY conjugate gradient method with Armijo line search for unconstrained optimization problems. Optim. Methods Softw. 22, 511–517 (2007) · Zbl 1133.65035
[21]	Zhang, L., Zhou, W., Li, D.: A descent modified Polak-Ribière-Polyak conjugate gradient method and its global convergence. IMA J. Numer. Anal. 26, 629–640 (2006) · Zbl 1106.65056
[22]	Zhang, L., Zhou, W., Li, D.: Global convergence of a modified Fletcher-Reeves conjugate gradient method with Armijo-type line search. Numer. Math. 104, 561–572 (2006) · Zbl 1103.65074
[23]	Zhang, L., Zhou, W., Li, D.: Some descent three-term conjugate gradient methods and their global convergence. Optim. Methods Softw. 22, 697–711 (2007) · Zbl 1220.90094