Oct, 2019

半定最优化问题的多面体和二阶圆锥分解

PDF
TL;DR研究了一种用于半定规划问题（SDOs）的切平面方法，证明了该方法基于有界性假设的收敛性。通过将该方法的收敛速度与初始外近似的直径联系起来，我们证明了当使用二阶锥逼近而不是线性逼近时该方法的表现更好。我们将该方法用于提供数千个协变量的稀疏 PCA 问题的边界间隙，并解决了 500x500 矩阵上的核范数问题。
cutting-plane methodsemidefinite optimizationconvergencesparse pcanuclear norm problems
发现论文，激发创造
  • 凸半定规划的混合算法

    提出了一种用于最优化正半定矩阵锥上凸光滑函数的混合算法，可以用于解决各种机器学习问题，并且在三个机器学习问题上的实验结果表明，该方法优于现有算法。

    Jun, 2012

  • 通过算子分裂和齐次自对偶嵌入实现锥优化

    该研究提出了一种用于解决大规模凸锥问题的一阶方法，该方法使用交替方向乘子法来解决自对偶嵌入问题，该方法不需要参数，可以找到原始解和对偶解，并且在大规模优化问题上表现出色。

    Dec, 2013

  • 部分面部减少：通过 PSD 锥体的近似来简化等价的 SDP

    我们开发了一种实用的半定规划 (SDP) 面部缩减程序，该程序利用了正半定锥的计算有效近似。该方法通过求解一系列较容易的优化问题简化 SDP，并可作为 SDP 求解器的有用预处理技术。我们展示了该方法在实践中应用的有效性，并描述了我们公开可用的软件实现。我们还展示了如何在我们的 PSD 锥近似中找到最大秩矩阵，并给出了一个基于面部缩减的预处理技术的双重解恢复的后处理过程。最后，我们展示如何选择逼近值以保留问题的稀疏性。

    Aug, 2014

  • 使用优化获得宽度无关、并行、简单、更快的正定半定规划求解器

    本文针对包装和覆盖半正定程序（或正半定规划）的近似求解，研究了多对数深度算法的设计，并提出了一种基于优化框架的简单算法，其正确性基于 Lieb-Thirring 不等式的新矩阵不等式和梯度截断技术的随机变体。

    Jul, 2015

  • 用度量的 Dikin Walk 高效采样 PSD 空间锥

    半定规划和优化中的采样过程，使用 Dikin 行走和内点方法结合，通过适当的指标选择，可以在多项式对数的复杂度下减少混合时间和步骤复杂度。

    Jul, 2023

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

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

    Jun, 2017

  • 二次罚函数半定规划低秩解的平滑分析

    本文采用 Burer-Monteiro 分解方法解决 SDP 问题，考虑约束条件次数随所需最优解的秩呈次二比例增长时，所有的近似局部最优解均为全局最优解，并将这个结果应用于 Max-Cut 和矩阵填充问题。

    Mar, 2018

  • 内存高效优化的锥下降

    通过对第一阶锥下降（CD）求解器进行直观性、理论性和算法实现方面的改进研究，发现 CD 可以通过对偶问题的几何推导得到直观的解释，从而为新算法设计打开了大门，其中包括动量变量 MOCO。进一步深入研究了 CD 和 MOCO 的对偶行为，揭示了解析合理的停止准则和设计预处理器以加快对偶收敛的潜力。最后，为了扩展半定规划（SDP）的规模，特别是对于低秩解，开发了一个内存高效的 MOCO 变体，并得到了数值验证。

    Aug, 2023

  • 凸优化、凸凹博弈的改进切割平面方法及其应用

    提出了一种新的剪切平面算法，采用多层数据结构来维护杠杆得分，通过随机投影，批量低秩更新，逆维护，多项式插值和快速矩阵乘法的复杂组合来实现，优化了以前算法的依赖性，并在经济学中的许多重要应用中实现了更好的性能。

    Apr, 2020

  • 基于递归割平面法的内存受限凸优化算法

    我们提出了一系列递归割平面算法，用于解决具有受限内存的可行性问题，这些算法可以用于一阶凸优化。

    Jun, 2023