Optimization Online


Approximation Properties and Tight Bounds for Constrained Mixed-Integer Optimal Control

Christian Kirches(christian.kirches***at***iwr.uni-heidelberg.de)
Felix Lenders(felix.lenders***at***iwr.uni-heidelberg.de)

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), 123 (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), 109149 (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.

Download: [PDF]

Entry Submitted: 04/12/2016
Entry Accepted: 04/12/2016
Entry Last Modified: 04/12/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society