×

Approximation properties of sum-up rounding in the presence of vanishing constraints. (English) Zbl 1462.49053

Summary: 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.

MSC:

49M20 Numerical methods of relaxation type
49M25 Discrete approximations in optimal control
90C59 Approximation methods and heuristics in mathematical programming
49J45 Methods involving semicontinuity and convergence; relaxation

Software:

Ipopt; Mintoc; SODAS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Berkovitz, L. D., Optimal Control Theory, Applied Mathematical Sciences, Vol. 12, ix+304 pp. (1974), Springer-Verlag, New York-Heidelberg · Zbl 0295.49001
[2] Bestehorn, F.; Hansknecht, C.; Kirches, C.; Manns, P., A switching cost aware rounding method for relaxations of mixed-integer optimal control problems, Proceedings of the 58th {IEEE} {C}onference on {D}ecision and {C}ontrol, 7134-7139 (2019)
[3] Bock, H. G.; Longman, R. W., Optimal control of velocity profiles for minimization of energy consumption in the {N}ew {Y}ork subway system, Proceedings of the {S}econd {IFAC} {W}orkshop on {C}ontrol {A}pplications of {N}onlinear {P}rogramming and {O}ptimization, 34-43 (1980)
[4] Cesari, Lamberto, Optimization-Theory and Applications, Applications of Mathematics (New York) 17, xiv+542 pp. (1983), Springer-Verlag, New York · Zbl 0506.49001 · doi:10.1007/978-1-4613-8165-5
[5] Fla{\ss}kamp, K.; Murphy, T.; Ober-Bl\"{o}baum, S., Switching time optimization in discretized hybrid dynamical systems, Proceedings of the 51st {IEEE} {C}onference on {D}ecision and {C}ontrol, 707-712 (2012)
[6] Garey, Michael R.; Johnson, David S., Computers and Intractability, A Series of Books in the Mathematical Sciences, x+338 pp. (1979), W. H. Freeman and Co., San Francisco, Calif. · Zbl 0411.68039
[7] Gerdts, Matthias, Solving mixed-integer optimal control problems by branch&bound: a case study from automobile test-driving with gear shift, Optimal Control Appl. Methods, 26, 1, 1-18 (2005) (2005) · doi:10.1002/oca.751
[8] Gerdts, Matthias, A variable time transformation method for mixed-integer optimal control problems, Optimal Control Appl. Methods, 27, 3, 169-182 (2006) · doi:10.1002/oca.778
[9] Hahn, M.; Kirches, C.; Manns, P.; Sager, S.; Zeile, C., Decomposition and approximation for pde-constrained mixed-integer optimal control, DFG SPP1962 Special Issue (2021), Birkh\"{a}user
[10] Hante, Falk M.; Sager, Sebastian, Relaxation methods for mixed-integer optimal control of partial differential equations, Comput. Optim. Appl., 55, 1, 197-225 (2013) · Zbl 1272.49026 · doi:10.1007/s10589-012-9518-3
[11] Hoheisel, T., Mathematical {P}rograms with {V}anishing {C}onstraints (2009)
[12] Jung, Michael N.; Kirches, Christian; Sager, Sebastian, On perspective functions and vanishing constraints in mixed-integer nonlinear optimal control. Facets of combinatorial optimization, 387-417 (2013), Springer, Heidelberg · Zbl 1320.49011 · doi:10.1007/978-3-642-38189-8\_16
[13] Jung, Michael N.; Kirches, Christian; Sager, Sebastian; Sass, Susanne, Computational approaches for mixed integer optimal control problems with indicator constraints, Vietnam J. Math., 46, 4, 1023-1051 (2018) · Zbl 1405.49002 · doi:10.1007/s10013-018-0313-z
[14] Kirches, C.; Lenders, F.; Manns, P., Approximation properties and tight bounds for constrained mixed-integer optimal control, SIAM J. Control Optim., 58, 3, 1371-1402 (2020) · Zbl 1443.49033 · doi:10.1137/18M1182917
[15] Lenders, F., Numerical {M}ethods for {M}ixed-{I}nteger {O}ptimal {C}ontrol with {C}ombinatorial {C}onstraints (2018)
[16] Manns, Paul; Kirches, Christian, Improved regularity assumptions for partial outer convexification of mixed-integer PDE-constrained optimization problems, ESAIM Control Optim. Calc. Var., 26, Paper No. 32, 16 pp. (2020) · Zbl 1439.49023 · doi:10.1051/cocv/2019016
[17] Manns, Paul; Kirches, Christian, Multidimensional sum-up rounding for elliptic control systems, SIAM J. Numer. Anal., 58, 6, 3427-3447 (2020) · Zbl 1455.49017 · doi:10.1137/19M1260682
[18] Sager, S., Numerical methods for mixed-integer optimal control problems (2005), Der andere Verlag T{\"o}nning, L{\"u}beck, Marburg
[19] Sager, S., Reformulations and algorithms for the optimization of switching decisions in nonlinear optimal control, Journal of {P}rocess {C}ontrol, 19, 8, 1238-1247 (2009)
[20] Sager, Sebastian, A benchmark library of mixed-integer optimal control problems. Mixed integer nonlinear programming, IMA Vol. Math. Appl. 154, 631-670 (2012), Springer, New York · Zbl 1242.90309
[21] Sager, Sebastian; Bock, Hans Georg; Diehl, Moritz, The integer approximation error in mixed-integer optimal control, Math. Program., 133, 1-2, Ser. A, 1-23 (2012) · Zbl 1259.90077 · doi:10.1007/s10107-010-0405-3
[22] Sager, Sebastian; Jung, Michael; Kirches, Christian, Combinatorial integral approximation, Math. Methods Oper. Res., 73, 3, 363-380 (2011) · Zbl 1220.90073 · doi:10.1007/s00186-011-0355-4
[23] Sager, Sebastian; Bock, Hans Georg; Reinelt, Gerhard, Direct methods with maximal lower bound for mixed-integer optimal control problems, Math. Program., 118, 1, Ser. A, 109-149 (2009) · Zbl 1160.49032 · doi:10.1007/s10107-007-0185-6
[24] Tauchnitz, N., Das {P}ontrjaginsche {M}aximumprinzip f\"{u}r eine {K}lasse hybrider {S}teuerungsprobleme mit {Z}ustandsbeschr\"{a}nkungen und seine {A}nwendung (2010)
[25] Vasudevan, Ramanarayan; Gonzalez, Humberto; Bajcsy, Ruzena; Sastry, S. Shankar, Consistent approximations for the optimal control of constrained switched systems-Part 1: A conceptual algorithm, SIAM J. Control Optim., 51, 6, 4463-4483 (2013) · Zbl 1288.49003 · doi:10.1137/120901490
[26] Vasudevan, Ramanarayan; Gonzalez, Humberto; Bajcsy, Ruzena; Sastry, S. Shankar, Consistent approximations for the optimal control of constrained switched systems-Part 1: A conceptual algorithm, SIAM J. Control Optim., 51, 6, 4463-4483 (2013) · Zbl 1288.49003 · doi:10.1137/120901490
[27] W\"{a}chter, Andreas; Biegler, Lorenz T., On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program., 106, 1, Ser. A, 25-57 (2006) · Zbl 1134.90542 · doi:10.1007/s10107-004-0559-y
[28] Yu, Jing; Anitescu, Mihai, Multidimensional sum-up rounding for integer programming in optimal experimental design, Mathematical Programming, 1-40 (2019)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.