硬约束到软约束（满足变成代价）

上级: relaxation

通向优化最重要的一步松弛：把一条硬约束（必须成立）变成一个惩罚项（成立更好，并且用违反了多少来衡量）。一个谓词变成了一个数量。

这一步怎么走

• SAT → MaxSAT。 SAT 问的是："存在一个赋值满足所有子句吗？"（一个是/否的判定问题）。MaxSAT 问的是："哪个赋值满足的子句最多？"（一个优化问题）。可行性 → 最优性。
• CSP → 软约束 / 加权优化。 硬约束变成加权惩罚；目标是找到使总违反量最小的赋值。（正是把 harness 的 CSP 软化。）
• 可行性 → 目标函数。 "在可行集里找一个点"变成"最小化到可行集的距离"——还是同一个集合，只是现在多了一个指向内部的梯度。

Lagrangian 本身就是这个松弛

硬约束 g(x) ≤ 0 变成加到目标函数上的一个惩罚项 λ · max(g(x), 0)——这正是 Lagrangian 的手法，乘子 λ 就是违反该约束的价格。所以 约束优化 就是逻辑可行性的软约束松弛：不是禁止 g(x) > 0，而是对它收费，让优化器在违反量和目标函数之间做权衡。

为什么它是通往优化的门

"满足 φ"（一个你只能检验真假的谓词）变成了"最小化对 φ 的违反"（一个你可以下降的数字）。一旦约束有了幅度，梯度下降、对偶、连续搜索就都可用了——你已经从逻辑迈进了 optimization。

代价： MaxSAT 依然是 NP-hard 的，而且惩罚权重 λ 必须被选定——难度并没有消失，只是转移到了给价格调参上（天下没有免费的午餐）。