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

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

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.