WQS 二分

引入

本文介绍利用 WQS 二分优化动态规划问题的方法。在不同的文章中，它也常称作带权二分、凸优化 DP、凸完全单调性 DP、Lagrange 乘子法等，在国外也称作 Aliens Trick。它最早由王钦石在《浅析一类二分方法》一文中总结。

WQS 二分通常用于解决这样一类优化问题：它们带有数量限制，直接求解代价较高；但一旦去除这一限制，问题本身就变得容易得多。

比如，假设要解决的问题是，要从 $n$ 个物品中选取 $m$ 个，并最优化某个较复杂的目标函数。如果设从前 $i$ 个物品中选取 $j$ 个，目标函数的最优值为 $f (i, j)$ ，那么原问题的答案就是 $f (n, m)$ 。这类问题中，状态转移方程通常是二维的。直接实现该状态转移方程，时间复杂度是 $O (n m)$ 的，难以接受。

进一步假设，没有数量限制的最优化问题容易解决。但是，选取到的最优数量未必满足原问题的数量限制。假设选取的物品过多。那么，就可以考虑在选取物品时，为每个选取到的物品都附加一个固定大小的惩罚 $k$ （即「带权二分」中的「权」），仍然解没有数量限制的最优化问题。根据 $k$ 的取值不同，选取到的最优数量也会有所不同；而且，随着 $k$ 的变化，选取到的最优数量也是单调变化的。所以，可以通过二分，找到 $k$ 使得选取到的最优数量恰为 $m$ 。假设此时目标函数的最优值为 $f_{k} (n)$ ，那么，只要消除额外附加的惩罚造成的价值损失，就能得到原问题的答案 $f (n, m) = f_{k} (n) + k m$ 。假设单次求解附加惩罚的问题的复杂度是 $O (T (n))$ 的，那么，算法的整体复杂度也就降低到了 $O (T (n) \log L)$ ，其中， $O (\log L)$ 是二分 $k$ 需要的次数。

这就是 WQS 二分的基本想法。但是，这一想法能够行得通，前提是 $f (n, m)$ 关于 $m$ 是凸的。否则，可能不存在使得最优数量恰为 $m$ 的附加惩罚 $k$ 。这也是这种 DP 优化方法常常称为「凸优化 DP」或「凸完全单调性 DP」的原因。

传统方法

设非空集合 $X$ 为（有限的）决策空间， $f : X \to R$ 为目标函数，且另有函数 $g : X \to R^{d}$ 用于施加限制。需要求解的问题，可以看作是计算如下最优化问题的价值函数 $v (y)$ 在某处的取值：

\begin{aligned} v (y) = min_{x \in X} & f (x) \\ subject to & g (x) = y . \end{aligned}

比如，对于前文提到的限制数量的问题， $X$ 可以理解为所有物品集合的子集族， $x \in X$ 是单个子集， $f (x)$ 是单个子集的价值函数， $g (x)$ 是子集 $x$ 中的元素个数。当然， $g (x)$ 并非只能是数量限制，后文提供了更为广泛的限制条件的例子。

约定

为了行文方便，本文仅讨论最小化目标函数的问题。最大化目标函数的问题与之相仿，只是需要将本文中的（下）凸函数相应地替换成凹函数（或称上凸函数）。或者，可以通过添加负号，将最大化目标函数的问题，转化为最小化它的相反数的问题。

几何直观

因为算法竞赛中遇到的大多数问题都是组合优化问题，决策空间 $X$ 通常没有良好的结构，所以，可以转而考察集合

D = {(g (x), f (x)) \in R \times R^{d} : x \in X} .

传统方法能够解决的主要是 $d = 1$ 的情形，即只有一个限制的情形。下图提供了此时点集 $D$ 的一种可能的图示。

图中的红点和蓝点是 $X$ 中所有可能的选择投影在平面 $(g (x), f (x))$ 上得到的集合 $D$ 。于是，原问题所要求的就是横坐标为 $y$ 的那些点中，纵坐标的最小值 $v (y)$ 。当 $y$ 变动时，所有这样的点 $(y, v (y))$ 就构成了图中的红点的集合。

为了求得点 $(y, v (y))$ 的纵坐标，可以考虑用斜率为 $λ \in R$ 的直线去切集合 $D$ 。如图所示，当直线的斜率选取得恰当时，经过点 $(y, v (y))$ 的那条直线，是所有经过集合 $D$ 中的点且斜率为 $λ$ 的直线中，截距 $f (x) - λ g (x)$ 最小的。将这一最小值记为

h (λ) = min_{x \in X} f (x) - λ g (x) .

那么，因为 $(y, v (y))$ 同样位于该直线上，就可以得到原问题的解

v (y) = h (λ) + λ y .

假设对于所有合理范围的 $λ$ ，上述函数 $h (λ)$ 都是容易求解的。这在算法竞赛中常常是成立的，因为它去掉了原问题中的限制条件。那么，现在面临的最为重要的两个问题，就是

是否存在这样的直线斜率 $λ$ ，使得它的截距最小值恰好取得在点 $(y, v (y))$ 处，以及
如果存在，如何找到这样的斜率 $λ$ 。

