组合问题拉格朗日分解的双重升级框架
本篇论文概述了 Lagrangian relaxation 的技术,介绍了应用该方法的示例算法以及在实现过程中的一些实际问题,并阐明了 Lagrangian relaxation 自然与广泛类的组合算法相结合,用于推理图形模型中的信息,在机器学习领域具有重要实际意义。
Jan, 2014
本文提出了一种原始 - 对偶算法框架,以获得近似解决方案来解决典型的约束凸优化问题,并严格描述了常见结构假设如何影响数值效率。通过选择双重平滑策略和中心点,我们的框架将分解算法、增广 Lagrange 以及交替方向乘子方法作为其特殊情况,并为所有迭代的原始目标残差和原始可行性间隙提供最优收敛速率。
Jun, 2014
通过 Lagrangian 分解,提出了一种新的神经网络验证方法,其在 GPU 上实施时可提供有效的结果,以推测最大化值的边界,并且可以随时停止,可用于推导形式化验证。
Feb, 2020
本文通过提出一种新的分解框架,开发了一类 Jacobi 最佳响应算法,提取出一种动态定价机制,并构建了一个易于特定应用的框架,以优于现有方法的效率解决分布式优化领域的一般非凸总效用函数问题。
Feb, 2013
本文提出了一种基于约束的图匹配方法,能够处理任意阶数、任意势函数的约束,在先前依赖于图结构的分解方法的基础上,通过约束匹配的分解,将图匹配重构为非凸非可分的优化问题,通过交替方向乘子法将其分解为多个较小、易于解决的子问题,从而设计了一个模块化可扩展的框架,并对基于两两约束和高阶约束的两个不同实例进行了研究,实验结果表明,所提出的解决方案在广泛采用的合成和真实示例基准测试中优于现有的两两图匹配方法,并且在高阶设置中具有竞争力。
Nov, 2016
提出了一个在分散优化设置下设计原始方法的框架,该框架适用于局部函数光滑且强凸。通过近似解决由加速增广拉格朗日方法引起的一系列子问题,从而提供了一种演导出几个著名的分散算法的系统方法。当与加速梯度下降相结合时,我们的框架会产生一种新的原始算法,其收敛速度是最优的,并且与最近确定的下限相匹配。我们提供实验结果,证明了拟议算法在高度病态问题上的有效性。
Jun, 2020
合作共进化算法(CC)经过密切结合策略发展为解决大规模全局优化(LSGO)问题的主导方法,而其效率和准确性主要受到分组阶段的影响。本文提出了一种复合可分性分组(CSG)方法,将差分分组(DG)和一般分离分组(GSG)有机整合到问题分解框架中,充分发挥两种方法的优势,以应对高计算复杂度的挑战。CSG 引入了逐步分解框架,通过递归地考虑每个非可分变量与已形成的非可分组之间的相互作用,准确地分解各种问题类型,并使用较少的计算资源。此外,为了增强 CSG 的效率和准确性,我们引入了两种创新方法:一种是乘性可分变量检测方法,另一种是非可分变量分组方法。通过广泛的实验结果表明,与 GSG 和最先进的 DG 系列设计相比,CSG 在更低的计算复杂度下实现了更准确的变量分组。
Mar, 2024
本文介绍了一种新的一阶原始 - 对偶优化框架,利用平滑、加速和同伦等三个经典思想,实现了具有许多广泛应用的凸优化,达到了最佳的收敛效果,针对只包含非平滑函数的情况。同时提供了重新启动策略,大大提高了实际性能,并展示了与增广拉格朗日方法的关系以及如何利用严格收敛率保证来利用强凸目标。最后提供了两个实例验证,表明新的方法可以优于 Chambolle-Pock 和交替方向乘法算法等现有的算法。
Jul, 2015
本文提出一种基于广泛并行的拉格朗日分解方法,用于解决出现在结构化预测中的 0-1 整数线性规划问题。通过使用二叉决策图对子问题进行表示,我们的 GPU 实现改进了 Lange 等人 (2021) 算法的运行时间。
Nov, 2021