精读笔记

Problem Setting

这篇论文处理的是 mpQP solution map 的全局 2-Lipschitz 常数计算复杂度，而不是提出一个更快的 Lipschitz 估计算法。熟悉 explicit MPC 的人都知道 z*(x) 是 continuous PWA，L 是所有 critical regions 上 affine gain Ki 的最大谱范数；实际瓶颈是 Ki 的候选集合由 active-set combinatorics 控制，数量可指数级增长。

真正的问题不是“枚举 CR 很慢”，而是：是否存在一种不枚举 CR、直接利用 QP 结构计算最大 Jacobian norm 的多项式算法？以前工作基本停在工程层面：explicit enumeration、decomposition、variable separation、MIP formulation 都能降低某些实例成本，但没有 worst-case lower bound，也没有回答困难来自 nx、nz、nc 中的哪一个。

论文把这个问题精确化为 mpQP-Lipschitz 的 exact / approximation 复杂度，并给出一个很清楚的分解：固定 nc 或 nz 时可多项式；固定 nx 不够，哪怕 nx=1 仍 APX-hard。因此关键矛盾是：参数空间几何维度可以很低，但沿着这个低维空间，active-set / affine-piece 序列仍能承载指数级离散信息。

Motivation

作者的动机不是改进 explicit MPC 工具链，而是补上一个基础复杂度缺口：长期以来大家把 Lipschitz constant 难算归因于 CR 数量爆炸，但 CR 数量爆炸只是某类算法的失败，不能排除存在更聪明的 global optimization / algebraic shortcut。

核心观察是：Lipschitz 常数本质上是“在所有可实现 active patterns 上最大化一个矩阵范数”。这和组合优化中的“在所有 binary assignments 上最大化一个目标”高度同构。只要能让 active pattern 或 PWA region 与 Boolean assignment 对齐，并让 Jacobian norm 读出目标值，就能把 MAX-CUT / MAX-2SAT 的 gap 搬过来。

另一个关键缺口是维度归因。控制场景里 nx 往往是系统状态维度，可能相对小；如果困难主要来自 nx，高维参数空间才是问题。但论文证明 nx=1 仍 hard，说明几何维度不是根因，根因是约束与变量共同诱导的 active-set 复杂度。

Core Idea

核心思想可以概括为：把 Lipschitz constant 计算重新看成一个隐式组合优化问题。mpQP 的每个 critical region 对应一个 affine Jacobian；求 L 就是在一组由可行 active-set 诱导的 Jacobian 中取最大谱范数。作者构造 mpQP，使这个最大谱范数几乎等价于 MAX-CUT / MAX-2SAT 的最优值，从而得到 gap-preserving hardness。

一般情形的 reduction 很直接：构造 z*(x)=M1 max(0,M2x)，其中 max 的 activation pattern 对应 cut indicator，M1 的 rank-one dominant term 把 ||Js||^2 放大成 n·CUT(s)，小扰动 δ 保证 Q 正定 / 构造合法，同时不破坏 gap。这个构造的本质是让 Jacobian norm 成为 cut value 的连续代理。

标量参数情形更有意思。nx=1 表面上只有一条线，似乎无法表达 2^n 个 assignments；论文用深 ReLU tent-map 的指数折叠能力解决这个问题：一维区间被 depth-n sawtooth 切成 2^n 段，每段编码一个 assignment。然后再证明任何 ReLU 网络都可嵌入为 mpQP 的唯一 optimizer。这里改变的建模方式是：不再直接用高维参数承载 Boolean vector，而是用一维 PWA 函数的深度组合承载指数多状态。

Method

1. MAX-CUT 到一般 mpQP-Lipschitz：构造一个约束形式足够简单的 mpQP，使 optimizer 等于 M1 max(0,M2x)。这里 max 的二值激活就是 active-set。M2=C^T 把 graph incidence 注入参数，M1=11^T+δI 让 Jacobian 的主项为 1(Cs)^T，因此谱范数平方读取 cut value。δ 的作用是保持构造良性并控制误差，使 approximation gap 不被扰乱。

2. 固定 nc 或 nz 的 tractability：利用每个 gain 可由一个 rank ≤ nz 的 linearly independent active subset 生成。若 nc 固定，active subsets 总数常数级；若 nz 固定，候选数为 nc 的固定阶多项式。这个结果重要，因为它说明 hard 不是来自连续优化本身，而是来自 active subset 数量随 nc、nz 联合增长。

