×

An acceleration of gradient descent algorithm with backtracking for unconstrained optimization. (English) Zbl 1101.65058

The author considers the unconstrained optimization problem where the objective function is convex and continuously differentiable. He focuses on the gradient descent algorithm with backtracking, and describes an improved version which accelerates convergence. In particular, the acceleration is based on a modification of the steplength by multiplying it with a positive parameter. The resulting algorithm is proven to be linearly convergent, and numerical experimentation in section 4 shows a significant improvement in performance.

MSC:

65K05 Numerical mathematical programming methods
90C25 Convex programming

Software:

CUTEr; CUTE
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Armijo, L.: Minimization of functions having Lipschitz continuous first partial derivatives. Pac. J. Math. 6, 1–3 (1966) · Zbl 0202.46105
[2] 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 · doi:10.1145/200979.201043
[3] Cauchy, A.: Méthodes générales pour la résolution des systémes déquations simultanées. C. R. Acad. Sci., Paris 25, 536–538 (1848)
[4] Dennis, J.E., Schnabel, R.B.: Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Prentice-Hall, Englewoods Cliffs, New Jersey (1983) · Zbl 0579.65058
[5] Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201–213 (2002) · Zbl 1049.90004 · doi:10.1007/s101070100263
[6] Fletcher, R.: Practical Methods of Optimization. Wiley, New York (1987) · Zbl 0905.65002
[7] Forsythe, G.E., Motzkin, T.S.: Asymptotic properties of the optimum gradient method. Bull. Am. Soc. 57, 183 (1951)
[8] Goldstein, A.A.: On steepest descent. SIAM J. Control 3, 147–151 (1965) · Zbl 0221.65094
[9] Humphrey, W.E.: A general minimising routine – minfun. In: Lavi, A., Vogl, T.P. (eds.) Recent Advances in Optimisation Techniques. Wiley, New York (1966)
[10] Lemaréchal, C.: A view of line search. In: Auslander, A., Oettli, W., Stoer, J. (eds.) Optimization and Optimal Control, pp. 59–78. Springer, Berlin (1981)
[11] Moré, J.J., Thuente, D.J.: On line search algorithms with guaranteed sufficient decrease. Mathematics and Computer Science Division Preprint MCS-P153-0590, Argonne National Laboratory, Argonne (1990)
[12] Potra, F.A., Shi, Y.: Efficient line search algorithm for unconstrained optimization. J. Optim. Theory Appl. 85, 677–704 (1995) · Zbl 0831.90106 · doi:10.1007/BF02193062
[13] Powell, M.J.D.: Some global convergence properties of a variable-metric algorithm for minimization without exact line searches. SIAM-AMS Proc., Philadelphia 9, 53–72 (1976) · Zbl 0338.65038
[14] Schinzinger, R.: Optimization in electromagnetic system design. In: Lavi, A., Vogl, T.P. (Eds.) Recent Advances in Optimisation Techniques. Wiley, New York (1966)
[15] Zhen-Jun, S.: Convergence of line search methods for unconstrained optimization. Appl. Math. Comput. 157, 393–405 (2004) · Zbl 1072.65087 · doi:10.1016/j.amc.2003.08.058
[16] Wolfe, P.: Convergence conditions for ascent methods. SIAM Rev. 11, 226–235 (1968) · Zbl 0177.20603 · doi:10.1137/1011036
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.