Convergence of finite-dimensional approximations for mixed-integer optimization with differential equations

• Autorzy: Hante Falk M. , Schmidt Martin
• Języki publikacji: EN

Abstrakty

EN

We consider a direct approach to solving the mixedinteger nonlinear optimization problems with constraints depending on initial and terminal conditions of an ordinary differential equation. In order to obtain a finite-dimensional problem, the dynamics are approximated using discretization methods. In the framework of general one-step methods, we provide sufficient conditions for the convergence of this approach in the sense of the corresponding optimal values. The results are obtained by considering the discretized problem as a parametric mixed-integer nonlinear optimization problem in finite dimensions, where the step size for discretization of the dynamics is the parameter. In this setting, we prove the continuity of the optimal value function under a stability assumption for the integer feasible set and second-order conditions from nonlinear optimization. We address the necessity of the conditions on the example of pipe sizing problems for gas networks.

Słowa kluczowe

EN

optimization; differential equations; optimal value function; Lipschitz continuity; parametric optimization; mixed integer nonlinear programming

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2019
• Tom: Vol. 48, No. 2
• Strony: 209--226
• Opis fizyczny: Bibliogr. 36 poz.

Twórcy

autor

Hante Falk M.

• Friedrich-Alexander-Universität Erlangen-Nürnberg, Angewandte Mathematik 2, Cauerstr. 11, 91058 Erlangen, Germany

autor

Schmidt Martin

• Trier University, Department of Mathematics, Universitätsring 15, 54296 Trier, Germany

Bibliografia

