We propose an adaptive refinement algorithm to solve total variation regularized measure optimization problems. The method iteratively constructs dyadic partitions of the unit cube based on (i) the resolution of discretized dual problems and (ii) the detection of cells containing points that violate...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Université de Montpellier
2025-03-01
|
| Series: | Open Journal of Mathematical Optimization |
| Subjects: | |
| Online Access: | https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.39/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849247390812340224 |
|---|---|
| author | Flinth, Axel de Gournay, Frédéric Weiss, Pierre |
| author_facet | Flinth, Axel de Gournay, Frédéric Weiss, Pierre |
| author_sort | Flinth, Axel |
| collection | DOAJ |
| description | We propose an adaptive refinement algorithm to solve total variation regularized measure optimization problems. The method iteratively constructs dyadic partitions of the unit cube based on (i) the resolution of discretized dual problems and (ii) the detection of cells containing points that violate the dual constraints. The detection is based on upper-bounds on the dual certificate, in the spirit of branch-and-bound methods. The interest of this approach is that it avoids the use of heuristic approaches to find the maximizers of dual certificates. We prove the convergence of this approach under mild hypotheses and a linear convergence rate under additional non-degeneracy assumptions. These results are confirmed by simple numerical experiments. |
| format | Article |
| id | doaj-art-011aca7180f04dc4b4e9efab87f48985 |
| institution | Kabale University |
| issn | 2777-5860 |
| language | English |
| publishDate | 2025-03-01 |
| publisher | Université de Montpellier |
| record_format | Article |
| series | Open Journal of Mathematical Optimization |
| spelling | doaj-art-011aca7180f04dc4b4e9efab87f489852025-08-20T03:58:14ZengUniversité de MontpellierOpen Journal of Mathematical Optimization2777-58602025-03-01612710.5802/ojmo.3910.5802/ojmo.39Flinth, Axel0de Gournay, Frédéric1Weiss, Pierre2Department of Mathematics and Mathematical Statistics, Umeå University, SwedenInstitut de Mathématiques de Toulouse (IMT), Université de Toulouse, CNRS, INSA, FranceInstitut de Recherche en Informatique de Toulouse (IRIT), Université de Toulouse, CNRS, Centre de Biologie Intégrative (CBI), Laboratoire de biologie Moléculaire, Cellulaire et Développement (MCD), FranceWe propose an adaptive refinement algorithm to solve total variation regularized measure optimization problems. The method iteratively constructs dyadic partitions of the unit cube based on (i) the resolution of discretized dual problems and (ii) the detection of cells containing points that violate the dual constraints. The detection is based on upper-bounds on the dual certificate, in the spirit of branch-and-bound methods. The interest of this approach is that it avoids the use of heuristic approaches to find the maximizers of dual certificates. We prove the convergence of this approach under mild hypotheses and a linear convergence rate under additional non-degeneracy assumptions. These results are confirmed by simple numerical experiments.https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.39/Total variationmeasure spacesFrank–Wolfe |
| spellingShingle | Flinth, Axel de Gournay, Frédéric Weiss, Pierre Open Journal of Mathematical Optimization Total variation measure spaces Frank–Wolfe |
| topic | Total variation measure spaces Frank–Wolfe |
| url | https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.39/ |