第一个问题相对容易解决。因为当直线斜率 $λ$ 发生变化时，所有这些直线切出的集合（即它们对应的上半平面的交）必然是一个凸集。因此，这些直线能够经过某个点，当且仅当这个点在该凸集的下凸壳上。这等价于说，函数 $v (y)$ 是凸函数。

第二个问题则更为精细。因为所求点的横坐标已经知道是 $y$ ，所以，一个自然的思路是，计算 $h (λ)$ 时，顺便求出限制函数 $g (x)$ 在当前最优解 $x_{λ}$ 处的取值。比如，在前文提到的例子中，求解带惩罚的问题时，可以记录带惩罚的目标函数取得最优解时，选取的物品数量。然后，将 $g (x_{λ})$ 与所期望的 $y$ 进行比较，并相应调整下次计算时的 $λ$ 的取值。这就是最为传统的 WQS 二分的方法。

总结一下，传统 WQS 二分的基本流程如下：

初始时，选取一个 $λ$ 的合理的区间；
在当前的区间中选择一个 $λ$ ；
求解带惩罚的问题 $h (λ) = min_{x \in X} f (x) - λ g (x)$ ，并记录它的最优解 $x_{λ}$ 处 $g (x)$ 的取值 $g (x_{λ})$ ；
如果 $g (x_{λ}) = y$ ，就得到原问题的最优价值 $v (y) = h (λ) + λ y$ ，直接结束算法；
否则，根据 $g (x_{λ})$ 与 $y$ 的大小关系，调整 $λ$ 的区间，并回到步骤 2。

这一基本流程已经足以解决一些问题，但并不完善。接下来，本文将讨论对这一基本流程的改进。

共线情形的处理

在应用基本流程时，首先遇到的问题就是共线情形无法正确处理。

如果点集 $D$ 的下凸壳上有三个及以上的红点共线，那么在上述基本流程中，可能无法正确地判断 $g (x_{λ})$ 与 $y$ 的大小关系。比如，设共线的三个红点的横坐标分别为 $y_{1}, y_{2}, y_{3}$ ，且它们共线的直线的斜率为 $λ^{*}$ 。那么，要正确求解 $v (y_{2})$ ，就必须保证算法终止时，最后计算的问题是 $h (λ^{*})$ ，因为 $λ^{*}$ 是唯一一个最小化截距时能够经过点 $(y_{2}, v (y_{2}))$ 的直线的斜率。但是，因为在求解 $h (λ^{*})$ 的过程中，记录的 $g (x_{λ^{*}})$ 可能是 $y_{1}, y_{2}, y_{3}$ 中的任意一个。如果记录到的 $g (x_{λ^{*}})$ 不等于 $y_{2}$ ，那么算法将错误地继续运行，并向着背离 $y_{2}$ 的方向调整 $λ$ 的区间，最终将得到错误的结果。

为了解决共线的情形，一种处理方法是在记录最优解 $x_{λ}$ 对应的 $g (x_{λ})$ 时，总是使之尽可能大（或尽可能小）。同时，将二分中的终止条件从寻找恰好满足 $g (x_{λ}) = y$ 的 $λ$ 改为寻找满足 $g (x_{λ}) \geq y$ （或 $g (x_{λ}) \leq y$ ）的最小（或最大）的 $λ$ 。在上一段的例子中，这相当于计算问题 $h (λ^{*})$ 时，输出的 $g (x_{λ^{*}})$ 是 $y_{3}$ 。这就保证了算法终止时，最后计算的问题是 $h (λ^{*})$ 。实现这一方法时，需要注意最后输出的不是 $h (λ) + λ g (x_{λ})$ 而是 $h (λ) + λ y$ ，因为记录的 $g (x_{λ})$ 未必等于实际的限制 $y$ 。

另一种处理方法是实数二分。如果问题涉及的数字都是整数，显然，WQS 二分中的斜率也是整数。在二分中引入实数，是为了保证错误地排除正确选项 $λ^{*}$ 时，可以通过小数部分调整回来，最终逼近正确答案 $λ^{*}$ 。例如，在上面的例子中，如果计算问题 $h (λ^{*})$ 时，记录的 $g (x_{λ^{*}})$ 是 $y_{1}$ ，小于所希望的 $y_{2}$ ，那么，算法就会转而考虑区间 $(λ^{*}, λ_{r}]$ ，其中， $λ_{r}$ 是 $λ$ 所在区间的右端点。对于整数的情形，这一区间实际应该写作 $[λ_{*} + 1, λ_{r}]$ ，这就排除了在后续算法中接近正确答案 $λ^{*}$ 的可能。但是，实数二分时，考虑的区间仍然是 $(λ^{*}, λ_{r}]$ ，而且，对于该区间中的 $λ$ ，求解 $h (λ)$ 时记录的 $g (x_{λ})$ 总是不小于 $y_{3}$ ，从而严格大于 $y_{2}$ 的。因此，随着算法继续进行，会不断地舍去右半区间，从而，最终得到的 $λ$ 的范围可以保证在 $λ^{*}$ 附近。当然，因为已经知道所求的斜率是一个整数，实数二分终止时的精度不必太高，只要能保证二分的区间中只包含一个整数即可，这一整数就是要寻找的 $λ^{*}$ 。

