×

zbMATH — the first resource for mathematics

On per-iteration complexity of high order Chebyshev methods for sparse functions with banded Hessians. (English) Zbl 1298.49050
Authors’ abstract: Some algorithms for unconstrained and differentiable optimization problems involve the evaluation of quantities related to high order derivatives. The cost of these evaluations depends widely on the technique used to obtain the derivatives and on some characteristics of the objective function: its size, structure and complexity. Functions with banded Hessian are a special case that we study in this paper. Because of their partial separability, the cost of obtaining their high order derivatives, subtly computed by the technique of automatic differentiation, makes high order Chebyshev methods more interesting for banded systems than for dense functions. These methods have an attractive efficiency as we can improve their convergence order without increasing significantly their algorithmic costs. This paper provides an analysis of the per-iteration complexities of high order Chebyshev methods applied to sparse functions with banded Hessians. The main result can be summarized as: the per-iteration complexity of a high order Chebyshev method is of order of the objective function’s. This theoretical analysis is verified by numerical illustrations.
MSC:
49M37 Numerical methods based on nonlinear programming
90C30 Nonlinear programming
90C60 Abstract computational complexity for mathematical programming problems
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Kchouk, B; Dussault, J-P, A new family of high order directions for unconstrained optimization inspired by Chebyshev and Shamanskii methods, Optim. Methods Softw., (2012) · Zbl 1282.90178
[2] Yamamoto, T, Historical developments in convergence analysis for Newton and Newton-like methods, J. Comput. Appl. Math., 124, 1-23, (2000) · Zbl 0965.65079
[3] Chebyshev, P.L.: Collected Works, vol. 5. Moscou-Leningrad (1951) · Zbl 0054.00304
[4] Zhang, H, On the Halley class of methods for unconstrained optimization problems, Optim. Methods Softw., 25, 753-762, (2009) · Zbl 1203.90154
[5] Dussault, J-P, High-order Newton-penalty algorithms, J. Comput. Appl. Math., 182, 117-133, (2005) · Zbl 1077.65061
[6] Dussault, J-P; Hamelin, B; Kchouk, B, Implementation issues for high order algorithms, Acta Math. Vietnamica, 34, 91-103, (2009) · Zbl 1182.65215
[7] Zhang, H., Xue, Y.: Computing the high order derivatives with automatic differentiation and its appli cation in Chebyshevs method. In: Proceeding of the Fourth International Conference on Natural Computation, vol. 1, pp. 304308 (2008) · Zbl 0215.27404
[8] Gutiérrez, JM; Hernández, MA, An acceleration of newton’s method: super-Halley method, Appl. Math. Comput., 117, 223-239, (2001) · Zbl 1023.65051
[9] Baur, W; Strassen, V, The complexity of partial derivatives, Theor. Comput. Sci., 22, 317-330, (1983) · Zbl 0498.68028
[10] Griewank, A., Walther, A.: Evaluating Derivatives, Principles and Techniques of Algorithmic Differentiation. Siam, Philadelphia (2008) · Zbl 1159.65026
[11] Coleman, TF; Moré, JJ, Estimation of sparse Hessian matrices and graph coloring problems, Math. Program., 28, 243-270, (1984) · Zbl 0572.65029
[12] Curtis, AR; Powell, MJD; Reid, JK, On the estimation of sparse Jacobian matrices, J. Inst. Math. Applic., 13, 117-119, (1974) · Zbl 0273.65036
[13] Powell, MJD; Toint, PhL, On the estimation of sparse Hessian matrices, SIAM J. Numer. Anal., 16, 1060-1074, (1979) · Zbl 0426.65025
[14] Griewank, A.: Complexity in Numerical Optimization.World Scientific Publishing Co. (1993) · Zbl 0968.90524
[15] Bischof, CH; Khademi, PM; Bouaricha, A; Carle, A, Efficient computation of gradients and Jacobians by dynamic exploitation of sparsity in automatic differentiation, Optim. Methods Softw., 7, 1-39, (1997) · Zbl 0879.68025
[16] Bischof, CH; Bouaricha, A; Khademi, K; Moré, JJ, Computing gradients in large-scale optimization using automatic differentiation, Informs J. Comput., 9, 185-194, (1997) · Zbl 0885.90100
[17] Moré, JJ, Automatic differentiation tools in optimization software. technical report ANL/MCS-P859-1100, argonne national laboratory, (2000), Illinois
[18] Walther, A, Computing sparse hessians with automatic differentiation, ACM Trans. Math. Softw., 35, 1-15, (2008) · Zbl 1291.65190
[19] Gebremedhin, AH; Tarafdar, A; Pothen, A; Walther, A, Efficient computation of sparse hessians using coloring and automatic differentiation, INFORMS J. Comput., 21, 209-223, (2009) · Zbl 1243.65071
[20] Gower, R., Mello, M.P.: Hessian matrix via automatic differentiation. Technical Report, Institute of MathematicsStatistics and Scientific Computing State University of Campinas-Unicamp. Sao Paulo (2010) · Zbl 1161.90486
[21] Griewank, A., Toint, Ph.L.: Nonlinear Optimization 1981. On the Unconstrained Optimization of Partially Separable Objective Functions. Academic, London (1982) · Zbl 0563.90085
[22] Vanderbil, R; Barel, M; Golub, G; Mastronardi, N, A bibliography on semiseparable matrices, CALCOLO, 42, 249-270, (2005) · Zbl 1168.15306
[23] Bouaricha, A; Moré, JJ, Impact of partial separability on large-scale optimization, Comp. Optim. Appl., 7, 27-40, (1997) · Zbl 0883.90107
[24] Conn, A.R., Gould, N.IM., Toint, Ph.L.: Computing methods in applied sciences and engineering. An Introduction to the Structure of Large Scale Nonlinear Optimization Problems and the LANCELOT Project. SIAM Publications (1990) · Zbl 0883.90107
[25] Nocedal, J.: Large scale unconstrained optimization.In: The State of the Art in Numerical Analysis, pp 311-338. Oxford University Press (1996) · Zbl 1168.15312
[26] Andrei, N, An unconstrained optimization test functions collection, Adv. Model. Optim., 10, 147-161, (2008) · Zbl 1161.90486
[27] Moré, JJ; Garbow, BS; Hillstrom, KE, Testing unconstrained optimization software, ACM Trans. Math. Softw., 7, 17-41, (1981) · Zbl 0454.65049
[28] Bongartz, I; Conn, AR; Gould, NIM; Toint, PhL, CUTE: constrained and unconstrained testing environments, ACM TOMS, 21, 123-160, (1995) · Zbl 0886.65058
[29] Asplund, E, Inverses of matrices \({a_{ij}}\) which satisfy \({{a_{ij}}}=0\) for \({j > i+p}\), Math. Scand., 7, 57-60, (1959) · Zbl 0093.24102
[30] Rozsa, P, On the inverse of band matrices, Integr. Equ. Oper. Theory, 10, 83-95, (1987) · Zbl 0628.65019
[31] Fox, L.: An Introduction to Numerical Linear Algebra, p 328. Clarendon Press, Oxford (1964) · Zbl 0122.35701
[32] Arbenz, P., Gander, W.: A survey of direct parallel algorithms for banded linear systems. Technical Report 221ETH Zürich, Department Informatik, Zürich (1994) · Zbl 0900.65070
[33] Gundersen, G; Steihaug, T, On large scale unconstrained optimization problems and higher order methods, Optim. Methods Softw., 25, 337-358, (2010) · Zbl 1202.65074
[34] Martin, RS; Wilkinson, JH, Symmetric decomposition of positive definite band matrices, Numer. Math., 7, 355-361, (1965) · Zbl 0137.32806
[35] Gill, P.E., Murray, W.: Recent mathematical developments in control. The Numerical Solution of a Problem in the Calculus of Variations. Academic London and NewYork (1973) · Zbl 0289.49026
[36] Golub, G.H., Van Loan, C.F.: Matrix Computations, 3rd edn. The Johns Hopkins University Press, Baltimore (1996) · Zbl 0865.65009
[37] Demmel, J.: On floating point errors in Cholesky. Technical Report, Courant Institute, New York (1989) · Zbl 0498.68028
[38] Remón, A; Quintana-Ortí, ES; Quintana-Ortí, G, Cholesky factorization of band matrices using multithreaded BLAS., 608-616, (2007), Berlin
[39] Anderson, E., Bai, Z., Bischof, C., Blackford, S., Demmel, J., Dongarra, J., Du Croz, J., Greenbaum, A., Hammarling, S., McKenney, A., Sorensen, D.: Lapack users guide. Software, Environments and Tools. SIAM, Philadelphia (1999) · Zbl 0934.65030
[40] The Numerical Algorithm Group Ltd: NAG Library Manual Mark 22. NAG, Oxford. Available Online www.nag.co.uk (2009) · Zbl 0965.65079
[41] Gundersen, G; Steihaug, T, Sparsity in higher order methods for uncontrained optimization, Optim. Methods Softw., 27, 275-294, (2011) · Zbl 1244.90220
[42] Kchouk, B., Dussault, J.-P.: The Chebyshev-Shamanskii method for solving systems of nonlinear equations. J. Optim. Theory Appl. 156(3) (2013). doi:10.1007/s10957-012-0159-6 · Zbl 1266.90174
[43] Griewank, A.: Complexity in nonlinear optimization. Some Bounds on the Complexity of Gradients, Jacobians and Hessians. P. Pardalos (1993) · Zbl 0968.90524
[44] Griewank, A.: On automatic differentiation. In: Mathematical Programming: Recent Developments and Applications, pp. 83108. Kluwer Academic Publishers (1989) · Zbl 0696.65015
[45] Intel: The intel\({® }\) 64 and ia-32 architectures optimization reference manual. June 2011. online edition www.intel.com · Zbl 1282.90178
[46] Hascoet, L., Pascual, V.: Tapenade 2.1 Users Guide. Technical Report 300. INRIA, Sophia Antipolis France · Zbl 1156.68634
[47] Kantorovich, L.V.: Functional Analysis and Applied Mathematics. National Bureau of Standards, Gaithersburg (1952)
[48] Tapia, RA, The Kantorovich theorem for newton’s method, Am. Math. Mon., 78, 389-392, (1971) · Zbl 0215.27404
[49] Cotte, R.: L’enjeu de la differentiation automatique dans les methodes de Newton d’ordres superieurs. Master’s thesis, University of Sherbrooke (2010)
[50] Ostrowski, A.M.: Solutions of Equations in Euclidean and Banach Spaces. Academic, New York (1973) · Zbl 0304.65002
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.