Approximation properties of sum-up rounding in the presence of vanishing constraints

Authors:
Paul Manns, Christian Kirches and Felix Lenders

Journal:
Math. Comp. **90** (2021), 1263-1296

MSC (2020):
Primary 90C59; Secondary 49M20, 49M25

DOI:
https://doi.org/10.1090/mcom/3606

Published electronically:
February 18, 2021

MathSciNet review:
4232224

Full-text PDF

Abstract | References | Similar Articles | Additional Information

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.

- L. D. Berkovitz,
*Optimal control theory*, Applied Mathematical Sciences, Vol. 12, Springer-Verlag, New York-Heidelberg, 1974. MR**0372707** - 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, Calif., 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.

Retrieve articles in *Mathematics of Computation*
with MSC (2020):
90C59,
49M20,
49M25

Retrieve articles in all journals with MSC (2020): 90C59, 49M20, 49M25

Additional 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

Keywords:
Discrete approximations,
error estimates,
relaxations of mixed integer optimal control

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.

Article copyright:
© Copyright 2021
American Mathematical Society