Mixed-integer optimal control problems with switching costs: a shortest path approach
- PDF / 1,038,602 Bytes
- 32 Pages / 439.37 x 666.142 pts Page_size
- 100 Downloads / 254 Views
Series B
Mixed-integer optimal control problems with switching costs: a shortest path approach Felix Bestehorn1 Paul Manns1
· Christoph Hansknecht1
· Christian Kirches1
·
Received: 31 January 2020 / Accepted: 13 October 2020 © The Author(s) 2020
Abstract We investigate an extension of Mixed-Integer Optimal Control Problems by adding switching costs, which enables the penalization of chattering and extends current modeling capabilities. The decomposition approach, consisting of solving a partial outer convexification to obtain a relaxed solution and using rounding schemes to obtain a discrete-valued control can still be applied, but the rounding turns out to be difficult in the presence of switching costs or switching constraints as the underlying problem is an Integer Program. We therefore reformulate the rounding problem into a shortest path problem on a parameterized family of directed acyclic graphs (DAGs). Solving the shortest path problem then allows to minimize switching costs and still maintain approximability with respect to the tunable DAG parameter θ . We provide a proof of a runtime bound on equidistant rounding grids, where the bound is linear in time discretization granularity and polynomial in θ . The efficacy of our approach is demonstrated by a comparison with an integer programming approach on a benchmark problem. Keywords Optimal control · Discrete approximations · Nonlinear programming · Mixed-integer programming · Combinatorics
Electronic supplementary material The online version of this article (https://doi.org/10.1007/s10107020-01581-3) contains supplementary material, which is available to authorized users.
B
Felix Bestehorn [email protected] Christoph Hansknecht [email protected] Christian Kirches [email protected] Paul Manns [email protected]
1
Institute for Mathematical Optimization, Technische Universität Braunschweig, Brunswick, Germany
123
F. Bestehorn et al.
Mathematics Subject Classification 49J15 · 49M215 · 90C30 · 90C11 · 97K30
1 Introduction This work considers optimal control problems of the form inf J ( y) + C(v) y,v
s.t. ˙y(t) = f ( y(t), v(t)) for t ∈ [0, T ], y(0) = y0 , v(t) ∈ {v1 , . . . , v M } for t ∈ [0, T ].
(MSCP)
In (MSCP), the measurable function v : [0, T ] → {v1 , . . . , v M } ⊂ Rn V is a discretevalued control input. The function y : [0, T ] → Rn Y is the state vector of an initial value problem (IVP). We assume a uniform Lipschitz estimate on f in the first variable and deduce from the Picard–Lindelöf theorem that for all controls v, there exists a unique solution y ∈ W 1,∞ ((0, T ), Rn Y ), the space of functions in L ∞ ((0, T ), Rn Y ) with weak derivatives in L ∞ ((0, T ), Rn Y ). The continuous function J assigns costs to the state vector y and the function C : L ∞ ((0, T ), Rn V ) → R assigns costs to the control function v. We leave its regularity unspecified here and note that a natural choice in this article is a measure of switching costs, like for example the total variation or a weighted variant thereof. Several approaches
Data Loading...
