SOS证书次数界达δ^-1/2，Lasserre层级收敛速率最优！
Sharp Degree Bounds for Putinar Certificates in Terms of the Positivity Margin via Analytic Sums of Squares
📖 AI 总结
该论文研究Putinar平方和证书的度数界问题，核心贡献是建立了以正性裕度δ为参数的尖锐度数上界。作者针对任意固定的Archimedean二次模与目标多项式度数上界，证明归一化多项式目标的证书度数不超过O(δ^{-1/2}log²(2/δ))，并通过构造三变量匹配下界实例说明该依赖关系在δ上已是最优，从而确认上界的尖锐性。作为推论，这些匹配界还给出了Lasserre层级的最坏情况收敛速率。该结果的意义在于首次刻画了证书度数对正性裕度的精确依赖，为平方和优化中证书复杂度的理论分析提供了紧的定量基准。
🔑 关键词速览
| Putinar证书 | 一种用于证明多项式在某个半代数集上非负的平方和表示方法，基于Putinar的Positivstellensatz定理。 |
| 正性裕度 | 多项式在可行域上的最小值与零之间的差距，衡量多项式严格正的程度。 |
| 平方和（SOS） | 指多项式可以表示为有限个多项式的平方和的形式，是多项式优化中的重要概念。 |
| 阿基米德二次模 | 一种特殊的二次模，满足阿基米德性质，即存在常数使得某个生成元可以控制所有变量的平方。 |
| Lasserre层级 | 一种基于平方和松弛的层次化方法，用于求解多项式优化问题，通过增加松弛阶数逐步逼近最优解。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