• Bachmann, F., Beermann, D., Lu, J. and Volkwein, S. (2017) PODBased Mixed-Integer Optimal Control of the Heat Equation. In: IHP Me3: Recent Developments in Numerical Methods for Model Reduction. Ed. by Gianluigi Rozza. Journal of Scientific Computing. Springer, 2017. url: http://nbn-resolving.de/urn:nbn:de:bsz:352-0-408645.
• Bank, B. and Hansel, R. (1984) Stability of mixed-integer quadratic programming problems. In: Math. Programming Stud. 21 (1984). Sensitivity, stability and parametric analysis, 1-17. doi: 10.1007/bfb0121208.
• Bertsekas, D. P. (2016) Nonlinear Programming. Athena Scientific, Belmont.
• Bragalli, C., D’Ambrosio, C., Lee, J., Lodi, A. and Toth, P. (2006) An MINLP Solution Method for a Water Network Problem. In: Algorithms ESA 2006, Yossi Azar and Thomas Erlebach, eds., Lecture Notes in Computer Science. 4168 Springer, Berlin Heidelberg, 696–707.
• Bragalli, C., D’Ambrosio, C., Lee, J., Lodi, A. and Toth, P. (2012) On the optimal design of water distribution networks: a practical MINLP approach. Optimization and Engineering 13(2), 219–246.
• Chen, Z. and Han, Y. (2012) Quantitative stability of mixed-integer twostage quadratic stochastic programs. Mathematical Methods of Operations Research 75(2), 149–163.
• Chvátal, V. (1983) Linear Programming. A Series of Books in the Mathematical Sciences. Freeman, New York.
• Elbinger, T., Gahn, M., Neuss-Radu, M., Hante, F. M., Voll, L. M., Leugering, G. and Knabner, P. (2016) Model based design of biochemical micro-reactors. Frontiers in Bioengineering and Biotechnology 4(13).
• Fügenschuh, A., Geisler, B., Gollmer, R., Morsi, A., Pfetsch, M., Rövekamp, E., Schmidt, M., Spreckelsen, K. and Steinbach, M. C. (2015) Physical and technical fundamentals of gas networks. In: Evaluating Gas Network Capacities, Thorsten Koch, Benjamin Hiller, Marc E. Pfetsch and Lars Schewe, eds. SIAM-MOS series on Optimization. SIAM, 17–44.
• Gugat, M. (1994) One-sided derivatives for the value function in convex parametric programming. Optimization 28(3-4), 301-314.
• Gugat, M.(1997) Parametric disjunctive programming: one-sided differentiability of the value function. Journal of Optimization Theory and Applications 92(2), 285–310.doi: 10.1023/A:1022603112856.
• Gugat, M. and Hante, F. M. (2016) Lipschitz continuity of the value function in mixed-integer optimal control problems. Mathematics of Control, Signals, and Systems 29(1).doi: 10.1007/s00498-016-0183-4.
• Gugat, M., Leugering, G., Martin, A., Schmidt, M., Sirvent, M. And Wintergerst, D. (2018) MIP-Based Instantaneous Control of Mixed-Integer PDE-Constrained Gas Transport Problems. Computational Optimization and Applications 70(1), 267-294.doi: 10.1007/s10589-017-9970-1.
• Gugat, M., Leugering, G., Martin, A., Schmidt, M., Sirvent, M. and Wintergerst, D. (2018) Towards Simulation Based Mixed-Integer Optimization with Differential Equations. Networks 72(1), 60–83.
• Habeck, O., Pfetsch, M. E., and Ulbrich, S. (2017) Global optimization of mixed-integer ODE constrained network problems using the example of stationary gas transport. Technische Universität Darmstadt.
• Hairer, E., Norsett, S. P. and Wanner, G. (1993) Solving Ordinary Differential Equations I. Nonstiff Problems. 2nd ed. Springer Series in Computational Mathematics. Springer-Verlag Berlin Heidelberg.
• Han, Y. and Chen, Z. (2015) Continuity of parametric mixed-integer quadratic programs and its application to stability analysis of two-stage quadratic stochastic programs with mixed-integer recourse. Optimization 64(9), 1983–1997.
• Hante, F. M. and Leugering, G. (2009) Optimal boundary control of convention-reaction transport systems with binary control functions. In: Hybrid systems: computation and control. Lecture Notes in Comput. Sci, 5469. Berlin: Springer, 209–222.
• Hante, F. M., Leugering, G., Martin, A., Schewe, L. and Schmidt, M. (2017) Challenges in Optimal Control Problems for Gas and Fluid Flow in Networks of Pipes and Canals: From Modeling to Industrial Applications. In: Industrial Mathematics and Complex Systems: Emerging Mathematical Models, Methods and Algorithms. Ed. by P. Manchanda, R. Lozi and A. H. Siddiqi. Industrial and Applied Mathematics. Springer Singapore, Singapore, 77–122.
• Hante, F. M., Leugering, G. and Seidman, T. I. (2009) Modeling and analysis of modal switching in networked transport systems. Appl. Math. Optim. 59(2), 275–292.
• Hante, F. M., Leugering, G. and Seidman, T. I. (2010) An augmented BV setting for feedback switching control. J. Syst. Sci. Complex. 23(3), 456–466.
• Kawajiri, Y. and Biegler, L. T. (2005) Optimization strategies for simulated moving bed and PowerFeed processes. AIChE Journal 52(4), 1343–1350.
• Kufner, T., Leugering, G., Martin, A., Medgenberg, J., Schelbert, J., Schewe, L., Stingl, M., Strohmeyer, C. and Walther, M. (2018) Towards a lifecycle oriented design of infrastructure by mathematical optimization. Optimization and Engineering. doi: 10.1007/s11081-018-9406-5.
• Leugering, G., Martin, A., Schmidt, M. and Sirvent, M. (2017) Nonoverlapping Domain Decomposition for Optimal Control Problems governed by Semilinear Models for Gas Flow in Networks. Control and Cybernetics 46(3), 191–225.
• Leugering, G. and Georg Schmidt, J. P. (2002) On the modelling and stabilization of flows in networks of open canals. SIAM J. Control Optim. 41(1), 164–180.
• Mills, H. D. (1956) Marginal values of matrix games and linear programs. In: Linear Inequalities and Related Systems, ed. by H. W. Kuhn and A. W. Tucker. Princeton University Press, 183–193.
• Polak, E. (1973) An historical survey of computational methods in optimal control. SIAM Rev. 15. Twentieth anniversary of the Society for Industrial and Applied Mathematics, Special lectures. Philadelphia, 553-584.
• Quarteroni, A., Sacco, R. and Saleri, F. (2007) Numerical Mathematics. 2nd ed. Texts in Applied Mathematics. Springer-Verlag, Berlin-Heidelberg.
• Sager, S. (2012) A benchmark library of mixed-integer optimal control problems. Mixed Integer Nonlinear Programming, 154. IMA Vol. Math. Appl. Springer, New York, 631–670.
• Schmidt, M., Steinbach, M. C. and Willert, B. M. (2015a) High detail stationary optimization models for gas networks. Optimization and Engineering, 16(1), 131–164.
• Schmidt, M., Steinbach, M. C. and Willert, B. M. (2015b) The precise NLP model. In: Evaluating Gas Network Capacities, ed. by T. Koch, B. Hiller, M. E. Pfetsch and L. Schewe. SIAM-MOS series on Optimization. SIAM, 181–210.
• Schmidt, M., Steinbach, M. C. and Willert, B. M. (2016) High detail stationary optimization models for gas networks: validation and results. Optimization and Engineering, 17(2), 437–472.
• Strehmel, K. and Weiner, R. (1995) Numerik gewöhnlicher Differentialgleichungen. Teubner Studienbücher Mathematik. [Teubner Mathematical Textbooks]. B. G. Teubner, Stuttgart, 462.
• Teschl, G. (2012) Ordinary Differential Equations and Dynamical Systems. Graduate Studies in Mathematics, 140. American Mathematical Society, Providence.
• Williams, A. C. (1963) Marginal Values in Linear Programming. Journal of the Society for Industrial and Applied Mathematics, 11(1), 82–94.
• Williams, A. C. (1989) Marginal values in mixed integer linear programming. Mathematical Programming 44(1), 67–75.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).