3. MAX-2SAT 到 1D ReLU Lipschitz：用 tent function 反复 composition，把 [0,1] 分成 2^n 个 atomic intervals；Gray-code bit extraction 在每段上生成对应 assignment 的 bit signals；Boolean gates 用 ReLU 可实现的 max/min/abs 组合构造 clause outputs。最终 Fφ 在某个 interval 上的斜率正比于该 assignment 满足的 clause 数，所以 Lip(Fφ)=scale·MAX-2SAT(φ)。

4. ReLU 到 mpQP：构造一个严格凸 QP，其约束 zℓ≥0、zℓ≥Wℓzℓ−1+bℓ 强制 zℓ 成为 ReLU activation。目标中的大偏移 Mℓ 保证存在满足 KKT 的非负 multipliers，严格凸性保证唯一最优解。这个 lemma 的价值在于建立 ReLU PWA 表达与 mpQP optimizer 之间的精确表示关系。

5. Output scaling：ReLU 嵌入后，mpQP 的 Lipschitz 常数作用在完整 solution vector，而不是只作用在网络输出。作者用大系数 K 放大输出层，使 hidden components 的 Lipschitz contribution 被相对压低，从而保持 approximation gap。这是必要的技术补丁，不是主要 conceptual contribution。

Key Insight / Why It Works

最关键的 insight 是：mpQP-Lipschitz 的难点不是谱范数计算，而是“可实现 active patterns 上的最大化”。谱范数只是读取组合目标的仪表；真正的硬度来自 active-set geometry 能模拟 Boolean assignment space。

一般 MAX-CUT reduction 成立的核心在于 rank-one amplification。J_s=(11^T+δI)ΣC^T 的主项 1s^TC^T 把 binary vector s 的 cut value 变成一个矩阵的 spectral norm；因为 ||1(Cs)^T||^2=n||Cs||^2=n·CUT(s)，最大 Lipschitz 常数自然等价于 MAX-CUT。δ 只是保证构造合法并让 gap-preserving 误差可控，属于 technical device，不是本质贡献。

nx=1 hardness 的核心是“深度折叠替代参数维度”。这点很值得迁移：即使输入维度固定，PWA map 的 composition depth / constraint-variable structure 仍可制造指数多线性片段。也就是说，低维参数域不等于低复杂度；复杂度可以藏在沿一维轨迹的 region sequence 中。这和 ReLU verification 里的 sawtooth hardness 是同一类机制。

ReLU→mpQP representation lemma 是论文中最有独立价值的部分。它不只是为了这篇 hardness 服务，还提供了一个把 neural network verification / Lipschitz lower bounds 转移到 parametric optimization 的接口。这里的 inductive bias 不是学习意义上的，而是表达能力对齐：ReLU 的 complementarity-like max structure 与 QP KKT active constraints 天然同构。

哪些是辅助？Gray-code encoding 是为了让 composition 顺序下的 interval indexing 干净，属于证明工程；output scaling 是为了处理 full solution vector Lipschitz 与 output Lipschitz 不一致的问题，也主要是 technical patch。数值实验基本是验证 scaling 形态，不构成核心证据。

我的判断：这篇真正推动的是复杂度归因和模型等价，而不是计算方法。它说明任何声称“通用快速精确计算 mpQP Lipschitz”的方法都必须利用额外结构；否则在 worst case 上不仅 exact 不可能，任意接近的 PTAS 也不可能。

Relation To Prior Work

最接近的 prior 有三条：explicit MPC 的 critical-region enumeration、MIP-based Lipschitz / PWA controller analysis、以及 ReLU network Lipschitz / verification 的 hardness 结果。

相对 explicit MPC，这篇的本质差异是从 algorithmic enumeration 转为 complexity lower bound。过去“CR 指数多”只能说明枚举法不可扩展；本文证明不存在一般意义上的多项式 exact / PTAS 替代方案，除非 P=NP。这是从经验复杂度到理论复杂度的升级。

