Submodular set-functions have many applications in combinatorial optimization, as they can be minimized and approximately maximized in polynomial time. A key element in many of the algorithms and analyses is the possibility of extending the submodular set-function to a convex function, which opens up tools from convex optimization. Submodularity goes beyond set-functions and has naturally been considered for problems with multiple labels or for functions defined on continuous domains, where it corresponds essentially to cross second-derivatives being nonpositive. In this paper, we show that most results relating submodularity and convexity for set-functions can be extended to all submodular functions. In particular, (a) we naturally define a continuous extension in a set of measures, (b) show that the extension is convex if and only if the original function is submodular, (c) prove that the problem of minimizing a submodular function is equivalent to a typically non-smooth convex optimization problem, and (d) propose another convex optimization problem with better computational properties (e.g., a smooth dual problem). Most of these extensions from the set-function situation are obtained by drawing links with the theory of multi-marginal optimal transport. We then provide practical algorithms to minimize generic submodular functions on discrete domains, with associated convergence rates.

本文研究了次模函数及其在凸优化和概率测度方面的应用，提出了连续化的概率测度拓展方式，利用多重边际最优传送理论对次模集函数情况下的推论进行了拓展，最终给出了离散域中通用次模函数的实际最小化算法及其收敛速率。

子模函数：从离散到连续领域