×

Relaxed multibang regularization for the combinatorial integral approximation. (English) Zbl 1469.49029

Summary: Multibang regularization and combinatorial integral approximation decompositions are two actively researched techniques for integer optimal control. We consider a class of polyhedral functions that arise particularly as convex lower envelopes of multibang regularizers and show that they have beneficial properties with respect to regularization of relaxations of integer optimal control problems. We extend the algorithmic framework of the combinatorial integral approximation such that a subsequence of the computed discrete-valued controls converges to the infimum of the regularized integer control problem.

MSC:

49M20 Numerical methods of relaxation type
90C11 Mixed integer programming
93C65 Discrete event control/observation systems
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] J. A. E. Andersson, J. Gillis, G. Horn, J. B. Rawlings, and M. Diehl, CasADi-A software framework for nonlinear optimization and optimal control, Math. Program. Comput., 11 (2019), pp. 1-36. · Zbl 1411.90004
[2] F. Bestehorn, C. Hansknecht, C. Kirches, and P. Manns, A switching cost aware rounding method for relaxations of mixed-integer optimal control problems, in Proceedings of the 58th Conference on Decision and Control (CDC), IEEE, 2019, pp. 7134-7139.
[3] F. Bestehorn, C. Hansknecht, C. Kirches, and P. Manns, Mixed-integer optimal control problems with switching costs: a shortest path approach, Math. Program., (2020), pp. 1-32.
[4] V. Böhm, On the continuity of the optimal policy set for linear programs, SIAM J. Appl. Math., 28 (1975), pp. 303-306. · Zbl 0294.90047
[5] T. Borrvall and J. Petersson, Topology optimization using regularized intermediate density control, Comput. Methods Appl. Mech. Engrg., 190 (2001), pp. 4911-4928. · Zbl 1022.74035
[6] M. A. Branch, T. F. Coleman, and Y. Li, A subspace, interior, and conjugate gradient method for large-scale bound-constrained minimization problems, SIAM J. Sci. Comput., 21 (1999), pp. 1-23. · Zbl 0940.65065
[7] C. Buchheim, A. Caprara, and A. Lodi, An effective branch-and-bound algorithm for convex quadratic integer programming, Math. Program., 135 (2012), pp. 369-395. · Zbl 1254.90121
[8] C. Clason, F. Kruse, and K. Kunisch, Total variation regularization of multi-material topology optimization, ESAIM Math. Model. Numer. Anal., 52 (2018), pp. 275-303. · Zbl 1397.49056
[9] C. Clason and K. Kunisch, Multi-bang control of elliptic systems, Ann. Inst. H. Poincaré Anal. Non Linéaire, 31 (2014), pp. 1109-1130. · Zbl 1304.49014
[10] C. Clason and K. Kunisch, A convex analysis approach to multi-material topology optimization, ESAIM Math. Model. Numer. Anal., 50 (2016), pp. 1917-1936. · Zbl 1354.49092
[11] C. Clason, C. Tameling, and B. Wirth, Vector-valued multibang control of differential equations, SIAM J. Control Optim., 56 (2018), pp. 2295-2326. · Zbl 1393.49007
[12] G. Dal Maso, An Introduction to \(\Gamma \)-Convergence, Progr. Nonlinear Differential Equations Appl. 8, Birkhäuser Basel, 1993. · Zbl 0816.49001
[13] I. Fonseca and G. Leoni, Modern Methods in the Calculus of Variations: \(L^p\) Spaces, Springer, Berlin, 2007. · Zbl 1153.49001
[14] D. Garmatter, M. Porcelli, F. Rinaldi, and M. Stoll, Improved penalty algorithm for mixed integer PDE Constrained Optimization (Mipdeco) Problems, preprint, arXiv:1907.06462, 2019.
[15] H. Goldberg, W. Kampowsky, and F. Tröltzsch, On Nemytskij operators in Lp-spaces of abstract functions, Math. Nachr., 155 (1992), pp. 127-140. · Zbl 0760.47031
[16] M. Gugat and F. Hante, On the turnpike phenomenon for optimal boundary control problems with hyperbolic systems, SIAM J. Control Optim., 57 (2019), pp. 264-289. · Zbl 1418.35252
[17] F. M. Hante and S. Sager, Relaxation methods for mixed-integer optimal control of partial differential equations, Comput. Optim. Appl., 55 (2013), pp. 197-225. · Zbl 1272.49026
[18] J. Haslinger and R. A. E. Mäkinen, On a topology optimization problem governed by two-dimensional Helmholtz equation, Comput. Optim. Appl., 62 (2015), pp. 517-544. · Zbl 1333.49063
[19] C. J. Himmelberg, T. Parthasarathy, and F. S. Van Vleck, Optimal plans for dynamic programming problems, Math. Oper. Res., 1 (1976), pp. 390-394. · Zbl 0368.90134
[20] M. Jung, Relaxations and Approximations for Mixed-Integer Optimal Control, PhD thesis, Heidelberg University, 2013.
[21] M. N. Jung, G. Reinelt, and S. Sager, The Lagrangian relaxation for the combinatorial integral approximation problem, Optim. Methods Softw., 30 (2015), pp. 54-80. · Zbl 1325.49028
[22] C. Kirches, F. Lenders, and P. Manns, Approximation properties and tight bounds for constrained mixed-integer optimal control, SIAM J. Control Optim., 58 (2020), pp. 1371-1402. · Zbl 1443.49033
[23] C. Kirches, P. Manns, and S. Ulbrich, Compactness and convergence rates in the combinatorial integral approximation decomposition, Math. Program., 2020, pp. 1-30.
[24] K. Kuratowski and C. Ryll-Nardzewski, A general theorem on selectors, Bull. Acad. Polon. Sci. Sér. Math. Astronom. Phys., 13 (1965), pp. 397-403. · Zbl 0152.21403
[25] S. Leyffer, P. Manns, and M. Winckler, Convergence of sum-up rounding schemes for cloaking problems governed by the Helmholtz equation, Comput. Optim. Appl., 79 (2021), pp. 1-29. · Zbl 1470.90052
[26] A. A. Lyapunov, On completely additive vector functions, Izv. Akad. Nauk SSSR, 4 (1940), pp. 465-478. · JFM 66.0219.02
[27] O. L. Mangasarian and T.-H. Shiau, Lipschitz continuity of solutions of linear inequalities, programs and complementarity problems, SIAM J. Control Optim., 25 (1987), pp. 583-595. · Zbl 0613.90066
[28] P. Manns and C. Kirches, Improved regularity assumptions for partial outer convexification of mixed-integer PDE-constrained optimization problems, ESAIM Control Optim. Calc. Var., 26 (2020). · Zbl 1439.49023
[29] P. Manns and C. Kirches, Multidimensional sum-up rounding for elliptic control systems, SIAM J. Numer. Anal., 58 (2020), pp. 3427-3447. · Zbl 1455.49017
[30] P. Manns, C. Kirches, and F. Lenders, Approximation properties of sum-up rounding in the presence of vanishing constraints, Math. Comput., 90 (2021), pp. 1263-1296. · Zbl 1462.49053
[31] M. Renardy and R. C. Rogers, An Introduction to Partial Differential Equations, Texts Appl. Math. 13, Springer, Berlin, 2006. · Zbl 1072.35001
[32] R. T. Rockafellar and R. J. B. Wets, Variational Analysis, Springer, Berlin, 2004. · Zbl 0888.49001
[33] S. Sager, Numerical Methods for Mixed-Integer Optimal Control Problems, Der andere Verlag Tönning, Lübeck, Marburg, 2005. · Zbl 1094.65512
[34] S. Sager, A benchmark library of mixed-integer optimal control problems, in Mixed Integer Nonlinear Programming, Springer, Berlin, 2012, pp. 631-670. · Zbl 1242.90309
[35] S. Sager, Sampling decisions in optimum experimental design in the light of Pontryagin’s maximum principle, SIAM J. Control Optim., 51 (2013), pp. 3181-3207. · Zbl 1292.62112
[36] S. Sager, H.-G. Bock, and M. Diehl, The integer approximation error in mixed-integer optimal control, Math. Program. Ser. A, 133 (2012), pp. 1-23. · Zbl 1259.90077
[37] S. Sager, H. G. Bock, M. Diehl, G. Reinelt, and J. P. Schlöder, Numerical methods for optimal control with binary control functions applied to a Lotka-Volterra type fishing problem, in Recent Advances in Optimization, Springer, Berlin, 2006, pp. 269-289. · Zbl 1107.49023
[38] S. Sager, M. Jung, and C. Kirches, Combinatorial integral approximation, Math. Methods Oper. Res., 73 (2011), pp. 363-380. · Zbl 1220.90073
[39] M. Sharma, M. Hahn, S. Leyffer, L. Ruthotto, and B. van Bloemen Waanders, Inversion of convection-diffusion equation with discrete sources, Optim. Eng., 2020, pp. 1-39.
[40] G. Stadler, Elliptic optimal control problems with L1-control cost and applications for the placement of control devices, Comput. Optim. Appl., 44 (2009). · Zbl 1185.49031
[41] E. M. Stein and R. Shakarchi, Real analysis: Measure theory, integration, and Hilbert spaces, Princeton University Press, Princeton, NJ, 2005. · Zbl 1081.28001
[42] L. Tartar, Compensated compactness and applications to partial differential equations, in Nonlinear Analysis and Mechanics: Heriot-Watt Symposium, Vol. 4, 1979, pp. 136-212. · Zbl 0437.35004
[43] P. Virtanen, R. Gommers, T. E. Oliphant, M. Haberland, T. Reddy, D. Cournapeau, E. Burovski, P. Peterson, W. Weckesser, J. Bright, S. J. van der Walt, M. Brett, J. Wilson, K. J. Millman, N. Mayorov, A. R. J. Nelson, E. Jones, R. Kern, P. van Mulbregt, et al., SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python, Nat. Methods, 17 (2020), pp. 261-272.
[44] C. Voglis and I. E. Lagaris, A rectangular trust region dogleg approach for unconstrained and bound constrained nonlinear optimization, in Proceedings of the WSEAS 6th International Conference on Applied Mathematics, 2004, pp. 1-7.
[45] A. Wächter and L. T. Biegler, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program., 106 (2006), pp. 25-57. · Zbl 1134.90542
[46] J. Yu and M. Anitescu, Multidimensional sum-up rounding for integer programming in optimal experimental design, Math. Program., 185 (2021), pp. 37-76. · Zbl 1458.62158
[47] C. Zeile, N. Robuschi, and S. Sager, Mixed-integer optimal control under minimum dwell time constraints, Math. Program., (2020), pp. 1-42.
[48] C. Zeile, T. Weber, and S. Sager, Combinatorial integral approximation decompositions for mixed-integer optimal control, Optimization Online, Preprint 6472, 2018.
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.