Approximation properties of sum-up rounding in the presence of vanishing constraints
HTML articles powered by AMS MathViewer
- by Paul Manns, Christian Kirches and Felix Lenders;
- Math. Comp. 90 (2021), 1263-1296
- DOI: https://doi.org/10.1090/mcom/3606
- Published electronically: February 18, 2021
- HTML | PDF | Request permission
Abstract:
Approximation algorithms like sum-up rounding that allow to compute integer-valued approximations of the continuous controls in a weak$^*$ sense have attracted interest recently. They allow to approximate (optimal) feasible solutions of continuous relaxations of mixed-integer control problems (MIOCPs) with integer controls arbitrarily close. To this end, they use compactness properties of the underlying state equation, a feature that is tied to the infinite-dimensional vantage point. In this work, we consider a class of MIOCPs that are constrained by pointwise mixed state-control constraints.
We show that a continuous relaxation that involves so-called vanishing constraints has beneficial properties for the described approximation methodology. Moreover, we complete recent work on a variant of the sum-up rounding algorithm for this problem class. In particular, we prove that the observed infeasibility of the produced integer-valued controls vanishes in an $L^\infty$-sense with respect to the considered relaxation. Moreover, we improve the bound on the control approximation error to a value that is asymptotically tight.
References
- L. D. Berkovitz, Optimal control theory, Applied Mathematical Sciences, Vol. 12, Springer-Verlag, New York-Heidelberg, 1974. MR 372707
- F. Bestehorn, C. Hansknecht, C. Kirches, and P. Manns, A switching cost aware rounding method for relaxations of mixed-integer optimal control problems, Proceedings of the 58th IEEE Conference on Decision and Control, 2019, pp. 7134–7139.
- H. G. Bock and R. W. Longman, Optimal control of velocity profiles for minimization of energy consumption in the New York subway system, Proceedings of the Second IFAC Workshop on Control Applications of Nonlinear Programming and Optimization, 1980, pp. 34–43.
- Lamberto Cesari, Optimization—theory and applications, Applications of Mathematics (New York), vol. 17, Springer-Verlag, New York, 1983. Problems with ordinary differential equations. MR 688142, DOI 10.1007/978-1-4613-8165-5
- K. Flaßkamp, T. Murphy, and S. Ober-Blöbaum, Switching time optimization in discretized hybrid dynamical systems, Proceedings of the 51st IEEE Conference on Decision and Control, 2012, pp. 707–712.
- Michael R. Garey and David S. Johnson, Computers and intractability, A Series of Books in the Mathematical Sciences, W. H. Freeman and Co., San Francisco, CA, 1979. A guide to the theory of NP-completeness. MR 519066
- Matthias Gerdts, Solving mixed-integer optimal control problems by branch&bound: a case study from automobile test-driving with gear shift, Optimal Control Appl. Methods 26 (2005), no. 1, 1–18 (2005). MR 2119264, DOI 10.1002/oca.751
- Matthias Gerdts, A variable time transformation method for mixed-integer optimal control problems, Optimal Control Appl. Methods 27 (2006), no. 3, 169–182. MR 2232339, DOI 10.1002/oca.778
- M. Hahn, C. Kirches, P. Manns, S. Sager, and C. Zeile, Decomposition and approximation for pde-constrained mixed-integer optimal control, DFG SPP1962 Special Issue, 2021. (accepted).
- Falk M. Hante and Sebastian Sager, Relaxation methods for mixed-integer optimal control of partial differential equations, Comput. Optim. Appl. 55 (2013), no. 1, 197–225. MR 3041753, DOI 10.1007/s10589-012-9518-3
- T. Hoheisel, Mathematical Programs with Vanishing Constraints, Dissertation, Julius–Maximilians–Universität Würzburg, 2009.
- Michael N. Jung, Christian Kirches, and Sebastian Sager, On perspective functions and vanishing constraints in mixed-integer nonlinear optimal control, Facets of combinatorial optimization, Springer, Heidelberg, 2013, pp. 387–417. MR 3156587, DOI 10.1007/978-3-642-38189-8_{1}6
- Michael N. Jung, Christian Kirches, Sebastian Sager, and Susanne Sass, Computational approaches for mixed integer optimal control problems with indicator constraints, Vietnam J. Math. 46 (2018), no. 4, 1023–1051. MR 3878792, DOI 10.1007/s10013-018-0313-z
- C. Kirches, F. Lenders, and P. Manns, Approximation properties and tight bounds for constrained mixed-integer optimal control, SIAM J. Control Optim. 58 (2020), no. 3, 1371–1402. MR 4101363, DOI 10.1137/18M1182917
- F. Lenders, Numerical Methods for Mixed-Integer Optimal Control with Combinatorial Constraints, Dissertation, Heidelberg University, 2018.
- Paul Manns and Christian Kirches, Improved regularity assumptions for partial outer convexification of mixed-integer PDE-constrained optimization problems, ESAIM Control Optim. Calc. Var. 26 (2020), Paper No. 32, 16. MR 4082471, DOI 10.1051/cocv/2019016
- Paul Manns and Christian Kirches, Multidimensional sum-up rounding for elliptic control systems, SIAM J. Numer. Anal. 58 (2020), no. 6, 3427–3447. MR 4189728, DOI 10.1137/19M1260682
- S. Sager, Numerical methods for mixed-integer optimal control problems, Der andere Verlag Tönning, Lübeck, Marburg, 2005.
- S. Sager, Reformulations and algorithms for the optimization of switching decisions in nonlinear optimal control, Journal of Process Control 19 (2009), no. 8, 1238–1247.
- Sebastian Sager, A benchmark library of mixed-integer optimal control problems, Mixed integer nonlinear programming, IMA Vol. Math. Appl., vol. 154, Springer, New York, 2012, pp. 631–670. MR 3587647
- Sebastian Sager, Hans Georg Bock, and Moritz Diehl, The integer approximation error in mixed-integer optimal control, Math. Program. 133 (2012), no. 1-2, Ser. A, 1–23. MR 2921089, DOI 10.1007/s10107-010-0405-3
- Sebastian Sager, Michael Jung, and Christian Kirches, Combinatorial integral approximation, Math. Methods Oper. Res. 73 (2011), no. 3, 363–380. MR 2805938, DOI 10.1007/s00186-011-0355-4
- Sebastian Sager, Hans Georg Bock, and Gerhard Reinelt, Direct methods with maximal lower bound for mixed-integer optimal control problems, Math. Program. 118 (2009), no. 1, Ser. A, 109–149. MR 2470887, DOI 10.1007/s10107-007-0185-6
- N. Tauchnitz, Das Pontrjaginsche Maximumprinzip für eine Klasse hybrider Steuerungsprobleme mit Zustandsbeschränkungen und seine Anwendung, Dissertation, BTU Cottbus, 2010.
- Ramanarayan Vasudevan, Humberto Gonzalez, Ruzena Bajcsy, and S. Shankar Sastry, Consistent approximations for the optimal control of constrained switched systems—Part 1: A conceptual algorithm, SIAM J. Control Optim. 51 (2013), no. 6, 4463–4483. MR 3141747, DOI 10.1137/120901490
- Ramanarayan Vasudevan, Humberto Gonzalez, Ruzena Bajcsy, and S. Shankar Sastry, Consistent approximations for the optimal control of constrained switched systems—Part 1: A conceptual algorithm, SIAM J. Control Optim. 51 (2013), no. 6, 4463–4483. MR 3141747, DOI 10.1137/120901490
- Andreas Wächter and Lorenz T. Biegler, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program. 106 (2006), no. 1, Ser. A, 25–57. MR 2195616, DOI 10.1007/s10107-004-0559-y
- Jing Yu and Mihai Anitescu, Multidimensional sum-up rounding for integer programming in optimal experimental design, Mathematical Programming (2019), 1–40.
Bibliographic Information
- Paul Manns
- Affiliation: Institute for Mathematical Optimization, Technische Universität Braunschweig, 38106 Braunschweig, Germany
- MR Author ID: 1201468
- ORCID: 0000-0003-0654-6613
- Email: paul.manns@tu-bs.de
- Christian Kirches
- Affiliation: Institute for Mathematical Optimization, Technische Universität Braunschweig, 38106 Braunschweig, Germany
- MR Author ID: 899522
- ORCID: 0000-0002-3441-8822
- Email: c.kirches@tu-bs.de
- Felix Lenders
- Affiliation: ABB Corporate Research, ABB AG, 68526 Ladenburg, Germany.
- ORCID: 0000-0003-3152-4221
- Email: felix.lenders@de.abb.com
- Received by editor(s): December 14, 2017
- Received by editor(s) in revised form: March 15, 2020, and September 25, 2020
- Published electronically: February 18, 2021
- Additional Notes: The first and second authors acknowledge funding by Deutsche Forschungsgemeinschaft through Priority Programme 1962, grants n^{o} KI1839/1-1 and KI1839/1-2. The second author acknowledges financial support by the German Federal Ministry of Education and Research, program “Mathematics for Innovations in Industry and Service”, grants n^{o} 05M2017-MoPhaPro, 05M2018-MOReNet, 05M2020-LEOPLAN, and program “IKT 2020: Software Engineering”, grant 01/S17089C-ODINE. The third author acknowledges funding by the German National Academic Foundation.
- © Copyright 2021 American Mathematical Society
- Journal: Math. Comp. 90 (2021), 1263-1296
- MSC (2020): Primary 90C59; Secondary 49M20, 49M25
- DOI: https://doi.org/10.1090/mcom/3606
- MathSciNet review: 4232224