Relaxations and Approximations for Mixed-Integer Optimal Control
Relaxations and Approximations for Mixed-Integer Optimal Control
复制标题
混合整数最优控制的松弛和近似
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Michael N. Jung
中科院分区：
文献类型：
--
作者：
Michael N. Jung
本文从不同的角度研究了一类混合最优控制问题。这些优化问题结合了联合收割机的困难，潜在的动态过程与组合决策。通常，这些组合决策被实现为系统的不同操作模式之间的切换决策。
在过去的几十年中，直接方法成为最先进的MIOCP求解器。一个有效的，严密的和可靠的积分松弛，即，分数值模型的公式化对于这些直接求解方法起着重要的作用。我们给出了详细的洞察几个放松的方法MIOCPs和比较它们各自的结构。特别地，这些是典型的解的结构和性质，如凸性，问题大小和数值行为。从这些结构特性，我们推导出一些所需的规格的求解器。此外，切换过程的建模和随后的限制直接解决了抖动解决方案的特定于类别的典型问题。
MIOCP的松弛方法之一是外凸化，其中二元变量仅进入仿射。对于这种松弛的解决方案的近似，我们采取了控制近似问题的积分意义上的Sager作为一个分解方法的一部分，仿射二进制控制MIOCPs。该问题描述了分数控制与二元控制的最佳逼近，使得相应的动态过程变化尽可能小。对于多维问题，我们开发了一种新的启发式算法，它首次给出了一个仅依赖于控制网格而不再依赖于系统控制数量的边界。对于具有附加约束的控制近似问题的推广，我们基于一维问题的拉格朗日松弛性质，导出了一种裁剪的分枝定界算法.该算法击败了几个数量级的混合线性规划（MILP）的这种特殊的近似问题的最先进的商业求解器。
总体而言，我们提出了几个，部分新的建模方法MIOCPs连同伴随的结构特性。在此基础上，我们发展了新的理论，某些松弛的解决方案的近似。我们将讨论所产生的结构利用算法的有效实施。这有助于更深入和更好地了解MIOCP。我们的实用性的理论观察的帮助下，四个典型的问题。所提出的方法和算法允许在其基础上的决策支持和分析工具在实践中的直接发展。
This thesis treats different aspects of the class of Mixed-Integer Optimal Control Problems (MIOCPs). These are optimization problems that combine the difficulties of underlying dynamic processes with combinatorial decisions. Typically, these combinatorial decisions are realized as switching decisions between the system’s different operations modes.
During the last decades, direct methods emerged as the state-of-the-art solvers for MIOCPs. The formulation of a valid, tight and dependable integral relaxation, i.e., the formulation of a model for fractional values, plays an important role for these direct solution methods. We give detailed insight into several relaxation approaches for MIOCPs and compare them with regard to their respective structures. In particular, these are the typical solution’s structures and properties as convexity, problem size and numerical behavior. From these structural properties, we deduce some required specifications of a solver. Additionally, the modeling and subsequent limitation of the switching process directly tackle the class-specific typical issue of chattering solutions.
One of the relaxation methods for MIOCPs is the outer convexification, where the binary variables only enter affinely. For the approximation of this relaxation’s solution, we took up on the control approximation problem in integral sense derived by Sager as part of a decomposition approach for MIOCPs with affine binary controls. This problem describes the optimal approximation of fractional controls with binary controls such that the corresponding dynamic process is changed as little as possible. For the multi-dimensional problem, we developed a new heuristic, which for the first time gives a bound that only depends on the control grid and not anymore on the number of the system’s controls. For the generalization of the control approximation problem with additional constraints, we derived a tailored branch-and-bound algorithm, which is based on the properties of the Lagrangian relaxation of the one-dimensional problem. This algorithm beats state-of-the-art commercial solvers for Mixed-Integer Linear Programs (MILPs) for this special approximation problem by several orders of magnitude.
Overall, we present several, partially new modeling approaches for MIOCPs together with the accompanying structural properties. On this basis, we develop new theories for the approximation of certain relaxed solutions. We discuss the efficient implementation of the resulting structure exploiting algorithms. This leads to a deeper and better understanding of MIOCPs. We show the practicability of the theoretical observations with the help of four prototypical problems. The presented methods and algorithms allow on their basis the direct development of decision support and analysis tools in practice.