Global convergence of the Armijo epsilon steepest descent algorithm
DOI:
https://doi.org/10.33993/jnaat412-978Keywords:
unconstrained optimization, global convergence, steepest descent algorithm, \( \varepsilon\)-algorithm, Armijo inexact line searchAbstract
In this article, we study the unconstrained minimization problem\[(P)\,\,\,\min\left\{ f(x):x\in\mathbb{R}^{n}\right\} .\]where \(f:\mathbb{R}^{n}\rightarrow\mathbb{R}\) is a continuously differentiable function. We introduce a new algorithm which accelerates the convergence of the steepest descent method. We further establish the global convergence of this algorithm in the case of Armijo inexact line search.Downloads
References
A.C. Aitken, On Bernoulli's numerical solution of algebraic equations, Proc. Roy. Soc. Edinburgh, 46 (1926), pp. 289-305, https://doi.org/10.1017/s0370164600022070 DOI: https://doi.org/10.1017/S0370164600022070
N. Andrei, An unconstrained optimization test functions collection, Advanced Modeling and Optimization, 10 (2008), pp. 147-161.
N. Andrei, Another conjugate gradient algorithm for unconstrained optimization, Annals of Academy of Romanian Scientists, Series on Science and Technology of Information, 1 (2008) no. 1, pp. 7-20.
L. Armijo, Minimization of functions having Lipschitz continuous first partial derivatives, Pacific J. Mathematics, 16 (1966) 1, pp. 1-3, http://dx.doi.org/10.2140/pjm.1966.16.1 DOI: https://doi.org/10.2140/pjm.1966.16.1
M.S. Bazaraa, H.D. Sherali and C.M Shetty, Nonlinear Programing, John Wiley & Sons, New York, 1993.
C. Brezinski, Acceleration de la convergence en analyse numérique, Lecture Notes in Mathematics, 584 (1977), Springer Verlag. DOI: https://doi.org/10.1007/BFb0089363
I. Bongartz, 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, https://doi.org/10.1145/200979.201043 DOI: https://doi.org/10.1145/200979.201043
C.G. Broyden, Quasi-Newton Methods and their application to Function Minimization, Mathematics of Coputation, 21 (1967), pp. 368-381, https://doi.org/10.1090/s0025-5718-1967-0224273-2 DOI: https://doi.org/10.1090/S0025-5718-1967-0224273-2
C.G. Broyden, The convergence of a class of double rank minimization algorithms 2. The new algorithm, J. Institute of Mathematics and its applications, 6 (1970), pp. 222-231, https://doi.org/10.1093/imamat/6.3.222 DOI: https://doi.org/10.1093/imamat/6.3.222
C.G. Broyden, J.E. Jr. Dennis and J .J. Moré, On the local and superlinear convergence of quasi-Newton methods, J .Inst. Math. Appl., 12 (1973), pp. 223-246, https://doi.org/10.1093/imamat/12.3.223 DOI: https://doi.org/10.1093/imamat/12.3.223
F. Cordellier, Transformations de suites scalaires et vectorielles, Thèse de doctorat d'état soutenue à l'université de Lille I, 1981.
W.C. Davidon, Variable Metric Method for Minimization, AEC research Development, Report ANL-5990, 1959. DOI: https://doi.org/10.2172/4252678
J.E.Jr. Dennis and J.J. Moré, A characterization of superlinear convergence and its application to quasi-Newton methods, Math. Comp., 28 (1974), pp. 549-560, https://doi.org/10.1090/s0025-5718-1974-0343581-1 DOI: https://doi.org/10.1090/S0025-5718-1974-0343581-1
J.E. Dennis and J.J. Moré, Quasi-Newton methods, motivation and theory, SIAM. Rev., 19 (1977), pp. 46-89, https://doi.org/10.1137/1019005 DOI: https://doi.org/10.1137/1019005
L.C.W. Dixon, Variable metric algorithms: necessary and sufficient conditions for identical behavior on nonquadratic functions, J. Opt. Theory Appl., 10 (1972), pp. 34-40, https://doi.org/10.1007/bf00934961 DOI: https://doi.org/10.1007/BF00934961
N. Djeghaba and R. Benzine, Accélération de la convergence de la méthode de la plus forte pente, Demonstratio Mathematica., 39 (2006) No. 1, pp. 169-181, https://doi.org/10.1515/dema-2006-0121 DOI: https://doi.org/10.1515/dema-2006-0121
R. Fletcher, A new approch to Variable Metric Algorithms, Computer Journal, 13 (1970), pp. 317-322, https://doi.org/10.1093/comjnl/13.3.317 DOI: https://doi.org/10.1093/comjnl/13.3.317
R. Fletcher, Practical methods of Optimization, Second Edition, John Wiley & Sons, Chichester, 1987.
R. Fletcher, An overview of unconstrained optimization, Algorithms for Continuous Optimization: the State of Art, E. Spedicato, ed., Kluwer Academic Publishers, 1994. DOI: https://doi.org/10.1007/978-94-009-0369-2_5
R. Fletcher, and M. Reeves, Function minimization by conjugate gradients, Computer J., 7 (1964), pp. 149-154, https://doi.org/10.1093/comjnl/7.2.149 DOI: https://doi.org/10.1093/comjnl/7.2.149
R. Fletcher, and M.M. Powell, A rapidly Convergent Descent Method for Minimization, Computer Journal, 6 (1963), pp. 163-168, https://doi.org/10.1093/comjnl/6.2.163 DOI: https://doi.org/10.1093/comjnl/6.2.163
G.E. Forsythe, On the asymptotic directions of the s-dimentional optimum gradient method, Numerische Mathematik, 11, 1968, pp. 57-76, https://doi.org/10.1007/bf02165472 DOI: https://doi.org/10.1007/BF02165472
P.E. Gill and W. Marray, Quasi-Newton Methods for unconstrained optimization, J.Inst. Maths applics, 9 (1972), pp. 91-108, https://doi.org/10.1093/imamat/9.1.91 DOI: https://doi.org/10.1093/imamat/9.1.91
A. Griewank, The global convergence of partitioned BFGS on problems with convex decompositions and Lipschitz gradients, Math. Prog., 50 (1991), pp. 141-175, https://doi.org/10.1007/bf01594933 DOI: https://doi.org/10.1007/BF01594933
D. Goldfarb, A Family of Variable Metric Methods Derived by Variational Means, Mathematics of Computation, 24 (1970), pp. 23-26, https://doi.org/10.1090/s0025-5718-1970-0258249-6 DOI: https://doi.org/10.1090/S0025-5718-1970-0258249-6
A.A. Goldstein and J.F. Price, An effective Algorithm for Minimization, Numerische Mathematik, 10 (1967), pp. 184-189, https://doi.org/10.1007/bf02162162 DOI: https://doi.org/10.1007/BF02162162
M.R. Hestenes and E. Stiefel, Methods of conjugate gradients for solving linear systems, J. Res. Nation-Bureau Stand., 49 (1952) No. 6, pp. 409-436, https://doi.org/10.6028/jres.049.044 DOI: https://doi.org/10.6028/jres.049.044
J. Nocedal and S.J. Wright, Numerical Optimization, Springer, Second edition, 2006.
E. Polak and G. Ribiere, Note sur la convergence de méthodes de directions conjuguées, Revue Française Informatique et Recherche opérationnelle, 16 (1969), pp. 35-43, https://doi.org/10.1051/m2an/196903r100351 DOI: https://doi.org/10.1051/m2an/196903R100351
B.T. Polyak, The Method of Conjugate Gradient in Extremum Problems, USSR Computational Mathematics and Mathematical Physics, (English Translation), 9 (1969), pp. 94-112, https://doi.org/10.1016/0041-5553(69)90035-4 DOI: https://doi.org/10.1016/0041-5553(69)90035-4
M.J.D, Powell, On the convergence of the variable metric algorithms, J. Inst. Math. Appl., 7 (1971), pp. 21-36, https://doi.org/10.1093/imamat/7.1.21 DOI: https://doi.org/10.1093/imamat/7.1.21
M.J.D. Powell, Some global convergence properties of variable metric algorithms for minimization without exact line searches, Nonlinear Programming, SIAM-AMS Proceedings, IX (1976), R.W. Cottle and C.E. Lemke eds., SIAM.
D.F. Shanno, Conditionning of quasi-Newton Methods for function minimization, Mathematics of Computation, 24 (1970), pp. 641-656, https://doi.org/10.1090/s0025-5718-1970-0274029-x DOI: https://doi.org/10.1090/S0025-5718-1970-0274029-X
P. Wolfe, Convergence conditions for ascent méthods, Siam Review, 11 (1969), pp. 226-235, https://doi.org/10.1137/1011036 DOI: https://doi.org/10.1137/1011036
P. Wynn, On a device for computing the e_{m}(S_{n}) transformation, M.T.A.C., 10 (1956), pp. 91-96, https://doi.org/10.1090/s0025-5718-1956-0084056-6 DOI: https://doi.org/10.1090/S0025-5718-1956-0084056-6
P. Wynn, Upon systems of recursions which obtain among quotients of the Padé table, Numer. Math., 8 (1966), pp. 264-269, https://doi.org/10.1007/bf02162562 DOI: https://doi.org/10.1007/BF02162562
Published
How to Cite
Issue
Section
License
Copyright (c) 2015 Journal of Numerical Analysis and Approximation Theory
This work is licensed under a Creative Commons Attribution 4.0 International License.
Open Access. This article is distributed under the terms of the Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