相对 MIP formulation，本文没有给更强 solver，而是解释为什么这些 formulation worst-case 指数是不可避免的。MIP 路线通常在 1/∞ norm 或 tight bound 上工作，本文聚焦 2-norm Lipschitz，更贴近 Lyapunov / robustness 分析中真正用的量。

相对 ReLU hardness，本文的 sawtooth + MAX-2SAT 并非完全新思想，属于已有 ReLU 表达复杂度 / Lipschitz hardness 思路的迁移；但新意在于构造性证明 ReLU network 可作为 mpQP unique optimizer，并处理 full-solution Lipschitz 的 scaling gap。这个接口是实质创新。

它属于“optimization-based control 的 complexity-theoretic characterization”谱系，而不是 MPC algorithm paper。贡献更像是给这个领域划定不可逾越的 worst-case 边界。

Dataset / Evaluation

实验覆盖三类 claim：联合增长导致 CR 指数增长；固定 nc 或 nz 后增长受限；固定 nx 仍可能指数增长。它们和理论结论方向一致，但实验不是证明，只是帮助读者把 reduction 的结论和常见 CR enumeration 现象对齐。

随机 mpQP 实验的价值有限但合理：它展示在无特殊结构的 dense random instances 上，nc 与 nz 的联合增长确实主导 CR 数量。固定 nc 时 CR count plateau，固定 nz 时 polynomial-but-large，固定 nx 时仍快速增长，这些都支持维度归因。

tent-map ReLU→mpQP 实验更贴近理论构造，验证 nx=1 下仍能生成 Θ(2^D) regions。这里不是现实 MPC benchmark，而是 construction sanity check。

明显 limitation 是 evaluation 只看 critical regions 数量，并未系统评估 Lipschitz constant 计算算法的 runtime、approximation quality 或不同 solver 的 failure mode。它验证的是“枚举复杂度表现”，不是直接验证 APX-hardness。没有真实控制系统 / 工业 MPC 实例，因此不能推出典型 MPC deployment 中一定难。

Limitation

1. 这是 worst-case 结果。hard instances 的矩阵结构非常人为，尤其 MAX-CUT reduction 和 tent-map ReLU construction 都带有强编码性质。对实际 MPC 中常见的稳定系统、短 horizon、稀疏 dynamics、box/input constraints、terminal set 等结构是否仍 hard，文中未充分说明。

2. APX-hardness 阈值依赖 reduction。一般情形给出 ρ<sqrt(17/16)，标量情形通过 MAX-2SAT 给 22/21 相关阈值；这些不是 tight characterization。是否存在 constant-factor approximation、结构化 approximation 或 norm-specific relaxation，仍开放。

3. 固定 nz 的 polynomial 结果在复杂度理论上成立，但阶数为 nz，实际 nz=10、20 时仍可能不可用。这里“polynomial-time solvable”不应被误读为 practical scalable。

4. ReLU→mpQP 构造中的 Mℓ 可能数值很大，虽然 bit-length polynomial，但 conditioning / numerical stability 可能很差。作为复杂度 reduction 没问题，作为实际建模等价则可能不稳定。文中对数值 conditioning 的影响未充分说明。

5. 实验主要来自 random dense instances 和构造性 tent-map，并不覆盖真实控制问题。所谓“复杂度来自 nc 和 nz 而非 nx”在 worst-case 意义上成立；但典型实例中 nx、horizon、constraint geometry 的耦合可能仍影响 solver 行为。

6. 论文没有给出可利用结构的正向算法。它告诉我们通用问题 hard，但没有细化哪些 MPC 子类可 tractable、哪些 structural parameters 可以 FPT 化。

Takeaway

• 1. 以后讨论 mpQP solution-map Lipschitz 计算时，不能再只说“CR 枚举指数多”；更准确的说法是：通用问题 APX-hard，CR explosion 反映了真实的组合下界。
• 2. 参数维度低并不能保证 tractable。
• nx=1 仍 hard 的机制提示：复杂度可以通过一维 PWA folding / active-set sequence 隐藏在深度或约束-变量耦合里。
• 3. ReLU 与 mpQP 的构造性等价值得迁移。

一句话总结

这篇论文把 mpQP 解映射 Lipschitz 常数计算从“经验上难枚举”提升为“复杂度上不可近似”的问题，并用 ReLU 折叠与 mpQP 表示等价说明困难根源在 active-set combinatorics 而非参数维度。