Convex relaxations of PDE-constrained optimization problems with combinatorial switching constraints

具有组合切换约束的偏微分方程约束优化问题的凸松弛

• 批准号: 468720830
• 负责人: Professor Dr. Christoph Buchheim
• 金额: --
• 依托单位: Lehrstuhl X: Numerische Analysis und Optimierung
• 依托单位国家: 德国
• 项目类别: Research Grants
• 资助国家: 德国
• 项目状态: 未结题
• 来源: https://gepris.dfg.de/gepris/projekt/468720830?language=en
• 关键词: Convex; relaxations; PDE; constrained; optimization

Optimal control problems arise in a variety of applications, such as chemical engineering, epidemiology, shifting of gear switches in automotive engineering, or switching of valves or compressors in gas and water networks. In particular, the control often comes in form of a finite set of switches which can be operated within a given continuous time horizon. For instance, the process of heating up a work piece can be described by a parabolic partial differential equation, where the temperature in any point of the work piece and at any point in time is implicitly determined by the setting of the switches up to that time point. The objective could be to obtain or to approximate a desired temperature distribution by means of an optimized switching.In practice, the switches often admit only a finite number of states. We will concentrate our investigation on the case of binary switches, which may be "on" or "off" at any given point in time. As long as no further restrictions are considered, such binary problems turn out to be closely related to the corresponding problems where the binary condition is relaxed. A typical approach is then to solve the relaxed problem first and to round the relaxed solution in a suitable way afterwards, in order to obtain an approximate solution of the original binary problem. However, this approach often fails when considering additional and very natural restrictions such as, e.g., a lower bound on the time span between two changes of the same switch, or an upper bound on the total number of times the switch may be changed.While such combinatorial constraints are often seen as an additional complication that can be treated in a heuristic postprocessing, we propose an approach where the combinatorial structure is at the heart of the algorithm. Our aim is to understand the convex hull of all feasible switching patterns and to describe it by cutting planes that are derived from finite-dimensional projections of this convex hull. The latter are binary polytopes and thus accessible to standard methods of polyhedral combinatorics. It is important to emphasize, however, that the projections will not depend on a predefined discretization, and that the overall algorithm will be defined in function space, contrary to first-discretize-than-optimize approaches that would lead to large non-convex mixed-integer optimization problems. Solving the resulting convex relaxations by an outer approximation approach and embedding this into a tailored branch-and-bound scheme, our objective is to obtain globally optimal solutions.

最佳控制问题出现在各种应用中，例如化学工程，流行病学，汽车工程中的齿轮开关转移或气体和水网络中阀门或压缩机的开关。特别是，该控件通常以有限的开关组形式出现，这些开关可以在给定的连续时间范围内操作。例如，加热工件的过程可以通过抛物线偏微分方程来描述，其中工件的任何点和任何时间点的温度都通过设置开关的设置直至该时间点隐含地确定。目的可能是通过优化的开关获得或近似于所需的温度分布。在实践中，开关通常仅接受有限数量的状态。我们将把调查集中在二进制开关案例上，该二进制开关可能在任何给定的时间点上“”或“关闭”。只要不考虑进一步的限制，这种二进制问题就与二进制条件放松的相应问题密切相关。然后，一种典型的方法是首先解决放松的问题，然后以合适的方式绕开放松的解决方案，以便获得原始二进制问题的近似解决方案。但是，这种方法通常在考虑额外和非常自然的限制时通常会失败。我们的目的是了解所有可行的开关模式的凸壳，并通过切割来自该凸壳的有限维投影的平面来描述它。后者是二进制多型，因此可以使用标准的多面体组合方法访问。但是，重要的是要强调，这些预测将不取决于预定义的离散化，并且总体算法将在功能空间中定义，这与首先限制的方法相反，这将导致大型非convex混合组合优化问题。通过外部近似方法求解所得的凸松弛，并将其嵌入量身定制的分支和结合方案中，我们的目标是获得全球最佳解决方案。