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

Abstract

Many real life applications lead to parabolic optimal control problems. In particular, the control often comes in form of a finite set of switches which can be operated within a given continuous time horizon and admit only a finite number of states. In this project, we have concentrated on binary switches that have bounded variation and possibly need to satisfy further combinatorial constraints. While many approaches presented in the literature for solving control problems with binary switches are heuristic and depend on a predetermined discretization, the project aimed at developing a branch-and-bound algorithm for solving the problems globally in function space. The major difficulty to design such an exact solution approach is the computation of tight dual bounds. For this purpose, we have investigated the closed convex hull of all feasible switching patterns and derived an outer description by linear inequalities based on finite-dimensional pro- jections. For the resulting convex relaxation, we have designed an outer approximation algorithm whose iterates converge strongly to the global minimizer of the relaxation. The overall approach is of general nature and the outer approximation algorithm is applicable to convex control problems whenever an efficient separation algorithm for the control constraints is known. To compute dual bounds numerically, the control problems have to be discretized using finite element methods, so that the obtained bounds depend on the discretization and are not necessarily valid in function space. To overcome this issue, we used an a posteriori error estimator. Finally, our branching strategy to fix the right-sided limit at appropriate time points of the switches guarantees that an increasing number of branching decisions leads to a unique solution of the subproblems in the limit. Our branch-and-bound algorithm thus converges to the global minimizer of the binary control problems. The performance of the algorithm now essentially depends on the quality and fast computation of the dual bounds. Numerical results for the case of bounded variation (without any further constraints) indicated that our dual bounds are rather tight, so that relatively few subproblems need to be inspected and refined within the branch-and-bound algo- rithm. Moreover, numerical tests verified that our tailored convexification can significantly improve the dual bounds given by the straightforward continuous relaxation, which are obtained by relaxing the binarity constraints of the controls.