SOS Polynomials

该数据集名为SOS Polynomials，由柏林Zuse研究所和柏林工业大学的研究团队创建。数据集包含了超过1亿个SOS多项式，用于训练Transformer模型，以预测给定多项式的近似最小单项式基，从而大幅度减少相应SDP问题的规模。数据集的创建过程采用了反向采样技术，确保了生成的基础具有足够的代表性。该数据集在多项式优化、控制理论、机器人等领域有着广泛的应用前景，有助于解决多项式非负性验证这一NP难题。This dataset, named SOS Polynomials, was developed by a research team from the Zuse Institute Berlin and the Technical University of Berlin. It contains over 100 million SOS polynomials, which are used to train Transformer models to predict the approximate minimal monomial basis of a given polynomial, thereby significantly reducing the scale of the corresponding SDP problems. The dataset was constructed using reverse sampling techniques, ensuring that the generated bases possess sufficient representativeness. This dataset has broad application prospects in fields such as polynomial optimization, control theory and robotics, and can help solve the NP-hard problem of polynomial nonnegativity verification.

搜集汇总

数据集介绍

构建方式

在多项式非负性认证的研究中，SOS Polynomials数据集通过反向采样技术构建，旨在为学习增强的平方和（SOS）编程提供训练基础。该数据集生成了超过一亿个SOS多项式及其对应的（近）最小单项式基对，覆盖了稠密、稀疏、低秩和块对角等多种矩阵结构。生成过程首先从给定的变量数和度数范围内均匀采样单项式集合作为基，然后随机生成半正定矩阵，通过基向量与矩阵的乘积构造具有已知紧凑SOS分解的多项式。这种设计确保了每个多项式都附带一个有效的基，同时通过调整变量数、度数和项数来增强数据多样性，使生成的多项式家族能够跨越不同问题规模，为Transformer模型提供丰富的结构模式学习素材。

特点

SOS Polynomials数据集的核心特点在于其规模宏大与结构多样性，专门服务于SOS基预测的机器学习任务。数据集不仅包含海量的多项式实例，还通过系统化的参数网格设计，涵盖了从4到100个变量、度数高达40的广泛配置，确保了模型能够接触不同复杂度的多项式结构。其单项式基经过理论下界验证，多数情况下接近最小规模，这为学习紧凑基预测提供了高质量监督信号。此外，数据集特别强调了分布外泛化能力，通过构造未见度数和变量排列的测试实例，评估模型对结构模式的迁移学习效果，为SOS编程的实际可扩展性提供了扎实的数据支撑。

使用方法

该数据集主要用于训练和评估基于Transformer的SOS基预测模型，以加速多项式非负性认证。在使用时，首先将多项式进行词元化处理，将每个单项式的系数和指数编码为序列输入模型；模型则基于编码后的多项式预测一个紧凑的单项式基序列。预测后的基需经过覆盖修复算法检查，确保其满足必要的结构条件；若初始基不完整，则通过贪心或排列评分机制迭代扩展基，直至找到有效的SOS分解或穷尽所有候选单项式。整个流程将学习预测与传统的半定规划求解相结合，在保持正确性保证的同时，显著降低了计算复杂度，为高维非凸多项式优化问题提供了高效的解决方案。

背景与挑战

背景概述

SOS Polynomials数据集诞生于2025年，由柏林工业大学、马德里卡洛斯三世大学及马克斯·普朗克智能系统研究所等机构的Nico Pelleriti、Christoph Spiegel、Shiwei Liu等学者共同构建。该数据集聚焦于多项式非负性认证这一NP难问题，该问题在非凸优化、控制理论与机器人学等领域具有核心应用价值。数据集通过逆向采样技术生成了超过一亿个具备已知平方和分解的多项式实例，旨在为学习增强型算法提供训练基础，以解决传统平方和规划中半定规划维度爆炸的计算瓶颈。

当前挑战

SOS Polynomials数据集旨在应对多项式非负性认证中的计算挑战，其核心问题在于高效寻找紧凑的单项式基以缩减半定规划规模。构建过程中的主要挑战包括：生成兼具多样性与理论紧致性的平方和多项式实例，需平衡矩阵结构的覆盖度与采样效率；设计能够准确预测近极小基的Transformer模型，需克服多项式序列表示与基生成之间的复杂映射关系；确保学习算法的正确性，需引入系统的回退机制以处理预测不完整的情况，同时维持与传统方法相当的理论保证。

常用场景

经典使用场景

在多项式非负性认证领域，SOS Polynomials数据集作为首个结合Transformer模型与半定规划（SDP）的学习增强方法，其经典使用场景聚焦于高效预测紧凑单项式基。通过生成超过一亿个已知平方和（SOS）分解的多项式及其近极小基对，该数据集训练Transformer模型从多项式输入中推断出最小化SDP规模的基向量。这一流程显著降低了传统基于牛顿多面体方法中基规模的二次增长瓶颈，为高维非凸多项式优化提供了可扩展的计算框架。

衍生相关工作

该数据集衍生的经典工作包括对传统SOS编程框架的多种扩展与改进。基于牛顿多面体与弦稀疏性的规则化方法（如TSSOS和Chordal分解）曾致力于利用问题结构缩减基规模，而本工作首次将学习预测与算法保证相结合，开创了学习增强SOS编程的新范式。后续研究进一步探索了大型语言模型在SOS验证中的推理能力，以及针对组合优化问题的神经算法设计，这些进展共同推动了计算代数与优化理论的交叉融合。

数据集最近研究

最新研究方向

在多项式非负性认证领域，SOS Polynomials数据集的最新研究聚焦于将深度学习与经典优化方法相结合，以解决传统平方和（SOS）编程中的计算瓶颈。近期，研究者提出了一种基于Transformer的神经平方和方法，通过预测紧凑的单项式基来大幅缩减半定规划（SDP）的规模。该方法利用超过一亿个SOS多项式生成的训练数据，训练模型识别多项式结构中的稀疏模式，从而在保持理论正确性的前提下，实现了相比传统牛顿多面体方法高达数百倍的加速。这一进展不仅推动了控制理论、机器人学和非凸优化等领域的实际应用，还为算法与预测框架下的学习增强优化提供了新范例，标志着SOS编程向高效可扩展方向迈出了关键一步。

相关研究论文

• Neural Sum-of-Squares: Certifying the Nonnegativity of Polynomials with Transformers

  柏林Zuse研究所, 柏林工业大学, 马德里卡洛斯三世大学, ELLIS图宾根研究所, 图宾根马克斯普朗克智能系统研究所, 图宾根AI中心 · 2025年