应用次梯度方法求解锥优化问题的框架
介绍一种通过使用可行初始点和避免垂直向量投影的简单框架来生成可行迭代序列,并通过每次迭代的线搜索来维护可行性的子梯度方法,避免了传统子梯度法的实用性限制。该算法具有传统方法类似的收敛率,然而误差是相对测量而非绝对测量。
May, 2016
该研究考虑一类具有强凸目标函数和 Lipschitz 连续梯度的无约束优化问题的梯度优化算法的分析和设计,通过将问题制定为鲁棒性分析问题并利用适当的积分二次约束理论进行设计,以提高现有算法的收敛速度和鲁棒性能力,并能够利用目标函数中的附加结构。
May, 2019
本文中我们考虑在闭凸子集上最小化一个非光滑非凸的目标函数 $f (x)$,同时满足附加的非光滑非凸约束 $c (x) = 0$。我们开发了一个统一的框架来发展基于 Lagrangian 的方法,在每次迭代中通过某些子梯度方法对原始变量进行单步更新。这些子梯度方法被 “嵌入” 到我们的框架中,以黑盒更新原始变量的方式加以合并。我们证明了在温和条件下,我们提出的框架继承了这些嵌入子梯度方法的全局收敛性保证。此外,我们证明了我们的框架可以扩展到解决具有期望约束的约束优化问题。基于我们提出的框架,我们展示了一系列现有的随机子梯度方法,包括 proximal SGD、proximal momentum SGD 和 proximal ADAM,可以嵌入到基于 Lagrangian 的方法中。对深度学习任务的初步数值实验表明,我们提出的框架可以为非凸非光滑约束优化问题提供高效的 Lagrangian-based 方法变体,并具有收敛性保证。
Apr, 2024
本文研究了基于次梯度方法的非光滑优化问题,针对具有凸性和弱凸性的目标函数,推导了次梯度方法的收敛性和复杂度界限,证明了步长的选取可以控制其移动轨迹,从而保证算法的收敛性。同时,还将该方法拓展到了截断型、随机型、增量型等非 Lipschitz 函数的问题上。
May, 2023
利用可适应性光滑函数的概念和 Bregman 基础的近端梯度方法,在解决具有复杂目标函数的非凸、非光滑最小化问题时,实现全局收敛。
Jun, 2017
本文研究了解决光滑的非强凸约束优化问题的一些一阶方法的收敛率,提供了一些松弛的强凸条件并证明了它们对于多种一阶方法的线性收敛是足够的,最后证明了所提出的松弛强凸条件涵盖了求解线性系统、线性规划和线性约束凸问题的重要应用。
Apr, 2015
本文提出了解决在信号处理、机器学习、统计学等领域中经常出现的各种凸锥问题的通用框架,包括决定问题的锥形公式,确定其对偶,应用平滑,使用一阶最优方法解决,以及一些新技术贡献,如新的连续方案、控制步长的新方法等,并通过数值实验表明该框架具有稳定和计算高效的特点,并发行了一套软件。
Sep, 2010
该篇研究综述了一系列针对包含大量凸组件函数的最小化求和问题的方法,这些方法通常采用单个组件的迭代,并分析了这些方法的收敛性和收敛速度。 此外,作者还探讨了这些方法在推理 / 机器学习、信号处理和大规模 / 分布式优化等方面的应用。
Jul, 2015
我们提出了一个基于条件梯度法的复合凸优化模板,该方法结合了平滑和同伦技术,在 CGM 框架下实现了最优的 O(1 /sqrt(k))收敛速度,并证明了在线性子问题具有加法或乘法误差时,同样的速率保持不变。此外,与相关工作相比,我们能够描述非平滑项为指示函数时的收敛性质。
Apr, 2018
该论文研究了由凸或 Prox-regular 函数组成的函数与光滑向量函数的复合函数最小化问题,提出了一种基于线性逼近和正则化项的子问题算法框架,并探讨了该子问题的局部解的性质、全局收敛性和含有原问题解的活动流形的识别性质。初步的计算结果具有良好的性能。
Dec, 2008