Jan, 2012

正半定规划的更快速、更简单的宽度独立并行算法

PDF
TL;DR本文研究了正半定规划的近似算法，提出了一种简单的 NC 并行算法，其迭代次数为 O (1/ϵ³ log³ n)，总工作量近似为因子分解中非零条目数的线性级别。
positive semidefinite programsapproximation algorithmssimple matrix operationsparallel algorithmsmatrix exponential
发现论文，激发创造
  • 使用优化获得宽度无关、并行、简单、更快的正定半定规划求解器

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

    Jul, 2015

  • 半定规划的更快内点方法

    本文介绍一种更快的内点法，用于求解具有变量大小的一般半定规划问题，并解释了算法的运行时间和矩阵乘法的指数和相对精度之间的关系。

    Sep, 2020

  • 正半定矩阵分解算法

    本文通过引入几种本地优化方案解决正半定因子分解问题，主要应用是用于计算半定扩展，即将多面体表示为 spactrahedra 的投影表示

    Jul, 2017

  • 正半定格罗滕迪克问题的秩约束

    本文设计了一个多项式时间逼近算法以解决正半定 Grothendieck 问题，得到了逼近比例，并证明了该逼近比例是最优的。作者也提出了一种改进的算法，并应用它来解决 Laplacian 矩阵的情况。

    Oct, 2009

  • 结构化半定规划用于恢复结构化预条件器

    我们开发了一个普遍框架用于寻找解线性系统的近似最优预条件器，利用该框架，我们获得了优化预条件化和线性系统求解问题的运行时间改进。

    Oct, 2023

  • 凸半定规划的混合算法

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

    Jun, 2012

  • 利用半正定规划对稀疏 PCA 进行直接求解

    研究在 Frobenius-norm 意义下，将正半定对称矩阵近似为一个秩为一的矩阵，其特征向量的基数有一个上限的问题以及其在协方差矩阵分解到稀疏因子等领域中的应用，提出了一个基于半定规划的方法，并讲解了 Nesterov's 平滑最小化技术在直接稀疏 PCA 方法中的应用。

    Jun, 2004

  • 半定规划方法求解稀疏图的二次分配问题

    本研究提出了一种新的半定规划 (SDP) 方法来解决二部图的匹配问题，采用正半定矩阵进行松弛，并通过聚类来加强松弛，使得计算复杂度和运行时间得到了缩减，可以应用于核磁共振光谱 (NMR) 等领域的匹配问题。

    Mar, 2017

  • 最近半正定规划可扩展性的调查及其在机器学习、控制和机器人领域的应用

    本文介绍了解决半定规划在机器学习、控制和机器人领域中可扩展性问题的最近方法，包括利用问题结构（如稀疏性和对称性）、生成低秩近似解决方案、更可扩展算法、以及将可扩展性与保守性相妥协的方法，并提供相应文献入口和实例，最后列出了实现本文所讨论的方法的软件包清单。

    Aug, 2019

  • SDPNAL$+$: 半定规划带非负约束的主化半平滑牛顿 - CG 增广拉格朗日方法

    提出了 SDPNAL+，一种用于半定规划（SDP）的 majorized semismooth Newton-CG 增广 Lagrange 方法。 它结合了收敛的 3 块交替方向乘法方法和矩阵变量上部分或全部非负约束的优化方法。 与其他两种代码相比，提出的方法不仅快速而且稳健，而且可以高效地解决所有从 SDPNAL 测试的 95 个困难 SDP 问题，同时另外两个方法分别只能成功解决 30 个和 16 个问题。

    Jun, 2014