Jul, 2016

Sparse-BSOS：具有稀疏性的大规模多项式优化有界次 SOS 层次结构

PDF
TL;DR本文提出了一种稀疏版本的有界次数 SOS 层次结构 BSOS，适用于多项式优化问题，特别针对结构稀疏模式问题。当稀疏模式满足运行交替性质时，这种具有固定大小的半定规划的稀疏 - BSOS 层次结构会收敛于原问题的全局最优解。此外，对于 SOS - 凸问题类，在层次结构的第一步就会出现有限收敛，就像在密集版本中一样。
发现论文，激发创造
  • TSSOS：一种利用项稀疏性的 Moment-SOS 层次

    本文介绍了一个新的半定编程松弛分层方法，可利用输入多项式的项（或单项式）稀疏性，包括使用在一个迭代过程中生成的与原始数据中的术语相关的邻接图的连通分量的完成得到的块对角矩阵。该框架应用于计算多项式优化问题的下界。

    Dec, 2019

  • 利用和弦扩展利用项稀疏性的矩 - 和悬空层次结构 Chordal-TSSOS

    提出了一种新的基于项稀疏性和和弦扩展的稀疏矩 - SOS 框架，应用于解决多项式优化问题。在两级半定规划松弛下，通过迭代过程获得准块对角矩阵，其图与原始数据中涉及的项有关，并通过各种数值算例表明了该方法的有效性和可扩展性。

    Mar, 2020

  • DSOS 和 SDSOS 优化：比完全平方和和半定性优化更易处理的替代方法

    本文介绍了 DSOS 和 SDSOS 最优化算法作为线性规划和二阶锥规划的替代方法，以允许一个在计算时间与解决方案质量之间进行权衡的选择，并且用多个应用领域的数值实验表明，我们可以在目前传统的平方和算法难以实现的规模上处理问题。

    Jun, 2017

  • 用逆矩阵动量 SOS 多项式分类典型性

    研究使用多项式表示数据点云时，一种与特定和坐标轴相关的 SOS 多项式可以准确捕获云的形状，同时对正交多项式的极值属性进行了推广和解释，具有广泛的应用潜力，例如网络入侵检测。

    Jun, 2016

  • 稀疏主成分分析的平方和下界

    本文研究使用凸松弛法解决高维机器学习问题时，统计与计算的权衡。对稀疏主成分分析（Sparse PCA）问题和 Sum-of-Squares（即 Lasserre / Parillo）凸松弛法进行了探究。通过研究发现基于次数 - 4 的 SoS 算法不能改善计算次数为 k² 的情况，为这种强大的凸松弛算法族中的一部分问题建立了平均情况下的下限，说明它们存在困难问题。

    Jul, 2015

  • 稀疏贝叶斯优化

    介绍了一种适用于解释性要求高场景下的基于正则化的 BO 方法（SEBO），以发现稀疏且解释性更高的配置。该方法使用一种基于连续同伦的可微松弛技巧，使其能够在直接处理 L0 正则化的同时实现目标优化和稀疏化探索，经过合成和真实世界问题的评估，证明这种方法能够有效优化稀疏化问题。

    Mar, 2022

  • 稀疏轴向对齐子空间的高维贝叶斯优化

    基于高斯过程 surrogate 模型，利用 Hamiltonian Monte Carlo 进行推断，能够迅速识别与建模未知目标函数相关的空间稀疏子空间，实现高维贝叶斯优化 (Bayesian optimization) 中样本效率与性能的权衡。

    Feb, 2021

  • 半定规划层次结构在图模型推断中的应用

    本文提出使用具有两个创新的二进制 SDP 松弛，同时聚焦于计算效率的 SOS 层次结构进行 MAP 推理，该算法在实际问题如图像去噪和 Ising 自旋玻璃方面表现优于 BP 和 GBP。

    Sep, 2017

  • 通过稀疏有界平方和规划实现全局保证最优平面位姿图和地标 SLAM

    该文章介绍了如何用稀疏 BSOS 分层算法将姿态 - 图和地标 - 图问题表述为多项式优化问题，并以全局最小化解决了这些问题，同时通过实验展示了该方法的卓越性能。

    Sep, 2018

  • 一种用于非负最小二乘问题中寻找结构稀疏解的方法及其应用

    利用结构稀疏性假设将稀疏非负线性组合与组合间的稀疏性拓展到字典组合元素的分组上，采用 Hoyer 惩罚与缩放梯度投影算法解决了字典高度相干限制带来的问题，解决了 DOAS 分析和高光谱混合问题。

    Jan, 2013