子模函数

形式陈述 ​

设 $E$ 是有限底集，集合函数 $f:2^E\to \mathbb{R}$ 称为子模函数，若对任意 $A,B\subseteq E$ 都有

$$f(A)+f(B)\ge f(A\cup B)+f(A\cap B).$$

等价地，对 $A\subseteq B\subseteq E$ 和 $e\in E\setminus B$，定义边际增量

$${\mathrm{\Delta }}_{e}f(A)=f(A\cup \{e\})-f(A),$$

则子模性恰好表示

$${\mathrm{\Delta }}_{e}f(A)\ge {\mathrm{\Delta }}_{e}f(B).$$

从二集合不等式到边际递减，可取 $A\cup \{e\}$ 与 $B$；反向则可把 $A\setminus B$ 的元素逐个加入 $B$ 与 $A\cap B$ 并累加边际差，有限性保证过程终止。需要分别说明的是：$f(\varnothing )=0$ 称为归一化，$A\subseteq B\Rightarrow f(A)\le f(B)$ 称为单调，$f(A)\ge 0$ 称为非负；三者都不是子模定义的一部分。

直觉 ​

子模性表达“越晚加入，新增得越少”。当当前集合很小时，新元素可能带来大量未覆盖信息；已有集合越丰富，同一个元素与既有内容重叠越多，边际贡献就越低。它与连续优化中的凹性共享收益递减的图像，但定义发生在集合格上，不能把集合并交不等式直接替换成普通导数条件。

二集合形式突出重叠：分别评估 $A$ 和 $B$ 所得到的总价值，至少覆盖合并后的整体价值与交集的共同价值。边际形式更适合算法，因为它直接比较同一候选元素在不同上下文中的作用。

例子与边界 ​

给定宇宙 $U$ 以及每个 $e\in E$ 覆盖的子集 $C_e\subseteq U$，定义

$$f(S)=\left|\bigcup _{e\in S}{C}_e\right|.$$

若 $A\subseteq B$，元素 $e$ 在 $B$ 之后能新增覆盖的对象不可能多于在 $A$ 之后，因此覆盖函数单调且子模。无向图的割函数 $f(S)=|\delta (S)|$ 也是子模的，但通常不单调：把顶点移入 $S$ 既可能增加跨割边，也可能把原有跨割边变成内部边。这说明“子模”并不隐含“越多越好”。熵公理库Shannon 熵Shannon entropy · Information entropy随机变量不确定性的平均信息量，以最优编码所需位数为基本解释。和拟阵秩则分别从信息重叠与独立性给出另外两类子模函数。

互补收益提供真实反例。取 $E=\{a,b\}$，令 $g(S)=1$ 当且仅当 $\{a,b\}\subseteq S$，否则为 $0$。从空集加入 $b$ 的边际收益为 $0$，从 $\{a\}$ 加入却为 $1$，违反边际递减，所以 $g$ 不是子模函数。若 $f$ 子模，则 $-f$ 满足反向不等式，称为超模；这不是把非单调函数误称为超模，而是改变了并交不等式的方向。

推论与应用 ​

非负、单调、归一化的子模函数在基数约束下可以用贪心算法公理库贪心算法Greedy algorithm每一步作局部最优且不回溯选择的算法设计范式。逐步选择最大边际元素，并获得经典的 $1-1/e$ 近似保证。保证依赖这些附加条件；对非单调子模目标直接沿用同一证明会失败。

子模函数还统一图割最小化、覆盖选择、传感器布置和信息摘要。拟阵的秩函数是整数值单调子模函数，并额外满足 $r(S)\le |S|$；这些额外秩公理把一般收益递减结构收紧为可交换的独立性系统。优化时必须区分最小化、无约束最大化以及带基数或拟阵约束的最大化，因为它们的可解性与近似界并不相同。

参考资料

• Satoru Fujishige, Submodular Functions and Optimization, 2nd ed., Elsevier, 2005, Chapters I–II.
• Alexander Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Springer, 2003, Chapters 44–45.