“对任意实值子模函数f，令F为其多线性扩张，还有”
形式陈述
坐标是入选概率，输入仍是有限集合函数
给有限底集E={0,…,n−1}和实值集合函数f:2ᴱ→ℝ。一个点x∈[0,1]ⁿ规定随机子集Rₓ：每个元素i以概率xᵢ入选，各元素的选择相互独立。定义多线性扩张
这里的期望只是有限加权和，f的全部值有限，所以没有可积性障碍。空底集只有一个子集，F=f(∅)。概率为0或1的坐标也直接代入乘积，不需要除法。定义对任意实值f成立；以下曲率结论才使用子模性。[1, §2.1]
固定其余坐标，F关于一个坐标xᵢ为仿射函数，因此“多线性”在这里指每个坐标的次数至多一。它不表示所有变量合起来是线性的，也不表示常数项必须为零。在集合指标点1_S处，随机子集必为S，故F(1_S)=f(S)。
F是与全部立方体顶点值相符的唯一多线性多项式。证明可逐坐标使用
把n个坐标依次展开，便得到定义中的2ⁿ项；不再留下自由系数。这个插值恒等式同时说明如何求值，却还没有给出多项式时间算法。
不除以概率的导数公式
令R_{−i}只从E{i}中按其坐标独立抽样。有限多项式直接求导得到
因此∂ᵢF不依赖xᵢ。这个写法在xᵢ=0、1时仍合法；若写成“条件于i入选/不入选”，零概率条件事件便需另作解释。
对i≠j，令R_{−i,−j}排除两坐标，则
若f单调，则式(1)非负；若f子模，则式(2)非正。这是两个独立条件，不能从子模性推出所有一阶导数非负。[1, §2.1]
直觉
先保留不确定选择，再计算实际集合价值
x=(1/2,1/2)不是“半个元素加半个元素”的集合。它规定四种可能集合及概率，F先在每种完整集合上求f，再平均。元素间的重叠收益因此被保留，而不是简单相加单例价值。
若f(S)表示至少选中a、b之一就覆盖一个区域，则
减去xₐx_b正好避免“两者都入选”时重复计算同一个区域。固定x_b，增加xₐ的边际斜率为1−x_b；b越可能已经覆盖它，a越难再带来新增收益。
两种曲率承担不同算法工作
虽然混合二阶导数都非正，F一般并不是全局凹函数。在刚才的二元例子中，沿x=(t,t)有F=2t−t²，曲线向下弯；沿x=(1/2+t,1/2−t)则有F=3/4+t²，曲线向上弯。
前者同时增加选择概率，用于控制连续增长的边际；后者把概率从一个坐标搬到另一个坐标，用于证明随机交换舍入不降低期望。不能把一个方向上的凹性推广到所有方向。
例子与边界
四候选覆盖的精确多项式
四个候选a、b、c、d分别覆盖
f(S)为覆盖区域数。区域0由a、b、c任一个覆盖；区域1、2由a或c覆盖；区域3、4只靠b；区域5只靠d。对每个区域算“至少一个相关候选入选”，得
在x=(1/2,1/2,1/2,1/2)处，四项为7/8、3/2、1、1/2，合计31/8。相应梯度为
例如∂ₐF=(1−x_b)(1−x_c)+2(1−x_c)，只计算a还可能新增的区域，且确实不含xₐ。
相同边缘概率不决定F
仍取每个坐标边缘概率1/2。若以各1/2的概率选择ac或bd，平均价值为(3+4)/2=7/2；若以各1/4选择ac、ad、bc、bd，平均为(3+4+5+4)/4=4。两种分布都与上述独立模型具有相同边缘，却分别得到7/2、4，而独立模型得到31/8。
所以F(x)不是所有具有边缘x的分布的共同价值；它专指独立分布。交换舍入构造相关分布并证明其期望至少为F(x)，正是额外的算法结论。
分数可行不意味着独立抽样可行
规定a、b最多选一项，c、d也最多选一项。各坐标1/2满足每组分数和为1，但独立抽样在每组以1/4概率同时选中两项。两组各自不超额的概率为3/4，全部可行的概率只有9/16。
求F时允许这些不满足配额的子集出现，因为原value oracle定义在全部2ᴱ上。求值分布和最终可行输出是不同接口。若oracle仅能评估可行集，就不足以直接执行式(1)的随机采样。
单调性与全局凹性都不可省略
两顶点一条边的割函数在空集/全集值0，在两个单点值1，子模却不单调；F=xₐ+x_b−2xₐx_b，当x_b>1/2时∂ₐF为负。其交换方向仍凸，但不能使用“增加任一坐标都不减值”的增长证明。
前面的单调覆盖例子已经反驳全局凹性：F(1,0)=F(0,1)=1，二者中点值3/4，小于端点平均1。也不能据混合导数非正就说F全局凸，因为沿(t,t)又严格凹。
推论与应用
用方向二阶导数统一证明
设一段直线x+td始终位于单位立方体。若d≥0，由式(2)及对角二阶导数为零，
故F沿任意非负方向凹。若d=eᵢ−eⱼ，则
所以沿交换方向是凸函数。多项式在立方体之外也有定义，边界点可以直接按这条一元多项式处理，无需在边界偷用未定义的条件分布。
对归一化、单调子模f，令M=maxᵢf({i})，空底集时约定M=0。边际递减给0≤∂ᵢF≤M；式(2)是两个非负边际之差，故−M≤∂ᵢⱼF≤0。向r个坐标同时增加δ时，这个界把有限步与瞬时梯度的差控制为至多δ²r(r−1)M/2，成为有限步连续贪心的可计算误差。
求值和估计都要收费
附件用Fraction逐项枚举全部子集，精确得到F、梯度和示例中的Hessian。若一次f查询成本为T_f，集合建立和概率乘积按每坐标常数算术计，F枚举需O((n+T_f)2ⁿ)，全部梯度的直接实现需O(n(n+T_f)2ⁿ)；Hessian诊断还多一个n因子。枚举可逐项累计，不必把2ⁿ份集合同时存下。n=0为常数入口。任意长有理数运算的位成本不在这些算术次数里。
式(1)也可通过独立样本平均估计，每个样本做两次value查询并建立一个至多n元素的集合。归一化单调子模条件下，观测边际在[0,M]中；采样版要给误差、失败概率和总样本数。一次数值看起来接近，不能自动替代所有自适应迭代上的共同保证。
综合练习要求同时用区域未覆盖概率和完整子集枚举得到31/8，再比较三种相同边缘分布，最后把这些导数送进可行方向和交换舍入。
参考资料
- Gruia Calinescu、Chandra Chekuri、Martin Pál、Jan Vondrák，Maximizing a Monotone Submodular Function Subject to a Matroid Constraint，SICOMP40(6)，2011，§2.1，印刷pp.1745–1746：多线性扩张、混合导数及方向性质。
- Chandra Chekuri、Jan Vondrák、Rico Zenklusen，Dependent Randomized Rounding for Matroid Polytopes and Applications，2009长稿，§2–4：多线性目标与相关舍入的接口。四候选、三种同边缘分布及精确有理数为本页自己的算例。