We propose a trust-region method that solves a sequence of linear integer programs to tackle integer optimal control problems regularized with a total variation penalty. The total variation penalty implies that the considered integer control problems admit minimizers. We introduce a local optimality concept for the problem, which arises from the infinite-dimensional perspective. In the case of a one-dimensional domain of the control function, we prove convergence of the iterates produced by our algorithm to points that satisfy first-order stationarity conditions for local optimality. We demonstrate the theoretical findings on a computational example.
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/cocv/2022059
Keywords: Mixed-integer optimal control, total variation
@article{COCV_2022__28_1_A66_0,
author = {Leyffer, Sven and Manns, Paul},
title = {Sequential linear integer programming for integer optimal control with total variation regularization},
journal = {ESAIM: Control, Optimisation and Calculus of Variations},
year = {2022},
publisher = {EDP-Sciences},
volume = {28},
doi = {10.1051/cocv/2022059},
mrnumber = {4499180},
zbl = {1500.49016},
language = {en},
url = {https://www.numdam.org/articles/10.1051/cocv/2022059/}
}
TY - JOUR AU - Leyffer, Sven AU - Manns, Paul TI - Sequential linear integer programming for integer optimal control with total variation regularization JO - ESAIM: Control, Optimisation and Calculus of Variations PY - 2022 VL - 28 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/cocv/2022059/ DO - 10.1051/cocv/2022059 LA - en ID - COCV_2022__28_1_A66_0 ER -
%0 Journal Article %A Leyffer, Sven %A Manns, Paul %T Sequential linear integer programming for integer optimal control with total variation regularization %J ESAIM: Control, Optimisation and Calculus of Variations %D 2022 %V 28 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/cocv/2022059/ %R 10.1051/cocv/2022059 %G en %F COCV_2022__28_1_A66_0
Leyffer, Sven; Manns, Paul. Sequential linear integer programming for integer optimal control with total variation regularization. ESAIM: Control, Optimisation and Calculus of Variations, Tome 28 (2022), article no. 66. doi: 10.1051/cocv/2022059
[1] , and , Vol. 254 of Functions of bounded variation and free discontinuity problems. Clarendon Press Oxford (2000). | MR | Zbl
[2] , , and , A switching cost aware rounding method for relaxations of mixedinteger optimal control problems, in 2019 IEEE 58th Conference on Decision and Control (CDC). IEEE (2019) 7134–7139. | DOI
[3] , , and , Mixed-integer optimal control problems with switching costs: a shortest path approach. Math. Program. Ser. B 188 (2020) 621–652. | MR | Zbl | DOI
[4] , and , Total generalized variation. SIAM J. Imag. Sci. 3 (2010) 492–526. | MR | Zbl | DOI
[5] , and , An effective branch-and-bound algorithm for convex quadratic integer programming. Math. Program. 135 (2012) 369–395. | MR | Zbl | DOI
[6] , and , Exact relaxation for classes of minimization problems with binary constraints. arXiv preprint (2012). | arXiv | Zbl
[7] , Second order analysis for bang-bang control problems of PDEs. SIAM J. Control Optim. 50 (2012) 2355–2372. | MR | Zbl | DOI
[8] and , Image recovery via total variation minimization and related problems. Numer. Math. 76 (1997) 167–188. | MR | Zbl | DOI
[9] and , Total variation blind deconvolution. IEEE Trans. Image Process. 7 (1998) 370–375. | DOI
[10] , and , Total variation regularization of multi-material topology optimization. ESAIM: Math. Model. Numer. Anal. 52 (2018) 275–303. | MR | Zbl | Numdam | DOI
[11] and , Multi-bang control of elliptic systems, in vol. 31 of Annales de l'Institut Henri Poincaré (c) Analysé Non Linéaire. Elsevier (2014) 1109–1130. | MR | Zbl | Numdam | DOI
[12] , and , Vector-valued multibang control of differential equations. SIAM J. Control Optim. 56 (2018) 2295–2326. | MR | Zbl | DOI
[13] , On the mixed-integer linear-quadratic optimal control with switching cost. IEEE Control Syst. Lett. 3 (2019) 990–995. | MR | DOI
[14] and , Sparse switching times optimization and a sweeping Hessian proximal method, in Operations Research Proceedings 2019. Springer (2020), pp. 89–95. | MR | Zbl | DOI
[15] and , Analysis of regularized total variation penalty methods for denoising. Inverse Probl. 12 (1996) 601. | MR | Zbl | DOI
[16] , and , Optimal finite element error estimates for an optimal control problem governed by the wave equation with controls of bounded variation. IMA J. Numer. Anal. 41 (2021) 2639–2667. | MR | Zbl | DOI
[17] and , A trust region SQP algorithm for mixed-integer nonlinear programming. Optim. Lett. 1 (2007) 269–280. | MR | Zbl | DOI
[18] , and , Discretized switching time optimization problems, in 2013 European Control Conference (ECC). IEEE (2013) 3179–3184. | DOI
[19] and , Subspace correction methods for total variation and \ell_1-minimization. SIAM J. Numer. Anal. 47 (2009) 3397–3428. | MR | Zbl | DOI
[20] , , , , , , , , , , , , , , , , , , , , , , , , , , and , The SCIP Optimization Suite 7.0. ZIB-Report 20-10, Zuse Institute Berlin (2020).
[21] , Solving mixed-integer optimal control problems by Branch&Bound: a case study from automobile test-driving with gear shift. Opt. Control Appi. Methods 26 (2005) 1–18. | MR | DOI
[22] and , Dini derivatives in optimization – Part I. Riv. Mate. le Scienze Econ. Sociali 15 (1992) 3–30. | MR | Zbl
[23] , and , Partial outer convexification for traffic light optimization in road networks. SIAM J. Sci. Comput. 39 (2017) B53–B75. | MR | Zbl | DOI
[24] , and , Binary optimal control by trust-region steepest descent. To appear Math. Program. (2022). | Zbl
[25] , , , and , 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. Springer (2017) 77–122. | MR | Zbl | DOI
[26] and , Relaxation methods for mixed-integer optimal control of partial differential equations. Comput. Optim. Appl. 55 (2013) 197–225. | MR | Zbl | DOI
[27] and , Optimal selection of the regularization function in a weighted total variation model. Part I: Modelling and theory. J. Math. Imag. Vision 59 (2017) 498–514. | MR | Zbl | DOI
[28] , Optimal control of the double integrator with minimum total variation. J. Optim. Theory Appi. 185 (2020) 966–981. | MR | Zbl | DOI
[29] , , and , Mixed-integer NMPC for predictive cruise control of heavy-duty trucks, in 2013 European Control Conference (ECC), IEEE (2013) 4118–4123. | DOI
[30] , and , Approximation properties and tight bounds for constrained mixed-integer optimal control. SIAM J. Control Optim. 58 (2020) 1371–1402. | MR | Zbl | DOI
[31] , and , Compactness and convergence rates in the combinatorial integral approximation decomposition. Math. Program. 188 (2020) 569–598. | MR | Zbl | DOI
[32] , , and , Imaging with Kantorovich-Rubinstein discrepancy. SIAM J. Imag. Sci. 7 (2014) 2833–2859. | MR | Zbl | DOI
[33] , , and , Control parameterization for optimal control problems with continuous inequality constraints: new convergence results. Numer. Algebra Cont. Optim. 2 (2012) 571–599. | MR | Zbl | DOI
[34] , Relaxed multibang regularization for the combinatorial integral approximation. arXiv preprint (2020), submitted. | arXiv | MR | Zbl
[35] and , Improved regularity assumptions for partial outer convexification of mixed-integer PDE-constrained optimization problems. ESAIM: COCV 26 (2020). | MR | Zbl | Numdam
[36] and , Multidimensional Sum-Up Rounding for elliptic control systems. SIAM J. Numer. Anal. 58 (2020) 3427–3447. | MR | Zbl | DOI
[37] and , Second order sufficient conditions for time-optimal bang-bang control. SIAM J. Control Optim. 42 (2004) 2239–2263. | MR | Zbl | DOI
[38] and , A trust-region-based derivative free algorithm for mixed integer programming. Comput. Optim. Appl. 60 (2015) 199–229. | MR | Zbl | DOI
[39] , and , Nonlinear total variation based noise removal algorithms. Physica D 60 (1992) 259–268. | MR | Zbl | DOI
[40] and , Optimal switching for hybrid semilinear evolutions. Nonlinear Anal.: Hybrid Syst. 22 (2016) 215–227. | MR | Zbl
[41] , Numerical methods for mixed-integer optimal control problems, Der andere Verlag Töonning, Luöbeck, Marburg (2005).
[42] , and , The integer approximation error in mixed-integer optimal control. Math. Program. Ser. A 133 (2012) 1–23. | MR | Zbl | DOI
[43] , and , Combinatorial integral approximation. Math. Methods Oper. Res. 73 (2011) 363–380. | MR | Zbl | DOI
[44] and , On mixed-integer optimal control with constrained total variation of the integer control. submitted (2019). | MR | Zbl
[45] , Operator Theory, A comprehensive course in analysis, Part 4. American Mathematical Society, Providence (2015). | DOI | MR | Zbl
[46] and , Real analysis: measure theory, integration, and Hilbert spaces. Princeton University Press (2009). | MR | Zbl
[47] , and , Optimal control of switching times in switched linear systems, in 2016 IEEE 55th Conference on Decision and Control (CDC), IEEE (2016) 7228–7233. | DOI
[48] and , Iterative methods for total variation denoising. SIAM J. Sci. Comput. 17 (1996) 227–238. | MR | Zbl | DOI
[49] , Vol. 109 of Applied functional analysis: main principles and their applications. Springer Science & Business Media (2012). | MR | Zbl
Cité par Sources :
The submitted manuscript has been created by UChicago Argonne, LLC, Operator of Argonne National Laboratory (“Argonne”). Argonne, a U.S. Department of Energy Office of Science laboratory, is operated under Contract No. DE-AC02-06CH11357. The U.S. Government retains for itself, and others acting on its behalf, a paid-up nonexclusive, irrevocable worldwide license in said article to reproduce, prepare derivative works, distribute copies to the public, and perform publicly and display publicly, by or on behalf of the Government. The Department of Energy will provide public access to these results of federally sponsored research in accordance with the DOE Public Access Plan http://energy.gov/downloads/doe-public-access-plan.
