非对易变量的多项式优化问题的收敛松弛
这篇论文主要探讨了应用于信号处理、数据挖掘和机器学习中的统计推理问题,当数据的维度很高时,常常导致较难处理的组合优化问题。文中提出了通过构建这些组合优化问题的凸松弛来解决问题的热门思想。其中,半定规划松弛是该家族中最有力的方法之一,并且出人意料地适用于形如矩阵或图形的数据问题。作者对几个经典的半定规划松弛模型进行了研究,尤其是适用于图同步和网络中的社区检测等统计问题的模型。通过将这些优化问题映射到带有向量自旋的统计力学模型中,使用统计力学中的非严谨技术来描述相应的相变,以期阐明半定规划松弛在高维统计问题中解决问题的有效性。
Nov, 2015
本文提出了一种针对大规模二次二次规划问题的新型 SDP(半定规划)公式,并基于此提出了两种求解方法,即准牛顿法和平滑牛顿法,该方法能有效地解决许多计算机视觉问题,包括聚类、图像分割、共同分割和注册等。
Nov, 2014
研究了二次约束二次规划及其半定松弛的一个参数化族,并给出了在参数值改变时半定松弛的精确性条件,在估计问题中有广泛应用,并可用于分析一般多项式优化问题的松弛稳定性。
Oct, 2017
本文提出了一个统一的框架,能够证明广泛使用的迭代一阶优化算法的指数收敛和次指数收敛速率,并展示了该框架对梯度法、近端算法及其加速变体的实用性,同时开发了连续时间对应物,能够分析梯度流和 Nesterov 加速法的连续时间极限。
May, 2017
利用现有的数值计算代数几何理论中的多项式优化问题,提出了一种通用的非最小化求解器,并将其应用于三维视觉中的非最小问题和一致性最大化问题,结果显示这种方法的结果与现有的方法相比非常有竞争力并且容易实现。
Sep, 2019
本文介绍了如何将一个经典的稀疏正则化模型 with an l0 范数惩罚转化为凸松弛的形式,在此基础上通过引入远离凸性的惩罚函数,如 Minimax Concave Penalty (MCP) 以及 reverse Huber penalty,进一步推导出新的解法,并且可以通过半定松弛方法求解。文章最终通过 Goemans-Williamson 圆整算法来找到近似解。
Oct, 2015
本研究探讨多项式中局部最小值的等级。为此,我们首先计算 H - 最小值,并构建半定松弛序列来满足一、二阶最优性条件,证明每个构建序列都在一些通用条件下有有限收敛。我们提供了计算所有局部最小值的程序,并在存在等式约束时得到了类似的结果,研究了若干扩展情况。
Nov, 2013