2025-11-10T02:43:53.338320

Fast Accelerated Proximal Gradient Method with New Extrapolation Term for Multiobjective Optimization

Huang

In this paper, we propose a novel extrapolation coefficient scheme within a new extrapolation term and develop an accelerated proximal gradient algorithm. We establish that the algorithm achieves a sublinear convergence rate. The proposed scheme only requires the Lipschitz constant estimate sequence to satisfy mild initial conditions, under which a key equality property can be derived to support the convergence analysis. Numerical experiments are provided to demonstrate the effectiveness and practical performance of the proposed method.

academic

Fast Accelerated Proximal Gradient Method with New Extrapolation Term for Multiobjective Optimization

基本信息

论文ID: 2507.06737
标题: Fast Accelerated Proximal Gradient Method with New Extrapolation Term for Multiobjective Optimization
作者: Huang Chengzhi
分类: math.OC (Optimization and Control)
发表时间: October 17, 2025
论文链接: https://arxiv.org/abs/2507.06737

摘要

本文提出了一种新的外推系数方案和外推项，并开发了一种加速近似梯度算法。该算法实现了次线性收敛率。所提出的方案仅要求Lipschitz常数估计序列满足温和的初始条件，在此条件下可以导出关键的等式性质来支持收敛性分析。数值实验验证了所提方法的有效性和实际性能。

研究背景与动机

要解决的问题：多目标优化问题，特别是复合无约束多目标优化问题： $\min_{x \in \mathbb{R}^n} F(x) \equiv (f_1(x) + g_1(x), \ldots, f_m(x) + g_m(x))^T$ 其中 $f_i$ 是光滑凸函数， $g_i$ 是凸函数（可能非光滑）。
问题重要性：多目标优化在实际应用中广泛存在，如图像恢复、压缩感知等领域。这类问题通常不存在单一最优解，而是由Pareto最优解组成的解集。
现有方法局限性：
- Tanabe等人将FISTA扩展到多目标优化，实现了 $O(1/k^2)$ 收敛率
- Sonntag等人和Zhang等人的工作存在理论证明不完整的问题，其收敛性分析依赖于辅助函数 $\sigma(z) = \min_{i=1,\ldots,m} F_i(x_k) - F_i(z)$ 的非负性，这一条件难以保证
研究动机：克服现有方法理论分析中的缺陷，提出对Lipschitz常数初始估计要求更温和的方法，并通过关键等式避免对 $\sigma$ 非负性的依赖。

核心贡献

提出新的外推项方案：采用 $y_k = x_k + \frac{k+\alpha-4}{k+\alpha-1}(x_k - x_{k-1})$ 的外推形式，其中 $\alpha \geq 3$
建立温和的初始条件：仅需要Lipschitz常数估计序列满足较弱的初始条件
导出关键等式性质：避免了对辅助函数非负性的依赖，完善了理论分析
证明次线性收敛率：在光滑情况下实现 $O(1/k^2)$ 收敛率，非光滑情况下实现 $O(1/k)$ 收敛率
扩展到非光滑情况：通过光滑化技术处理完全非光滑的多目标优化问题

方法详解

任务定义

考虑复合无约束多目标优化问题(MOP)： $\min_{x \in \mathbb{R}^n} F(x) = (f_1(x) + g_1(x), \ldots, f_m(x) + g_m(x))^T$

其中：

$f_i: \mathbb{R}^n \to \mathbb{R}$ 是连续可微的凸函数
$g_i: \mathbb{R}^n \to \mathbb{R}$ 是凸函数（可能非光滑）
目标是找到弱Pareto最优解

模型架构

光滑情况算法（Algorithm 1）

核心子问题： $\min_{z \in \mathbb{R}^n} \phi_{L(f)}(z; x, y) = \max_{i=1,\ldots,m}[\langle\nabla f_i(y), z-y\rangle + g_i(z) + f_i(y) - F_i(x)] + \frac{L(f)}{2}\|z-y\|^2$

算法步骤：

计算外推点： $y_k = x_k + \frac{k+\alpha-4}{k+\alpha-1}(x_k - x_{k-1})$
求解子问题： $x_{k+1} = p_{s_k}(x_k, y_k)$
更新参数： $s_{k+1} = \eta s_k$ ，其中 $\eta = \frac{(k+\alpha-2)^2}{(k+\alpha-1)(k+\alpha-3)}$

参数条件：

当 $\alpha > 3$ 时： $0 < \frac{\alpha-2}{\alpha-3}s_0 < \frac{1}{L(f)}$
当 $\alpha = 3$ 时： $0 < s_0 < \frac{1}{L(f)}$

非光滑情况算法（Algorithm 2）

通过光滑化函数 $\tilde{f}_i(x, \mu)$ 逼近非光滑函数 $f_i(x)$ ，其中光滑化函数满足：

连续可微性：对固定 $\mu > 0$ ， $\tilde{f}(\cdot, \mu)$ 连续可微
一致性： $\lim_{z \to x, \mu \downarrow 0} \tilde{f}(z, \mu) = f(x)$
梯度一致性： $\{\lim_{z \to x, \mu \downarrow 0} \nabla\tilde{f}(z, \mu)\} \subseteq \partial f(x)$

技术创新点

新的外推系数设计：通过特定的参数更新方式 $\eta = \frac{(k+\alpha-2)^2}{(k+\alpha-1)(k+\alpha-3)}$ 确保 $s_k < \frac{1}{L(f)}$ 恒成立
关键等式导出：通过巧妙的代数操作和参数选择，避免了对 $\sigma_k(z)$ 非负性的依赖
统一框架：当 $\alpha = 3$ 时退化为已有方法，但提供了更完整的理论分析

实验设置

数据集

论文提到了三个三目标优化问题的数值实验：

BK1&ℓ1问题
JOS1&ℓ1问题
SP1&ℓ1问题

评价指标

使用merit函数 $u_0(x) = \sup_{z \in \mathbb{R}^n} \min_{i=1,\ldots,m}[F_i(x) - F_i(z)]$ 评估算法性能，该函数满足：

$u_0(x) \geq 0$ 对所有 $x$ 成立
$x$ 是弱Pareto最优当且仅当 $u_0(x) = 0$

实现细节

停止准则： $\|x_k - x_{k+1}\| < \varepsilon$
对于非光滑情况还需要 $\mu_k < \varepsilon$
参数更新： $\mu_{k+1} = \frac{k+\alpha-2}{k+\alpha-1}\mu_k$ ， $s_{k+1} = \frac{k+\alpha-2}{k+\alpha-3}s_k$