×

zbMATH — the first resource for mathematics

Higher-order reverse automatic differentiation with emphasis on the third-order. (English) Zbl 1332.65034
Summary: It is commonly assumed that calculating third order information is too expensive for most applications. But we show that the directional derivative of the Hessian (\(D^3 f(x)\cdot d\)) can be calculated at a cost proportional to that of a state-of-the-art method for calculating the Hessian matrix. We do this by first presenting a simple procedure for designing high order reverse methods and applying it to deduce several methods including a reverse method that calculates \(D^3f(x)\cdot d\). We have implemented this method taking into account symmetry and sparsity, and successfully calculated this derivative for functions with a million variables. These results indicate that the use of third order information in a general nonlinear solver, such as Halley-Chebyshev methods, could be a practical alternative to Newton’s method. Furthermore, high-order sensitivity information is used in methods for robust aerodynamic design. An efficient high-order differentiation tool could facilitate the use of similar methods in the design of other mechanical structures.

MSC:
65D25 Numerical differentiation
15A69 Multilinear algebra, tensor calculus
65F50 Computational methods for sparse matrices
49Q12 Sensitivity analysis for optimization problems on manifolds
Software:
ADOL-C; ColPack; CUTE; CUTEr; dcc
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Griewank, A., Walther, A.: Evaluating derivatives, 2nd edn. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (2008) · Zbl 1159.65026
[2] Gebremedhin, AH; Manne, F; Pothen, A, What color is your Jacobian? graph coloring for computing derivatives, SIAM Rev., 47, 629-705, (2005) · Zbl 1076.05034
[3] Griewank, A; Naumann, U, Accumulating Jacobians as chained sparse matrix products, Math. Progr., 95, 555-571, (2003) · Zbl 1023.90053
[4] Gower, RM; Mello, MP, A new framework for the computation of hessians, Optim. Methods Softw., 27, 251-273, (2012) · Zbl 1311.65084
[5] 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
[6] Gutiérrez, JM; Hernández, MA, A family of Chebyshev-Halley type methods in Banach spaces, Bull. Aust. Math. Soc., 55, 113-130, (1997) · Zbl 0893.47043
[7] Amat, S; Busquier, S, Third-order iterative methods under Kantorovich conditions, J. Math. Anal. Appl., 336, 243-261, (2007) · Zbl 1128.65036
[8] Wang, X., Kou, J.: Semilocal convergence and R-order for modified Chebyshev-Halley methods. J. Numer. Algorithms 64(1),105-126 (2013) · Zbl 1279.65065
[9] Ezquerro, JA; Hern, MA, New Kantorovich-type conditions for halley’s method, Appl. Numer. Anal. Comput. Math., 77, 70-77, (2005) · Zbl 1076.65052
[10] Xu, X; Ling, Y, Semilocal convergence for halley’s method under weak Lipschitz condition, Appl. Math. Comput., 215, 3057-3067, (2009) · Zbl 1187.65059
[11] Susanto, H; Karjanto, N, Newtons methods basins of attraction revisited, Appl. Math. Comput., 215, 1084-1090, (2009) · Zbl 1175.65055
[12] Yau, L; Ben-Israel, A, The Newton and Halley methods for complex roots, Am. Math. Mon., 105, 806-818, (1998) · Zbl 1002.65059
[13] Gundersen, G; Steihaug, T, Sparsity in higher order methods for unconstrained optimization, Optim. Methods Softw., 27, 275-294, (2012) · Zbl 1244.90220
[14] Gundersen, G; Steihaug, T, On diagonally structured problems in unconstrained optimization using an inexact super Halley method, J. Comput. Appl. Math., 236, 3685-3695, (2012) · Zbl 1256.65055
[15] Gundersen, G; Steihaug, T, On large-scale unconstrained optimization problems and higher order methods, Optim. Methods Softw., 25, 337-358, (2010) · Zbl 1202.65074
[16] Papadimitriou, DI; Giannakoglou, KC, Robust design in aerodynamics using third-order sensitivity analysis based on discrete adjoint. application to quasi-1D flows, Int. J. Numer. Methods Fluids, 69, 691-709, (2012)
[17] Papdimitriou, DI; Giannakoglou, KC, Third-order sensitivity analysis for robust aerodynamic design using continuous adjoint, Int. J. Numer. Methods Fluids, 71, 652-670, (2013)
[18] Ozaki, I; Kimura, F; Berz, M, Higher-order sensitivity analysis of finite element method by automatic differentiation, Comput. Mech., 16, 223-234, (1995) · Zbl 0845.73071
[19] Ederington, LH; Guan, W, Higher order greeks, J. Deriv., 14, 7-34, (2007)
[20] Kariwala, V, Automatic differentiation-based quadrature method of moments for solving population balance equations, AIChE J., 58, 842-854, (2012)
[21] Corliss, G.F.F., Griewank, A., Henneberger, P.: High-order stiff ODE solvers via automatic differentiation and rational prediction. In: Vulkov, L., Waśniewski, J., Yalamov, P. (eds.) Lecture notes in computer science, pp. 114-125. Springer, Berlin, Heidelberg (1997) · Zbl 1187.65059
[22] Guckenheimer, J; Meloon, B, Computing periodic orbits and their bifurcations with automatic differentiation, SIAM J. Sci. Comput., 22, 951-985, (2000) · Zbl 0976.65111
[23] Griewank, A; Walther, A; Utke, J, Evaluating higher derivative tensors by forward propagation of univariate Taylor series, Math. Comput., 69, 1117-1130, (2000) · Zbl 0952.65028
[24] Naumann, U.: The art of differentiating computer programs: An introduction to algorithmic differentiation. Number 24 in Software, Environments, and Tools. SIAM, Philadelphia (2012) · Zbl 1275.65015
[25] Neidinger, RD, An efficient method for the numerical evaluation of partial derivatives of arbitrary order, ACM Trans. Math. Softw., 18, 159-173, (1992) · Zbl 0892.65011
[26] Fraenkel, LE, Formulae for high derivatives of composite functions, Math. Proc. Camb. Philos. Soc., 83, 159, (1978) · Zbl 0388.46032
[27] Griewank, A; Juedes, D; Utke, J, ADOL-C, a package for the automatic differentiation of algorithms written in C/C++, ACM Trans. Math. Softw., 22, 131-167, (1996) · Zbl 0884.65015
[28] Bongartz, I., Conn, A.R., Gould, N., Toint, P.L.: CUTE: constrained and unconstrained testing environment. ACM Trans. Math. Softw. 21(1), 123-160 (1995) · Zbl 0886.65058
[29] Hock, W; Schittkowski, K, Test examples for nonlinear programming codes, J. Optim. Theory Appl., 30, 127-129, (1980) · Zbl 0393.90072
[30] Luksan, L., Vlcek, J.: Test problems for unconstrained optimization. Technical Report 897, Academy of Sciences of the Czech Republic (2003) · Zbl 1108.90029
[31] Abate, J., Bischof, C., Roh, L., Carle, A.: Algorithms and design for a second-order automatic differentiation module. In: Proceedings of the 1997 International Symposium on Symbolic and Agebraic Computation (ACM), pp. 149-155, New York (1997) · Zbl 0923.68068
[32] Walther, A., Griewank, A.: Advantages of binomial checkpointing for memory-reduced adjoint calculations. In: Feistauer, M., Dolejší, V., Knobloch, P., Najzar, K. (eds.) Numerical Mathematics and Advanced Applications, pp. 834-843. Springer, Berlin, Heidelberg (2004). ISBN: 978-3-642-62288-5. doi:10.1007/978-3-642-18775-9_82 · Zbl 1056.65064
[33] Sternberg, J., Griewank, A.: Reduction of storage requirement by checkpointing for time-dependent optimal control problems in ODEs. In: Norris, B., Bücker, M., Corliss, G., Hovland, P., Naumann, U. (eds.) Automatic Differentiation: Applications, Theory, and Implementations, 0, pp. 99-110. Springer, 1 edition (2006) · Zbl 1270.49041
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.