×

On the abs-polynomial expansion of piecewise smooth functions. (English) Zbl 07368763

Summary: Tom Streubel has observed that for functions in abs-normal form, generalized Taylor expansions of arbitrary order \(\bar{d}-1\) can be generated by algorithmic piecewise differentiation. Abs-normal form means that the real or vector valued function is defined by an evaluation procedure that involves the absolute value function \(|\cdot|\) apart from arithmetic operations and \(\bar{d}\) times continuously differentiable univariate intrinsic functions. The additive terms in Streubel’s expansion are abs-polynomial, i.e. involve neither divisions nor intrinsics. When and where no absolute values occur, Moore’s recurrences can be used to propagate univariate Taylor polynomials through the evaluation procedure with a computational effort of \(O(\bar{d}^2)\), provided all univariate intrinsics are defined as solutions of linear ODEs. This regularity assumption holds for all standard intrinsics, but for irregular elementaries one has to resort to Faa di Bruno’s formula, which has exponential complexity in \(\bar{d}\). As already conjectured, we show that the Moore recurrences can be adapted for regular intrinsics to the abs-normal case. Finally, we observe that where the intrinsics are real analytic the expansions can be extended to infinite series that converge absolutely on spherical domains.

MSC:

65D15 Algorithms for approximation of functions
41A10 Approximation by polynomials
41A58 Series expansions (e.g., Taylor, Lidstone series, but not Fourier series)
49J52 Nonsmooth analysis

Software:

