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.