Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Optimization-based convex relaxations for nonconvex parametric systems of ordinary differential equations

  • Full Length Paper
  • Series B
  • Published:
Mathematical Programming Submit manuscript

Abstract

Novel convex and concave relaxations are proposed for the solutions of parametric ordinary differential equations (ODEs), to aid in furnishing bounding information for deterministic global dynamic optimization methods. These relaxations are constructed as the solutions of auxiliary ODE systems with embedded convex optimization problems, whose objective functions employ convex and concave relaxations of the original ODE right-hand side. Unlike established relaxation methods, any valid convex and concave relaxations for the original right-hand side are permitted in the approach, including the McCormick relaxations and the \(\alpha \)BB relaxations. In general, tighter such relaxations will necessarily translate into tighter relaxations for the ODE solutions, thus providing tighter bounding information for an overarching global dynamic optimization method. Notably, if McCormick relaxations are employed in the new approach, then the obtained relaxations are guaranteed to be at least as tight as state-of-the-art ODE relaxations based on generalized McCormick relaxations. The new relaxations converge rapidly to the original system as the considered parametric subdomain shrinks. Several examples are presented for comparison with established ODE relaxations, based on a proof-of-concept implementation in MATLAB. In a global optimization case study, the new ODE relaxations are shown to lead to fewer branch-and-bound global optimization iterations than state-of-the-art relaxations.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

