本文探讨了标准半正定规划松弛下紧 QCQP 的条件,表明当二次本征值多重性足够大时松弛是紧的,并得到了相似的充分条件。此外,结果还暗示了同时对角化 QCQP 的二阶锥松弛的紧性的新充分条件。
Nov, 2019
这篇论文主要探讨了应用于信号处理、数据挖掘和机器学习中的统计推理问题,当数据的维度很高时,常常导致较难处理的组合优化问题。文中提出了通过构建这些组合优化问题的凸松弛来解决问题的热门思想。其中,半定规划松弛是该家族中最有力的方法之一,并且出人意料地适用于形如矩阵或图形的数据问题。作者对几个经典的半定规划松弛模型进行了研究,尤其是适用于图同步和网络中的社区检测等统计问题的模型。通过将这些优化问题映射到带有向量自旋的统计力学模型中,使用统计力学中的非严谨技术来描述相应的相变,以期阐明半定规划松弛在高维统计问题中解决问题的有效性。
Nov, 2015
本文提出了一种针对大规模二次二次规划问题的新型 SDP(半定规划)公式,并基于此提出了两种求解方法,即准牛顿法和平滑牛顿法,该方法能有效地解决许多计算机视觉问题,包括聚类、图像分割、共同分割和注册等。
Nov, 2014
本文介绍了一种针对大规模问题的新型 SDP 公式,具有类似于传统 SDP 公式的松弛界限及较高的计算效率,可用于解决各种应用程序,包括聚类,图像分割,共同分割和注册。
Apr, 2013
通过解决凸松弛,可以证明神经网络对抗性示例的鲁棒性。最近,提出了一种基于半定编程松弛的较少保守的鲁棒性证明方法。本文提出一种几何技术,用于确定该 SDP 证书是否是精确的,并在单隐藏层下证明该证书的精确性,并验证其理论洞见。
Jun, 2020
本文采用 Burer-Monteiro 分解方法解决 SDP 问题,考虑约束条件次数随所需最优解的秩呈次二比例增长时,所有的近似局部最优解均为全局最优解,并将这个结果应用于 Max-Cut 和矩阵填充问题。
Mar, 2018
通过转换一个分布映射算法为一个近似解,我们提出了一个通过利用半正定规划松弛和 SOS 证明系统之间的联系来舍入 SOS 松弛的一般方法,并应用于 3 个已知问题的改进,分别是:低次多项式最大值问题、小集合扩展问题以及恢复一个种植稀疏向量的多项式时间算法。
Dec, 2013
本文提出将最小二乘问题转化为凸性的半定规划问题,通过刚体变换及刚体理论来稳定恢复解,同时实验证明该方法在噪声较大时表现显著优于谱松弛法和流形优化方法。
Jun, 2013
本文提出了一种无需转换法的凸松弛方法,用于解决由排列矩阵表示的二次优化问题,该方法在求解图像排列和多图匹配问题等实例中表现出更好的性能。
Nov, 2017
通过基于代数几何工具的一般框架分析,我们研究了用于解决涉及旋转的非凸优化问题的半定松弛的能力。研究中表明其在注册、手眼校准和旋转平均等应用中性能好、稳定。但在极端情况下会存在非常数解,需要适当的参数化方法。
Jan, 2021