解读 | An Exact Semidefinite Lift of a Nonspectrahedral Hyperbolicity Cone

结果族 095:Hyperbolicity cones without semidefinite lifts · 学科:Convex and metric geometry · 验证状态:暂无形式化证明,请以社区核验为准

入门导读 🐣

姊妹篇刚证明:有一块 23 变量的凸”地”,无论用多大的矩阵都写不出”体检表”。这一篇马上补上后半句:若允许帮手上场——额外引入 307 个辅助变量——同一块地就能在高维里写成标准的矩阵半正定条件,再投影回来。就像圆是圆柱在墙上的影子:影子本身写不出简单公式,本体在高一维处却极规整。

关键词卡片

看个具体例子

提升后的”数字版”关系是:@@M@@x\in K\iff\exists v\in\mathbb{R}^{307}:\ \sum_{\nu=1}^{23}x_\nu A_\nu+\sum_{j=1}^{307}v_jB_j\succeq0@@,其中矩阵全是 @@M@@100\times100@@ 的。

高维中的谱面:100×100 对称矩阵半正定 Σ xνAν + Σ vjBj ⪰ 0 23 变量双曲锥 K 本身无 LMI 投影=扔掉 307 个辅助变量 v

尺寸从哪来:330 维矩量空间的坐标扣除 23 个输出方程,恰剩 307 个辅助变量;测试向量空间 @@M@@5\times20=100@@ 给出矩阵尺寸。等价覆盖整个闭锥,包括边界上 @@M@@X@@ 奇异的退化点,无需再取闭包;作者声明这只是显式上界,未必最小。

为什么值得关心

它与姊妹篇合起来给同一个锥下了完整判决:不是谱面,但是谱面影子——”辅助变量”这一个小让步,就足以恢复矩阵可表示性。

暂无形式化证明(AI 结果待核验)

过渡 | An Exact Semidefinite Lift of a Nonspectrahedral Hyperbolicity Cone

由浅入深:从类比走向定理

第一级台阶

姊妹篇说那块 23 变量的”地”在自家坐标里写不出矩阵体检表;这一篇请帮手上场:加装 307 个辅助刻度,在高维空间里先把地写规整,再把这些刻度投影掉。导读里”圆是圆柱的影子”说的正是这件事:影子(原坐标下的地)难写公式,本体(高维中的标准区域)却规矩。于是研究对象从一块地变成”一块地加一个高维本体”,操作是”建本体、再投影”。

第二级台阶

精确化两个概念。谱面指能写成线性矩阵不等式解集的凸集:把变量线性填入一个固定大小的对称矩阵并要求半正定。谱面影子是谱面的线性投影,等价说法是存在半定提升——点属于集合,当且仅当能补出一组辅助变量使联合矩阵半正定。矩量矩阵则是把一个线性泛函在一族测试多项式两两乘积上的取值排成的对称矩阵,是半定方法编码非负性的标准器件。

第三级台阶

定理针对姊妹篇那个由行列式定义的 23 变量闭双曲锥陈述。结论是:存在 23 个系数矩阵与 307 个辅助矩阵,全部是 100 阶实对称阵,使上述”补辅助变量”的等价在整个闭锥上成立——连边界上 X 奇异的退化点也一并覆盖,不必再取闭包。证明没有可丢的假设,真正的门槛在反向:可行的矩量泛函未必是单个角度处的赋值,要靠”次数二匹配引理”这个有界次代数部件把切片不等式从半定条件里榨出来。合起来读:这个锥不是谱面,却是谱面影子;尺寸只是显式上界。

一句话结论

为姊妹篇那个 23 变量的非谱面双曲锥构造了精确半定提升:@@M@@100\times100@@ 齐次对称铅笔加 307 个辅助变量,覆盖含奇异边界点的整个闭锥——该锥不是谱面,却是谱面影子。

问题背景

谱面(spectrahedron)是有限仿射线性矩阵不等式 @@M@@L(x)\succeq0@@ 的解集;谱面影子(spectrahedral shadow)是谱面的线性投影,等价于允许引入辅助变量的半定提升(semidefinite lift)。辅助变量可能让原本无表示的集合变得可表示,这正是广义 Lax 猜想与其”投影版”强弱之别的来源。围绕双曲锥(hyperbolicity cone)的表示问题,此前正面结果都依赖边界正则性:Netzer 与 Sanyal 证明边界光滑的双曲锥可提升,Scheiderer 近期在 Nash 光滑边界假设下给出二阶锥提升。本族的姊妹篇刚证明了一个 23 变量的显式双曲锥不是谱面,留下一个悬而未决的对照问题:允许辅助变量之后,它有没有精确提升?本文给出肯定回答,而且提升是显式、有界次代数的构造,对整个闭锥(包括退化点)精确成立,不需要取闭包。

