辅助子模型问题实现局部最优解
考虑Markov随机场能量最小化问题的线性规划放松,使用平滑技术缓解原问题的非光滑特性,通过基于松弛主次目标函数的对偶差距的自适应缩减方法,提出了一种避免迭代过程中对平滑参数进行人工调整的策略,能够稳定收敛于全局最优解。
Oct, 2012
本文研究两个新的优化问题——在满足子模下限的约束条件下最小化子模函数(子模覆盖)和在满足子模上限的约束条件下最大化子模函数(子模背包)。我们将这些问题表述为约束优化问题,并获得许多有界逼近保证。此外,我们证明了这两个问题的紧密关联,并提供了一种解决一个问题的逼近算法用于获得另一个问题的逼近保证。最后,我们通过实验证明了本文算法的效果和良好的可扩展性。
Nov, 2013
本文提出了一种基于函数提升的新型空间连续凸松弛框架,旨在解决多标签问题,与之前提出的基于函数提升的方法相比,本方法基于分段凸近似,因此需要更少的标签;与最近的基于MRF的方法相比,本方法在一个空间连续设置中进行,并且显示较少的栅格偏差;此外,本文的公式在局部意义上是可能得到的最紧凑的凸松弛,易于实现并允许在GPU上进行高效原始-对偶优化。本方法在几个计算机视觉问题上的效果证明了其有效性。
Dec, 2015
本文介绍了一种弱DR属性,用于给出有关子模性的统一特征,证明了可以在近似保证的同时高效地最大化子模连续函数,为在一般下闭凸约束条件下最大化单调DR-子模连续函数和在盒约束条件下的非单调子模连续函数提供了算法,并探讨了其在不同实际应用中的应用性。
Jun, 2016
该论文提出了基于随机条件梯度方法的优化问题求解算法,用于解决大规模维度下的凸函数、连续子模型等多种问题,并证明了当问题维度高时,该方法较与传统的随机梯度下降法更加稳定,同时计算时间复杂度也得到了有效降低。
Apr, 2018
我们提出了一种新的优化算法,元素级放松标量辅助变量(E-RSAV),它满足无条件能量耗散定律,并展现了修改后能量与原能量之间的改进对齐。我们的算法在凸面设定中具有线性收敛的严格证明。此外,我们还提出了一种简单的加速算法,在一元情况下将线性收敛速度提高到超线性。我们还提议了一种具有斯蒂芬森步长的自适应版本的E-RSAV。通过充分的数值实验验证了我们算法的鲁棒性和快速收敛性。
Sep, 2023
给出了一种用于解决具有弱凸目标和凸线性/非线性约束问题的阻尼近端增广Lagrange方法(DPALM)。通过采用阻尼对偶步长而不是全步长,确保对偶迭代的有界性。如果每个DPALM子问题解到适当的精度,则DPALM可以在O(ε^{-2})的外部迭代中产生一个近似ε-KKT点。此外,我们在目标函数为正则化平滑函数或正则化构成形式的情况下建立了DPALM的整体迭代复杂性。对于前一种情况,通过将加速近端梯度(APG)方法应用于每个DPALM子问题,DPALM实现了复杂度为Τ(ε^{-2.5}),从而产生一个ε-KKT点。对于后一种情况,通过使用APG来解决每个子问题的Moreau包络平滑版本,DPALM的复杂度为O(~ε^{-3}),从而得到一个近似ε-KKT点。我们的外部迭代复杂性和整体复杂性要么推广了现有的无约束或线性约束问题的最佳结果到凸约束问题,要么改进了解决相同结构问题的已知最佳结果。此外,通过在线性/二次约束的非凸二次规划和线性约束的鲁棒非线性最小二乘上进行数值实验,展示了所提出的DPALM方法在效率上超过了几种最先进的方法。
Nov, 2023