精读笔记
Problem Setting
论文标题：Heilbronn's Problem in the Unit Triangle: Certified Optimal Configurations for up to n<=8（arXiv preprint / 2026-07-17）。
这篇论文解决的不是“如何数值找到漂亮构型”，而是一个更硬的认证问题：在单位直角三角形 T 内，对 n 个点最大化所有三点三角形面积的最小值，并证明给出的构型是全局最优。这里的困难点在于目标函数是所有三元组面积的 min，面积又带绝对值和取向不确定性，导致连续非凸优化和组合取向选择纠缠在一起。
以前方法卡在两个地方：一类是构造型或记录型结果，只能给出 lower bound；另一类是网格搜索或 branch-and-bound，可以给 upper bound 但代价高、gap 难闭合。关键矛盾是：精确几何问题需要全局证明，但原始自由点模型几乎没有足够结构让求解器有效剪枝。作者真正要做的是把“几何最优性”转译成“可认证的混合整数非凸优化实例”。
Motivation
已有路线不够的原因不是缺少候选解，而是缺少能证明候选解不可改进的机制。尤其 n=7、n=8 已有相当可信的构型，但上界证明仍停在较松网格或昂贵 branch-and-bound 上，这说明瓶颈在 certification，而不是 search。
作者的关键观察是：三角形区域不是普通凸域，它有强仿射结构；同时最小面积包围三角形理论会强制凸包与边界发生特定接触。也就是说，最优解虽然表面上是 n 个自由点，但至少某个等价最优解可以被规范化成“多点在边界上”的形式。缺口正是在这里：此前没有把这个几何结构系统地嵌入 MIQCP，从而把连续自由度、对称性和取向不确定性一起压下来。
Core Idea
核心思想是先证明“可以不失一般性地看一个边界规范化的最优解”，再对这个缩小后的空间做全局 MIQCP 认证。Proposition 1 是整篇的枢纽：若最优构型的凸包不是整个 T，则存在面积保持仿射像，使得至少四个点落在边界上，且一条边上有两个点、另外两条边各至少一个点。再利用 T 的 S3 仿射对称性，可以固定双占边为 e1。
这改变了建模方式：原始问题是全自由点加所有三元组取向；新模型带有几何归一化、边界锚定和部分取向固定。这个 inductive bias 很强，而且是可证明不丢最优解的。和 prior 的本质区别是，它不是更细网格、更久搜索或更好的候选构造，而是通过几何结构减少认证空间，让通用求解器可以给出 global certificate。
Method
1. 边界结构定理：解决最优解缺少锚点的问题。作者利用最小面积包围三角形的两个事实：每条边中点与凸包接触，以及存在一条边 flush 于凸包边。若存在更小包围三角形，可仿射放大面积目标而矛盾；因此 T 本身是最小包围三角形。这个论证把最优性转化为边界接触约束。
2. 仿射对称固定：解决等价构型太多的问题。T 的三个顶点可由面积保持仿射映射任意置换，因此边界上双占的那条边可固定为 e1。这一步不是 cosmetic symmetry breaking，而是直接减少连续变量并固定若干取向。
3. MIQCP 面积模型：解决绝对面积最小化下界的全局认证问题。每个三元组面积 A_ijk 是双线性的；引入二进制变量选择取向，使 z <= |A_ijk| 被写成 z <= ±A_ijk。目标最大化 z。求解器证明全局最优，而不是仅给局部解。
4. n=8 的代数后处理：解决数值最优值的解释问题。作者将认证最优解与 Chen-Zeng-Zhou 的十一临界三角形系统对齐，验证 septic 多项式根，并证明该多项式 Galois 群为 S7。这部分更像 arithmetic diagnosis，不是 MIQCP 成功的必要条件。
Key Insight / Why It Works
最有效的部分几乎肯定是 Proposition 1 加 Corollary 1，而不是 MIQCP 本身。MIQCP 对这种问题是自然写法，但如果没有边界结构，三元组数量、二进制取向和连续非凸性会很快把模型拖垮。论文的实质贡献是给求解器喂了一个强到足以闭合 gap 的几何先验，并且证明这个先验不排除最优解。
从机制上看，这不是 scaling，也不是 data；它是 problem-specific inductive bias。作者把 Heilbronn 问题中的 latent structure 显式化：最优构型不是任意散点，而受最小包围三角形接触条件约束。边界点固定后，模型中的非凸性仍在，但可行域被切到足够小，取向也部分稳定，求解器才有机会完成全局证明。
n=8 的快速连续化版本则更偏 engineering / inherited structure：利用 Chen-Zeng-Zhou 的临界三角形定位，把点限制在小 box 内，使所有取向常量化。这说明若已经知道局部组合类型，认证会非常快；但这也暴露出方法对组合模式发现的依赖。表中 2324 秒的 run 更有说服力，因为它不继承 Chen-Zeng-Zhou 的 Theorem 2；0.04 秒版本更像用已有结构做验证，而不是独立发现。
Relation To Prior Work
最接近的路线是作者在单位正方形上的 companion MIQCP 框架，以及三角形区域上的历史构造、网格搜索和 branch-and-bound 上界。论文属于“computational certification + exact reconstruction”的谱系：用优化求解器给全局证书，再把数值解还原为精确或代数对象。
和单位正方形工作的差别在于，三角形与正方形不是仿射等价的；square 的 exact results 不能直接搬过来。这里新增的信息是三角形区域特有的边界结构定理，以及 S3 仿射对称对模型规模的压缩。和 Chen-Zeng-Zhou 相比，本质差异是后者给 n=8 的高成本 upper-bound/代数猜想路线，而本文提供独立 MIQCP 全局认证，并补上 septic 的 Galois 群解释。
看似新的部分中，MIQCP 表达本身并不新，面积双线性和取向二进制是直接建模；真正实质创新是把最小包围三角形理论嵌入 Heilbronn 最优构型分析，从而让 mixed-integer optimization 成为证明工具。
Dataset / Evaluation
这里没有传统 dataset，evaluation 是一组小 n 几何实例。覆盖范围很窄：单位直角三角形，n<=8。它充分验证了作者最明确的 claim，即这些小规模实例可被全局认证，并且 n=7、n=8 的历史 gap 可关闭。
但 evaluation 不支持更强 claim，例如方法对 n 大幅扩展、对一般凸域通用、或对未知组合结构自动稳定发现。n<=8 的结果很强，但属于 exact small-instance certification，不是 scalable optimization benchmark。文中给出相对既有方法的时间优势，但这部分需要谨慎解读：优势部分来自新的几何归约，部分来自现代 Gurobi 和建模工程；二者贡献比例文中未充分说明。
Limitation
第一，方法成立强依赖三角形区域的仿射对称和最小包围三角形接触结构。换到一般凸域，这个四边界点规范化未必存在；换到更高 n，边界锚定可能仍不足以控制组合爆炸。
第二，scalability 上限明显。三元组数量为 O(n^3)，取向二进制也随三元组增长；即使固定 n 个左右的取向，剩余 MIQCP 仍会迅速变难。n=8 已需数十分钟量级，n>=9 是否可行文中没有实质证据。
第三，n=8 的 exact story 仍未完全闭合。作者证明 septic 的 Galois 群为 S7，并用高精度和临界三角形匹配支持 Chen-Zeng-Zhou 猜想；但同时承认仍需证明 T11 的十一类三角形同时 minimal。也就是说，全局数值认证与代数闭式解释之间还有缝隙。
第四，增益归因不完全清晰。核心增益显然来自几何结构和 symmetry fixing，但具体有多少来自 Proposition 1，有多少来自求解器版本、box localization、orientation pre-fixing 或模型工程，文中未充分拆分。不能把这篇解读成通用 MIQCP scaling 的胜利。
Takeaway
- 1. 最值得迁移的 insight 是：在几何优化里，先证明存在一个结构化最优代表，再做 mixed-integer certification，往往比直接全空间搜索有效得多。
- 2. 对 Heilbronn 类问题，边界接触和最小包围体理论可能是比局部构型猜测更强的入口。
- 未来 n>=9 的关键不一定是更强求解器，而是继续找到可证明的组合/边界规范化。
- 3. 这篇把“小规模精确几何问题”从构造和数值猜测推进到可认证优化，但还没有解决大规模规律或完整族刻画。
一句话总结
这篇论文在 Heilbronn 三角形问题中真正推进的是一种“几何结构归约 + MIQCP 全局认证”的小规模精确证明范式，其核心贡献不是搜索到构型，而是证明可以把最优性认证压进一个足够结构化的优化模型。