Clarkson 加权抽样

漏掉的重要约束要更容易被再次抽中 ​

随便抽一个小子集，经常会漏掉真正决定全局答案的约束。算法不把所有违反者永久塞进一个不断膨胀的子问题，而是提高它们下一轮出现的机会。小样本规模固定，增加的是抽样分布的偏向。

为什么违反者太多时反而不加权？若几乎全部权重都同时翻倍，各项的相对概率几乎没变，重要约束也没变得更突出。轻违反阈值控制总权增长，才能让某份真正的全局基比全体约束更快变重。

精确整数票，不把大权重转浮点 ​

按固定 ID 次序建立累计权重 $s_i=\sum _{j\le i}{w}_j$。独立均匀取整数票 $t\in \{0,\dots ,W-1\}$，用二分查找理路二分查找Binary search在有序数组中反复排除一半候选区间的查找算法。找第一个 $s_i>t$，就精确实现概率 $w_i/W$。当 $t$ 恰为某项累计值时，应归入下一项，故是严格大于而不是大于等于。

一轮内重复抽中同一个约束，不意味着它在求解时应多次施加，也不意味着更新时要按抽中次数翻倍。倍增对象是全局检查得到的违反集合，每个违反 ID 只乘二一次。重新使用同一串票或每轮重置相同种子会破坏条件独立性，不能沿用下面的概率证明。

四轮真实轨迹 ​

取二维约束 $h_i:x\le i$，$i=0,\dots ,127$，最大化 $x$；字典序中的 $y$ 方向由形式框处理。最终最强约束是 $h_0$。执行器用允许不可行系统的保守维数上界 $\delta =3$，每轮抽 $54$ 次，初始 $W=128$。

种子194产生以下完整运行；“样本最小 ID”决定本轮 $x$ 上界，全部54个原始抽样 ID 保存在下载结果中。

第二轮后总权是 $128+3=131$；第三轮增加的是当前 $w_0=2$，所以变成133，而不是132。最后 $x=0$ 为真正最优值，不能在第二轮得到 $x=3$ 时提前退出。

固定样本只负责求候选 ​

这个例子的约束实际上全都平行，最优基只有一个 ID；算法使用更大的合法维数上界只会使样本更大。一般输入可能需要两个最优性约束，或者三条矛盾约束。不能从这一次运行看到单元素基，就把通用二维求解器的 $\delta$ 改成一。

若将最强约束替换为与其余约束矛盾的几条半平面，输出应变成不可行。若删掉所有限制目标增长的半平面，输出应变成无界射线。加权外层不负责修补底层 LP 接口，把这三类状态全写成一个未经定义的数值会破坏模型的局部性。

有放回样本的违反权界 ​

固定当前权重。令 $Z_1,\dots ,Z_{r+1}$ 为独立同分布的加权抽样，$R$ 是前 $r$ 项所含的不同约束集合。条件于 $R$，最后一项违反它的概率恰为 $w(V(R))/W$。

反过来，固定全部 $r+1$ 个抽样位置构成的多重集，均匀选一个位置删除。若某约束出现至少两次，删除其中一个位置不改变所含约束集合。其余可能改变答案的位置，对应去重集合中的极端元素，至多 $\delta$ 个。因此由交换性，

这段论证允许重复、允许基不唯一，也不把有放回样本误当均匀 $r$ 元子集。由 Markov 不等式理路Markov 不等式Markov's inequality非负随机变量超过阈值的概率由其期望除以阈值控制。，

所以条件于任意过去历史，下一轮至少以一半概率通过轻违反阈值或直接结束。条件概率下界才是后续期望轮数证明所需的性质。

每轮有效倍增都击中一份固定的全局基 ​

固定完整系统的一份基 $B^{\ast }$，不要求唯一。若候选还违反某些约束，却没有违反 $B^{\ast }$ 中任何一项，逐个把 $B^{\ast }$ 的项加入样本。每次都保持原值，且局部性使违反集合保持不变。最终得到

这里用 $\phi$ 表示 LP-type 的优化值函数，与整数权重分开记。相等再结合局部性给出 $V(R)=V(H)=\varnothing$，与尚有违反者矛盾。因此每轮没有结束的有效倍增，必将 $B^{\ast }$ 中至少一个权重乘二。

为避免实现混淆，程序把优化解存为 symbolic，整数权重数组单独存为 weights，不会拿同一个数兼任两个含义。

基增长快，总权增长慢 ​

设进行了 $k$ 次没有结束的有效倍增。每次总权至多乘 $1+1/(3\delta )$，所以

设 $b=|B^{\ast }|\le \delta$。若 $b=0$，初始值已是全局值，算法直接结束；否则该基各项权重的乘积至少为 $2^k$。由算术—几何平均不等式，

合并得到

所以有效倍增只有 $O(\delta \log (n+1))$ 次；每次等待下一次有效试验的条件期望至多二，算法几乎必然结束，期望总轮数也为这个数量级。基非唯一不影响证明，因为从头到尾只固定任意一份 $B^{\ast }$。

实际成本与维度依赖 ​

设单次违反测试成本为 $C_v$，至多 $r$ 个约束的小求解器成本为 $Q(r)$。按前缀权重加二分实现，一轮需

次基本操作，故总期望乘上 $O(\delta \log (n+1))$。这显式保留了 $r=6{\delta }^2$ 和小求解器代价；没有免费抽样，也没有免费检查完整输入。

附件只实例化二维 LP，固定 $\delta =3$，用精确枚举形式框顶点的小内核求解样本；若不可行，再删除冗余样本约束取得至多三行证书。这个内核最坏 $Q(r)=O((r+4{)}^4)$，对固定的54项是常数，因此整个加权循环期望为 $O((n+1)\log (n+2))$ 次精确算术/整数操作，工作空间 $O(n+1)$。它不是 Clarkson 混合算法的期望线性实现。

上述有效轮数界还给出 $W_k\le n^{1+1/[3(\ln 2-1/3)]}$，所以权重与整数票只需 $O(\log (n+1))$ 位，不会因为无限次拒绝就持续增长。几何有理数运算仍须计输入位长；开启完整日志会额外保存每轮54次抽样及违反 ID，其总大小按实际轨迹计。预算为零直接返回未知，空约束则由底层求解器按原目标返回有限零目标或无界，不需要抽样。

终结任务要求重放以上四轮，逐次核阈值和总权，再用独立完整 LP 求解核验最后输出。完整执行器保留这些原始抽样记录，读者可以换输入而不是只重画概率直觉。