Integer optimization with total variation regularization
Loading...
Date
2024
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
This thesis is concerned with the analysis and solution of integer optimization problems in function space with total variation regularization. We prove the existence of optimal solutions and provide first-order optimality conditions. A function space trust-region algorithm for the solution in the multi-dimensional case is proposed and its convergence to stationary points is analyzed.
In order to compute lower bounds for the global optimization of integer optimization problems with total variation regularization, we consider the relaxation that is obtained by relaxing the integrality condition to box constraints. In order to apply an outer-approximation algorithm in function space, we introduce a regularization of the relaxation which includes a regularized total variation and a Tikhonov regularization. We derive necessary and sufficient optimality conditions for an example from optimal control and use them for the construction of an instance with known optimal solution.
For the numerical solution of integer optimization problems with total variation regularization, we introduce a novel discretization to recover the total variation in the presence of integrality restrictions. Due to the restriction of the integer-valued discretized input functions to prescribed finite-element meshes, the known discretizations from literature generally fail to recover the total variation of limit functions correctly. Our novel discretization consists of two embedded meshes for the discretization of the input function and the discretization of the total variation term whose mesh sizes are superlinearly coupled. In order to conserve compactness, we add an additional constraint to the discretized problems that vanishes as the superlinearly coupled mesh sizes are driven to zero. This constraint contains a constant whose admissible range is determined and whose choice has a significant impact on the numerical results. We propose an outer-approximation algorithm to solve the discretized problems. Moreover, we transfer the discretization to the relaxation.
With our numerical experiments, we demonstrate the practicability of the proposed discretizations and algorithms. In particular, we illustrate that our novel discretization scheme is able to recover the interfaces of level sets of limit functions correctly while the anisotropic discretizations from literature lead to distortions.
Description
Table of contents
Keywords
Total variation, Infinite-dimensional optimization with integrality restrictions, Coupled discretizations, Trust-region methods, Regularization, Outer-approximation