从具有隐式海森阻尼的惯性动力学到加速前向-后向算法
《Communications in Nonlinear Science and Numerical Simulation》:From inertial dynamics with implicit Hessian damping to accelerated forward–backward algorithms
【字体:
大
中
小
】
时间:2026年10月22日
来源:Communications in Nonlinear Science and Numerical Simulation 3.8
编辑推荐:
**摘要**
本文研究具有消失阻尼 α/t 的惯性动力系统,用于最小化凸复合目标函数,其中对光滑部分施加了带有任意时间依赖参数的隐式 Hessian 阻尼机制。我们建立了目标残差沿原始轨迹的 O(1/t2) 收敛速率。在更严格的参数条件下,我们进一步获得了 o(1/t2)
**摘要**
本文研究具有消失阻尼 α/t 的惯性动力系统,用于最小化凸复合目标函数,其中对光滑部分施加了带有任意时间依赖参数的隐式 Hessian 阻尼机制。我们建立了目标残差沿原始轨迹的 O(1/t2) 收敛速率。在更严格的参数条件下,我们进一步获得了 o(1/t2) 的收敛速率以及轨迹向极小化子的收敛性。显式-隐式时间离散化导出了一种加速的前后向算法,其外推点和梯度评估点是分离的,该算法通过将惯性参数分离开来推广了 FISTA。
**引言**
考虑凸复合优化问题:
$$\min_{x \in \mathbb{R}^n} f(x) = g(x) + h(x),$$
其中 g, h 是两个凸函数,且 h 是 L-光滑的,即存在常数 L > 0 使得
$$\|\nabla h(x) - \nabla h(y)\| \leq L\|x - y\|, \quad \forall x, y \in \mathbb{R}^n.$$
在整个论文中,我们用 S 表示问题 (1.1) 的解集,用 min f 表示 (1.1) 的最小值,使得对任意 x* ∈ S 有 min f = f(x*)。我们始终假设 S ≠ ?。
自从 Su 等人 [1] 具有影响力的工作以来,人们已经认识到,用于求解 (1.1) 的 Nesterov 加速梯度方法 [2] 可以通过如下二阶动力系统获得连续时间解释:
$$(AVD_\alpha) \quad \ddot{x}(t) + \frac{\alpha}{t}\dot{x}(t) + \nabla f(x(t)) = 0,$$
参数选择为 α = 3。当 α ≥ 3 时,该动力系统具有衰减速率 f(x(t)) ? min f = O(1/t2) [1],也可以被视为快速迭代收缩/阈值算法(FISTA)[3] 的连续时间对应物,并且 (AVD_α) 的轨迹 x(t) 收敛于 (1.1) 的极小化子 [4], [5]。此外,当 α > 3 时,它实现了改进的速率 f(x(t)) ? min f = o(1/t2),如 [6] 所示。对应的离散 Nesterov 加速前后向算法也收敛于 (1.1) 的极小化子 [4], [7],并具有 o(1/k2) 的收敛速率 [8]。通过在 (AVD_α) 中引入额外的几何 Hessian 驱动阻尼,Attouch 等人 [9], [10] 研究了如下二阶微分方程在各种参数设置下的快速收敛性:
$$(DIN\text{-}AVD)_{\alpha, \beta(t), \gamma(t)}: \quad \ddot{x}(t) + \frac{\alpha}{t}\dot{x}(t) + \beta(t)\nabla^2 f(x(t))\dot{x}(t) + \gamma(t)\nabla f(x(t)) = 0,$$
他们表明 (DIN-AVD)_{α,β(t),γ(t)} 通过考虑目标函数的局部曲率改进了对振荡的控制。Attouch 等人 [10] 和 Shi 等人 [11] 进一步通过 (DIN-AVD)_{α,β(t),γ(t)} 的时间离散化方案提出了新的加速梯度算法,并证明了与相应连续动力学相匹配的快速收敛性质。He 和 Fang [12] 研究了带有次梯度校正的加速前后向算法,该算法由 (DIN-AVD)_{α,β,1+β/t} 的时间离散化导出。对于更一般形式的 Hessian 阻尼动力系统 (DIN-AVD)_{α,β(t),γ(t)} 及其对应的离散算法,我们请参考读者 [13], [14], [15], [16], [17], [18]。
(DIN-AVD)_{α,β(t),γ(t)} 中的显式 Hessian 项在适当的可微性假设下自然形成。Alecsa 等人 [19] 提出了一种避免显式计算 Hessian 的替代方法,通过如下惯性动力系统:
$$\ddot{x}(t) + \frac{\alpha}{t}\dot{x}(t) + \nabla f(x(t) + (\delta + \beta t)\dot{x}(t)) = 0. \tag{1.2}$$
通过对 ?f(·) 应用 Taylor 展开,得到
$$\nabla f(x(t) + (\delta + \beta t)\dot{x}(t)) \approx \nabla f(x(t)) + (\delta + \beta t)\nabla^2 f(x(t))\dot{x}(t).$$
因此,动力系统 (1.2) 与具有显式 Hessian 驱动阻尼的 (DIN-AVD)_{α,β(t),γ(t)} 密切相关。因此,项 ?f(x(t) + (δ + βt)?(t)) 被称为隐式 Hessian 阻尼,它已从连续时间和离散角度进行了广泛研究;参见 [20], [21], [22]。Alecsa 等人 [19] 表明,由 (1.2) 生成的轨迹 x(t) 满足收敛速率
$$f(x(t) + (\delta + \beta t)\dot{x}(t)) - \min f = O(1/t^2),$$
当 α > 3, δ > 0, β ∈ ?,或 α ≥ 3, δ = 0, β ≥ 0 时。此外,他们证明了当 f 光滑且 δ = 0 时,f(x(t)) ? min f = O(1/t2)。通过对动力系统 (1.2) 应用显式离散化方案,他们获得了如下一般惯性梯度算法:
$$\begin{cases} y_k = x_k + \alpha_k(x_k - x_{k-1}), \\ z_k = x_k + \beta_k(x_k - x_{k-1}), \\ x_{k+1} = y_k - s\nabla f(z_k), \end{cases} \tag{1.3}$$
其中 α_k = k/(k+α) 且 β_k = (δk + βk + α)/(k + α)。值得注意的是,算法 (1.3) 允许不同的惯性系数 α_k 和 β_k,并且在适当的参数选择下恢复经典的 Nesterov 加速梯度方法。尽管一些研究在非凸设置下考察了算法 (1.3) 及其一般前后向变体的收敛性质;参见 [23], [24], [25],但具有分离外推点和梯度评估点的复合凸方案的可信分析仍然是一个值得关注的课题。对于 (AVD_α),目标残差是沿原始轨迹 x(t) 直接评估的。对于隐式 Hessian 阻尼动力系统 (1.2),平移轨迹 x(t) + (δ + βt)?(t) 在收敛分析中起着至关重要的作用,而当 δ = 0, β ≥ 0 时,沿原始轨迹的目标估计在 [19] 中获得。这促使我们研究是否可以将隐式 Hessian 校正仅应用于复合目标的光滑部分,同时仍能沿原始轨迹直接控制完整的目标残差。
受这些观察的启发,我们将 (AVD_α) 与隐式 Hessian 阻尼机制相结合,提出如下惯性动力系统用于求解凸问题 (1.1):
$$\ddot{x}(t) + \frac{\alpha}{t}\dot{x}(t) + \nabla g(x(t)) + \nabla h(x(t) + \beta(t)\dot{x}(t)) = 0, \tag{1.4}$$
初始条件为 (x(t?), ?(t?)) = (u?, v?),其中 u?, v? ∈ ??, t? > 0, α > 3,且 β: [t?, +∞) → (0, +∞) 是一个连续函数。这里,我们考虑消失阻尼 α/t 是因为它与 Nesterov 加速方法密切相关;参见 [13], [26], [27], [28], [29], [30]。在下文的连续时间分析中,g 取为可微的并通过经典项 ?g(x(t)) 进入,而隐式 Hessian 校正仅通过 ?h(x(t) + β(t)?(t)) 应用于光滑部分 h。这种非对称处理对于复合结构是自然的:可能不光滑的部分 g 是在离散化后由次微分/近端步隐式处理的组件,而平移梯度评估需要 h 的可微性和 Lipschitz 梯度结构。将平移梯度校正应用于不光滑的 g 通常与激励该算法的近端分裂不兼容。收敛分析沿原始轨迹直接控制完整的目标残差 f(x(t)) ? min f。值得注意的是,当 h(x) = 0 时,动力系统 (1.4) 退化为 (AVD_α);当 g(x) = 0 时,它退化为隐式 Hessian 阻尼动力系统 (1.2)。在 β(t) 的适当条件下,我们将表明由 (1.4) 生成的轨迹 x(t) 同时具有全局收敛性和快速收敛速率。
当 g: ?? → ? ∪ {+∞} 是一个适当的、下半连续的凸函数(可能不可微)时,动力系统 (1.4) 可以自然地推广为如下微分包含:
$$\ddot{x}(t) + \frac{\alpha}{t}\dot{x}(t) + \partial g(x(t)) + \nabla h(x(t) + \beta(t)\dot{x}(t)) \ni 0, \tag{1.5}$$
其中 ?g(x) 表示 g 在 x 处的次微分,定义为
$$\partial g(x) = \{\omega \in \mathbb{R}^n \mid g(y) \geq g(x) + \langle \omega, y - x \rangle, \quad \forall y \in \mathbb{R}^n\}.$$
近年来,通过惯性动力系统的时间离散化设计加速算法在优化领域引起了相当大的关注,参见 [31], [32], [33], [34], [35], [36], [37]。然而,重要的是要强调,并非所有此类系统的离散化方案都必然导致具有可证明收敛速率的数值算法,也并不总是保持底层连续动力学的收敛行为 [38], [39]。这自然提出了以下问题:能否设计一个 (1.5) 的适当离散化方案,使得所得到的算法继承与连续时间系统 (1.4) 一致的收敛性质?在下文中,我们将详细研究这个问题。包含式 (1.5) 用于激励近端离散化;第 2 节中的连续时间收敛定理是针对可微 g 陈述的,而离散分析允许 g 是不光滑的、扩展值的。
对于具有"不光滑 + 光滑"结构的问题 (1.1),我们假设 g(x) 是一个适当的、下半连续的凸函数,而 h(x) 是一个 L-光滑的凸函数。我们采用如下离散方案对包含式 (1.5) 进行离散化。时间步长固定为 s。定义 t_k = ks + (α ? 1)s 且 x_k = x(t_k)。我们将不光滑项隐式处理,在 x_{k+1} 处评估 ?g,将光滑项显式处理,在已知的预外推点 x_k + β_k s(x_k ? x_{k?1}) 处评估 ?h。这种隐式-显式离散化 (1.5) 导出
$$\frac{x_{k+1} - 2x_k + x_{k-1}}{s} + \frac{\alpha(k + \alpha - 1)}{s}(x_k - x_{k-1}) + \partial g(x_{k+1}) + \nabla h(x_k + \beta_k s(x_k - x_{k-1})) \ni 0,$$
这等价于
$$x_{k+1} - \left(x_k + \frac{k-1}{k+\alpha-1}(x_k - x_{k-1})\right) + s\left(\partial g(x_{k+1}) + \nabla h(x_k + \beta_k s(x_k - x_{k-1}))\right) \ni 0. \tag{1.6}$$
回忆 g 的近端算子,参数为 s > 0,定义为
$$\text{Prox}_{s,g}(y) = \arg\min_x \left\{g(x) + \frac{1}{2s}\|x - y\|^2\right\}.$$
用 β_k 替换 β_k s,方程 (1.6) 产生如下加速前后向算法(算法 1)。
在算法 1 中,系数 α_k 确定用于近端步的外推点 y_k,而 β_k 确定梯度评估点 z_k。这种设计将两个算法角色分离开来。由于 α? = 0 且 0 ≤ β? ≤ α?,我们有 β? = 0,因此 y? = z? = x?。每当第 3 节中出现比值 β_k/α_k 时,我们采用约定 β?/α? = 1。由于 y? = z? = x?,此约定使得首次迭代的不匹配项消失。当 β_k = α_k 时,算法 1 退化为经典方案
$$\begin{cases} y_k = x_k + \alpha_k(x_k - x_{k-1}), \\ x_{k+1} = \text{Prox}_{s,g}(y_k - s\nabla h(y_k)), \end{cases} \tag{1.7}$$
这正是一种著名的 FISTA 型算法。(1.7) 在各种 α_k 选择下的收敛性质已在文献中被广泛研究;参见例如 [40], [41], [42], [43]。我们的分析超越了 β_k = α_k 这一选择:下降估计必须保留并控制不匹配项 1 ? β_k/α_k,而 Lyapunov 论证表明,加速的目标收敛、速度衰减、次微分衰减、迭代点收敛以及 o(1/k2) 速率即使在 y_k ≠ z_k 的情况下仍然有效。因此,双参数公式的主要优势在于选择梯度评估点方面的额外灵活性,而非保证在数值性能上统一优于 FISTA。
**我们的贡献。** 我们研究了用于凸复合优化的隐式 Hessian 阻尼惯性动力系统,其中隐式 Hessian 校正仅作用于光滑部分,且控制参数 β(t) 可随时间变化。通过构造适当的 Lyapunov 函数,我们证明了当 β(t) ≤ (α ? 3)/L 时,目标残差具有速率 f(x(t)) ? min f = O(1/t2)。该界直接来源于 Lyapunov 估计中速度耗散系数的符号,并允许 β(t) 保持有界远离零。在更强的一致条件 β(t) ≤ τ < (α ? 3)/L 下,我们建立了轨迹向极小化子的收敛性以及改进的速率 f(x(t)) ? min f = o(1/t2)。隐式-显式离散化导出了一种具有不同外推参数和梯度评估参数的加速前后向方法。所得到的方案将 FISTA 型方法作为 β_k = α_k 的特例,而我们的广义下降不等式和离散 Lyapunov 估计量化了梯度评估点可以偏离外推点多远而不丧失加速速率。
**记号:** 设 ?·, ·? 和 ‖·‖ 分别表示内积和欧几里得范数。对于任何闭集 Ω ? ??,我们定义 dist2(0, Ω) = min_{x ∈ Ω} ‖x‖2。给定函数 g: ?? → ? ∪ {+∞},其定义为 dom(g) = {x ∈ ?? | g(x) < +∞}。若 dom(g) ≠ ?,则称 g 是适当的;若 g(x) ≤ lim inf_{y→x} g(y),则称 g 在 x 处下半连续。
**组织结构:** 在第 2 节中,我们讨论可微连续时间模型的适定性,并建立收敛速率和轨迹收敛性。第 3 节在 α_k 和 β_k 上的显式耦合条件下分析算法 1。第 4 节提供理论结果的数值插图,第 5 节对论文进行总结。辅助结果收集在附录 A 中。
**第 1.4 节 动力系统 (1.4) 的收敛分析**
在本节中,我们研究动力系统 (1.4) 的快速收敛性质。在此之前,我们先讨论由 (1.4) 生成的轨迹的存在性。如果 ?g 是全局 Lipschitz 连续的,那么结合 ?h 的 L-Lipschitz 连续性,与 (1.4) 相关的向量场在各远离 t = 0 的紧致时间区间上关于状态变量全局 Lipschitz 连续。因此,根据 Cauchy-Lipschitz-Picard 定理 [44] 和 [19 中的论证,
**第 2 节 算法 1 的收敛分析**
在本节中,我们证明当惯性参数 α_k 和 β_k 满足适当的不等式时,加速前后向算法保持快速收敛性质,类似于 FISTA 型方法。算法 1 的收敛分析采用 Lyapunov 函数方法,受第 2 节中引入的连续时间惯性动力系统启发。具体而言,该算法可以被解释为连续动力系统的离散化
**数值实验**
图像去模糊是成像和信号处理中的典型逆问题,其中观测图像受到模糊和噪声的退化。为了恢复原始图像,我们考虑基于小波的 ??-正则化模型
$$\min_X F(X) = \|AX - B\|_F^2 + \mu\|WX\|_1.$$
这里,A 表示与标准差为 1.5 的归一化 9 × 9 高斯核的循环卷积,W 是三级正交 Haar 变换。所有小波系数都被惩罚。我们使用 256 × 256 的 Cameraman 图像,灰度
**结论与未来工作**
在本工作中,我们考虑了具有消失阻尼 α/t 的隐式 Hessian 阻尼惯性动力系统,用于凸复合优化问题 (1.1)。通过将隐式 Hessian 校正仅应用于光滑部分,我们建立了沿原始轨迹的衰减速率 f(x(t)) ? min f = O(1/t2)。在更强的参数条件下,我们获得了改进的速率 f(x(t)) ? min f = o(1/t2) 以及轨迹向极小化子的收敛性。隐式-显式离散化导出了一种具有
**CRediT 作者贡献声明**
Xin He:撰写 – 审阅与编辑,撰写 – 原稿撰写,方法学,概念化。Ya-Ping Fang:撰写 – 审阅与编辑,监督,方法学,资金获取。
**利益冲突声明**
作者声明他们没有已知的可能影响本文所报告工作的竞争性财务利益或个人关系。
Xin He | Ya-Ping Fang
中国四川成都,西华大学理学院