References

  1. Acary, V., Pérignon, F.: Siconos: a software platform for modeling, simulation, analysis and control of nonsmooth dynamical systems. Simul. Notes Europe 17(34), 19–26 (2007)

    Google Scholar 

  2. Adjiman, C.S., Dallwig, S., Floudas, C.A., Neumaier, A.: A global optimization method, \(\alpha \)BB, for general twice-differentiable constrained NLPs-I. Theor. Adv. Comput. Chem. Eng. 22(9), 1137–1158 (1998)

    Article  Google Scholar 

  3. Althoff, M., Stursberg, O., Buss, M.: Reachability analysis of nonlinear systems with uncertain parameters using conservative linearization. In: 2008 47th IEEE Conference on Decision and Control, pp. 4042–4048. IEEE (2008)

  4. Banga, J.R., Alonso, A.A., Singh, R.P.: Stochastic dynamic optimization of batch and semicontinuous bioprocesses. Biotechnol. Prog. 13(3), 326–335 (1997)

    Article  Google Scholar 

  5. Banga, J.R., Moles, C.G., Alonso, A.A.: Global optimization of bioprocesses using stochastic and hybrid methods. In: Floudas, C.A., Pardalos, P.M. (eds.) Frontiers in Global Optimization, pp. 45–70. Springer (2004)

  6. Berge, C.: Topological Spaces: Including a Treatment of Multi-valued Functions, Vector spaces, and Convexity. Oliver and Boyd, Edinburgh (1963)

    MATH  Google Scholar 

  7. Bernard, O., Hadj-Sadok, Z., Dochain, D., Genovesi, A., Steyer, J.P.: Dynamical model development and parameter identification for an anaerobic wastewater treatment process. Biotechnol. Bioeng. 75(4), 424–438 (2001)

    Article  Google Scholar 

  8. Bezanson, J., Edelman, A., Karpinski, S., Shah, V.B.: Julia: A fresh approach to numerical computing. SIAM Rev. 59(1), 65–98 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  9. Bompadre, A., Mitsos, A.: Convergence rate of McCormick relaxations. J. Global Optim. 52(1), 1–28 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  10. Bompadre, A., Mitsos, A., Chachuat, B.: Convergence analysis of Taylor models and McCormick–Taylor models. J. Global Optim. 57(1), 75–114 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  11. Chachuat, B., Villanueva, M.: Bounding the solutions of parametric ODEs: when Taylor models meet differential inequalities. In: Bogle, I.D.L., Fairweather, M. (eds.) Computer Aided Chemical Engineering, vol. 30, pp. 1307–1311. Elsevier (2012)

  12. Chutinan, A., Krogh, B.H.: Verification of polyhedral-invariant hybrid automata using polygonal flow pipe approximations. In: International Workshop on Hybrid Systems: Computation and Control, pp. 76–90. Springer (1999)

  13. Čižniar, M., Podmajerskỳ, M., Hirmajer, T., Fikar, M., Latifi, A.M.: Global optimization for parameter estimation of differential-algebraic systems. Chem. Pap. 63(3), 274–283 (2009)

    Article  Google Scholar 

  14. Clarke, F.H.: Generalized gradients and applications. Trans. Am. Math. Soc. 205, 247–262 (1975)

    Article  MathSciNet  MATH  Google Scholar 

  15. Diedam, H., Sager, S.: Global optimal control with the direct multiple shooting method. Optimal Control Appl. Methods 39(2), 449–470 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  16. Du, K., Kearfott, R.B.: The cluster problem in multivariate global optimization. J. Global Optim. 5(3), 253–265 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  17. Dunning, I., Huchette, J., Lubin, M.: JuMP: A modeling language for mathematical optimization. SIAM Rev. 59(2), 295–320 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  18. Egea, J.A., Vazquez, E., Banga, J.R., Martí, R.: Improved scatter search for the global optimization of computationally expensive dynamic models. J. Global Optim. 43(2–3), 175–190 (2009)

    Article  MATH  Google Scholar 

  19. Esposito, W.R., Floudas, C.A.: Global optimization for the parameter estimation of differential-algebraic systems. Ind. Eng. Chem. Res. 39(5), 1291–1310 (2000)

    Article  Google Scholar 

  20. Falk, J.E., Soland, R.M.: An algorithm for separable nonconvex programming problems. Manag. Sci. 15(9), 550–569 (1969)

    Article  MathSciNet  MATH  Google Scholar 

  21. Filippov, A.: Differential Equations with Discontinuous Righthand Sides. Kluwer, Dordrecht (1988)

    Book  Google Scholar 

  22. Gomez, J.A., Höffner, K., Barton, P.I.: DFBAlab: A fast and reliable MATLAB code for dynamic flux balance analysis. BMC Bioinform. 15(1), 409 (2014)

    Article  Google Scholar 

  23. Harrison, G.: Dynamic models with uncertain parameters. In: Avula, X. (eds.) Proceedings of the 1st International Conference on Mathematical Modeling 1, 295–304 (1977)

  24. Hartman, P.: Ordinary Differential Equations, 2nd edn. SIAM, Philadelphia (2002)

    Book  MATH  Google Scholar 

  25. Harwood, S.M., Barton, P.I.: Efficient polyhedral enclosures for the reachable set of nonlinear control systems. Math. Control Signals Syst. 28(1), 8 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  26. Harwood, S.M., Barton, P.I.: Affine relaxations for the solutions of constrained parametric ordinary differential equations. Optimal Control Appl. Methods 39(2), 427–448 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  27. Harwood, S.M., Scott, J.K., Barton, P.I.: Bounds on reachable sets using ordinary differential equations with linear programs embedded. IMA J. Math. Control Inf. 33(2), 519–541 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  28. Houska, B., Chachuat, B.: Branch-and-lift algorithm for deterministic global optimization in nonlinear optimal control. J. Optim. Theory Appl. 162(1), 208–248 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  29. Huang, H., Adjiman, C.S., Shah, N.: Quantitative framework for reliable safety analysis. AIChE J. 48(1), 78–96 (2002)

    Article  Google Scholar 

  30. Khajavirad, A., Sahinidis, N.V.: A hybrid LP/NLP paradigm for global optimization relaxations. Math. Program. Comput. 10(3), 383–421 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  31. Khalil, H.K., Grizzle, J.W.: Nonlinear Systems, vol. 3. Prentice hall, Upper Saddle River (2002)

    Google Scholar 

  32. Khan, K.A., Barton, P.I.: Switching behavior of solutions of ordinary differential equations with abs-factorable right-hand sides. Syst. Control Lett. 84, 27–34 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  33. Khan, K.A., Watson, H.A., Barton, P.I.: Differentiable McCormick relaxations. J. Global Optim. 67(4), 687–729 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  34. Kurzhanski, A., Varaiya, P.: Reachability analysis for uncertain systems-the ellipsoidal technique. Dyn. Contin. Discrete Impulsive Syst. Ser. B 9, 347–368 (2002)

    MathSciNet  MATH  Google Scholar 

  35. Liberti, L., Pantelides, C.C.: Convex envelopes of monomials of odd degree. J. Global Optim. 25(2), 157–168 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  36. Lin, Y., Stadtherr, M.A.: Deterministic global optimization for parameter estimation of dynamic systems. Ind. Eng. Chem. Res. 45(25), 8438–8448 (2006)

    Article  Google Scholar 

  37. Lin, Y., Stadtherr, M.A.: Validated solutions of initial value problems for parametric ODEs. Appl. Numer. Math. 57(10), 1145–1162 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  38. Maranas, C.D., Floudas, C.A.: Finding all solutions of nonlinearly constrained systems of equations. J. Global Optim. 7(2), 143–182 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  39. MATLAB: 9.6.0.1072779 (R2019a). The MathWorks Inc., Natick (2019)

    Google Scholar 

  40. McCormick, G.P.: Computability of global solutions to factorable nonconvex programs: part I—convex underestimating problems. Math. Program. 10(1), 147–175 (1976)

    Article  MATH  Google Scholar 

  41. Misener, R., Floudas, C.A.: ANTIGONE: Algorithms for continuous/integer global optimization of nonlinear equations. J. Global Optim. 59(2–3), 503–526 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  42. Mitsos, A., Chachuat, B., Barton, P.I.: McCormick-based relaxations of algorithms. SIAM J. Optim. 20(2), 573–601 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  43. Moore, R.E.: Methods and Applications of Interval Analysis. SIAM, Philadelphia (1979)

    Book  MATH  Google Scholar 

  44. Müller, M.: Über das fundamentaltheorem in der theorie der gewöhnlichen differentialgleichungen. Math. Z. 26(1), 619–645 (1927)

    Article  MathSciNet  MATH  Google Scholar 

  45. Najman, J., Mitsos, A.: Tighter McCormick relaxations through subgradient propagation. J. Global Optim. 75(3), 565–593 (2019)

    Article  MathSciNet  MATH  Google Scholar 

  46. Nedialkov, N.S., Jackson, K.R., Corliss, G.F.: Validated solutions of initial value problems for ordinary differential equations. Appl. Math. Comput. 105(1), 21–68 (1999)

    MathSciNet  MATH  Google Scholar 

  47. Nesterov, Y.: Lectures on Convex Optimization, vol. 137. Springer, Cham (2018)

    MATH  Google Scholar 

  48. Papamichail, I., Adjiman, C.S.: A rigorous global optimization algorithm for problems with ordinary differential equations. J. Global Optim. 24(1), 1–33 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  49. Park, T., Barton, P.I.: State event location in differential-algebraic models. ACM Trans. Model. Comput. Simul. TOMACS 6(2), 137–165 (1996)

    Article  MATH  Google Scholar 

  50. Pérez-Galván, C., Bogle, I.D.L.: Global optimisation for dynamic systems using interval analysis. Comput. Chem. Eng. 107, 343–356 (2017)

    Article  Google Scholar 

  51. Rackauckas, C., Nie, Q.: Differentialequations. jl—a performant and feature-rich ecosystem for solving differential equations in Julia. J. Open Res. Softw. 5(1), 15 (2017)

    Article  Google Scholar 

  52. Ryoo, H.S., Sahinidis, N.V.: A branch-and-reduce approach to global optimization. J. Global Optim. 8(2), 107–138 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  53. Sahinidis, N.V.: BARON: A general purpose global optimization software package. J. Global Optim. 8(2), 201–205 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  54. Sahlodin, A.M., Chachuat, B.: Discretize-then-relax approach for state relaxations in global dynamic optimization. In: Pierucci, S., Buzzi-Ferraris, G. (eds.) Computer Aided Chemical Engineering, vol. 28, pp. 427–432. Elsevier (2010)

  55. Sahlodin, A.M., Chachuat, B.: Convex/concave relaxations of parametric ODEs using Taylor models. Comput. Chem. Eng. 35(5), 844–857 (2011)

    Article  MATH  Google Scholar 

  56. Schaber, S.D., Scott, J.K., Barton, P.I.: Convergence-order analysis for differential-inequalities-based bounds and relaxations of the solutions of ODEs. J. Global Optim. 73(1), 113–151 (2019)

    Article  MathSciNet  MATH  Google Scholar 

  57. Scott, J.K.: Reachability analysis and deterministic global optimization of differential-algebraic systems. Ph.D. thesis, Massachusetts Institute of Technology (2012)

  58. Scott, J.K., Barton, P.I.: Tight, efficient bounds on the solutions of chemical kinetics models. Comput. Chem. Eng. 34(5), 717–731 (2010)

    Article  Google Scholar 

  59. Scott, J.K., Barton, P.I.: Bounds on the reachable sets of nonlinear control systems. Automatica 49(1), 93–100 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  60. Scott, J.K., Barton, P.I.: Improved relaxations for the parametric solutions of ODEs using differential inequalities. J. Global Optim. 57(1), 143–176 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  61. Scott, J.K., Chachuat, B., Barton, P.I.: Nonlinear convex and concave relaxations for the solutions of parametric ODEs. Optimal Control Appl. Methods 34(2), 145–163 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  62. Scott, J.K., Stuber, M.D., Barton, P.I.: Generalized McCormick relaxations. J. Global Optim. 51(4), 569–606 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  63. Singer, A.B., Barton, P.I.: Bounding the solutions of parameter dependent nonlinear ordinary differential equations. SIAM J. Sci. Comput. 27(6), 2167–2182 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  64. Singer, A.B., Taylor, J.W., Barton, P.I., Green, W.H.: Global dynamic optimization for parameter estimation in chemical kinetics. J. Phys. Chem. A 110(3), 971–976 (2006)

    Article  Google Scholar 

  65. Smith, E.M., Pantelides, C.C.: Global optimisation of nonconvex MINLPs. Comput. Chem. Eng. 21, S791–S796 (1997)

    Article  Google Scholar 

  66. Smith, E.M., Pantelides, C.C.: A symbolic reformulation/spatial branch-and-bound algorithm for the global optimisation of nonconvex MINLPs. Comput. Chem. Eng. 23(4–5), 457–478 (1999)

    Article  Google Scholar 

  67. Song, Y., Khan, K.A.: Comparing solutions of related ordinary differential equations using new differential inequalities. Under review

  68. Stuber, M.D., Scott, J.K., Barton, P.I.: Convex and concave relaxations of implicit functions. Optim. Methods Softw. 30(3), 424–460 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  69. Tawarmalani, M., Sahinidis, N.V.: Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications. Springer, Dordrecht (2002)

    Book  MATH  Google Scholar 

  70. Tawarmalani, M., Sahinidis, N.V.: A polyhedral branch-and-cut approach to global optimization. Math. Program. 103(2), 225–249 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  71. Thibault, L.: On subdifferentials of optimal value functions. SIAM J. Control Optim. 29(5), 1019–1036 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  72. Tsoukalas, A., Mitsos, A.: Multivariate McCormick relaxations. J. Global Optim. 59(2–3), 633–662 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  73. Villanueva, M.E., Houska, B., Chachuat, B.: Unified framework for the propagation of continuous-time enclosures for parametric nonlinear ODEs. J. Global Optim. 62(3), 575–613 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  74. Wächter, A., Biegler, L.T.: On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math. Program. 106(1), 25–57 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  75. Walter, W.: Differential and Integral Inequalities. Springer, New York (1970)

    Book  Google Scholar 

  76. Watson, H.A., Vikse, M., Gundersen, T., Barton, P.I.: Optimization of single mixed-refrigerant natural gas liquefaction processes described by nondifferentiable models. Energy 150, 860–876 (2018)

    Article  Google Scholar 

  77. Wechsung, A., Schaber, S.D., Barton, P.I.: The cluster problem revisited. J. Global Optim. 58(3), 429–438 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  78. Wilhelm, M., Stuber, M.D.: Easy Advanced Global Optimization (EAGO): An open-source platform for robust and global optimization in Julia. In: 2017 AIChE Annual Meeting. AIChE (2017)

  79. Wilhelm, M.E., Le, A.V., Stuber, M.D.: Global optimization of stiff dynamical systems. AIChE J 65(12), e16836 (2019)

    Article  Google Scholar 

  80. Yang, X., Scott, J.K.: Efficient reachability bounds for discrete-time nonlinear systems by extending the continuous-time theory of differential inequalities. In: 2018 Annual American Control Conference (ACC), pp. 6242–6247. IEEE (2018)

Download references

Author information

Authors and Affiliations

  1. Department of Chemical Engineering, McMaster University, Hamilton, ON, Canada

    Yingkai Song & Kamil A. Khan

Authors
  1. Yingkai Song
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Kamil A. Khan
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Kamil A. Khan.

Ethics declarations

Conflict of interest

The authors declare that they have no conflict of interest.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This work was supported by the Natural Sciences and Engineering Research Council of Canada (NSERC) under Grant RGPIN-2017-05944.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Song, Y., Khan, K.A. Optimization-based convex relaxations for nonconvex parametric systems of ordinary differential equations. Math. Program. 196, 521–565 (2022). https://doi.org/10.1007/s10107-021-01654-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-021-01654-x

Keywords

Mathematics Subject Classification

Search

Navigation