正确地处理共线情形后，WQS 二分足以解决绝大多数算法竞赛会遇到的 WQS 二分的问题。但是，这一方法仍然存在一些不足之处：它无法处理 $g (x_{λ})$ 难以记录的情形，也无法处理高维 WQS 二分中多个点共面的情形。本文将进一步考察最优化问题 $v (y)$ 的性质，并提出更为一般的处理方法。

对偶方法

本节介绍一种 WQS 二分的实现方法，它只要求对于所有 $λ \in R^{d}$ ，可以高效地计算

h (λ) = min_{x \in X} f (x) - λ \cdot g (x)

的取值，且原问题的最优价值 $v (y)$ 是关于 $y \in R^{d}$ 的凸函数[^high-d-convex]。用一句话概括，本节将证明原问题的价值函数 $v (y)$ 就等于它的对偶问题的最优价值

v^{⋆} (y) = sup_{λ \in R^{d}} h (λ) + λ \cdot y,

而对偶问题的目标函数是关于 $λ \in R^{d}$ 的凹函数，从而是单峰函数，可以通过三分法或黄金分割法高效地求解，复杂度仍然是 $O (T (n) \log^{d} L)$ 的。这就完全地解决了传统 WQS 二分方法中记录 $g (x_{λ})$ 的值可能会出现的问题，同时，允许将 WQS 二分的思想应用至高维的情形。

另外，本节还说明， $g (x_{λ})$ 的范围可以通过 $h (λ)$ 求得，而无需在求解 $h (λ)$ 时额外记录。例如，对于 $d = 1$ 且问题只涉及整数的情形，可以证明 $g (x_{λ})$ 的取值范围恰为

[h (λ - 1) - h (λ), h (λ) - h (λ + 1)] .

这实际上也对于不得不采取前文所述二分流程的题目，提供了又一种解决共线问题的方法。

接下来，本节将用凸分析的理论证明这些结论成立。至于这些方法的具体应用，可以参考例题一节。

Lagrange 对偶

考虑用 Lagrange 乘子法解决该问题。引入 Lagrange 乘子 $λ \in R^{d}$ ，那么，Lagrangian 可以写作

L (x, λ, y) = f (x) - λ \cdot g (x) + λ \cdot y .

因为只要 $g (x) - y$ 有一个分量非零，就可以让相应的 $λ$ 的分量趋于（正或负）无穷，所以有

