精读笔记

Problem Setting

【A characterization of maximal inhomogeneous-quadratic-free sets】（arXiv preprint / 2026）

这篇论文实际处理的是：给定一个由单个非齐次二次不等式定义的集合 S={s: sᵀAs+bᵀs+c≤0}，如何完整刻画所有 full-dimensional maximal S-free convex sets。经过标准规约，核心对象变成 Qg(a,d)={(x,y): ∥x∥≤∥y∥, aᵀx+dᵀy=-1}，也就是齐次二次锥 Qh={(x,y):∥x∥≤∥y∥} 的一个仿射截面。

真正困难点是 maximality 在截面上不按直觉继承。对 Qh，已有结果说 maximal Qh-free cone 可以写成 CΓ={-Γ(β)ᵀx+βᵀy≤0, ∀β∈Dm}，其中 Γ 是非扩张映射且 0 不在 Γ(Dm) 的 convex hull 中。但一旦切到 H:aᵀx+dᵀy=-1，CΓ∩H 可能不是 maximal Qg-free；有些原本支撑 Qh-free cone 的 inequalities 在 H 上可以删掉，甚至必须删掉才能得到 maximal Qg-free set。关键矛盾是：齐次锥结构提供了全局母体，但非齐次约束只关心一个 affine slice，slice 中的 maximality 由 Γ 与 hyperplane normal (a,d) 的相对位置决定。

Motivation

已有路线的缺口很明确：homogeneous case 已被 Muñoz–Paat–Serrano 通过 non-expansive functions 完整刻画，但非齐次二次约束不能简单套用，因为 homogenization 后固定 t=1 会引入超平面切片。general S-free maximality theorem 虽然存在，但对二次结构几乎不可读，不能告诉我们 maximal sets 的可构造形式。

作者的核心观察是：非齐次二次并不需要一个全新的几何语言；它仍然可以嵌入 Qh 的非扩张函数框架，只是 maximality 要在 H 上重新判断。也就是说，缺的不是 cone CΓ 的刻画，而是一个“哪些 CΓ inequalities 在 affine slice 中仍然必要”的选择规则。本文的 G(Γ,a,d) 正是这个缺口的几何编码。

Core Idea

核心思想可以压缩成一句话：所有非齐次二次 maximal-free sets 都来自 homogeneous maximal-free cones 的 affine slice，但 slice 上要按 hyperplane 方向筛掉一部分 cone inequalities。具体地，从 Γ:Dm→Dn 生成 CΓ，再定义 G={β: aᵀΓ(β)+dᵀβ≤0}，候选 maximal Qg-free set 是 CGΓ∩H，其中只保留 β∈G 的 inequalities。

这改变了问题的建模方式：不是直接在非齐次二次集合上刻画 convex sets，而是先回到齐次 cone 的“support function / non-expansive map”表示，再分析 affine slicing 对 facet 必要性的影响。与 prior homogeneous work 的本质区别不在 Γ 本身，而在 hyperplane H 引入了方向性：当 ∥a∥≤∥d∥ 时，部分 inequalities 可被安全移除；当 ∥d∥<∥a∥ 时，maximality 反而要求一个 all-or-nothing 条件 G=Dm。这是本文最有信息量的地方。

Method

1. 规约：一般 indefinite inhomogeneous quadratic 先 homogenize，再 diagonalize，得到 Q'g={(x,y,z):∥x∥≤∥y∥, aᵀx+dᵀy+hᵀz=-1}。若 h≠0，已有论证把问题退回 homogeneous Qh；真正剩余的是 h=0 的 Qg。这个步骤说明研究 Qg 不是特例，而是完整覆盖单二次不等式的 normal form。

2. Lift 到 cone：对任意 full-dimensional maximal Qg-free K⊆H，考虑 cone(K)。由于 K 的 relative interior 避开 Qg，cone(K) 的 interior 避开 Qh，于是 cone(K) 可扩张到 maximal Qh-free cone CΓ。由 maximality 得 K=CΓ∩H 的某种形式。这一步把 slice 问题重新连接到已有 homogeneous characterization。

3. Inequality deletion via G：并非所有 β∈Dm 都需要保留。定义 G={β:aᵀΓ(β)+dᵀβ≤0}。Theorem 2 说明每个 maximal Qg-free set 可表示为 CGΓ∩H。这里 G 的作用是判断对应 inequality 与 H 的相对朝向：它编码了该 inequality 在 slice 上是否仍参与阻挡 Qg。

4. 两个 norm regime：若 ∥a∥≤∥d∥=1，除 a=Γ(-d) 的退化情况外，CGΓ∩H 总是 full-dimensional maximal Qg-free。若 ∥d∥<∥a∥=1，则必须 G=Dm；只要有 β∉G，就能构造严格更大的 Qg-free set，说明原集合不 maximal。这是论文的主判别式。

5. Tilting 与 exposing sequences：为了证明 sufficiency，作者需要处理 H 上任意 valid inequalities，而不仅是从 CΓ 继承的 inequalities。tilting lemma 把 H 上的 valid inequality 调整为 cone-valid inequality；exposing sequence criterion 则证明每个保留的 essential inequality 都由 Qg 中逼近点暴露，从而阻止任何严格扩张。

Key Insight / Why It Works

最核心的有效性来自一个很干净的几何事实：非齐次性只破坏了尺度不变性，但没有破坏二次锥 Qh 的支撑结构。通过把问题放回 Rn×Rm 的 cone ambient space，再在 H 上切片，作者避免直接处理非齐次二次曲面的复杂形状；所有复杂性被压缩为 Γ 与 (a,d) 的内积条件 aᵀΓ(β)+dᵀβ。