LiPsMin
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Boeck, P.; Gompil, B.; Griewank, A.; Hasenfelder, R.; Strogies, N., Experiments with generalized midpoint and trapezoidal rules on two nonsmooth ODE’s, Mongolian Math. J., 17, 39-49 (2013) · Zbl 1314.65092
[2] Bosse, T., Narayanan, S.H.K., and Hascoet, L., Piecewise linear AD via source transformation, 2016. published as preprint via Argonne National Laboratory.
[3] Clarke, F. H., Optimization and Nonsmooth Analysis (1983), Wiley: Wiley, New York · Zbl 0582.49001
[4] Clees, T., Nikitin, I., and Nikitina, L., Making network solvers globally convergent, in Simulation and Modeling Methodologies, Technologies and Applications, M.S. Obaidat, T. Ören, and Y. Merkuryev, eds., Springer International Publishing, Cham, 2018, pp. 140-153.
[5] Demyanov, V.F. and Rubinov, A.M., An introduction to quasidifferential calculus, Quasidifferentiability and related topics, Vol. 43, Nonconvex Optim. Appl., Kluwer Acad. Publ., Dordrecht, 2000, pp. 1-31. · Zbl 0978.49016
[6] Fiege, S.; Walther, A.; Griewank, A., An algorithm for nonsmooth optimization by successive piecewise linearization, Math. Prog., 177, 343-370 (2018) · Zbl 1420.49015
[7] Fiege, S.; Walther, A.; Kulshreshtha, K.; Griewank, A., Algorithmic differentiation for piecewise smooth functions: a case study for robust optimization, Optim Meth and Soft, 33, 4-6, 1073-1088 (2018) · Zbl 1401.90168
[8] Griewank, A., Automatic Directional Differentiation of Nonsmooth Composite Functions, in Recent developments in Optimization / Seventh French-German Conference on Optimization, Dijon 1994, R. Durier, ed., Springer Verlag, 1995, pp. 155-169. · Zbl 0839.65024
[9] Griewank, A., On stable piecewise linearization and generalized algorithmic differentiation, Optim. Meth. and Soft., 28, 6, 1139-1178 (2013) · Zbl 1278.65021
[10] Griewank, A.; Bernt, J. U.; Radons, M.; Streubel, T., Solving piecewise linear systems in abs-normal form, Linear. Algebra. Appl., 471, 500-530 (2015) · Zbl 1308.90179
[11] Griewank, A.; Hasenfelder, R.; Radons, M.; Lehmann, L.; Streubel, T., Integrating Lipschitzian dynamical systems using piecewise algorithmic differentiation, Optim. Meth. and Soft., 33, 4-6, 1089-1107 (2018) · Zbl 1401.65070
[12] Griewank, A.; Streubel, T.; Lehmann, L.; Radons, M.; Hasenfelder, R., Piecewise linear secant approximation via algorithmic piecewise differentiation, Optim. Meth. and Soft., 33, 4-6, 1108-1126 (2018) · Zbl 1408.90322
[13] Griewank, A. and Walther, A., Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation, Other Titles in Applied Mathematics. Society for Industrial and Applied Mathematics (SIAM), 2008. · Zbl 1159.65026
[14] Griewank, A.; Walther, A., First- and second-order optimality conditions for piecewise smooth objective functions, Optim. Meth. and Soft., 31, 5, 904-930 (2016) · Zbl 1385.90026
[15] Griewank, A.; Walther, A., Finite convergence of an active signature method to local minima of piecewise linear functions, Optim. Meth. and Soft., 34, 5, 1035-1055 (2019) · Zbl 1428.90177
[16] Griewank, A.; Walther, A., Relaxing kink qualifications and proving convergence rates in piecewise smooth optimization, SIAM. J. Optim., 29, 262-289 (2019) · Zbl 1410.90252
[17] Griewank, A.; Walther, A.; Fiege, S.; Bosse, T., On Lipschitz optimization based on gray-box piecewise linearization, Math. Program., 158, 1, 383-415 (2016) · Zbl 1350.49038
[18] Klatte, D. and Kummer, B., Nonsmooth equations in optimization, in Nonconvex Optimization and its Applications, Regularity, calculus, methods and applications, Vol. 60, Kluwer Academic Publishers, Dordrecht, 2002. · Zbl 1173.49300
[19] Kubota, K., Enumeration of subdifferentials of piecewise linear functions with abs-normal form, Optim. Meth. and Soft., 33, 4-6, 1156-1172 (2018) · Zbl 1403.65012
[20] Leipnik, R. B.; Pearce, C. E.M., The multivariate Fa di Bruno formula and multivariate Taylor expansions with explicit integral remainder term, The ANZIAM J., 48, 3, 327-341 (2007) · Zbl 1149.46036
[21] Mordukhovich, B.S., Variational analysis and generalized differentiation. I, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], Vol. 330, Springer-Verlag, Berlin, 2006. Basic theory.
[22] Radons, M., Direct solution of piecewise linear systems, Theor. Comput. Sci., 626, 97-109 (2016) · Zbl 1336.68144
[23] Radons, M., A note on surjectivity of piecewise affine mappings, Optim. Lett., 13, 439-443 (2019) · Zbl 1420.90068
[24] Rall, L.B. and Corliss, G.F., An introduction to automatic differentiation, SIAM, Philadelphia, PA, 1996, pp. 1-17. · Zbl 0940.65019
[25] Schirotzek, W., Nonsmooth analysis, Universitext, Springer, Berlin, 2007. Available at doi:10.1007/978-3-540-71333-3. · Zbl 1120.49001
[26] Scholtes, S., Introduction to Piecewise Differentiable Equations (2012), Springer: Springer, New York · Zbl 1453.49002
[27] Streubel, T., Griewank, A., Radons, M., and Bernt, J.U., Representation and analysis of piecewise linear functions in abs-normal form, in System Modeling and Optimization, C. Pötzsche, C. Heuberger, B. Kaltenbacher, and F. Rendl, eds., Springer Berlin Heidelberg, Berlin, Heidelberg, 2014, pp. 327-336. · Zbl 1325.65087
[28] Streubel, T., Tischendorf, C., and Griewank, A., Piecewise polynomial taylor expansions-the generalization of faà di bruno’s formula. Technical Report 18-24, ZIB, Takustr. 7, 14195 Berlin, 2018.
[29] Streubel, T., Strohm, C., Trunschke, P., and Tischendorf, C., Generic construction and efficient evaluation of flow network DAEs and their derivatives in the context of gas networks, in Operations Research Proceedings 2017, N. Kliewer, J.-F. Ehmke, and R. Borndörfer, eds., Springer International Publishing, Cham, 2018, pp. 627-632. · Zbl 1397.90087
[30] Walther, A.; Griewank, A., Characterizing and testing subdifferential regularity in piecewise smooth optimization, SIAM. J. Optim., 29, 1473-1501 (2019) · Zbl 1422.49016
[31] Whish, C.M., XXXIII. On the Hindú Quadrature of the Circle, and the infinite Series of the proportion of the circumference to the diameter exhibited in the four S’ástras, the Tantra Sangraham, Yucti Bháshá, Carana Padhati, and Sadratnamála, July 1834. Available at: doi:10.1017/s0950473700001221.
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.