upward-reequilibration

向上再平衡——cut 与 price 向上流动

父级:recursive-harness

一个节点已经在它的局部均衡处完成了拆分,结果依然糟糕——它能不能把这个情况往上推,带着足以让祖先节点重新评估自己那一层均衡的信息?可以——而且优化理论已经把这套机制经营了五十年:分解方法(decomposition methods),cut 与 price 向上流动。

1. 把"在均衡点上仍然糟糕"说清楚

该节点算出自己的局部 U 曲线,发现 R(n)>R(n^*) > 它的配额——曲线的最小值就已经高于父节点分配的 (α, B)。这不是一个"再努力一点"的信号,而是一份不可行性证明在我的预算内,没有任何粒度能满足我的 spec。它与轨迹冲突("这次尝试失败了")在性质上不同:这是一个结构性冲突——出问题的不是任何一次执行,而是父节点的取景(framing)本身。

2. 向上传递的是曲线,不是失败

向上传递的消息带的是这个局部问题的形状:可达到的下限 R(n)R(n^*)、哪一项占主导(split-α 还是 leaf-ε)、以及地形在哪里是恶劣的(哪些子区域落在模型能力流形之外)。恰好对应经典分解方法里的两个等级:

  • 硬的一面:Benders 可行性 cut。 子问题不可行时,Benders 分解不会只返回"失败"——它返回一个 cut,用来约束主问题下一次的选择:"在这个预算下,任何用这种方式取景这片地形的拆分都不可行。"这个对应关系是严格成立的:no-good learning ≡ 组合 Benders cut(Codato–Fischetti)。所以这正是conflict-learning-and-backjumping那套机制,从决策维度推广到了粒度维度:一次普通的回跳(backjump)改变的是分支;一个可行性 cut 改变的是树的形状
  • 软的一面:price(对偶)。 即便一个子节点是可行的,它也会报告自己满足 spec 的边际成本——也就是其约束的影子价格(shadow price),即hard-to-soft-constraints的拉格朗日乘子读法。父节点随后在兄弟节点之间重新分配配额(把 α/B 从便宜的孩子挪给昂贵的孩子),而不需要重新拆分——这是 Dantzig–Wolfe 式的价格协调。

3. 父节点如何重新达到均衡

父节点自己的 U 曲线,本是建立在对每个区域 ε(s)估计之上的;而子节点报回来的,是实测的地形。用实测替换估计 → 父节点的曲线移动 → 它的均衡点随之移动 → 它换一种方式重新拆分;如果它自己的新下限也超出了自己的配额,这个 cut 就再往上传一层——如此递归,直到某个祖先节点能吸收它,或者一路传到根。在根节点上,一个无法被吸收的 cut,就是giant-tasks-nonprimitive所说的加公理时刻:人类扩展这个系统(更多预算、放松 spec、新的证明形式)。

4. 为什么它不会振荡

Cut 是单调累积的(主问题的可行集只会收缩),α/B 的账本也只会被消耗——这正是让 CDCL 收敛的那条"赋值非单调、知识单调"的腿。每一次重新均衡都要从账本里付账,并且永久性地收窄搜索空间。机械协调者负责存储这些 cut(no-good 存储泛化为 cut 存储),并按来源(provenance)路由它们。

5. 闭合的循环

任务树本身就是一个分解算法——主问题就是父节点的拆分选择,子问题就是各个子节点。"该往上传什么"这个问题,优化理论五十年前就给出了答案:cut 与 price。从逻辑到优化的这次迁移,又一次在树的上行通道上闭合了。

一个在任何粒度下都无法满足 spec 的子节点,并不是失败了——它是在教:它送上去一个 cut,重塑父节点的问题;送上去一个 price,重新平衡整个家族的预算。

upward-reequilibration