Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2507.00442 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915373160333312 |
|---|---|
| author | Gomez, Andres Han, Shaoning |
| author_facet | Gomez, Andres Han, Shaoning |
| contents | We study a general class of convex submodular optimization problems with indicator variables. Many applications such as the problem of inferring Markov random fields (MRFs) with a sparsity or robustness prior can be naturally modeled in this form. We show that these problems can be reduced to binary submodular minimization problems, possibly after a suitable reformulation, and thus are strongly polynomially solvable. %We also discuss the implication of our results in the case of quadratic objectives. Furthermore, we develop a parametric approach for computing the associated extreme bases under certain smoothness conditions. This leads to a fast solution method, whose efficiency is demonstrated through numerical experiments. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_00442 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Convex Submodular Minimization with Indicator Variables Gomez, Andres Han, Shaoning Optimization and Control We study a general class of convex submodular optimization problems with indicator variables. Many applications such as the problem of inferring Markov random fields (MRFs) with a sparsity or robustness prior can be naturally modeled in this form. We show that these problems can be reduced to binary submodular minimization problems, possibly after a suitable reformulation, and thus are strongly polynomially solvable. %We also discuss the implication of our results in the case of quadratic objectives. Furthermore, we develop a parametric approach for computing the associated extreme bases under certain smoothness conditions. This leads to a fast solution method, whose efficiency is demonstrated through numerical experiments. |
| title | Convex Submodular Minimization with Indicator Variables |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2507.00442 |