子模函数以及Lovász拓展

参考文献:

Wikipedia - Submodular function

Lecture 7: Submodular Functions, Lovász Extension and Minimization

Learning with Submodular Functions: A Convex Optimization Perspective

子模函数 (Submodular Function)

一个函数 被称为子模函数，如果对于任意的 和 ，都有以下不等式成立：

一个等价的定义是，如果对于任意的 和 ，都有：

第一个不等式可以被解释为“边际收益递减”，即添加一个元素到集合 的收益大于或等于添加同样的元素到更大的集合 的收益。

几个常见的子模函数示例包括：

• 令图 ，定义函数 ，则 是子模的，其中 表示集合 和其补集 之间的边集。
• 令图 为一个二分图，。 对于所有 ，定义 ，其中 是 的邻居节点集合，则 是子模的。也是单调的。
• 令 是 个离散随机变量。对任意 ，定义 ，其中 是 的熵，则 是子模的。

Lovász拓展 (Lovász Extension)

In a word, the Lovasz extension is a weighted average of the values at the corners.

对于函数 ，其Lovász拓展定义为：

其中 。

Lovász拓展被称为拓展，因为它保留了离散点集上的函数值。注意到，对于离散点，都有：。所以 与 在离散点集上是相同的。

等价的构造定义

将向量 的分量按降序重新排列为 ，然后定义集合序列 。

则：

并约定 。

这个定义可以看作是对函数 在每个集合 上的值进行加权平均，其中权重是相邻元素之间的差值。

对于子模函数 ，另一个有用的定义是，令 为 的拟阵多面体（polymatroid）

则

等价性证明

按 分段积分：

引理：

对于子模函数 ，其拟阵多面体 的顶点一一对应于排列

证明：

是平凡的

对于任意的 ，考虑一个排列 ，它首先列出 中的元素（按某种顺序），然后列出 中的元素。

对于这个排列 ，我们有：

现在考虑任意的排列 ，我们可以证明如果某个 出现在 的前面，则交换它们的位置不会减少 的值。

原来 的贡献是 ， 交换后变为 。

而子模函数性质告诉我们，。

因此， 在所有排列 中是最大的。

所以

另外，注意到 。

所以 满足 个线性无关约束，故 是 的顶点。

现在证明 ：

不难知道最优解 一定是对应排列 的顶点。

注意到

我们有：

Lovász拓展在子模函数上的性质

我们有如下定理：

定理：对于函数 ， 是子模函数当且仅当其 Lovász 拓展 是凸函数。

充分性：如果 是子模函数，则对于任意的 和 ，都有： 证明：由 Lovász 拓展的定义，我们有： 因此， 是凸函数。

必要性：如果 是凸函数，则对于任意的 和 ，（这里将视作限制到上）

都有： 证明：

令 和

因此，

现在我们用Lovász拓展的定义来计算左侧，设 ，则： - 对于 ， - 对于 ， - 其他情况，

所以

因此，我们得到了： 这就证明了必要性。