Feb, 2013

可分约束凸优化问题的高效并行坐标下降算法：应用于分布式 MPC

PDF
TL;DR本文提出了一种并行坐标下降算法，用于解决具有可分离约束的光滑凸优化问题，在线性网络系统的分布式模型预测控制（MPC）中可能出现。我们的算法基于块坐标下降更新，并具有非常简单的迭代。我们证明了该算法在光滑凸优化的标准假设下具有（次）线性收敛率。此外，我们的算法使用本地信息，因此适用于分布式实现。此外，它具有较低的迭代复杂性，适用于嵌入式控制。我们派生了一个基于这种新并行算法的 MPC 方案，其中网络中的每个子系统都可以使用分布式和廉价的计算来计算可行的和稳定的控制输入。为了确保 MPC 方案的稳定性，我们使用从分布式合成中派生的终端成本公式。初步的数字测试显示我们的优化算法比其他现有方法具有更好的性能。
发现论文，激发创造
  • 异步并行随机坐标下降算法

    本文提出了一种异步并行随机坐标下降算法，它具有线性收敛速率和 $1/K$ 的次线性速率，可实现基于多核系统的近线性加速，并取得了在 40 核处理器上的实现结果。

    Nov, 2013

  • 大数据优化的并行坐标下降方法

    本文针对最小化部分可分平滑凸函数和简单可分离凸函数之和的问题，展示了随机（块）坐标下降法在并行化时可以加速。 研究表明，与串行方法相比，在高概率下近似解决问题所需的迭代次数的理论加速比简单地依赖于并行处理器数量和目标函数平滑部分可分离的自然且易于计算的可分离度度量。 此外，当每次迭代更新的块数是随机的时，该算法的处理能力也非常出色，并可以解决涉及具有 200 亿个非零元素的矩阵的 LASSO 问题。

    Dec, 2012

  • 随机块坐标下降方法解决网络线性约束最优化问题

    本文介绍了基于随机块坐标梯度下降的并行优化算法，能够快速高效地解决大规模线性可分凸问题在网络结构上的应用，收敛速率与更新组件 $ au$ 线性相关，并探讨了稀疏半定规划解法和具体应用。

    Apr, 2015

  • 大规模鞍点问题的随机并行块坐标下降

    本文提出一种新的针对分离结构和非强凸函数的凸凹鞍点问题的高效随机块坐标下降方法，采用自适应原始 - 对偶更新方法，可灵活地并行优化大规模问题。该方法在多个机器学习应用中均有显著提高，包括鲁棒主成分分析、Lasso 和通过组 Lasso 进行特征选择等。在理论和实际上，我们证明了该方法在所有这些应用中都具有明显优势。

    Nov, 2015

  • 分布式块坐标下降法用于最小化部分可分离函数

    本文提出了一种分布式随机块坐标下降方法来最小化具有大量变量 / 坐标的凸函数，并分析了其复杂度，其中局部块可分的光滑部分直接影响了其复杂度，进一步扩展了已有研究成果，该方法在分布式环境下的实现还使用了集群计算和计算同步等技术。

    Jun, 2014

  • 异步随机坐标下降：并行与收敛性质

    本文提出一种异步并行随机近端坐标下降算法，用于最小化由光滑凸函数和可分离凸函数组成的复合目标函数，并给出在多核处理器上的实现结果。

    Mar, 2014

  • 自适应随机原始对偶坐标下降算法处理可分离鞍点问题

    本文提出了一种基于随机块坐标下降和自适应步长的原始 - 对偶更新框架，用于解决具有可分结构的凸 - 凹鞍点问题，并在正则化的经验风险最小化问题上进行了实证分析，结果表明该方法具有较快的收敛速度和良好的表现。

    Jun, 2015

  • 坐标下降算法

    本研究旨在介绍了坐标下降算法的基本原理、变体及其扩展，特别关注于在数据分析、机器学习等领域中的应用及并行执行的收敛性等。

    Feb, 2015

  • 更加现实的假设下的异步坐标下降

    本篇论文研究非同步并行块协调下降算法，证明了更实际的假设条件下算法的收敛性，并构建了直接模拟目标进展和延迟的李雅普诺夫函数。

    May, 2017

  • 加速、并行和近端坐标下降

    本篇论文提出了一种新的随机坐标下降方法，能够并行、加速和提高期望可分超逼近，此方法能够同时最小化依赖于少数坐标的多个凸函数的和，通过使用新的安全且大的步长，使得该方法不需要执行完整的矢量运算。

    Dec, 2013