Approximation Properties and Tight Bounds for Constrained Mixed-Integer Optimal Control
Abstract: We extend recent work on mixed-integer nonlinear optimal control prob- lems (MIOCPs) to the case of integer control functions subject to constraints. Promi- nent examples of such systems include problems with restrictions on the number of switches permitted, or problems that minimize switch cost. We extend a theorem due to [Sager et al., Math. Prog. A, 133(1-2), 1–23 (2012)] to the case of MIOCPs with constraints on the integer control and show that the integrality gap is zero in function space event after adding constraints of this type. For the time discretized problem, we extend a sum-up rounding (SUR) scheme due to [Sager et al., Math. Prog. A, 118(1), 109–149 (2009)] to the new problem class. Our scheme permits to constructively ob- tain an ε-feasible and ε-optimal binary feasible control. We derive two tighter upper bounds on the integer control approximation error made by SUR. For unconstrained binary controls, we reduce the approximation error bound from O(|Ω|) to O(log |Ω|) asymptotically, where |Ω| is the number of binary controls. We further show that this new bound is tight. For constrained binary controls, we show that the approximation problem is more difficult, and we give a proof of an approximation error bound of complexity O(|Ω|). A numerical example compares our approach to a state of the art MINLP solver and illustrates the applicability of these results when solving MIOCPs using the direct and simultaneous approach.
Keywords: Optimal Control · Mixed-Integer Optimization · Ordinary Differential Equations · Switched Dynamic Systems · Approximation Theory
Category 1: Combinatorial Optimization (Approximation Algorithms )
Category 2: Complementarity and Variational Inequalities
Category 3: Nonlinear Optimization (Systems governed by Differential Equations Optimization )
Citation: Submitted to Mathematical Programming.
Entry Submitted: 04/12/2016
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|