TSSOS:一种利用项稀疏性的 Moment-SOS 层次
提出了一种新的基于项稀疏性和和弦扩展的稀疏矩 - SOS 框架,应用于解决多项式优化问题。在两级半定规划松弛下,通过迭代过程获得准块对角矩阵,其图与原始数据中涉及的项有关,并通过各种数值算例表明了该方法的有效性和可扩展性。
Mar, 2020
本文提出了一种稀疏版本的有界次数 SOS 层次结构 BSOS,适用于多项式优化问题,特别针对结构稀疏模式问题。当稀疏模式满足运行交替性质时,这种具有固定大小的半定规划的稀疏 - BSOS 层次结构会收敛于原问题的全局最优解。此外,对于 SOS - 凸问题类,在层次结构的第一步就会出现有限收敛,就像在密集版本中一样。
Jul, 2016
本文介绍了 DSOS 和 SDSOS 最优化算法作为线性规划和二阶锥规划的替代方法,以允许一个在计算时间与解决方案质量之间进行权衡的选择,并且用多个应用领域的数值实验表明,我们可以在目前传统的平方和算法难以实现的规模上处理问题。
Jun, 2017
研究使用多项式表示数据点云时,一种与特定和坐标轴相关的 SOS 多项式可以准确捕获云的形状,同时对正交多项式的极值属性进行了推广和解释,具有广泛的应用潜力,例如网络入侵检测。
Jun, 2016
本文研究使用凸松弛法解决高维机器学习问题时,统计与计算的权衡。对稀疏主成分分析(Sparse PCA)问题和 Sum-of-Squares(即 Lasserre / Parillo)凸松弛法进行了探究。通过研究发现基于次数 - 4 的 SoS 算法不能改善计算次数为 k² 的情况,为这种强大的凸松弛算法族中的一部分问题建立了平均情况下的下限,说明它们存在困难问题。
Jul, 2015
本文介绍了一种罚矩阵估计过程,旨在同时具有稀疏和低秩的解决方案。我们引入了一个凸混合惩罚,同时涉及 l1 范数和迹范数。我们在链接预测问题中限制了广义误差,并开发了近端下降策略以有效解决优化问题,并在合成和真实数据集上评估了性能。
Jun, 2012
本文提出使用具有两个创新的二进制 SDP 松弛,同时聚焦于计算效率的 SOS 层次结构进行 MAP 推理,该算法在实际问题如图像去噪和 Ising 自旋玻璃方面表现优于 BP 和 GBP。
Sep, 2017
通过转换一个分布映射算法为一个近似解,我们提出了一个通过利用半正定规划松弛和 SOS 证明系统之间的联系来舍入 SOS 松弛的一般方法,并应用于 3 个已知问题的改进,分别是:低次多项式最大值问题、小集合扩展问题以及恢复一个种植稀疏向量的多项式时间算法。
Dec, 2013
利用结构稀疏性假设将稀疏非负线性组合与组合间的稀疏性拓展到字典组合元素的分组上,采用 Hoyer 惩罚与缩放梯度投影算法解决了字典高度相干限制带来的问题,解决了 DOAS 分析和高光谱混合问题。
Jan, 2013