LP-type 问题 | Codeboy's Blog

形式陈述

值、违反者与两条公理

很多优化问题有大量约束，但最优解只由少量约束决定。这个现象还不够支持抽样算法：必须保证一个小集合既保存当前答案，也保存未来约束怎样使答案改变。LP-type 模型把这两个要求分开写清。

设 $H$ 是有限约束集合， $w:2^H\to\Omega$ ，其中 $\Omega$ 带全序。本页使用每个子集都有已定义值的版本，以值越大表示约束越强。要求：

单调性： $F\subseteq G$ 时， $w(F)\le w(G)$ 。
局部性： $F\subseteq G$ 且 $w(F)=w(G)$ 时，对所有 $h\in H$ ，

w(F\cup\{h\})>w(F) \quad\Longleftrightarrow\quad w(G\cup\{h\})>w(G).

定义违反集合

V(F)=\{h\in H:w(F\cup\{h\})>w(F)\}.

单调性使 $V(F)$ 不含 $F$ ，局部性则说同值的嵌套集合拥有完全相同的违反集合。文献也允许一个未定义底值并只在非底值处要求局部性；采用该版本时，必须先处理那些子问题，不能把本页所有子集都适用的证明原样套过去。[1, Definition 3.1]

基是包含关系极小，不是个数最小

$B\subseteq G$ 是 $G$ 的一份基，若 $w(B)=w(G)$ ，且每个真子集 $B'\subsetneq B$ 都有 $w(B')<w(B)$ 。有限性保证每个 $G$ 至少有一份基：只要能删除一个约束而不改变值就继续删，最终必停止。

组合维数 $\delta$ 是所有子集的所有基中最大的基大小，不只是完整输入的一份最优证书大小。完整输入恰巧有一个很小的基，不会自动给出全局 $\delta$ 。LP-type 中的“基”是约束子集，未必是线性代数的向量基，也不是单纯形表选出的列基。

可执行接口至少包括：求小子集的值或代表解；测试一个约束是否违反；必要时返回一份基。基只需要包含极小，通常没有必要要求唯一。Clarkson 加权抽样正是用小子集求解器与违反测试反复处理大输入的算法之一。

直觉

小集合需要保留“未来反应”

如果 $B$ 是 $G$ 的基，单调性只告诉我们它们当前值相同；局部性进一步告诉我们：下一个约束是否会迫使值升高，只看 $B$ 已经足够。它允许把历史约束压缩成一个小的决定集合，却不要求把整个可行域压缩成同一个几何形状。

例如两个不同的多边形可以共享一个字典序最优点。它们形状不一样，但在“加入一个半平面会不会排除当前唯一最优点”这一问题上反应一致。若加入的半平面保留该点，最优点继续合法；若排除它，两者的规范最优值都必须改变。

删除关键点比选择一份基更稳妥

定义极端元素

X(G)=\{h\in G:w(G\setminus\{h\})<w(G)\}.

它恰好等于 $G$ 的全部基的交集。若某份基不含 $h$ ，删除 $h$ 后仍保留那份基，值不会下降；反过来，若删去 $h$ 不改变值，在 $G\setminus\{h\}$ 中继续删减就得到一份不含它的基。因此 $|X(G)|\le\delta$ ，即使存在许多不同的基也成立。

不能把圆上每个点或每条紧约束都当成极端元素。多个证书彼此替代时，可能一份基有两个元素，所有基的交却为空。反向分析计数的是“删除谁真的改变答案”，不是“谁看起来位于边界”。

例子与边界

四个圆上点，两个不同的基

取 $H=\{(-1,0),(1,0),(0,1),(0,-1)\}$ ， $w(G)$ 为其最小包围圆的平方半径，并给空集单独值 $-1$ 。非空集合的最小圆唯一，所以嵌套集合半径相同就意味着圆相同，局部性成立。空集若也用零半径，便会与不同位置的单点混淆，因此这里的 $-1$ 是合同的一部分。

完整集合的半径平方为 $1$ 。两对相对点分别是一份基；删除任意一个点，另一对相对点仍在，所以 $X(H)=\varnothing$ 。每份基有两个点，不代表必有两个删除关键点。

只保留 LP 的目标数值可能失败

在固定正方形 $[0,1]^2$ 内最小化 $x$ 。令 $F$ 无额外约束， $G=\{y\ge1\}$ 。两者最优目标值都为零。再加入 $h:y\le0$ ， $F\cup\{h\}$ 仍有最优值零， $G\cup\{h\}$ 却不可行。只存标量零的值函数不满足局部性。