sup_{λ \in R^{d}} L (x, λ, y) = {\begin{cases} f (x), & g (x) = y, \\ + \infty, & otherwise . \end{cases}

这说明，原问题可以写作

\begin{aligned} v (y) & = min_{x \in X} sup_{λ \in R^{d}} L (x, λ, y) . \end{aligned}

交换两次最值操作，就得到它的对偶问题：

\begin{aligned} v^{⋆} (y) & = sup_{λ \in R^{d}} min_{x \in X} L (x, λ, y) \\ = sup_{λ \in R^{d}} h (λ) + λ \cdot y . \end{aligned}

马上要说明的是，在 $v (y)$ 是关于 $y$ 的凸函数的条件下，强对偶（strong duality）成立，即 $v^{⋆} (y) = v (y)$ 。

凸共轭

为了说明强对偶成立，需要引入凸共轭的概念。

凸共轭

对于函数 $f : R^{d} \to R \cup {\pm \infty}$ ，它的 凸共轭（convex conjugate），或称 Legendre–Fenchel 变换（Legendre–Fenchel transformation），是指函数

f^{*} (x^{*}) = sup_{x \in R^{d}} x^{*} \cdot x - f (x) .

从变量 $x^{*}$ 的角度看， $f^{*} (x^{*})$ 是一系列线性函数的上确界，所以，必然是 $R^{d}$ 上的凸函数。

超平面的「斜率向量」和「截距」

本文所讨论的向量空间 $R^{d + 1}$ 中的超平面的方程都具有形式

y = k \cdot x + b .

也就是说，本文不会涉及平行于 $y$ 轴的超平面。为表述方便，本文并不严谨地将 $k$ 称为该超平面的「斜率向量」， $b$ 称为该超平面的「截距」。将这一超平面的方程写成更标准的形式，就是

k \cdot x - y = - b .

它的一个法向量是 $(k, - 1)$ 。因此，所谓的斜率向量其实是将超平面的法向量归一化使得它的最后一个分量等于 $- 1$ 时，所得到的法向量的前 $d$ 个分量。

几何直观上，函数 $f (x)$ 的凸共轭描述的是，对于所有斜率向量为 $x^{*}$ 且与函数 $f (x)$ 的上境图

epi f = {(x, y) \in R^{d} \times R : f (x) \leq y}

相交的超平面，截距 $f (x) - x^{*} \cdot x$ 的最小值就是 $- f^{*} (x^{*})$ 。换句话说，函数 $f (x)$ 总在超平面 $y = x^{*} \cdot x - f^{*} (x^{*})$ 上方，且与该平面切于点 $(x_{0}, f (x_{0}))$ ；当然，可能存在其余的切点。这样的超平面，称为 $f (x)$ 在 $x_{0}$ 处的 支撑超平面（supporting hyperplane）。函数 $f (x)$ 的一个支撑超平面的截距由它的斜率向量唯一确定，凸共轭就提供了这个从斜率向量到截距的映射。

在集合 $X$ 上最小化 $f (x) - λ \cdot g (x)$ 就等价于在集合 ${(y, v (y))}$ 上最小化 $v (y) - λ \cdot y$ ：

\begin{aligned} min_{x} f (x) - λ \cdot g (x) & = min_{y \in g (X)} (min_{x \in X : g (x) = y} f (x) - λ \cdot g (x)) \\ = min_{y \in g (X)} (min_{x \in X : g (x) = y} f (x)) - λ \cdot y \\ = min_{y \in g (X)} v (y) - λ \cdot y . \end{aligned}

因此，有

h (λ) = min_{y \in g (X)} v (y) - λ \cdot y = - v^{*} (λ) .

这说明 $h (λ)$ 是关于 $λ \in R^{d}$ 的凹函数。进而，有

v^{⋆} (y) = sup_{λ \in R^{d}} λ \cdot y - v^{*} (λ) = v^{* *} (y) .

也就是说，对偶问题的价值函数 $v^{⋆} (y)$ 是原问题的价值函数 $v (y)$ 的双重凸共轭，也称为 双共轭（biconjugate）。

所以，问题转化为：什么样的函数 $v (y)$ 满足它的双共轭就等于它自身？这一问题的答案由如下定理给出：

定理（Fenchel–Moreau）

对于函数 $f : R^{d} \to R \cup {\pm \infty}$ ，它的双共轭等于它自身，即 $f^{* *} = f$ ，当且仅当以下三个条件之一满足：

$f (x)$ 是正常凸函数且下半连续，
$f (x) \equiv + \infty$ ，或
$f (x) \equiv - \infty$ 。

证明

一个函数是正常的（proper），当且仅当它从不取得 $- \infty$ 的值，且不永远取得 $+ \infty$ 的值。

对于非正常函数的情形，可以验证 $f (x) \equiv + \infty$ 和 $f (x) \equiv - \infty$ 互为共轭。除此之外，只要 $f (x)$ 在任何一点处取到 $- \infty$ ，必然有 $f^{*} (x^{*}) \equiv + \infty$ 。所以，满足 $f^{* *} = f$ 的非正常函数只有这两种情形。下面的讨论仅限于正常函数。对于正常函数，下半连续且凸的条件等价于它的上境图是闭凸集。

这一条件的必要性是容易的。因为 $f = f^{* *}$ 是 $f^{*}$ 的凸共轭，作为一系列线性函数的上确界，它的上境图必然是一系列闭凸集的交集，所以必然是闭凸集。这就说明，满足 $f^{* *} = f$ 的正常函数必然是下半连续且凸的。

反过来，这些条件也是充分的。和其他强对偶定理的证明一样，证明可以分为两步。

第一步，说明弱对偶成立，即 $f (x) \geq f^{* *} (x)$ 。由凸共轭的定义可知，对于所有 $x, x^{*} \in R^{d}$ ，都有

f^{*} (x^{*}) \geq x^{*} \cdot x - f (x) .

这就说明，对于所有 $x, x^{*} \in R^{d}$ ，同样有

f (x) \geq x^{*} \cdot x - f^{*} (x^{*}) .

对不等式右侧中的 $x^{*}$ 取上确界，就有 $f (x) \geq f^{* *} (x)$ 。

第二步，利用超平面分离定理说明 $f (x) \leq f^{* *} (x)$ 。假设不然，存在 $x_{0} \in R^{d}$ 使得 $f (x_{0}) > f^{* *} (x_{0})$ 成立。因为 $f (x)$ 的上境图 $epi (f)$ 是闭凸集，而且单点集 ${(x_{0}, f^{* *} (x_{0}))}$ 是紧凸集，所以，根据超平面分离定理，存在 $(λ, t) \in R^{d} \times R$ 和 $α \in R$ 使得对于所有 $x \in dom f := {x \in R^{d} : f (x) < + \infty}$ 和所有 $y \geq f (x)$ 都有

λ \cdot x - t y < α < λ \cdot x_{0} - t f^{* *} (x_{0})

成立。因为 $y$ 可以选得任意大，所以必然有 $t \geq 0$ 。这又可以分为两种情形。

首先，讨论 $t > 0$ 的情形。此时，将不等式的各部分都同除以 $t$ ，并设 $λ^{'} = t^{- 1} λ$ 和 $α^{'} = t^{- 1} α$ ，就得到

λ^{'} \cdot x - y < α^{'} < λ^{'} \cdot x_{0} - f^{* *} (x_{0}) .

对所有 $x \in dom f$ ，令 $y = f (x)$ ，就都成立

α^{'} > λ^{'} \cdot x - f (x) .

故而，对不等号右侧的 $x$ 取上确界，有

α^{'} \geq sup_{x \in R^{d}} λ^{'} \cdot x - f (x) = f^{*} (λ^{'}) .

进而，有

f^{* *} (x_{0}) < λ^{'} \cdot x_{0} - f^{*} (λ^{'}) \leq sup_{x^{*} \in R^{d}} x^{*} \cdot x_{0} - f^{*} (x^{*}) = f^{* *} (x_{0}) .

这一矛盾说明 $t > 0$ 的情形并不成立。

最后，讨论 $t = 0$ 的情形。事实上，将要说明的是，可以通过微扰，将它转化为 $t > 0$ 的情形。任取 $λ_{0} \in dom f^{*}$ ，根据凸共轭的定义可知，对于任何 $x \in dom f$ 和 $y \geq f (x)$ 都有

λ_{0} \cdot x - y \leq f^{*} (λ_{0}) .

因此，对于任意 $ε > 0$ ，都有

(λ + ε λ_{0}) \cdot x - ε y < α + ε f^{*} (λ_{0}) .

同时，因为 $α < λ \cdot x_{0}$ ，所以，对于充分小的 $ε > 0$ ，又有

α + ε f^{*} (λ_{0}) < (λ + ε λ_{0}) \cdot x_{0} - ε f^{* *} (x_{0}) .

因此，如果取 $λ^{'} = λ + ε λ_{0}$ ， $t^{'} = ε$ 和 $α^{'} = α + ε f^{*} (λ_{0})$ ，那么，就有

λ^{'} \cdot x - t^{'} y < α^{'} < λ^{'} \cdot x_{0} - t^{'} f^{* *} (x_{0}) .

这就又回到了前一种情形，仍然会导致矛盾。

这一矛盾说明，并不存在满足 $f (x_{0}) > f^{* *} (x_{0})$ 的点 $x_{0} \in R^{d}$ 。故而，总有 $f (x_{0}) \leq f^{* *} (x_{0})$ 。

结合这两步证明的结果，就得到 $f^{* *} (x) = f (x)$ 成立。

因此，强对偶成立，当且仅当 $v (y)$ 是关于 $y \in R^{d}$ 的凸函数[^other-conditions]。

次梯度

上一节说明了，带惩罚的问题的价值函数 $h (λ)$ 是原问题的价值函数 $v (y)$ 的凸共轭的相反数。因为凸共轭的定义实际上是一个含参数的最优化问题，所以它也成立类似包络定理的结论。但是，因为凸函数并非处处可微的，所以需要首先将导数的定义推广到凸函数的情形。这就引出了次梯度的概念。

次梯度

对于凸函数 $f : R^{d} \to R \cup {\pm \infty}$ 和 $x_{0} \in dom f$ ，如果向量 $x^{*} \in R^{d}$ 满足对于任何 $x \in R^{d}$ ，都有

f (x) \geq f (x_{0}) + x^{*} \cdot (x - x_{0}),

那么，就称 $x^{*}$ 是 $f (x)$ 在 $x_{0}$ 处的一个 次梯度（subgradient）。函数 $f (x)$ 在 $x_{0}$ 处的全体次梯度的集合称为它在该处的 次微分（subdifferential），记作 $\partial f (x_{0})$ 。

几何直观上，凸函数 $f (x)$ 在 $x_{0}$ 处的次微分，就是它在该处的所有支撑超平面的斜率向量的集合。对于一维的情形，次微分

\partial f (x_{0}) = [\partial_{-} f (x_{0}), \partial_{+} f (x_{0})],

其中， $\partial_{-} f (x_{0})$ 和 $\partial_{+} f (x_{0})$ 分别是函数 $f (x)$ 在 $x_{0}$ 处的左右导数。进一步地，对于整数集上的凸函数 $f : Z \to R \cup {\pm \infty}$ 延拓而来的 $\tilde{f} (x)$ ，它在整数点 $x = k$ 处的左右导数就是左右两侧的一阶差分：

\partial \tilde{f} (k) = [f (k) - f (k - 1), f (k + 1) - f (k)] .

显然，凸函数 $f (x)$ 在点 $x_{0}$ 处可微，当且仅当它在该处的次微分 $\partial f (x_{0})$ 是单点集。

因为凸共轭提供了从支撑超平面的斜率向量到它的截距的映射，所以，利用凸共轭，可以判断一个斜率向量 $x^{*}$ 是否是凸函数 $f (x)$ 在给定点 $x$ 处的一个次梯度。

定理（凸共轭与次梯度）

对于正常凸函数 $f : R^{d} \to R$ 和任意 $x, x^{*} \in R^{d}$ ，都有

x^{*} \in \partial f (x) ⟺ x^{*} \cdot x = f (x) + f^{*} (x^{*}) .

进而，如果 $f$ 还是下半连续的，那么这两个条件都等价于 $x \in \partial f^{*} (x^{*})$ 。

证明

按照次梯度的定义， $x^{*} \in \partial f (x)$ ，当且仅当

f (x^{'}) \geq f (x) + x^{*} \cdot (x^{'} - x), \forall x^{'} \in R^{d} .

这等价于

x^{*} \cdot x - f (x) \geq x^{*} \cdot x^{'} - f (x^{'}), \forall x^{'} \in R^{d} .

这又等价于

x^{*} \cdot x - f (x) \geq sup_{x^{'} \in R^{d}} x^{*} \cdot x^{'} - f (x^{'}) = f^{*} (x^{*}) .

但是，依据凸共轭的定义，总是有

x^{*} \cdot x - f (x) \leq f^{*} (x^{*}) .

因此，前一式中的大于等于号实际上等价于等号，也就等价于下式

x^{*} \cdot x = f (x) + f^{*} (x^{*}) .

这就完成了第一部分的证明。

对于 $f$ 是下半连续的正常凸函数的情形，依 Fenchel–Moreau 定理，有 $f^{* *} = f$ 。因此，这两个条件等价于

x^{*} \cdot x = f^{*} (x^{*}) + f^{* *} (x) .

再次应用第一部分的结论，它们也就等价于 $x \in \partial f^{*} (x^{*})$ 。

这一结论说明，如果 $f^{* *} = f$ ，那么凸共轭 $f^{*}$ 在 $x^{*}$ 处的次微分 $\partial f^{*} (x^{*})$ ，恰好就是斜率向量为 $x^{*}$ 的支撑超平面与上境图 $epi f$ 的交点的 $x$ 分量的集合。

推论

对于下半连续的正常凸函数 $f : R^{d} \to R$ 和任意 $x, x^{*} \in R^{d}$ ，都有

\begin{aligned} \partial f (x) & = \arg max_{y^{*} \in R^{d}} x \cdot y^{*} - f^{*} (y^{*}), \\ \partial f^{*} (x^{*}) & = \arg max_{y \in R^{d}} x^{*} \cdot y - f (y) . \end{aligned}

证明

下面，证明第二个等式。第一个等式的证明与之类似。

按照凸共轭的定义，有

f^{*} (x^{*}) = sup_{y \in R^{d}} x^{*} \cdot y - f (y),

所以，

x \in \arg max_{y \in R^{d}} x^{*} \cdot y - f (y)

当且仅当 $f^{*} (x^{*}) = x^{*} \cdot x - f (x)$ ，而这一等式成立，又当且仅当 $x \in \partial f^{*} (x^{*})$ 。这就证明了两个集合是相等的。

应用到本文的场景中，这一结论说明，求解问题

h (λ) = min_{x \in X} f (x) - λ \cdot g (x) = min_{y \in g (X)} v (y) - λ \cdot y

时，限制函数 $g (x)$ 在最优决策集合上的取值恰为 $\partial (- h (λ))$ 。对于 $d = 1$ 且问题只涉及整数的情形，这一集合就是区间

[h (λ - 1) - h (λ), h (λ) - h (λ + 1)] .

对于连续的整数 $λ$ ，这些区间首尾相接，所以，如果用于二分，只需要计算一侧的端点即可。

凸性证明

应用 WQS 二分的前提条件是价值函数的凸性。在算法竞赛中，可以通过打表、感性理解等方式猜测凸性成立。但是，严格地证明凸性成立，往往并不容易。本节结合如下经典题目，介绍算法竞赛中常见的证明凸性的方法。

种树问题

有 $n$ 个树坑，要种 $m$ 棵树。树不能栽种于相邻的两个坑。给定长度为 $n$ 的序列 ${a_{i}}$ ，表示在每个坑种树的收益，收益可正可负。求种完这 $m$ 棵树最大可能的收益和。

简言之，就是在长度为 $n$ 的链上，求解大小为 $m$ 的最大权独立集的问题。

这些方法粗略地可以分为四类：

归约为凸优化问题（包括线性规划等）的价值函数对参数的凸性，这包括建立费用流模型等方法；
利用状态转移方程也可以归纳地证明凸性成立，过程中可能会用到一些保持凸性的变换；
对于区间分拆类型的问题，可以验证每段区间的成本函数满足四边形不等式；
最后，对于特殊的问题，也可以通过交换论证直接说明凸性成立。

这些证明方法本身往往都同该问题的某种解法联系在一起。

归约为含参凸优化

考虑如下形式的含参凸优化问题：

v (y) = inf_{x \in D (y)} f (x, y) .

其中，目标函数 $f : R^{n} \times R^{d} \to R \cup {\pm \infty}$ 对于每个 $y \in R^{d}$ 都是关于 $x \in R^{m}$ 的凸函数，而可行域 $D : R^{d} \to P (R^{m})$ 是 $R^{d}$ 上的集合值函数，且对于每个 $y \in R^{d}$ ，集合 $D (y)$ 都是凸集。这些条件保证了对于任意参数 $y \in R^{d}$ ，这都是一个凸优化问题。

定理

假设上述含参凸优化问题满足如下条件：

目标函数 $f (x, y)$ 是关于 $(x, y)$ 的凸函数；
可行域映射 $y \mapsto D (y)$ 的图像 ${(x, y) : x \in D (y)}$ 是凸集。

如果对于任意 $y \in R^{d}$ ，都有 $v (y) > - \infty$ ，那么，价值函数 $v (y)$ 是关于 $y$ 的正常凸函数。

证明

对于任意 $y_{1}, y_{2} \in R^{d}$ 和 $α \in (0, 1)$ ，需要证明

v (α y_{1} + (1 - α) y_{2}) \leq α v (y_{1}) + (1 - α) v (y_{2}) .

如果 $v (y_{1}) = + \infty$ 或 $v (y_{2}) = + \infty$ ，那么不等式的右侧就是 $+ \infty$ ，不等式必然成立。否则， $v (y_{1})$ 和 $v (y_{2})$ 都是有限值。对于任意 $ε > 0$ 和 $i = 1, 2$ ，都存在 $x_{i} \in D (y_{i})$ 使得 $f (x_{i}, y_{i}) < v (y_{i}) + ε$ 成立。利用映射 $D$ 的图像的凸性可知

α x_{1} + (1 - α) x_{2} \in D (α y_{1} + (1 - α) y_{2}) .

也就是说， $α x_{1} + (1 - α) x_{2}$ 是参数为 $α y_{1} + (1 - α) y_{2}$ 的最优化问题的一个可行解。利用最优化条件和目标函数的凸性可知

\begin{aligned} v (α y_{1} + (1 - α) y_{2}) & \leq f (α x_{1} + (1 - α) x_{2}, α y_{1} + (1 - α) y_{2}) \\ \leq α f (x_{1}, y_{1}) + (1 - α) f (x_{2}, y_{2}) \\ < α v (y_{1}) + (1 - α) v (y_{2}) + ε . \end{aligned}

因为 $ε$ 的选取是任意的，令 $ε \to 0$ ，就有

v (α y_{1} + (1 - α) y_{2}) \leq α v (y_{1}) + (1 - α) v (y_{2}) .

因此，价值函数 $v (y)$ 的凸性成立。

算法竞赛中，最为常见的凸优化问题就是线性规划问题。

推论

设 $c \in R^{n}$ ， $A_{1} \in R^{d_{1} \times n}$ ， $A_{2} \in R^{d_{2} \times n}$ ， $y_{1} \in R^{d_{1}}$ ， $y_{2} \in R^{d_{2}}$ 。考虑如下含参线性规划问题：

v (y_{1}, y_{2}) = min_{x \in R^{n}} c \cdot x subject to A_{1} x \leq y_{1}, A_{2} x = y_{2}, x \geq 0.

那么，价值函数 $v (y_{1}, y_{2})$ 是关于 $(y_{1}, y_{2})$ 的凸函数。

无论是不等式约束，还是等式约束，线性规划的价值函数都是约束条件参数的凸函数。

很多图论问题都可以写成线性规划问题的形式：

网络流问题：最大流、最小割、最小费用流；
无负环的最短路问题；
二分图的最大（权）匹配、最小点覆盖等问题；
一般图的最大（权）匹配问题；
最小生成树问题[^mst]。

因此，这些问题的价值函数都是这些问题的参数的凸（凹）函数。

整数约束

利用图论模型为实际问题建模时，通常有隐含的整数限制，例如一条边只能选或不选、流量只能是整数等。因此，它们只能转化为整数线性规划（integer linear programming, ILP）问题而非线性规划（LP）问题。因为 ILP 问题并非凸优化问题，所以它的价值函数未必是该问题的参数的凸函数。将一个 ILP 问题中的整数约束松弛掉后就得到一个 LP 问题，但后者未必存在满足整数约束的最优解。因此，松弛整数约束后得到的 LP 的最优价值有可能严格优于相应的 ILP 问题，两者未必等价。

上文列举的那些图论问题，都可以写成一个 LP 问题而不需要施加整数约束；但对于其他的一些问题，例如一般图的最大独立集问题等，整数约束则是必要的。另外，即使一个图论问题可以写成 LP 的形式，在该问题引入额外的线性约束条件后，仍然可能会破坏相应的 ILP 问题和 LP 问题的等价性，从而这个带约束的图论问题不再能够写成线性规划的形式。

例如，在费用流的语境下，有如下常见结论：

推论

最小费用流模型中，最小费用 $v (m)$ 是流量 $m$ 的凸函数。

证明

设有向图 $G = (V, E)$ ，边 $(i, j)$ 的容量为 $c_{i j}$ ，单位流量的费用为 $w_{i j}$ ,，源点和汇点分别为 $s$ 和 $t$ 。记决策变量为 ${f_{i j}}$ ，其中， $f_{i j}$ 为边 $(i, j) \in E$ 的流量。那么，最小费用流可以写成如下线性规划问题：

\begin{aligned} v (m) = min_{{f_{i j}}} & \sum_{(i, j) \in E} w_{i j} f_{i j} \\ subject to & \sum_{(j, i) \in E} f_{j i} - \sum_{(i, j) \in E} f_{i j} = {\begin{cases} - m, & i = s, \\ m, & i = t, \\ 0, & otherwise, \end{cases} \forall i \in V, \\ 0 \leq f_{i j} \leq c_{i j}, \forall (i, j) \in E . \end{aligned}

因此，最小费用 $v (m)$ 是参数 $m$ 的凸函数。

算法竞赛中很多问题都可以归约为网络流等图论问题，从而都可以通过类似的方式建立价值函数的凸性。

利用这一方法，可以得到种树问题的第一个凸性证明：

凸性证明一

种树问题的最大收益实际上可以通过如下最大费用最大流模型得出：

从源点 $s$ 出发，向结点 $r$ ，连接一条容量为 $m$ 、费用为 $0$ 的边；
从结点 $r$ 出发，向每个奇数结点 $i = 1, 3, \dots, 2 ⌈ n / 2 ⌉ - 1$ 连接一条容量为 $1$ 、费用为 $0$ 的边；
从每个偶数结点 $i = 0, 2, \dots, 2 ⌊ n / 2 ⌋$ 出发，向汇点 $t$ 连接一条容量为 $1$ 、费用为 $0$ 的边；
对于每个 $i = 1, \dots, n$ ，从 $i - 1$ 和 $i$ 中的奇数结点出发，向偶数结点连接一条容量为 $1$ 、费用为 $a_{i}$ 的边。

最终答案就是求得的最大费用。将这一图论模型转换为相应的线性规划问题（具体见上文推论的证明），那么，总流量 $m$ 将出现在表示边 $(s, r)$ 的流量限制的不等式中。由推论可知，最大费用 $v (m)$ 是流量 $m$ 的凹函数。

利用该费用流模型，可以通过模拟费用流或反悔贪心的方法在 $O (n \log n)$ 的复杂度内解决该问题。

利用状态转移方程

尽管状态转移方程无法提供有效的计算方式，但是，它常常可以用于证明状态函数 $f (i, j)$ 对于参数 $j$ 具有凸性。具体地说，就是将 $f (i, \cdot)$ 这一函数视为 $i$ 处的状态，就可以将关于 $f (i, j)$ 的状态转移方程看作是关于 $f (i, \cdot)$ 的递推关系，从而可以归纳地证明每个 $f (i, \cdot)$ 都是凸函数。这类证明凸性的方法在 Slope Trick 优化 DP 的场景中更为常见，该页面也讨论了常见的保持凸性的变换。

这一方法同样可以用于证明种树问题的凸性：

凸性证明二

设 $f (i, j)$ 为前 $i$ 个坑种 $j$ 棵树时的最大收益。考察如下状态转移方程：

f (i, j) = max {f (i - 1, j), f (i - 2, j - 1) + a_{i}} .

将这一状态转移方程看作是函数 $f (i, \cdot)$ 的递推关系式。因为最值符号内涉及两个不同的函数，这并不能表达为卷积上确界的形式。但是，仍然可以通过归纳的方法证明函数 $f (i, \cdot)$ 是凹函数。

实际上，需要归纳地证明如下两点：

$f (i, j) - f (i - 2, j - 1)$ 关于 $j$ 递减；
$f (i, j) - f (i - 1, j)$ 关于 $j$ 递增。

归纳起点是平凡的。假设它们对于所有 $i - 1$ 及之前的自然数都成立，现在证明它对 $i$ 也成立。直接验证即可。

首先，由归纳假设，有

f (i - 1, j) - f (i - 2, j - 1) = (f (i, j) - f (i - 2, j - 1)) - (f (i, j) - f (i - 1, j))

关于 $j$ 递减。所以，有

f (i, j) - f (i - 2, j - 1) = max {f (i - 1, j) - f (i - 2, j - 1), a_{i}}

关于 $j$ 递减，且

f (i, j) - f (i - 1, j) = max {0, a_{i} - (f (i, j) - f (i - 2, j - 1))}

关于 $j$ 递增。这就完成了归纳。

进而，有

f (i, j) - f (i, j - 1) = (f (i, j) - f (i - 2, j - 1)) - (f (i, j - 1) - f (i - 1, j - 1)) - (f (i - 1, j - 1) - f (i - 2, j - 1))

关于 $j$ 递减。这就说明 $f (i, j)$ 是关于 $j$ 的凹函数，从而，价值函数 $v (m) = f (n, m)$ 是关于 $m$ 的凹函数。

这个证明的一个副产品是，对于任意 $i$ ，都存在 $p_{i}$ 使得

f (i, j) = {\begin{cases} f (i - 1, j), & j \leq p_{i}, \\ f (i - 2, j - 1) + a_{i}, & j > p_{i} . \end{cases}

这说明，可以通过平衡树直接维护序列 $f (i, \cdot)$ ，复杂度是 $O (n \log^{2} n)$ 的。但是，好处是可以处理任意种树间隔的一般情形，且一次性地获得了所有 $v (m)$ 的值。

四边形不等式

算法竞赛中，另一类常见的成立凸性的问题是区间分拆问题。该页面证明了，如果单个区间的成本函数满足四边形不等式，那么限制区间个数的区间分拆问题的最小成本是区间个数的凸函数。该页面同样提供了一些判断某个函数 $w (l, r)$ 是否满足四边形不等式的方法。最为直接的方法就是计算它的二阶混合差分：

\begin{aligned} Δ_{l} Δ_{r} w (l, r) & = Δ_{l} (w (l, r + 1) - w (l, r)) \\ = w (l + 1, r + 1) - w (l + 1, r) - w (l, r + 1) + w (l, r) . \end{aligned}

函数 $w (l, r)$ 满足四边形不等式，当且仅当 $Δ_{l} Δ_{r} w (l, r)$ 非正。直观上，满足四边形不等式的函数通常意味着，区间向两侧扩大——即左端点向左移动和右端点向右移动——具有某种协同效应。

种树问题同样可以看作是一个区间分拆问题，可以通过验证四边形不等式进行证明。

凸性证明三

在种树的收益序列前添加一个 $a_{0}$ ，它可以是任何值。然后，种树问题就等价于将序列 ${a_{0}, a_{1}, \dots, a_{n}}$ 分成 $m$ 段，且每段的收益函数为

w (l, r) = max_{i \in [l + 1, r]} a_{i}

的区间分拆问题。也就是说，每一段的收益是除去第一棵树外，其余树的收益的最大值——这就保证了间隔种树。

因为这是最大化问题，需要验证「交叉大于包含」，即对于任意 $a

本页面最近更新：2025/9/27 00:48:44，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：c-forrest, HeRaNO, jyeric
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用