论文标题
带有指标变量的凸subsodular最小化
Convex Submodular Minimization with Indicator Variables
论文作者
论文摘要
我们研究了指标变量的一般凸supdular优化问题。以这种形式自然建模的许多应用程序，例如以稀疏性或鲁棒性来推断马尔可夫随机场（MRF）的问题。我们表明，这些问题可以简化为二进制的下管最小化问题，可能是在适当的重新重新制定之后，因此可以在多个一级解决方面解决。此外，我们开发了一种参数方法，用于在某些平滑度条件下计算相关的极端基础。这导致了一种快速解决方案方法，该方法通过数值实验来证明其效率。
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. 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.