一种修复是把目标值以及逐坐标消除并列后的规范最优点一起作为全序值；不可行则用大于全部可行值的标记。对于最大化接口，约束增加会让规范最优值下降，因此要把这个规范值的比较次序反过来作为模型中的 $w$ 次序，才能满足这里“约束越多，值越大”的单调性。形式框的仿射系数也先按算法的最终字典序组成键，再取反序；不要仅把最大化数值原样填入 $w$ 。注意“算法碰巧返回某一个最优点”不够，选择规则必须由约束集合决定，不能依赖插入历史。Seidel 二维算法用精确字典序实现这一要求。

直径虽有两个见证点，仍不局部

令 $a=(-1,0),b=(1,0),p=(0,1),q=(0,-3/2)$ ，值取平方直径。 $F=\{a,b\}$ 与 $G=\{a,b,p\}$ 都有值 $4$ 。向 $F$ 加 $q$ 后，新增距离平方为 $13/4<4$ ，值不变；向 $G$ 加 $q$ 后， $\|p-q\|^2=25/4>4$ ，值增大。

因此 $q$ 违反 $G$ 而不违反 $F$ 。每个直径由两个点见证，仍不能据此把直径问题当成组合维数二的 LP-type 问题。这是局部性承担的真实限制，而不只是术语上的附加条件。

推论与应用

抽样恒等式来自一次双计数

从 $n=|H|$ 个约束中均匀取一个恰含 $r$ 项的子集 $R$ ， $0\le r<n$ 。再取均匀的 $(r+1)$ 元子集 $Q$ 。记

v_r=\mathbb E|V(R)|,\qquad x_{r+1}=\mathbb E|X(Q)|.

这里的期望分别对固定大小的均匀子集取。考虑所有二元组 $(R,h)$ ，其中 $h\notin R$ 且 $h$ 违反 $R$ ；把它改写为 $(Q,h)=(R\cup\{h\},h)$ ，条件恰是 $h\in X(Q)$ 。所以

\binom nr v_r=\binom n{r+1}x_{r+1},\qquad \frac{v_r}{n-r}=\frac{x_{r+1}}{r+1}.

进而

\mathbb E|V(R)|\le\delta\frac{n-r}{r+1}.

恒等式本身甚至不需要局部性：只需对加入/删除是否改变值采用一致定义。局部性用于后续算法把当前违反者与一份全局基联系起来，不能因为双计数暂时没用它，就把整个抽样算法的前提删掉。[1, Lemma 1.1]

把四点例子全部算完

对前面的四个轴向点取 $r=2$ ，共有六份样本。两份相对点样本已经决定单位圆，违反者为零；四份相邻点样本的直径圆都被剩下两点违反。所以

v_2=(2\cdot0+4\cdot2)/6=4/3.

四份三点集合各有一对唯一的相对点基，故 $x_3=2$ 。恒等式两边都是 $2/3$ ： $v_2/(4-2)=(4/3)/2$ ， $x_3/3=2/3$ 。完整四点集合的极端元素为空，与三点样本中的两个极端元素并不矛盾，二者是不同随机层。

什么时候值得调用这个模型

建立 LP-type 接口时，先写清所有子集的值，包括空集、不可行和可能无界的子问题；再证明规范选择与局部性；最后给所有基的统一大小上界以及真正可执行的违反测试。只证明完整问题有一个最优解，并没有完成这些步骤。

即使 $\delta$ 是常数，小基求解也可能昂贵。复杂度应分别计违反测试数、求基调用数和单次求解成本，不能把“至多 $\delta$ 个约束”直接叫作常数时间。在变维输入中， $\delta$ 随维度增长，更不能把固定维数的线性界当作高维求解器保证。

终结任务将枚举四点集合的全部子集、全部基和全部样本，独立核验局部性与抽样恒等式；它还要求保留上面的直径反例，说明哪一个公理真的失效。

参考资料

Bernd Gärtner、Emo Welzl，“A Simple Sampling Lemma: Analysis and Applications in Geometric Optimization”，2001，§1 Lemma 1.1；§3 Definitions 3.1–3.2、Fact 3.3，PDF pp.2、6–8。该文的底值版本需注意其局部性适用域。
Raimund Seidel，“Small-Dimensional Linear Programming and Convex Hulls Made Easy”，1991，§2，印刷 pp.425–426：规范最优点与退化情形下的删除关键约束。
Kenneth L. Clarkson，“Las Vegas Algorithms for Linear and Integer Programming When the Dimension Is Small”，1995，§2.2–3：小约束集求解和全局违反检查的算法用途。

形式陈述 ​

值、违反者与两条公理 ​

基是包含关系极小，不是个数最小 ​

小集合需要保留“未来反应” ​

删除关键点比选择一份基更稳妥 ​

四个圆上点，两个不同的基 ​

只保留 LP 的目标数值可能失败 ​

直径虽有两个见证点，仍不局部 ​

抽样恒等式来自一次双计数 ​

把四点例子全部算完 ​

什么时候值得调用这个模型 ​

反向链接