精读笔记

Problem Setting

[A Relaxation and Rectification (ReCR) Framework for Systems with Linear and Complementary Constraints: Theoretical Foundation, Algorithms and Numerical Experiments]（arXiv preprint / 2026）

这篇论文实际解决的是 SLCC/LCP 的 feasibility problem，而不是一般意义上的优化求解：目标是找到满足线性约束与互补约束的点，或判定不可行。困难点在于互补约束把每个坐标变成一个隐式二选一分支，导致问题本质上有组合结构；直接把它写成 LCQO、merit function、nonsmooth equation 或 MPEC 后，通常只会得到 stationary point，不能保证回到原 SLCC 可行集。

关键矛盾是：线性 relaxation 很容易解，但太弱；完整互补系统有精确语义，但不可扩展。本文试图在两者之间插入一个 objective-learning 层：不改变 polyhedral relaxation 的约束，而是寻找一个线性目标，使 relaxation 的最优解自动满足互补性。这个视角比“求一个更强 convex relaxation”更像是在学习一个能暴露正确 complementarity pattern 的 surrogate objective。

Motivation

已有路线不够的地方很明确：LP relaxation 丢掉互补结构，DC/ADM/interior/nonsmooth 方法停在 stationarity，branch-and-bound 能给全局性但不 scalable。作者抓住的观察是：对 LCP，若真实解 x* 已知，那么取 c = M^T x*，LP relaxation 的 primal-dual optimality 可以把 x* 恢复出来；也就是说，互补性可以被某个线性目标“编码”。

因此真正缺的是一套理论说明：是否总存在这样的 objective vector？如果存在，能否通过可解的 LP/QP 子问题逐步逼近它？ReCR 的出发点不是设计另一个 merit function，而是把 complementarity violation 解释为目标函数选择错误后的信号，并用这个信号修正目标。

Core Idea

论文的核心不是某个具体算法，而是把 SLCC feasibility 从 variable-space search 改写为 objective-space rectification。URT 说明：如果 LCP/SLCC 可行，则存在某组线性目标，使得 relaxation LP 的 primal-dual optimal pair 携带一个可恢复的互补可行解；进一步可构造等价 bilinear program，把目标向量 c 也作为变量。这一步把原来的 hard complementarity condition 转成“寻找正确 linear objective”的问题。

这种建模方式引入的 inductive bias 是：正确的互补模式会表现为 LP/QP relaxation 最优解中的 slack/violation 结构，而不是需要通过显式枚举所有分支发现。ReCR 每轮解一个 convex relaxation，然后用当前解的互补冲突修正 objective，使下一轮 LP 更偏向消除这些冲突。和 prior 的本质差异在于，它不是在固定 merit landscape 上做 local descent，而是在不断重塑 relaxation objective；这解释了为什么它在某些非凸/不连通 solution set 上比 ReQR 或 PATH 更稳。

Method

关键机制可以压缩为四个。

第一，URT / BLO reformulation 解决“为什么可以只调目标”的问题：LCP 可行当且仅当存在某个 c，使固定 c 的 LP primal-dual optimum 满足 x <= y 之类的条件；由此得到一个 bilinear model，其全局最优值为 0 时恢复可行解，正值时指向不可行。

第二，PD-ReCR 使用 dual slack s^c 更新 c <- c + s^c。它直接对应 Theorem 2.4 中 s^c = 0 的充要/判别条件，因此理论最干净，但变量空间扩大，计算上不划算。

第三，P-ReCR 用 primal 解构造 rectification vector：只在 x_i > 0 且 slack_i > 0 的坐标上惩罚，这正好针对互补 violation。safe-guide direction 的作用是防止 zero components 的目标系数失控，并维持当前 basis/active pattern 的稳定性。它是算法实际可用性的关键 engineering choice。

第四，ReQR/H-ReCR 承认 P-ReCR 是 first-order-like，接近解时精度不足，于是切到 DC-style convex QP refinement。H-ReCR 的本质是先用 objective-space rectification 找到较好 basin，再用 quadratic local refinement 提高精度；这比单独 ReQR 更不容易困在坏 stationary point。

Key Insight / Why It Works

最重要的 insight 是：互补系统的难点可以部分转移到“选择目标函数”上，而目标函数选择错误会在 LP optimal slack 中留下可利用的方向信号。这个信号不是普通 residual；它来自 relaxation LP 的最优性结构，因此比直接最小化 x^T(Mx-r) 更有 active-set 信息。P-ReCR 的 s^p 实际在做一种 active-set curriculum：先通过 LP 找到一个极点/面，再惩罚当前同时正的 x 和 slack，推动目标改变，使下一个 LP 落到另一个面上。

我认为论文最实质的贡献是 URT + rectification 的解释框架，而不是 ReQR。ReQR 基本就是 DC programming / convex-concave procedure 在 LCP QO reformulation 上的重述；H-ReCR 的有效性主要来自把 P-ReCR 当作 basin finder，再用 ReQR 做 local polishing。这里的“learning”“ReLU”“backpropagation”类比偏修辞，不是核心技术。

