zbMATH — the first resource for mathematics

Branch-locking AD techniques for nonsmooth composite functions and nonsmooth implicit functions. (English) Zbl 1401.90270
Summary: A recent nonsmooth vector forward mode of algorithmic differentiation (AD) computes Nesterov’s L-derivatives for nonsmooth composite functions; these L-derivatives provide useful sensitivity information to methods for nonsmooth optimization and equation solving. The established reverse AD mode evaluates gradients efficiently for smooth functions, but it does not extend directly to nonsmooth functions. Thus, this article examines branch-locking strategies to harness the benefits of smooth AD techniques even in the nonsmooth case, in order to improve the computational performance of the nonsmooth vector forward AD mode. In these strategies, each nonsmooth elemental function in the original composition is ‘locked’ into an appropriate linear ‘branch’. The original composition is thereby replaced with a smooth variant, which may be subjected to efficient AD techniques for smooth functions such as the reverse AD mode. In order to choose the correct linear branches, we use inexpensive probing steps to ascertain the composite function’s local behaviour. A simple implementation in C\(++11\) is described, and the developed techniques are extended to nonsmooth local implicit functions and inverse functions.

90C56 Derivative-free methods and methods using generalized derivatives
49J52 Nonsmooth analysis
49M15 Newton-type methods
65K15 Numerical methods for variational inequalities and related problems
amodMC; dcc; Eigen; libMC
Full Text: DOI
[1] Computationally relevant generalized derivatives: Theory, evaluation, and applications, Submitted (2017)
[2] Baumrucker, B. T.; Biegler, L. T., MPEC strategies for cost optimization of pipeline operations, Comput. Chem. Eng., 34, 900-913, (2010)
[3] Beckers, M.; Mosenkis, V.; Naumann, U.; Forth, S.; Hovland, P.; Phipps, E.; Utke, J.; Walther, A., adjoint mode computation of subgradients for mccormick relaxations, Recent Advances in Algorithmic Differentiation, 103-113, (2012), Springer-Verlag, Berlin · Zbl 1253.65031
[4] Bertsimas, D.; Tsitsiklis, J. N., Introduction to Linear Optimization, (1997), Athena Scientific, Nashua
[5] Clarke, F. H., Optimization and Nonsmooth Analysis, (1990), SIAM, Philadelphia, PA · Zbl 0696.49002
[6] Cottle, R. W.; Pang, J. S.; Stone, R. E., The Linear Complementarity Problem, (2009), SIAM, Philadelphia
[7] Duran, M. A.; Grossmann, I. E., simultaneous optimization and heat integration of chemical processes, AIChE J., 32, 123-138, (1986)
[8] Facchinei, F.; Pang, J. S., Finite-Dimensional Variational Inequalities and Complementarity Problems, (2003), Springer-Verlag, New York, Inc., New York
[9] Facchinei, F.; Fischer, A.; Herrich, M., an LP-Newton method: nonsmooth equations, KKT systems, and nonisolated solutions, Math. Program., Ser. A, 146, 1-36, (2014) · Zbl 1317.90276
[10] Fletcher, R.; Leyffer, S., solving mixed integer nonlinear programs by outer approximation, Math. Program., 66, 327-349, (1994) · Zbl 0833.90088
[11] Generalized derivatives of lexicographic linear programs, Submitted (2016)
[12] Griewank, A.; Durier, R.; Michelot, C., automatic directional differentiation of nonsmooth composite functions, 155-169, (2012), Springer, Dijon
[13] Griewank, A., on stable piecewise linearization and generalized algorithmic differentiation, (2012)
[14] Griewank, A., on stable piecewise linearization and generalized algorithmic differentiation, Optim. Method. Softw., 28, 1139-1178, (2013) · Zbl 1278.65021
[15] Griewank, A.; Walther, A., Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation, (2008), SIAM, Philadelphia, PA · Zbl 1159.65026
[16] 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
[17] Griewank, A.; Walther, A.; Fiege, S.; Bosse, T., on Lipschitz optimization based on gray-box piecewise linearization, Math. Program. A, 158, 383-415, (2016) · Zbl 1350.49038
[18] Eigen v3.2.10, Available at (2016)
[19] Hiriart-Urruty, J. B.; Lemaréchal, C., Convex Analysis and Minimization Algorithms II: Advanced Theory and Bundle Methods, (1993), Springer-Verlag, Berlin · Zbl 0795.49002
[20] Hiskens, I. A., stability of hybrid system limit cycles: application to the compass gait biped robot, 774-779, (2001)
[21] Hjersted, J. L.; Henson, M. A., steady-state and dynamic flux balance analysis of ethanol production by saccharomyces cerevisiae, IET Syst. Biol., 3, 167-179, (2009)
[22] Höffner, K.; Harwood, S. M.; Barton, P. I., A reliable simulator for dynamic flux balance analysis, Biotechnol. Bioeng., 110, 792-802, (2013)
[23] Höffner, K.; Khan, K. A.; Barton, P. I., generalized derivatives of dynamic systems with a linear program embedded, Automatica, 63, 198-208, (2016) · Zbl 1329.93104
[24] Test problems for large-scale nonsmooth minimization, Report of the Department of Mathematical Information Technology B. 4/2007, University of Jyväskylä, 2007
[25] Khan, K. A.; Barton, P. I.; Forth, S.; Hovland, P.; Phipps, E.; Utke, J.; Walther, A., evaluating an element of the Clarke generalized Jacobian of a piecewise differentiable function, Recent Advances in Algorithmic Differentiation, 115-125, (2012), Springer-Verlag, Berlin · Zbl 1251.65028
[26] Khan, K. A.; Barton, P. I., evaluating an element of the Clarke generalized Jacobian of a composite piecewise differentiable function, ACM Trans. Math. Softw., 39, 23:1-23:28, (2013) · Zbl 1295.65076
[27] Khan, K. A.; Barton, P. I., generalized derivatives for solutions of parametric ordinary differential equations with non-differentiable right-hand sides, J. Optimiz. Theory Appl., 163, 355-386, (2014) · Zbl 1304.49035
[28] Khan, K. A.; Barton, P. I., A vector forward mode of automatic differentiation for generalized derivative evaluation, Optim. Method Softw., 30, 1185-1212, (2015) · Zbl 1329.49023
[29] Generalized derivatives for hybrid systems, IEEE T. Automat. Control. in press (2016)
[30] Kiwiel, K. C., Methods of Descent for Nondifferentiable Optimization, (1985), Springer-Verlag, Berlin · Zbl 0561.90059
[31] Kojima, M.; Shindo, S., extension of Newton and quasi-Newton methods to systems of \(##?##\) equations, J. Oper. Res. Soc. Jpn, 29, 352-375, (1986) · Zbl 0611.65032
[32] Leine, R. I.; Nijmeijer, H., Dynamics and Bifurcations of Non-Smooth Mechanical Systems, (2004), Springer, Berlin · Zbl 1068.70003
[33] McCormick, G. P., computability of global solutions to factorable nonconvex programs: part I – convex underestimating problems, Math. Program., 10, 147-175, (1976) · Zbl 0349.90100
[34] Mitsos, A.; Chachuat, B.; Barton, P. I., mccormick-based relaxations of algorithms, SIAM J. Optim., 20, 573-601, (2009) · Zbl 1192.65083
[35] Moore, R. E., Methods and Applications of Interval Analysis, (1979), SIAM, Philadelphia · Zbl 0417.65022
[36] Naumann, U., The Art of Differentiating Computer Programs: An Introduction to Algorithmic Differentiation, (2012), SIAM, Philadelphia · Zbl 1275.65015
[37] Nesterov, Y., lexicographic differentiation of nonsmooth functions, Math. Program. B, 104, 669-700, (2005) · Zbl 1082.49023
[38] Neumaier, A., Interval Methods for Systems of Equations, (1990), Cambridge University Press, Cambridge · Zbl 0706.15009
[39] Nocedal, J.; Wright, S. J., Numerical Optimization, (2006), Springer, New York · Zbl 1104.65059
[40] Qi, L., convergence analysis of some algorithms for solving nonsmooth equations, Math. Oper. Res., 18, 227-244, (1993) · Zbl 0776.65037
[41] Qi, L.; Sun, J., A nonsmooth version of Newton’s method, Math. Program., 58, 353-367, (1993) · Zbl 0780.90090
[42] Raman, R.; Grossmann, I. E., modelling and computational techniques for logic based integer programming, Comput. Chem. Eng., 18, 563-578, (1994)
[43] Sahlodin, A. M.; Watson, H. A.J.; Barton, P. I., nonsmooth model for dynamic simulation of phase changes, AIChE J., 62, 3334-3351, (2016)
[44] Scholtes, S., Introduction to Piecewise Differentiable Equations, (2012), Springer, New York · Zbl 06046475
[45] Shor, N. Z., Minimization Methods for Non-Differentiable Functions, (1985), Springer-Verlag, Berlin · Zbl 0561.90058
[46] Siegel, S. F.; Zirkel, T. K., A functional equivalence verificaiton suite for high-performance scientific computing, Math. Comput. Sci., 5, 427-435, (2011) · Zbl 1264.68066
[47] Siegel, S. F.; Zirkel, T. K., the toolkit for accurate scientific software, Math. Comput. Sci., 5, 395-426, (2011) · Zbl 1264.68113
[48] Stechlinski, P. G.; Barton, P. I., generalized derivatives of differential-algebraic equations, J. Optim. Theory Appl., 171, 1-26, (2016) · Zbl 1353.49025
[49] Sweetser III, T. H., A minimal set-valued strong derivative for vector-valued Lipschitz functions, J. Optim. Theory Appl., 23, 549-562, (1977) · Zbl 0345.26005
[50] Ulbrich, M., Semismooth Newton Methods for Variational Inequalities and Constrained Optimization Problems in Function Spaces, (2011), SIAM, Philadelphia · Zbl 1235.49001
[51] Watson, H. A.J.; Khan, K. A.; Barton, P. I., multistream heat exchanger modeling and design, AIChE J., 61, 3390-3403, (2015)
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.