×

Computationally relevant generalized derivatives: theory, evaluation and applications. (English) Zbl 1401.49016

Summary: A new method for evaluating generalized derivatives in nonsmooth problems is reviewed. Lexicographic Directional (LD-)derivatives are a recently developed tool in nonsmooth analysis for evaluating generalized derivative elements in a tractable and robust way. Applicable to problems in both steady-state and dynamic settings, LD-derivatives exhibit a number of advantages over current theory and algorithms. As highlighted in this article, the LD-derivative approach now admits a suitable theory for inverse and implicit functions, nonsmooth dynamical systems and optimization problems, among others. Moreover, this technique includes an extension of the standard vector forward mode of Automatic Differentiation (AD) and acts as the natural extension of classical calculus results to the nonsmooth case in many ways. The theory of LD-derivatives is placed in the context of state-of-the-art methods in nonsmooth analysis, with an application in multistream heat exchanger modeling and design used to illustrate the usefulness of the approach.

MSC:

49J52 Nonsmooth analysis
49M15 Newton-type methods
65K15 Numerical methods for variational inequalities and related problems
90C31 Sensitivity, stability, parametric optimization
90C56 Derivative-free methods and methods using generalized derivatives
49Q12 Sensitivity analysis for optimization problems on manifolds

Software:

NDA; PNEW; PATH Solver; dcc; libMC
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Acary, V.; Bonnefon, O.; Brogliato, B., Nonsmooth Modeling and Simulation for Switched Circuits, (2011), Springer, New York · Zbl 1208.94003
[2] Baier, R.; Farkhi, E.; Roschina, V., directed subdifferentiable functions and the directed subdifferential without delta-convex structure, J. Optim. Theory Appl., 160, 391-414, (2014) · Zbl 1307.90140
[3] Baier, R.; Farkhi, E.; Roschina, V., from quasidifferentiable to directed subdifferentiable functions: exact calculus rules, J. Optim. Theory Appl., 171, 384-401, (2016) · Zbl 1353.49015
[4] Barton, P. I.; Lee, C. K., modeling, simulation, sensitivity analysis, and optimization of hybrid systems, ACM Trans. Model Comput. Simul., 12, 256-289, (2002) · Zbl 1390.93118
[5] Barton, P. I.; Lee, C. K., design of process operations using hybrid dynamic optimization, Comput. Chem. Eng., 28, 955-969, (2004)
[6] Barton, P. I.; Lee, C. K.; Yunt, M., optimization of hybrid systems, Comput. Chem. Eng., 30, 1576-1589, (2006)
[7] Baumrucker, B.; Renfro, J.; Biegler, L. T., MPEC problem formulations and solution strategies with chemical engineering applications, Comput. Chem. Eng., 32, 2903-2913, (2008)
[8] Benyahia, B.; Lakerveld, R.; Barton, P. I., A plant-wide dynamic model of a continuous pharmaceutical process, Ind. Eng. Chem. Res., 51, 15393-15412, (2012)
[9] Bonnans, J. F.; Shapiro, A., optimization problems with perturbations: A guided tour, SIAM Rev., 40, 228-264, (1998) · Zbl 0915.49021
[10] Bonnans, J. F.; Shapiro, A., Perturbation Analysis of Optimization Problems, (2000), Springer, New York · Zbl 0966.49001
[11] Brogliato, B., Nonsmooth Mechanics, (1999), Springer, London · Zbl 0917.73002
[12] Clarke, F. H., Optimization and Nonsmooth Analysis, (1990), SIAM, Philadelphia, PA · Zbl 0696.49002
[13] Clarke, F. H.; Ledyaev, Y. S.; Stern, R. J.; Wolenski, P. R., Nonsmooth Analysis and Control Theory Vol. 178, (2008), Springer, New York
[14] Cortes, J., discontinuous dynamical systems, IEEE Control Syst., 28, 36-73, (2012) · Zbl 1395.34023
[15] Cottle, R. W.; Pang, J. S.; Stone, R. E., The Linear Complementarity Problem, (2009), SIAM, Philadelphia, PA · Zbl 1192.90001
[16] Dirske, S. P.; Ferris, M. C., the PATH solver: A non-monotone stabilization scheme for mixed complementarity problems, Optim. Method Softw., 5, 123-156, (1995)
[17] Duran, M. A.; Grossmann, I. E., simultaneous optimization and heat integration of chemical processes, AIChE J., 32, 123-138, (1986)
[18] Facchinei, F.; Fischer, A.; Herrich, M., an LP-Newton method: nonsmooth equations, KKT systems, and nonisolated solutions, Math. Prog., 146, 1-36, (2014) · Zbl 1317.90276
[19] Facchinei, F.; Pang, J. S., Finite-Dimensional Variational Inequalities and Complementarity Problems: Volume I, (2003), Springer, New York
[20] Facchinei, F.; Pang, J. S., Finite-Dimensional Variational Inequalities and Complementarity Problems: Volume II, (2003), Springer, New York
[21] Ferris, M. C.; Munson, T. S., interfaces to PATH 3.0: design, implementation and usage, Comput. Optim. Appl., 12, 207-227, (1999) · Zbl 1040.90549
[22] Filippov, A. F., Differential Equations with Discontinuous Righthand Sides, (1988), Kluwer Academic Publishers, Dordrecht
[23] Gal, T., Postoptimal Analyses, Parametric Programming and Related Topics, (1995), Walter de Gruyter, Berlin
[24] Galán, S.; Feehery, W. F.; Barton, P. I., parametric sensitivity functions for hybrid discrete/continuous systems, Appl. Numer. Math., 31, 17-47, (1999) · Zbl 0937.65137
[25] Goebel, R.; Sanfelice, R.; Teel, A. R., hybrid dynamical systems, IEEE Control Syst., 29, 28-93, (2009) · Zbl 1395.93001
[26] Griewank, A.; urier, R., automatic directional differentiation of nonsmooth composite functions, Recent Developments in Optimization 1994, 155-169, (1995), Springer Verlag, Dijon · Zbl 0839.65024
[27] Griewank, A., on stable piecewise linearization and generalized algorithmic differentiation, Optim. Methods Softw., 28, 1139-1178, (2013) · Zbl 1278.65021
[28] 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
[29] Griewank, A.; Walther, A., Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation, (2008), SIAM, Philadelphia · Zbl 1159.65026
[30] Griewank, A.; Walther, A.; Fiege, S.; Bosse, T., on Lipschitz optimization based on gray-box piecewise linearization, Math. Prog., 158, 383-415, (2016) · Zbl 1350.49038
[31] Grossmann, I. E.; Yeomans, H.; Kravanja, Z., A rigorous disjunctive optimization model for simultaneous flowsheet optimization and heat integration, Comput. Chem. Eng., 22, 157-164, (1998)
[32] Heemels, W. P.M. H.; Schumacher, J. M.; Weiland, S., linear complementarity systems, SIAM J. Appl. Math., 60, 1234-1269, (2000) · Zbl 0954.34007
[33] Heemels, W. P.M. H.; Schutter, B. D.; Bemporad, A., equivalence of hybrid dynamical models, Automatica, 37, 1085-1091, (2001) · Zbl 0990.93056
[34] Hiriart-Urruty, J. B.; Lemaréchal, C., Convex Analysis and Minimization Algorithms I: Fundamentals, (1996), Springer, Berlin
[35] Hiriart-Urruty, J. B.; Lemaréchal, C., Convex Analysis and Minimization Algorithms II: Advanced Theory and Bundle Methods, (1996), Springer, Berlin
[36] 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)
[37] Höffner, K.; Barton, P. I., design of microbial consortia for industrial biotechnology, Comput. Aided Chem. Eng., 34, 65-74, (2014)
[38] Höffner, K.; Harwood, S. M.; Barton, P. I., A reliable simulator for dynamic flux balance analysis, Biotechnol. Bioeng., 110, 792-802, (2013)
[39] 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
[40] Horst, R.; Tuy, H., Global Optimization: Deterministic Approaches, (1993), Springer, Berlin
[41] Kamath, R. S.; Biegler, L. T.; Grossmann, I. E., modeling MHEXs with and without phase changes for simultaneous optimization and heat integration, AIChE J., 58, 190-204, (2012)
[42] Khan, K. A., relating lexicographic smoothness and directed subdifferentiability, Set-Valued Var. Anal., 25, 233–244, (2017) · Zbl 1365.90247
[43] Branch-locking AD techniques for nonsmooth composite functions and nonsmooth implicit functions, Optim. Methods Softw. in press (2017). Available at
[44] 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, Berlin · Zbl 1251.65028
[45] 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
[46] Khan, K. A.; Barton, P. I., generalized derivatives for solutions of parametric ordinary differential equations with non-differentiable right-hand sides, J. Optim. Theory Appl., 163, 355-386, (2014) · Zbl 1304.49035
[47] Khan, K. A.; Barton, P. I., generalized gradient elements for nonsmooth optimal control problems, 1887-1892, (2014)
[48] Khan, K. A.; Barton, P. I., switching behavior of solutions of ordinary differential equations with nonsmooth right-hand sides, Syst. Control. Lett., 84, 27-34, (2015) · Zbl 1326.93064
[49] Khan, K. A.; Barton, P. I., A vector forward mode of automatic differentiation for generalized derivative evaluation, Optim. Methods Softw., 30, 1185-1212, (2015) · Zbl 1329.49023
[50] generalized derivatives for hybrid systemsIEEE. Trans. Autom. Control62201731933208
[51] Khan, K. A.; Watson, H. A.J.; Barton, P. I., differentiable mccormick relaxations, J. Global Optim., 67, 687-729, (2017) · Zbl 1365.49027
[52] Kiwiel, K. C., Methods of Descent for Nondifferentiable Optimization, (1985), Springer, Berlin · Zbl 0561.90059
[53] Klatte, D.; Kummer, B., Nonsmooth Equations in Optimization: Regularity, Calculus, Methods and Applications, (2002), Kluwer Academic Publishers, Dordecht · Zbl 1173.49300
[54] Kojima, M.; Shindoh, S., extensions of Newton and quasi-Newton methods to systems of \(##?##\) equations, J. Oper. Res. Soc. Jpn., 29, 352-374, (1986) · Zbl 0611.65032
[55] Kruger, A. Y., on Fréchet subdifferentials, J. Math. Sci., 116, 3325-3358, (2003) · Zbl 1039.49021
[56] on a bundle algorithm for nonsmooth optimizationNonlinear Programming, 4th ed., Academic PressNew York1981245281
[57] Levy, A. B.; Mordukhovich, B. S., coderivatives in parametric optimization, Math. Prog., 99, 311-327, (2004) · Zbl 1079.90136
[58] Liberzon, D., Switching in Systems and Control, (2012), Springer Science & Business Media, New York
[59] Lukšan, L.; Vlček, J., A bundle-Newton method for nonsmooth unconstrained minimization, Math. Prog., 83, 373-391, (1998) · Zbl 0920.90132
[60] Lukšan, L.; Vlček, J., algorithm 811: NDA: algorithms for nondifferentiable optimization, ACM Trans. Math. Softw., 27, 193-213, (2001) · Zbl 1070.65552
[61] Lygeros, J.; Johansson, K. H.; Sastry, S.; Egerstedt, M., on the existence of executions of hybrid automata, 2249-2254, (1999)
[62] Lygeros, J.; Johansson, K.; Simic, S.; Sastry, S., dynamical properties of hybrid automata, IEEE. Trans. Autom. Control., 48, 2-17, (2003) · Zbl 1364.93503
[63] Method and apparatus for liquefying gases, (1975), US Patent 3,914,949
[64] McCormick, G. P., computability of global solutions to factorable nonconvex programs: part I—convex underestimating problems, Math. Prog., 10, 147-175, (1976) · Zbl 0349.90100
[65] Mitsos, A.; Chachuat, B.; Barton, P. I., mccormick-based relaxations of algorithms, SIAM J. Optim., 20, 573-601, (2009) · Zbl 1192.65083
[66] Mordukhovich, B. S., generalized differential calculus for nonsmooth and set-valued mappings, J. Math. Anal. Appl., 183, 250-288, (1994) · Zbl 0807.49016
[67] Mordukhovich, B. S., Variational Analysis and Generalized Differentiation I: Basic Theory, (2006), Springer, Berlin
[68] Naumann, U., The Art of Differentiating Computer Programs: An Introduction to Algorithmic Differentiation, (2012), SIAM, Philadelphia · Zbl 1275.65015
[69] Nesterov, Y., lexicographic differentiation of nonsmooth functions, Math. Prog., 104, 669-700, (2005) · Zbl 1082.49023
[70] Nocedal, J.; Wright, S. J., Numerical Optimization, (2006), Springer, New York · Zbl 1104.65059
[71] Páles, Z.; Zeidan, V., infinite dimensional generalized Jacobian: properties and calculus rules, J. Math. Anal. Appl., 344, 55-75, (2008) · Zbl 1211.49020
[72] Pang, J. S.; Ralph, D., piecewise smoothness, local invertibility, and parametric analysis of normal maps, Math. Oper. Res., 21, 401-426, (1996) · Zbl 0857.90122
[73] Pang, J. S.; Shen, J., strongly regular differential variational systems, IEEE Trans. Autom. Control, 52, 242-255, (2007) · Zbl 1366.93271
[74] Pang, J. S.; Stewart, D. E., differential variational inequalities, Math. Prog., 113, 345-424, (2008) · Zbl 1139.58011
[75] Pang, J. S.; Stewart, D. E., solution dependence on initial conditions in differential variational inequalities, Math. Prog., 116, 429-460, (2009) · Zbl 1194.49033
[76] Qi, L., convergence analysis of some algorithms for solving nonsmooth equations, Math. Oper. Res., 18, 227-244, (1993) · Zbl 0776.65037
[77] Qi, L.; Sun, J., A nonsmooth version of Newton’s method, Math. Prog., 58, 353-367, (1993) · Zbl 0780.90090
[78] Raghunathan, A. U.; Diaz, M. S.; Biegler, L. T., an MPEC formulation for dynamic optimization of distillation operations, Comput. Chem. Eng., 28, 2037-2052, (2004)
[79] Ralph, D.; Scholtes, S., sensitivity analysis of composite piecewise smooth equations, Math. Prog., 76, 593-612, (1997) · Zbl 0871.90094
[80] Roe, P. L., characteristic-based schemes for the Euler equations, Annu. Rev. Fluid Mech., 18, 337-365, (1986) · Zbl 0624.76093
[81] Sahlodin, A. M.; Barton, P. I., optimal campaign continuous manufacturing, Ind. Eng. Chem. Res., 54, 11344-11359, (2015)
[82] Sahlodin, A. M.; Watson, H. A.J.; Barton, P. I., nonsmooth model for dynamic simulation of phase changes, AIChE J., 62, 3334-3351, (2016)
[83] Scholtes, S., Introduction to Piecewise Differentiable Equations, (2012), Springer, New York · Zbl 1453.49002
[84] Schumacher, J. M., complementarity systems in optimization, Math. Prog., 101, 263-295, (2004) · Zbl 1076.90060
[85] Scott, J. K.; Barton, P. I., improved relaxations for the parametric solutions of ODEs using differential inequalities, J. Global Optim., 57, 143-176, (2013) · Zbl 1273.49034
[86] Scott, J. K.; Chachuat, B.; Barton, P. I., nonlinear convex and concave relaxations for the solutions of parametric ODEs, Optim. Control Appl. Methods, 34, 145-163, (2013) · Zbl 1273.93089
[87] Shor, N. Z., Minimization Methods for Non-Differentiable Functions, (1985), Springer, Berlin · Zbl 0561.90058
[88] Stechlinski, P. G.; Barton, P. I., generalized derivatives of differential–algebraic equations, J. Optim. Theory Appl., 171, 1-26, (2016) · Zbl 1353.49025
[89] Stechlinski, P. G.; Barton, P. I., generalized derivatives of optimal control problems with nonsmooth differential-algebraic equations embedded, 592-597, (2016)
[90] Stechlinski, P. G.; Barton, P. I., dependence of solutions of nonsmooth differential–algebraic equations on parameters, J. Differ. Equ., 262, 2254-2285, (2017) · Zbl 1362.34019
[91] Sweetser, T. H., A minimal set-valued strong derivative for vector-valued Lipschitz functions, J. Optim. Theory Appl., 23, 549-562, (1977) · Zbl 0345.26005
[92] Tsoukalas, A.; Mitsos, A., multivariate mccormick relaxations, J. Global Optim., 59, 633-662, (2014) · Zbl 1312.90068
[93] Ulbrich, M., Semismooth Newton Methods for Variational Inequalities and Constrained Optimization Problems in Function Spaces, (2011), SIAM, Philadelphia · Zbl 1235.49001
[94] Watson, H. A.J.; Barton, P. I., modeling phase changes in multistream heat exchangers, Int. J. Heat Mass Transfer, 105, 207-219, (2017)
[95] Watson, H. A.J.; Khan, K. A.; Barton, P. I., multistream heat exchanger modeling and design, AIChE J., 61, 3390-3403, (2015)
[96] Watson, H. A.J.; Vikse, M.; Gundersen, T.; Barton, P. I., reliable flash calculations: part 1. nonsmooth inside-out algorithms, Ind. Eng. Chem. Res., 56, 960-973, (2017)
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.