Discretization of Total Variation in Optimization with Integrality Constraints
Authors:
- 25 February 2025
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Numerical Analysis
- Vol. 63 (1) , 437-460
Abstract
We introduce discretizations of infinite-dimensional optimization problems with total variation regularization and integrality constraints on the optimization variables. We advance the discretization of the dual formulation of the total variation term with Raviart–Thomas functions, which is known from the literature for certain convex problems. Since we have an integrality constraint, the previous analysis from Caillaud and Chambolle [ IMA J. Numer. Anal., 43 (2022), pp. 692–736] no longer holds. Even weaker [Formula: see text]-convergence results no longer hold because the recovery sequences generally need to attain noninteger values to recover the total variation of the limit function. We solve this issue by introducing a discretization of the input functions on an embedded, finer mesh. A superlinear coupling of the mesh sizes implies an averaging on the coarser mesh of the Raviart–Thomas ansatz, which enables us to recover the total variation of integer-valued limit functions with integer-valued discretized input functions. Moreover, we are able to estimate the discretized total variation of the recovery sequence by the total variation of its limit and an error depending on the mesh size ratio. For the discretized optimization problems, we additionally add a constraint that vanishes in the limit and enforces compactness of the sequence of minimizers, which yields their convergence to a minimizer of the original problem. This constraint contains a degree of freedom whose admissible range is determined. Its choice may have a strong impact on the solutions in practice as we demonstrate with an example from imaging.Keywords
All Related Versions
Funding Information
- Deutsche Forschungsgemeinschaft (MA 10080/2-1, ME 3281/10-1, 271512359)
This publication has 35 references indexed in Scilit:
- Crouzeix–Raviart Approximation of the Total Variation on Simplicial MeshesJournal of Mathematical Imaging and Vision, 2020
- A partial outer convexification approach to control transmission linesComputational Optimization and Applications, 2018
- Challenges in Optimal Control Problems for Gas and Fluid Flow in Networks of Pipes and Canals: From Modeling to Industrial Applications2017
- The Shannon Total VariationJournal of Mathematical Imaging and Vision, 2017
- Accelerated Alternating Descent Methods for Dykstra-Like ProblemsJournal of Mathematical Imaging and Vision, 2017
- Density of polyhedral partitionsCalculus of Variations and Partial Differential Equations, 2017
- Solving mixed-integer optimal control problems by branch&bound: a case study from automobile test-driving with gear shiftOptimal Control Applications and Methods, 2005
- Image recovery via total variation minimization and related problemsNumerische Mathematik, 1997
- Mixed and Hybrid Finite Element Methods1991
- The gradient theory of phase transitions and the minimal interface criterionArchive for Rational Mechanics and Analysis, 1987