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

最优控制问题出现在各种应用中，例如化学工程、流行病学、汽车工程中的齿轮开关的切换、或气体和水网络中的阀门或压缩机的切换。特别地，控制通常以可以在给定的连续时间范围内操作的开关的有限集合的形式出现。例如，加热工件的过程可以通过抛物线偏微分方程来描述，其中工件的任何点和任何时间点的温度隐含地由直到该时间点的开关的设置来确定。其目的是通过优化开关来获得或近似期望的温度分布。在实践中，开关通常只允许有限数量的状态。我们将集中我们的调查的情况下，二进制开关，这可能是“上”或“关闭”在任何给定的时间点。只要不考虑进一步的限制，这种二元问题原来是密切相关的二元条件放宽相应的问题。然后，典型的方法是首先解决松弛的问题，然后以适当的方式对松弛的解进行舍入，以获得原始二元问题的近似解。然而，当考虑额外的和非常自然的限制时，这种方法通常会失败，例如，同一开关的两个变化之间的时间跨度上的下限，或开关的总次数上的上限可能会changed.While这样的组合约束往往被视为一个额外的复杂性，可以在一个启发式的后处理，我们提出了一种方法，组合结构是在算法的核心。我们的目标是了解所有可行的开关模式的凸船体，并描述它的切割平面，来自有限维投影的凸船体。后者是二元多面体，因此可以使用多面体组合学的标准方法。然而，重要的是要强调，投影将不依赖于预定义的离散化，并且整个算法将在函数空间中定义，与首先离散化然后优化的方法相反，这种方法会导致大型非凸混合整数优化问题。通过外近似方法求解凸松弛，并将其嵌入到一个定制的分支定界方案中，我们的目标是获得全局最优解。

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.