原始 - 对偶速率与证明
本文提出了一种原始 - 对偶算法框架,以获得近似解决方案来解决典型的约束凸优化问题,并严格描述了常见结构假设如何影响数值效率。通过选择双重平滑策略和中心点,我们的框架将分解算法、增广 Lagrange 以及交替方向乘子方法作为其特殊情况,并为所有迭代的原始目标残差和原始可行性间隙提供最优收敛速率。
Jun, 2014
本文介绍了一个统一的架构,分析了一类大型原始对偶分裂问题,并使用抽象分析证明了分裂算法的收敛性速率以及推导了变量度量、步长和松弛下的推导速率等相关内容。
Aug, 2014
本文介绍了一种新的一阶原始 - 对偶优化框架,利用平滑、加速和同伦等三个经典思想,实现了具有许多广泛应用的凸优化,达到了最佳的收敛效果,针对只包含非平滑函数的情况。同时提供了重新启动策略,大大提高了实际性能,并展示了与增广拉格朗日方法的关系以及如何利用严格收敛率保证来利用强凸目标。最后提供了两个实例验证,表明新的方法可以优于 Chambolle-Pock 和交替方向乘法算法等现有的算法。
Jul, 2015
本文提出了批处理和随机的原始 - 对偶算法,可以自适应地利用数据的强凸性,即使在没有正则化的情况下也能实现线性收敛,并介绍了适用于逻辑回归的免双重正演算法。
Mar, 2017
本文介绍了多步优化算法的收敛加速方案,并使用 Chebyshev 问题模拟了迭代过程中的行为,同时讨论了该方案在原始 - 对偶算法中的应用,并在逻辑回归问题中进行了数值实验。
Oct, 2018
本文提出一种新的加速梯度下降的变种,该方法不需要任何有关目标函数的信息,使用精确线性搜索进行实际加速收敛,可以根据已知的凸和非凸目标函数的下界进行收敛,具有原始对偶属性,并可在非欧几里得设置中应用。同时,我们还提出了一种适用于非平滑问题的通用方法。
Sep, 2018
本篇论文提出一种基于分布式环境中的 L1 正则化优化问题的通信高效框架,通过将经典目标在更一般的原始对偶设定中进行观察,我们开发了一类新方法,能够有效地分布式和应用于常见的稀疏性诱导模型。
Dec, 2015
本文介绍了一种随机外推的原始 - 对偶坐标下降方法,它适应数据矩阵的稀疏性和目标函数的有利结构,更新了仅包含稀疏数据的一小部分原始和对偶变量,并使用较大的步长和密集数据,保留了为每种情况设计的特定方法的优点。此外,我们的方法不需要任何修改即可适应稀疏性,在有利的情况下获得快速收敛保证,特别是我们证明了在度规亚正则情况下的线性收敛,这适用于强凸强凹问题和分段线性二次函数。我们显示了序列的几乎确定收敛和原始 - 对偶间隙和目标值的最优亚线性收敛率,在一般凸凹情况下。数值证据证明了我们的方法在稀疏和密集环境中的最新实证表现,与现有方法相匹配和改进。
Jul, 2020
本论文聚焦于在网络环境下、分布式优化或者具有多时间尺度的系统中连续、可能非自治的 Primal-Dual 动力学,并展示了 Primal-Dual 算法在特定度量意义下确实是严格收缩的情况,以及在不同近似 Primal-Dual 系统中建立稳定性和性能保证的鲁棒性分析。同时,本论文为多时间尺度多层优化系统的性能提供了评估,并利用 Primal-Dual 表示控制系统的自动发电控制来说明其结果。
Mar, 2018