The integer approximation error in mixed-integer optimal control

• 成果类型: Article
• 署名作者: Sager, Sebastian; Bock, Hans Georg; Diehl, Moritz
• 署名单位: Ruprecht Karls University Heidelberg; KU Leuven
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-010-0405-3
• 发表日期: 2012
• 页码: 1-23
• 关键词: Optimization

摘要

We extend recent work on nonlinear optimal control problems with integer restrictions on some of the control functions (mixed-integer optimal control problems, MIOCP). We improve a theorem (Sager et al. in Math Program 118(1): 109-149, 2009) that states that the solution of a relaxed and convexified problem can be approximated with arbitrary precision by a solution fulfilling the integer requirements. Unlike in previous publications the new proof avoids the usage of the Krein-Milman theorem, which is undesirable as it only states the existence of a solution that may switch infinitely often. We present a constructive way to obtain an integer solution with a guaranteed bound on the performance loss in polynomial time. We prove that this bound depends linearly on the control discretization grid. A numerical benchmark example illustrates the procedure. As a byproduct, we obtain an estimate of the Hausdorff distance between reachable sets. We improve the approximation order to linear grid size instead of the previously known result with order (Hackl in Reachable sets, control sets and their computation, augsburger mathematisch-naturwissenschaftliche schriften. Dr. Bernd Winer, Augsburg, 1996). We are able to include a Special Ordered Set condition which will allow for a transfer of the results to a more general, multi-dimensional and nonlinear case compared to the Theorems in Pietrus and Veliov in (Syst Control Lett 58:395-399, 2009).