它不是 scaling law，也不是 data-driven generalization；更像一种 better inductive bias + test-time compute。每次 LP/QP solve 是 test-time compute，用求解器把当前 objective 下的 global relaxation optimum 算出来；rectification 则利用 relaxation optimum 的 latent active-set structure。有效性依赖 relaxation 解能暴露出接近真实互补模式的 violated set。如果 LP relaxation 的极点结构与真实 complementarity pattern 弱相关，ReCR 可能只是在不同错误面之间移动。

不可行证书部分要谨慎看：它不是 ReCR 自动推出的全局证书，而是在 ReCR 缩小 violated index set 后，对剩余分支做 LP 枚举。因此证书能力很大程度依赖 violated set 足够小；若残余冲突集大，仍回到指数复杂度。

Relation To Prior Work

最接近的谱系有三条：LCP/SLCC 的 merit-function 或 nonsmooth equation 方法，LCQO/DC reformulation 方法，以及 mixed-integer / branch-and-bound 的显式 complementarity pattern search。ReCR 与第一类的区别是它不在固定 merit function 上做下降；与第二类的区别是它不只优化 x^T(Mx-r)，而是动态改变 LP objective；与第三类的区别是它试图先用 continuous relaxation 找到小的冲突集，再局部分支。

看似新的部分中，ReQR 基本是已有 DC/DCA 思想的重组；safe-guide、hybrid switching 更偏 engineering。真正新增的信息是 URT 给出的“存在好线性目标”的 primal-dual characterization，以及由 dual/primal slack 导出的 objective rectification 机制。这个机制把 active-set identification、LP sensitivity、complementarity violation 三者连到一起，是论文区别于传统 stationarity 方法的地方。

从技术谱系上，它属于 structured nonconvex feasibility 的 relaxation-guided active-set search，而不是经典全局优化。它的全局性来自理论等价的 bilinear model，但算法实际求解的是一系列 convex subproblems，因此全局保证与实际 performance 之间仍有明显 gap。

Dataset / Evaluation

实验覆盖面比普通 LCP paper 更宽：经典小 LCP、结构化大 LCP、合成 feasible/infeasible/nonconvex LCP、以及来自 AVI/friction/contact/Nash 的 SLCC。它确实验证了一个重要现象：在一些非凸或不可行构造中，H-ReCR 比 PATH/ReQR 更稳，且在 infeasible synthetic cases 能通过分支 LP 给出证书。

但 evaluation 对核心 claim 的支持并不完全充分。大规模结构化 LCP 中大量 0-iteration 成功，说明初始 relaxation 已经足够强，这更像 benchmark/data construction 友好，而不是 ReCR 迭代机制的 scalability 证据。合成 P17/P21/P22 明显按论文机制设计，能展示方法优势，但也可能放大了 objective rectification 对这类结构的适配性。

没有真实工业规模 SLCC 或复杂 MPEC-derived instances 的系统测试；也没有充分 ablation 去分离 URT initialization、safe-guide、rectification、ReQR polishing、Gurobi 子问题求解能力各自贡献。增益来源不清，尤其 H-ReCR 相对 PATH 的优势是否来自算法机制，还是来自 PATH 默认设置/不可行证书接口不匹配，文中未充分说明。

Limitation

第一，理论假设偏强。许多结论依赖精确 LP/QP solve、strict feasibility、boundedness、nondegenerate accumulation point。实际算法用 tolerance、Gurobi、启发式 switching，理论和实现之间有 gap。

第二，算法没有真正消除 NP-hardness。它把主要困难转移到 objective-space search 和最终 branch LP certificate。若 ReCR 终止时 violated complementarity set 很大，不可行判定仍指数爆炸；若停在坏 stationary point，证书不一定便宜。

第三，scalability 上限受子问题求解器支配。每轮 LP/QP 共享约束但论文基本 black-box 调 Gurobi，没有利用 warm start、basis reuse、matrix structure。大规模 dense SLCC 的 CPU 已经很高，说明当前实现不是 lightweight first-order method。

第四，H-ReCR 的成功机制没有被充分拆解。它可能只是“先用 LP 目标扰动找到较好 active set，再用 DC polishing”的组合收益；哪些 case 需要 P-ReCR，哪些 case ReQR 足够，哪些 case PATH 更强，论文没有给出结构性判别。

第五，不可行证书说法需要限定。证书来自枚举剩余分支并解 LP，而不是从 bilinear relaxation duality 中直接给出；因此它是 conditional certificate procedure，不是 scalable infeasibility oracle。

Takeaway

• 1. 最值得迁移的不是具体 ReCR 算法，而是“通过选择 relaxation objective 编码非凸结构”的思路；这对 binary feasibility、conic complementarity、某些 KKT systems 都可能有用。
• 2. 互补约束的 active-set 信息可以从 LP relaxation optimum 的 slack/basis 中提取，而不一定要显式枚举分支；这是比普通 merit residual 更有结构的信息。
• 3. H-ReCR 暗示一种实用范式：先用 cheap convex relaxation 的 objective perturbation 做 global-ish basin search，再用 DC/QP 做 local high-accuracy refinement。
• 这个范式可能比单纯追求更强 convex relaxation 更现实。

一句话总结

这篇论文把 SLCC/LCP 可行性从直接处理互补约束转成寻找可恢复互补模式的 relaxation objective，是一种 relaxation-guided active-set rectification 框架；理论亮点在 URT，实际收益主要来自 objective-space 搜索与局部 DC refinement 的组合。