Theory of submodular programs: A fenchel-type min-max theorem and subgradients of submodular functions
Theory of submodular programs: A fenchel-type min-max theorem and subgradients of submodular functions
复制标题
子模程序理论：芬切尔型最小-最大定理和子模函数的次梯度
DOI：
10.1007/bf02592218
复制
发表时间：
1984
影响因子：
2.7
通讯作者：
S. Fujishige
中科院分区：
文献类型：
--
作者：
S. Fujishige
我们考虑子模规划，它是在有或没有约束的分配格上最小化子模函数的问题。我们定义了子模(或超模)函数的凸(凹)共轭函数，并证明了子模函数和超模函数的Fancel型极小-极大定理。我们还定义了子模函数的次梯度，得到了子模规划的可行解是最优的充要条件，这是凸规划的Karush-Kuhn-Tucker条件的对应。
We consider submodular programs which are problems of minimizing submodular functions on distributive lattices with or without constraints. We define a convex (or concave) conjugate function of a submodular (or supermodular) function and show a Fenchel-type min-max theorem for submodular and supermodular functions. We also define a subgradient of a submodular function and derive a necessary and sufficient condition for a feasible solution of a submodular program to be optimal, which is a counterpart of the Karush-Kuhn-Tucker condition for convex programs.