Randomization and Performance Improvement for Integer Optimal Control with Total Variation Regularization

Abstract

Mixed-integer PDE-constrained optimization problems are computationally challenging due to both the combinatorial nature of integer programming as well as evaluation of the model. Many algorithms and subsequent performance improvements have been developed to solve these problems, but they are often limited by problem size. We numerically analyze two such algorithms: SLIP and Patch-SLIP, which solve trust-region subproblems over either the full or partial domain, respectively. We additionally propose and prove convergence of a randomized third algorithm, Randomized-Patch-SLIP, which solves trust-region subproblems over randomly selected patches of the domain. We compare performance of all three algorithms with various improvement techniques found throughout the literature; the purpose of this work is to document the best combinations of these improvements in conjunction with various solvers. We additionally establish benchmark problems in image denoising and cloaking. Computational results are reported on combinations of algorithms and improvements, and code used in the experiments is provided as a package.