×
Andrei, Neculai

An accelerated conjugate gradient algorithm with guaranteed descent and conjugacy conditions for unconstrained optimization. (English) Zbl 1253.49017

Optim. Methods Softw. 27, No. 4-5, 583-604 (2012).
Summary: In this paper, we suggest a new conjugate gradient algorithm such that for all \(k\geq 0\) both the descent and the conjugacy conditions are guaranteed. The search direction is selected as a linear combination of \(-g_{k+1}\) and \(s_k\), where \(g_{k+1}=\nabla f(x_{k+1})\), \(s_k=x_{k+1}-x_k\) and the coefficients in this linear combination are selected in such a way that both the descent and the conjugacy conditions are satisfied at every iteration. In order to define the algorithm and to prove its convergence, the modified Wolfe line search is introduced, in which the parameter in the standard second Wolfe condition is changed at every iteration. It is shown that for general nonlinear functions, the algorithm with modified Wolfe line search generates directions bounded away from infinity. The algorithm uses an acceleration scheme modifying the step length \(\alpha_k\) in such a manner as to improve the reduction of the function values along the iterations. Numerical comparisons with some conjugate gradient algorithms using a set of 750 unconstrained optimization problems, some of them from the CUTE library, show that the computational scheme outperforms the known conjugate gradient algorithms like Hestenes and Stiefel, Polak et al., Dai and Yuan or hybrid Dai and Yuan, as well as the CG-DESCENT method by Hager and Zhang with the Wolfe line search conditions.

Cited in 1 Document

MSC:

49M20 Numerical methods of relaxation type
65K05 Numerical mathematical programming methods
90C30 Nonlinear programming

Keywords:

conjugate gradient; Wolfe’s line search; descent condition; conjugacy condition; unconstrained optimization

Software:

Algorithm 500; CUTEr; MINPACK-2
PDF BibTeX XML Cite
\textit{N. Andrei}, Optim. Methods Softw. 27, No. 4--5, 583--604 (2012; Zbl 1253.49017)
Full Text: DOI

References:

[1] DOI: 10.1007/s11075-006-9023-9 · Zbl 1101.65058
[2] DOI: 10.1007/s10589-007-9055-7 · Zbl 1168.90608
[3] DOI: 10.1080/10556780600822260 · Zbl 1270.90068
[4] DOI: 10.1016/j.aml.2006.06.015 · Zbl 1116.90114
[5] Andrei N., Stud. Inf. Control 16 pp 333– (2007)
[6] Andrei N., Adv. Model. Optim. 10 pp 147– (2008)
[7] Aris R., The mathematical theory of diffusion and reaction in permeable catalysts (1975) · Zbl 0315.76051
[8] Averick B. M., The MINPACK-2 Test Problem Collection
[9] Bebernes J., Mathematical Problems from Combustion Theory (1989)
[10] DOI: 10.1007/s00245-001-0003-0 · Zbl 0990.90134
[11] DOI: 10.1145/200979.201043 · Zbl 0886.65058
[12] Boyd S., Convex Optimization (2004)
[13] DOI: 10.1007/BF01441967 · Zbl 0404.76036
[14] DOI: 10.1007/PL00005464 · Zbl 1006.65063
[15] DOI: 10.1007/s002450010019 · Zbl 0973.65050
[16] DOI: 10.1023/A:1012930416777 · Zbl 1007.90065
[17] DOI: 10.1137/S1052623497318992 · Zbl 0957.65061
[18] DOI: 10.1007/s101070100263 · Zbl 1049.90004
[19] Fletcher R., Practical Optimization: Vol. 1: Unconstrained Optimization (1980)
[20] DOI: 10.1093/comjnl/7.2.149 · Zbl 0132.11701
[21] Glowinski R., Numerical Methods for Nonlinear Variational Problems (1984) · Zbl 0536.65054
[22] DOI: 10.1016/0045-7825(86)90073-3 · Zbl 0591.73119
[23] DOI: 10.1137/030601880 · Zbl 1093.90085
[24] Hager W. W., Pacific J. Optim. 2 pp 35– (2006)
[25] Hestenes M. R., J. Res. Nat. Bur. Stand. 49 pp 409– (1952) · Zbl 0048.09901
[26] DOI: 10.1016/j.cam.2006.03.005 · Zbl 1116.65069
[27] DOI: 10.1007/BF01589116 · Zbl 0696.90048
[28] Nitsche J. C.C., Lectures on Minimal Surfaces 1 (1989) · Zbl 0688.53001
[29] Nocedal J., Linear and Nonlinear Conjugate Gradient Related Methods pp 9– (1996) · Zbl 0866.65037
[30] DOI: 10.1287/opre.26.6.1073 · Zbl 0419.90074
[31] Polak E., Computational methods in optimization: A unified approach (1971) · Zbl 0301.90040
[32] Polak E., Rev. Fr. Inform. Rech. Oper. 3e Année 16 pp 35– (1969)
[33] DOI: 10.1016/0041-5553(69)90035-4 · Zbl 0229.49023
[34] DOI: 10.1007/BF01580369 · Zbl 0356.65056
[35] DOI: 10.1007/BFb0099521
[36] DOI: 10.1287/moor.3.3.244 · Zbl 0399.90077
[37] DOI: 10.1145/355666.355673 · Zbl 0319.65042
[38] Yuan Y., Analysis on the conjugate gradient method (1990)
[39] DOI: 10.1002/zamm.19950750118 · Zbl 0823.65061
[40] DOI: 10.1137/1011036 · Zbl 0177.20603
[41] DOI: 10.1137/1013035 · Zbl 0216.26901
[42] Zoutendijk G., Integer and Nonlinear Programming pp 37– (1970) · Zbl 0228.90034
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.