主要结果

沿用姊妹篇的多项式:@@M@@p(X,Z,y)=\det\big((\det X)Z-\Phi_y(\operatorname{adj}X)\big)@@,其中 @@M@@\Phi_y@@ 由 Choi–Lam 矩阵 @@M@@Q(y)@@ 诱导,@@M@@K=K(p,e)@@ 是它关于 @@M@@e=(I_4,I_4,0)@@ 的闭双曲锥。主定理(Theorem 2.5):存在固定矩阵 @@M@@A_1,\ldots,A_{23},B_1,\ldots,B_{307}\in\Sym^{100}@@,使得对每个点 @@M@@x=(X,Z,y)@@ 都有 @@M@@Dx\in K\quad\Longleftrightarrow\quad \exists v\in\mathbb{R}^{307}:\ \sum_{\nu=1}^{23}x_\nu A_\nu+\sum_{j=1}^{307}v_jB_j\succeq0 .@@ 等价在整个闭锥上成立,包括 @@M@@X@@ 奇异的点;铅笔是齐次的、无常数项。作者强调尺寸只是显式上界,不声称极小。由于姊妹篇已证此锥在原始坐标下没有任何齐次半定表示(仿射表示对含原点的锥可自动齐次化),本文说明:它非谱面,但确是谱面影子。

证明思路

先做角切片。平面族 @@M@@y=Y_\theta(\eta,\xi)=\eta(\cos\theta,\sin\theta,0)+\xi(0,0,1)@@ 覆盖整个 @@M@@\mathbb{R}^3@@;在每个平面上,Choi–Lam 矩阵 @@M@@Q(y)@@ 有显式复 Gram 分解 @@M@@F_\theta(\eta,\xi)=\eta U(\theta)+\xi V_0@@,系数是 @@M@@\theta@@ 的次数至多三的三角多项式(trigonometric polynomial)。由 Gram 列构造斜块 @@M@@B(r)@@,叠加得到恒等式 @@M@@\sum_j B(r_j)^\top WB(r_j)=\Phi_{Y_\theta}(W)@@,于是 20 阶齐次铅笔 @@M@@L_\theta@@ 的行列式在切片上恰等于 @@M@@p@@;对称铅笔的特征值全实,这顺便重证了双曲性,而且 @@M@@L_\theta\succeq0@@ 当且仅当切片点属于 @@M@@K@@——奇异 @@M@@X@@ 的情形也一并成立。

再把角参数变成矩量条件。@@M@@\theta@@ 是连续参数,本身不是有限线性矩阵不等式;作者转而使用矩方法(moment method):提升变量取为 330 维空间 @@M@@\mathcal E@@(22 个切片变量的线性函数,系数为次数至多七的三角多项式)上的线性泛函 @@M@@\Lambda@@,要求它满足 23 个输出方程(@@M@@\Lambda(\mathcal X)=X@@ 等)以及单个半定条件 @@M@@H(\Lambda)\succeq0@@——@@M@@H@@ 是 @@M@@100\times100@@ 的矩矩阵(moment matrix),元素为 @@M@@\Lambda\big(f_af_b(L_\theta)_{ij}\big)@@,@@M@@f@@ 取遍 @@M@@1,\cos\theta,\sin\theta,\cos2\theta,\sin2\theta@@。正向容易:@@M@@K@@ 中每点取一个合适的 @@M@@\theta_0@@ 处的赋值泛函即为可行见证,即使 @@M@@X@@ 奇异也无妨。

