Sep, 2014

用于符号多项式优化的相对熵松弛

PDF
TL;DR本文介绍一种通过一系列随着规模逐渐增大的相对熵优化问题计算上下界的方法，其关键在于使用相对熵函数提供的一种凸嵌参数解决某些全局非负信号量集的证明。并利用实数代数几何的表示定理，证明我们的下界序列收敛于广泛的符号式程序类的全局最优值。最后，我们通过数值实验展示了我们的方法的有效性。
signomial programsconvex relaxationsrelative entropy functionnonnegativity certificatesnumerical experiments
发现论文，激发创造
  • 半定松弛中的相变

    这篇论文主要探讨了应用于信号处理、数据挖掘和机器学习中的统计推理问题，当数据的维度很高时，常常导致较难处理的组合优化问题。文中提出了通过构建这些组合优化问题的凸松弛来解决问题的热门思想。其中，半定规划松弛是该家族中最有力的方法之一，并且出人意料地适用于形如矩阵或图形的数据问题。作者对几个经典的半定规划松弛模型进行了研究，尤其是适用于图同步和网络中的社区检测等统计问题的模型。通过将这些优化问题映射到带有向量自旋的统计力学模型中，使用统计力学中的非严谨技术来描述相应的相变，以期阐明半定规划松弛在高维统计问题中解决问题的有效性。

    Nov, 2015

  • 非对易变量的多项式优化问题的收敛松弛

    本文介绍了一种解决量子理论和量子信息科学中涉及的多项式不等式约束的最优化问题的方法，使用一系列半定规划松弛方法生成一个单调递增的下界序列，并介绍了从相应的半定规划问题的解中提取全局优化器的方法。

    Mar, 2009

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

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

    Sep, 2017

  • 正则化与放松：统计变量选择的锥优化视角

    本文介绍了如何将一个经典的稀疏正则化模型 with an l0 范数惩罚转化为凸松弛的形式，在此基础上通过引入远离凸性的惩罚函数，如 Minimax Concave Penalty (MCP) 以及 reverse Huber penalty，进一步推导出新的解法，并且可以通过半定松弛方法求解。文章最终通过 Goemans-Williamson 圆整算法来找到近似解。

    Oct, 2015

  • 舍入平方和松弛问题

    通过转换一个分布映射算法为一个近似解，我们提出了一个通过利用半正定规划松弛和 SOS 证明系统之间的联系来舍入 SOS 松弛的一般方法，并应用于 3 个已知问题的改进，分别是：低次多项式最大值问题、小集合扩展问题以及恢复一个种植稀疏向量的多项式时间算法。

    Dec, 2013

  • 半正定松弛局部稳定性

    研究了二次约束二次规划及其半定松弛的一个参数化族，并给出了在参数值改变时半定松弛的精确性条件，在估计问题中有广泛应用，并可用于分析一般多项式优化问题的松弛稳定性。

    Oct, 2017

  • 线性规划中熵惩罚的明确分析

    使用熵惩罚方法解决线性规划问题已成为优化界的新热点，这种方法不仅用于解决最优输运问题，并广泛应用于现代大规模机器学习中。本文通过提供一个新的证明来解决关于熵惩罚的长期问题，该证明具有指数收敛和相当的精确度，同时表明熵惩罚方法不适用于线性分配问题的近似解。

    Jun, 2018

  • 利用半定松弛和应用程序实现大规模的二值二次规划

    本文提出了一种针对大规模二次二次规划问题的新型 SDP（半定规划）公式，并基于此提出了两种求解方法，即准牛顿法和平滑牛顿法，该方法能有效地解决许多计算机视觉问题，包括聚类、图像分割、共同分割和注册等。

    Nov, 2014

  • 关于 QCQP 的 SDP 松弛的紧度

    本文探讨了标准半正定规划松弛下紧 QCQP 的条件，表明当二次本征值多重性足够大时松弛是紧的，并得到了相似的充分条件。此外，结果还暗示了同时对角化 QCQP 的二阶锥松弛的紧性的新充分条件。

    Nov, 2019

  • 通过内存高效的半定规划使验证无关网络实现认证

    该论文介绍了一种新的 SDP 算法，利用迭代特征向量方法将其各种操作表达为网络正反向传播。在 MNIST 和 CIFAR-10 数据集上的两个验证矢量网络中，将 L-inf 的验证鲁棒准确性从 1％提高到 88％和从 6％提高到 40％

    Oct, 2020