计算机视觉中的半定规划的双凸松弛
本文提出了一种针对大规模二次二次规划问题的新型 SDP(半定规划)公式,并基于此提出了两种求解方法,即准牛顿法和平滑牛顿法,该方法能有效地解决许多计算机视觉问题,包括聚类、图像分割、共同分割和注册等。
Nov, 2014
本文介绍了一种针对大规模问题的新型 SDP 公式,具有类似于传统 SDP 公式的松弛界限及较高的计算效率,可用于解决各种应用程序,包括聚类,图像分割,共同分割和注册。
Apr, 2013
本文研究了一类包括最大割、随机块模型社区检测、鲁棒 PCA、相位恢复和旋转同步等应用的半定规划 SDP,表明以 Burer-Monteiro 公式为代表的低秩 SDP 几乎从不具有虚假的局部最优解。
Jun, 2016
该论文提出了一种通用的多类弱监督分类方法,其中引入了一种基于凸松弛的代价函数来解决软最大损失的本地极小问题,于是设计了一种算法来高效地解决相应的半定规划问题,并在不同数据集上表现出较好的效果,包括多实例学习和半监督学习,以及聚类任务。
Jun, 2012
本文研究基于多项式函数的双层规划问题(BPPs),并利用 Fritz John 条件和 Jacobi 表示将 BPPs 等价地转换为半无限多项式规划(SIPPs)。结合交换技术和 Lasserre 半定松弛方法,提出了求解简单和一般 BPPs 的数值方法,对于简单 BPPs,证明了其全局最优解的收敛性,数值实验表明了所提算法的高效性。
Aug, 2015
这篇论文主要探讨了应用于信号处理、数据挖掘和机器学习中的统计推理问题,当数据的维度很高时,常常导致较难处理的组合优化问题。文中提出了通过构建这些组合优化问题的凸松弛来解决问题的热门思想。其中,半定规划松弛是该家族中最有力的方法之一,并且出人意料地适用于形如矩阵或图形的数据问题。作者对几个经典的半定规划松弛模型进行了研究,尤其是适用于图同步和网络中的社区检测等统计问题的模型。通过将这些优化问题映射到带有向量自旋的统计力学模型中,使用统计力学中的非严谨技术来描述相应的相变,以期阐明半定规划松弛在高维统计问题中解决问题的有效性。
Nov, 2015
利用现有的数值计算代数几何理论中的多项式优化问题,提出了一种通用的非最小化求解器,并将其应用于三维视觉中的非最小问题和一致性最大化问题,结果显示这种方法的结果与现有的方法相比非常有竞争力并且容易实现。
Sep, 2019
本研究提出了一种可应用于任何非最小化求解器的鲁棒全局估计通用方法,该方法利用了鲁棒估计与异常值处理之间的 Black-Rangarajan 对偶并结合逐步非凸性与 SDP 解法求解,解决了常规稳健代价函数导致的非凸性问题;本方法应用于点云和网格登记,位姿图优化和基于图像的形状算法中,具有 70-80%异常值鲁棒性,并且比专门的局部求解器更准确和更快。
Sep, 2019
我们开发了一种实用的半定规划 (SDP) 面部缩减程序,该程序利用了正半定锥的计算有效近似。该方法通过求解一系列较容易的优化问题简化 SDP,并可作为 SDP 求解器的有用预处理技术。我们展示了该方法在实践中应用的有效性,并描述了我们公开可用的软件实现。我们还展示了如何在我们的 PSD 锥近似中找到最大秩矩阵,并给出了一个基于面部缩减的预处理技术的双重解恢复的后处理过程。最后,我们展示如何选择逼近值以保留问题的稀疏性。
Aug, 2014