本文最可能的实质贡献是发现并证明 G 的筛选规则，以及 ∥a∥≤∥d∥ / ∥d∥<∥a∥ 的分相。这个分相不是技术偶然：当 d 主导时，H 与 y-direction 的相互作用允许沿 slice 删除某些 inequalities 而仍保持 Qg-free；当 a 主导时，删除任何不满足条件的 inequality 都会打开一个 push-out 方向，使集合可扩张。因此 Theorem 4 的“几乎任意 Γ 都行”和 Theorem 5 的“必须 G=Dm”反映的是截面几何的真实相变。

辅助但必要的部分是 tilting/exposing sequence machinery。它们本身更像证明技术：tilting 解决 arbitrary valid inequality 不在 cone description 中的问题，exposing sequence 负责把 local support 转成 maximality。真正 insight 不在这些工具，而在如何选 J/I、如何让 Qg 中的序列同时满足 H 与 Qh，并暴露对应 inequality。

这不是 scaling、不是 data coverage、不是 empirical engineering。它是一个 convex-geometric representation theorem。若从 optimization cut generation 角度看，当前贡献主要是扩大可用 maximal-free set 的理论族；实际性能增益文中没有验证，不能假定会自动转化为 solver improvement。

Relation To Prior Work

最接近的是 Muñoz–Paat–Serrano 2025 对 homogeneous Qh-free sets 的刻画。本文几乎完全继承其语言：Γ:Dm→Dn、non-expansiveness、0∉conv Γ(Dm)、CΓ 的 support inequality 描述。真正新增的是 affine slice 下的 maximality 判定，而不是 non-expansive representation 本身。

相对 Muñoz–Serrano 2020/2022 的 maximal quadratic-free sets，本文从构造若干族推进到完整 characterization。此前可实现 cuts 只覆盖这个巨大空间中的某些简单 family；本文告诉我们原则上完整空间是什么。但“完整空间”是无限维函数空间，工程上仍需要二次筛选。

相对 general S-free theory，本文不是提出新的抽象 maximality criterion，而是把已有 criterion 特化到二次锥截面，并得到可读的充要条件。实质创新在于把 homogeneous result、Zorn extension、tilting、exposing sequence 组合成一个对 Qg 完整闭合的结构定理。看似新的是很多 technical lemmas；真正新增的信息是 G-rule 和 norm-regime dichotomy。

Dataset / Evaluation

无数据集、无实验、无 benchmark。这是理论数学/优化论文，evaluation 等价于定理覆盖范围与证明闭合性。

就 claim 而言，理论证据充分支持“完整刻画所有单二次 maximal-free sets”这一主张：PSD/NSD 情形被简单处理，indefinite homogeneous 由已有 Qh 结果覆盖，indefinite inhomogeneous 由 Qg 结果补齐。它没有验证的是 optimization 层面的实际价值：这些新 maximal-free sets 是否能生成更强 cuts，是否能在 QCQP/MIQCP solver 中稳定分离，是否比已有实现族带来显著收益，文中均未评估。因此若把 claim 扩展成“显著强化 cutting-plane methods”，目前证据不足。

Limitation

1. 刻画是完整的，但不是有限可计算的。Γ 是定义在单位球面上的非扩张函数，空间无限维；即使有 G 条件，也没有给出如何在实际问题中搜索最优 Γ 或有效 separation。

2. Full-dimensional 假设是合理但有选择性的。低维 maximal-free sets 在理论上可能 vacuous 或退化，本文基本绕开这些对象；对于实际算法中可能出现的 lower-dimensional relaxations，映射关系未充分展开。

3. 工程转化缺失。intersection cut 框架需要给定当前 relaxation vertex 选择一个包含该点的 maximal S-free set；本文告诉你所有这样的 set 的结构，但没有解决选择问题。实际增益来源不清，可能最终只能依赖少数手工参数化 Γ，而不是完整 characterization。

4. 数值复杂性未讨论。CGΓ 通常由无限多个 inequalities 定义，exposed-ray reduction 仍是抽象的 convex analysis；在高维 m 下，Dm 上的连续索引会带来严重 separation 和 representation 问题。

5. 与已有 cut families 的强度关系仍不透明。文中说明 prior 只实现了一族并有正面结果，但没有给出新族相对这些 cuts 的 dominance、incomparability 或 closure 关系。理论上更 general 不自动意味着 computationally stronger。

Takeaway

• 1. 非齐次二次 maximal-free sets 的本质不是新曲面几何，而是 homogeneous cone CΓ 在 affine hyperplane 上的 facet survival problem。
• 2. G(Γ,a,d) 是最值得迁移的 insight：当一个 homogeneous free set 被 affine constraint 切片时，maximality 取决于 support inequalities 与 slice normal 的符号关系，而不是简单继承全部 facets。
• 3. ∥a∥≤∥d∥ 与 ∥d∥<∥a∥ 的相变值得记住；它说明 homogenization 后线性项落在 positive-eigen directions 还是 negative-eigen directions，会实质改变 maximal-free geometry。
• 4. 下一步真正有价值的不是再证明更多 abstract characterization，而是把 non-expansive Γ 空间变成可优化、可分离、可数值稳定使用的 cut-generating family，并明确其相对现有 QCQP cuts 的强度边界。

一句话总结

这篇论文把 homogeneous quadratic-free sets 的非扩张函数刻画推广到非齐次二次的 affine-slice 情形，用 G-rule 与 norm-regime dichotomy 补齐了单二次 maximal-free set 的理论分类，但其算法价值仍取决于未来如何有限化和选择 Γ。