真正的难点在反向:可行泛函未必是某角度处的赋值,甚至未必来自任何测度,所以必须从 @@M@@H(\Lambda)\succeq0@@ 直接榨出切片不等式。这里的关键新部件是”次数二匹配引理”(degree-two matching):对任意(可以不定的)@@M@@S\in\mathbb S^3@@ 与 @@M@@(z_1,z_2)\ne(0,0)@@,存在次数至多二的三角矩阵 @@M@@C(\theta)@@,其 Gram 矩阵恒为 @@M@@Q(z)@@、且配对 @@M@@\langle F_\theta,C\rangle_S=\operatorname{tr}\big(SQ(Y_\theta(\eta,\xi),z)\big)@@ 关于 @@M@@\eta,\xi@@ 线性。构造是用 @@M@@2\times2@@ 西旋转 @@M@@M(\theta)@@ 作用于固定因子:西性保住 Gram 矩阵,旋转把三次频率压制为一次谐波(核心是恒等式 @@M@@w^3\kappa=w_0^2w@@),再在单个角度处匹配函数值与一阶导数即可锁定配对。以 @@M@@C@@ 的列拼出测试向量 @@M@@q\in(\mathcal T_2)^{20}@@ 代入半定条件,角依赖被恒等式”配平”,得到一族标量不等式:对所有 @@M@@u\in\mathbb{R}^4@@、@@M@@D\in\mathbb S^4@@、@@M@@z\in\mathbb{R}^3@@, @@M@@Du^\top Zu+\operatorname{tr}\big(J_uDXDJ_u^\top Q(z)\big)-2\operatorname{tr}\big(J_uDJ_u^\top Q(y,z)\big)\ge0 .@@ 最后分况收网:@@M@@X@@ 正定时取 @@M@@D=X^{-1},z=y@@ 得 @@M@@Z\succeq\Phi_y(X^{-1})@@;@@M@@X@@ 奇异时,取 @@M@@D=tvv^\top@@(@@M@@v\in\ker X@@)得值域条件 @@M@@\operatorname{range}B_j\subseteq\operatorname{range}X@@,取 @@M@@D=X^\dagger@@ 得 @@M@@Z\succeq\Phi_y(X^\dagger)=\sum_jB_j^\top X^\dagger B_j@@;配方即可验证切片铅笔半正定,故点属于 @@M@@K@@。尺寸核算:@@M@@\mathcal E@@ 有 @@M@@22\times15=330@@ 个坐标,扣除 23 个输出方程恰余 307 个辅助变量,测试空间 @@M@@5\times20=100@@ 给出铅笔尺寸。

可信度与备注

本文暂无形式化证明,按 OpenAI 官方声明,未经形式化的结果可能有问题,请以社区核验为准。文章自足地重证了双曲性与切片刻画,仅在对比意义上引用姊妹篇的”非谱面”结论,两文合起来精确刻画了同一个锥:非谱面但谱面影子。族内另一篇高维构造则证明某些双曲锥连谱面影子都不是;三篇合观,恰好把 Lax 猜想谱系(谱面、影子、无提升)的三个层级各安放到一个具体例子上。文中明确声明尺寸非极小,未做最小性讨论。


深入 | An Exact Semidefinite Lift of a Nonspectrahedral Hyperbolicity Cone

深入探讨:像审稿人一样追问 🔍

问 1:证明里最脆弱的一环在哪里?

答:反向包含。正向容易:K 中每点在某个角度处取赋值泛函即得可行见证。反向时,满足矩量矩阵半定条件的线性泛函不必来自任何测度、更不必是单点赋值;必须靠次数二匹配引理配平角依赖,从半定条件直接榨出切片不等式。这一环是全文技术核心,也最怕出代数细节错误。

问 2:为什么必须覆盖奇异 X 的点,只提升内点不行吗?

答:定理明确要求等价在整个闭锥上成立,包括 X 奇异的退化边界点。若只覆盖内点,投影出的集合可能差一个闭包,”精确提升”名不副实。证明为此分况收网:X 奇异时用 D=tvvᵀ 得值域条件、用 D=X† 得 Z⪰Φ_y(X†),再配方验证切片铅笔半正定。

问 3:与 Netzer–Sanyal、Scheiderer 的提升定理相比,真正新意是什么?

答:此前正面结果都依赖边界正则性(光滑或 Nash 光滑边界)。本文的锥显式非谱面、带退化边界点,提升由有界次代数构造直接给出;且全文自足——自证双曲性与切片刻画,仅在对比意义上引用姊妹篇的”非谱面”结论。

问 4:次数二匹配引理为什么不能省?

答:它是把连续角参数压进有限矩阵的关键:用 2×2 西旋转作用于固定 Gram 因子,西性保住 Gram 矩阵,旋转把三次频率压成一次谐波,再匹配函数值与一阶导数锁定配对。没有它,半定条件里的测试向量不足以恢复切片不等式,反向即断。次数一是否够用,论文未展开。

问 5:这类暂无形式化的 AI 生成证明最可能错在哪?

答:典型风险是簿记式错误:Gram 分解的三角多项式系数、矩矩阵元素 Λ(f_a f_b (L_θ)_ij) 的指标运算、330−23=307 与 5×20=100 的尺寸核算。这些机械计算局部看似显然、总量却大,恰是生成模型易错处;本文按官方声明属待社区核验之列。

问 6:谁会用这个结果?

答:双曲规划与多项式优化方向的研究者:它说明该锥上的线性目标优化原则上可化为 100 阶、330 变量的半定规划;也表示问题(哪些双曲锥是谱面影子)有了第一个”非谱面的影子”标杆。但 100×100 离实用尚远,且论文声明尺寸非极小。

总评

与姊妹篇合璧,把同一个锥的表示地位精确钉死在”非谱面、是影子”一层,是 Lax 猜想谱系里必要的一块拼图。最大风险在反向论证的匹配引理与矩量簿记尚无形式化核对,宜先做数值抽查再引为定论。