Structured Convex Optimization under Submodular Constraints
Structured Convex Optimization under Submodular Constraints
复制标题
DOI：
--
复制
发表时间：
2013-08
期刊：
影响因子：
--
通讯作者：
Kiyohito Nagano;Y. Kawahara
中科院分区：
文献类型：
--
作者：
Kiyohito Nagano;Y. Kawahara
机器学习中的许多离散和连续优化问题都与子模约束下的凸极小化问题有关。在本文中，我们处理一个次模函数与有向图结构，我们表明，范围广泛的凸优化问题的次模约束下，可以更有效地解决比一般次模优化方法减少到最大流问题。此外，我们给出了一些应用，其中包括稀疏优化方法，所提出的方法是有效的。此外，我们通过计算实验评估所提出的方法的性能。
A number of discrete and continuous optimization problems in machine learning are related to convex minimization problems under submodular constraints. In this paper, we deal with a submodular function with a directed graph structure, and we show that a wide range of convex optimization problems under submodular constraints can be solved much more efficiently than general submodular optimization methods by a reduction to a maximum flow problem. Furthermore, we give some applications, including sparse optimization methods, in which the proposed methods are effective. Additionally, we evaluate the performance of the proposed method through computational experiments.