基于Bregman距离的非精确邻近点算法求解拟凸多目标优化问题

An Inexact Proximal Point Method with Bregman Distance for Quasi-Convex Multiobjective Optimization

摘要: 本文针对无约束拟凸多目标优化问题，提出了一种基于Bregman距离的非精确邻近点算法，该算法在正则化项中引入Bregman距离以替代传统欧几里得距离。研究中考虑了该算法的两种误差准则(绝对误差准则和相对误差准则)，并在温和假设条件下建立收敛性理论：当目标函数连续可微时，两种准则下算法生成的序列均收敛到问题的帕累托稳定点；当目标函数真凸且下半连续时，序列收敛到问题的弱帕累托最优点。进一步地，通过引入一个额外的增长条件证明了：若正则化参数有界，采用相对误差准则的算法具有线性收敛速率；若该参数收敛至零，则可实现超线性收敛。

Abstract: This paper proposes an inexact proximal point algorithm based on Bregman distance for solving unconstrained quasi-convex multiobjective optimization problems, where the Bregman distance is employed in the regularization term. Two error criteria (absolute error criterion and relative error criterion) for the algorithm are considered. Under some mild assumptions, it is proven that: when the objective functions are continuously differentiable, the sequences generated by the algorithm under both criteria converge to the Pareto stationary points of the problem; when the objective functions are proper convex and lower semicontinuous, the sequences converge to the weak Pareto optimal points of the problem. Furthermore, by introducing an additional growth condition, it is shown that the convergence rate of the method using the relative error criterion is linear if the regularization parameters are bounded, and superlinear if these parameters converge to zero.

1. 引言

邻近点算法(Proximal Point Method, PPM) [1]通过引入正则化项将复杂原问题转化为一系列易于求解的子问题，在单目标优化问题中展现出卓越的求解能力。随着研究的深入，学者们将邻近点算法扩展至多目标优化领域，提出了标量化邻近点算法(Scalarized Proximal Point Method, SPPM)。该方法通过引入标量化函数将多目标问题转化为单目标问题，从而借助成熟的单目标优化理论进行求解。然而，当目标函数为拟凸且局部Lipschitz连续时，精确求解往往计算成本高昂，甚至不可行。

本文提出一种基于Bregman距离的非精确邻近点算法，用于求解无约束拟凸多目标优化问题。该方法在正则化项中采用Bregman距离替代欧几里得范数，并允许Fréchet$\epsilon$ -次微分的非精确计算。受Rockafellar [2]精度准则的启发，我们提出两种误差准则，并在温和假设下证明：当目标函数真且下半连续时，算法序列收敛于弱帕累托最优点；当目标函数拟凸且Lipschitz连续时，序列收敛于帕累托稳定点。进一步地，在附加增长条件下，我们证明采用相对误差准则的算法具有线性收敛速率，且当正则化参数趋于零时可实现超线性收敛。

2. 预备知识

在本文中，$\langle \cdot ,\cdot \rangle$ 表示$n$ 维实欧几里得空间${ℝ}^n$ 的内积，$\Vert \cdot \Vert$ 表示其对应的范数。设$B\left(x,\epsilon \right)$ 表示以$x$ 为中心、半径$\epsilon >0$ 的闭球，并用$B$ 表示${ℝ}^n$ 的单位闭球。用$\top$ 表示转置符号。$\nabla f\left(x\right)$ 表示$f$ 在$x$ 处的梯度。对任意非空子集$C\subseteq {ℝ}^n$ ，$C$ 的指示函数${\delta }_C(\cdot )$ 定义为：当$x\in C$ 时，${\delta }_C\left(x\right)=0$ ，否则(即$x\notin C$ 时)，${\delta }_C\left(x\right)=+\infty$ 。集合$C$ 是闭集当且仅当${\delta }_C(\cdot )$ 下半连续。

定义2.1 设$f:{ℝ}^n\to \overline{ℝ}=ℝ\cup \left\{+\infty \right\}$ 是真下半连续函数，且$\epsilon$ 是任意非负实数。$f$ 在$x\in \text{dom }f$ 处的Fréchet$\epsilon$ -次微分定义为

${\widehat{\partial }}_{\epsilon }f\left(x\right)=\left\{v\in {ℝ}^n:\underset{\Vert h\Vert \to 0}{\lim \inf }\frac{f\left(y\right)-f\left(x\right)-\langle v,h\rangle }{\Vert h\Vert }\ge -\epsilon \right\}.$

显然，当$\epsilon =0$ 时，Fréchet$\epsilon$ -次微分就退化为Fréchet次微分，记为$\widehat{\partial }f\left(x\right)$ 。根据[3]，我们可以得到这两种次微分之间的如下关系

$v\in {\widehat{\partial }}_{\epsilon }f\left(x\right)\iff v\in \widehat{\partial }\left(f(\cdot )+\epsilon \Vert \cdot -x\Vert \right)\left(x\right).$ (1)

以下结果确保了真函数的极小值点集合非空的充分条件。

命题2.1 [4] 若真函数$f:{ℝ}^n\to \overline{ℝ}$ 在$\overline{x}\in \text{dom }f$处有局部极小值，则$0\in \widehat{\partial }f\left(\overline{x}\right)$ 。

引理2.1 [4] 设$f:{ℝ}^n\to \overline{ℝ}$ 是下半连续且强制的真函数，则其最优值$f^{*}$ 是有限的，且以下集合是非空且紧的。

$\arg {\min }_{x\in {ℝ}^n}f\left(x\right):=\left\{x\in \mathrm{dom}f:f\left(x\right)\le f\left(y\right),\forall y\in \mathrm{dom}f\right\}.$

下面给出Bregman距离的定义并研究其关键性质(参见[5])，这些性质是我们算法的理论基础。

定义2.2 设$\varphi :{ℝ}^n\to \overline{ℝ}$ 在$int\left(\text{dom }\varphi \right)$ 上严格凸且可微。与$\varphi$ 相关联的Bregman距离${\mathcal{D}}_{\varphi }:\text{dom }\varphi \times int\left(\text{dom }\varphi \right)\to ℝ$ 定义为

${\mathcal{D}}_{\varphi }\left(x,y\right):=\varphi \left(x\right)-\varphi \left(y\right)-\langle \nabla \varphi \left(y\right),x-y\rangle .$

Bregman距离不是严格意义上的距离，${\mathcal{D}}_{\varphi }\left(x,y\right)\ge 0$ ，当且仅当$x=y$ 时等号成立。此外，一般来说它既不对称，也不满足三角不等式。当$\varphi (\cdot )=\frac{1}{2}{\Vert \cdot \Vert }^2$ 时，${\mathcal{D}}_{\varphi }\left(\cdot ,\cdot \right)$ 就退化为半欧几里得距离的平方。

引理2.2 [6]设$\varphi :{ℝ}^n\to \overline{ℝ}$ 是真闭严格凸函数，在点$a,b,c,d\in {ℝ}^n$ 处有限，且在$a,b\in {ℝ}^n$ 处可微，则有

$\langle \nabla \varphi \left(a\right)-\nabla \varphi \left(b\right),c-d\rangle ={\mathcal{D}}_{\varphi }\left(c,b\right)+{\mathcal{D}}_{\varphi }\left(d,a\right)-{\mathcal{D}}_{\varphi }\left(c,a\right)-{\mathcal{D}}_{\varphi }\left(d,b\right).$ (2)

为确保算法的良定性，对$\varphi$ 做如下假设。

(A1) $\nabla \varphi$ 局部Lipschitz连续；

(A2) $\varphi$ 是强凸函数。

命题2.2 设${\mathcal{D}}_{\varphi }\left(x,y\right)$ 是满足假设(A1)和(A2)的Bregman距离。则对每个$y\in {ℝ}^n$ ，${\mathcal{D}}_{\varphi }\left(\cdot ,y\right)$ 在$y$ 处是局部Lipschitz连续且强制的。

证明：固定$y\in {ℝ}^n$ 。由假设(A1)，存在$\delta >0$ 和$L^{\prime }>0$ ，使得对任意$x\in B\left(y,\delta \right)$ ，有$\Vert \nabla \varphi \left(x\right)\Vert \le L^{\prime }$ 。由定义2.2知，对任意$x_1,x_2\in B\left(y,\delta \right)$ ，有

$\begin{array}{c}\Vert {\mathcal{D}}_{\varphi }\left(x_1,y\right)-{\mathcal{D}}_{\varphi }\left(x_2,y\right)\Vert =\Vert \varphi \left(x_1\right)-\varphi \left(x_2\right)-\langle \nabla \varphi \left(y\right),x_1-x_2\rangle \Vert \\ =\Vert \langle \nabla \varphi \left(\xi \right),x_1-x_2\rangle -\langle \nabla \varphi \left(y\right),x_1-x_2\rangle \Vert \\ \le \Vert \nabla \varphi \left(\xi \right)-\nabla \varphi \left(y\right)\Vert \Vert x_1-x_2\Vert \\ \le 2L^{\prime }\Vert x_1-x_2\Vert .\end{array}$

所以函数${\mathcal{D}}_{\varphi }\left(\cdot ,y\right)$ 在$y$ 处局部Lipschitz连续。

固定$y\in {ℝ}^n$ 。由假设(A2)，存在$\sigma >0$ ，使得对所有，有：

$\varphi \left(x\right)\ge \varphi \left(y\right)+\langle \nabla \varphi \left(y\right),x-y\rangle +\frac{\sigma }{2}{\Vert x-y\Vert }^2.$

由定义2.2，显然

${\mathcal{D}}_{\varphi }\left(x,y\right)\ge \frac{\sigma }{2}{\Vert x-y\Vert }^2.$ (3)

令$\Vert x\Vert \to +\infty$ 取极限，可得

$\underset{\Vert x\Vert \to +\infty }{\lim }{\mathcal{D}}_{\varphi }\left(x,y\right)\ge \underset{\Vert x\Vert \to +\infty }{\lim }\frac{\sigma }{2}{\Vert x-y\Vert }^2=+\infty .$

因此${\mathcal{D}}_{\varphi }\left(\cdot ,y\right)$ 是强制函数。

在${ℝ}^m$ 中，符号${ℝ}_{+}^m$ 表示非负象限，${ℝ}_{++}^m$ 表示正象限。设$x,y\in {ℝ}^m$ 为两个向量。本文中考虑的偏序关系$\underset{\_}{\prec }(\prec )$ 由${ℝ}_{+}^m\left({ℝ}_{++}^m\right)$ 诱导，定义为：$x\underset{\_}{\prec }y\left(x\prec y\right)\iff y-x\in {ℝ}_{+}^m\left(y-x\in {ℝ}_{++}^m\right)$ 。

本文研究以下无约束多目标优化问题：

${\min }_{x\in {ℝ}^n}F\left(x\right):={\left(f_1\left(x\right),\cdots ,f_m\left(x\right)\right)}^{\top },$ (4)

其中每个目标函数$f_i:{ℝ}^n\to \overline{ℝ}$ 是真拟凸函数，且。如果多目标函数的每个分量函数是拟凸的(或凸的、连续可微的、可微的、连续的、下半连续的)，则称该多目标函数是拟凸的(或凸的、连续可微的、可微的、连续的、下半连续的)。

设$J_F\left(x\right)$ 表示$F$ 在$x$ 处的雅可比矩阵，即$J_F\left(x\right)$ 是${ℝ}^{m\times n}$ 中的一个矩阵，其元素${\left(J_F\left(x\right)\right)}_{ij}=\frac{\partial f_i\left(x\right)}{\partial x_j}$ ，其中$i=1,\cdots ,m$ ，$j=1,\cdots ,n$ 。我们可以将其表示为：$J_F\left(x\right)={\left(\nabla f_1\left(x\right),\cdots ,\nabla f_m\left(x\right)\right)}^{\top }$ 。若多目标函数$F:{ℝ}^n\to {ℝ}^m$ 是可微的，且对任意$x,y\in {ℝ}^n$ ，都满足以下条件：

$J_F\left(x\right)\left(y-x\right)\nprec 0\Rightarrow F\left(y\right)\nprec F\left(x\right),$

则称$F$ 是伪凸的。

注2.1 上述伪凸向量值函数的定义可参考[7]。若$F$ 是按分量伪凸的，那么$F$ 是伪凸的，反之不成立。此外，伪凸函数是拟凸函数(参见[8])。

定义2.3 决策向量$x^{*}\in {ℝ}^n$ 是

1) 问题(4)的帕累托最优点，如果不存在$x\in {ℝ}^n$ ，使得$F\left(y\right)\underset{\_}{\prec }F\left(x^{*}\right)$ 且$F\left(x\right)\ne F\left(x^{*}\right)$ ；

2) 问题(4)的弱帕累托最优点，如果不存在$x\in {ℝ}^n$ ，使得$F\left(y\right)\prec F\left(x^{*}\right)$ ；

3) 问题(4)的帕累托稳定点，如果对所有$v\in {ℝ}^n$ ，都有$J_F\left(x^{*}\right)v\cap \left(-{ℝ}_{++}^m\right)=\varnothing$ 。

众所周知，每个帕累托最优点也是弱帕累托最优点，且每个弱帕累托最优点也是帕累托稳定点。此外，当$F$ 是伪凸函数时，问题(4)的帕累托稳定点也是弱帕累托最优点(也可参见[8])。

3. 算法

在本节中，我们针对多目标优化问题(4)提出一种基于Bregman距离的非精确标量化邻近点算法(ISPPMB)，然后给出该算法的一些基本性质，这些性质将在收敛性分析中用到。为此，对问题(4)中的函数$F$ 作如下假设：

(H1) $F\succcurlyeq 0$ ，即对任意$i=1,\cdots ,m$ 和$x\in {ℝ}^n$ ，有$0\underset{\_}{\prec }{f}_i\left(x\right)$ ；

(H2) $F$ 是拟凸的；

(H3) $f_i:{ℝ}^n\to \overline{ℝ}\left(i=1,2,\cdots ,m\right)$ 是真下半连续函数，且$\text{dom }F={\displaystyle \underset{i=1}{\overset{m}{\cap }}\text{dom }}{f}_i\ne \varnothing$ ；

(H4) $\left(F\left(x_0\right)-{ℝ}_{+}^m\right)\cap F\left({ℝ}^n\right)$ 是${ℝ}_{+}^m$ -完备的。即对每个满足$a_0=x_0$ 且对所有$k\in \mathbb{N}$ 都有$F\left(a_{k+1}\right)\underset{\_}{\prec }F\left(a_k\right)$ 的序列$\left\{a_k\right\}\subseteq {ℝ}^n$ ，存在$a\in {ℝ}^n$ ，使得对所有$k\in \mathbb{N}$ ，都有$F\left(a\right)\underset{\_}{\prec }F\left(a_k\right)$ 。

假设(H4)已在诸多关于凸或拟凸向量优化的邻近点算法研究工作中被采用，可参考文献[9]、[10]和[11]。显然，若每个目标函数$f_i\left(x\right)$ 均为强制函数，则水平集${\Omega }_k:=\left\{x\in {ℝ}^n:F\left(x\right)\underset{\_}{\prec }F\left(x_k\right)\right\}$ 为紧集，此时假设(H4)自然成立。

本文所考虑的ISPPMB算法如下。

Algorithm 1. 基于Bregman距离的非精确标量化邻近点算法(ISPPMB)

初始化：设$x_0\in {ℝ}^n$ 为任意初始点。选择满足假设(A1)和(A2)的Bregman函数$\varphi (\cdot )$ 。设置$k:=0$ 。 迭代步骤：给定$x_k$ , 找到$x_{k+1}\in {\Omega }_k$ 和$e_{k+1}\in {ℝ}^n$ 使得：

$e_{k+1}\in {\widehat{\partial }}_{{\epsilon }_k}\left(\langle F(\cdot ),z_k\rangle +{\delta }_{{\Omega }_k}(\cdot )\right)\left(x_{k+1}\right)+{\alpha }_k\left(\nabla \varphi \left(x_{k+1}\right)-\nabla \varphi \left(x_k\right)\right),$ (5) 其中，${\Omega }_k:=\left\{x\in {ℝ}^n:F\left(x\right)\underset{\_}{\prec }F\left(x_k\right)\right\}$ ，${\alpha }_k>0$ ，$\left\{z_k\right\}\subset {ℝ}_{+}^m\backslash \left\{0\right\}$ 且$\Vert z_k\Vert =1$ 。 停止准则：若$x_{k+1}=x_k$ 或$x_{k+1}$ 是帕累托稳定点，则停止。否则，令$k\leftarrow k+1$ 并返回迭代步骤。

命题3.1 设$F:{ℝ}^n\to {ℝ}^m$ 满足假设 (H1)、(H2)和(H3)。那么，ISPPMB算法是良定的。

证明：采用数学归纳法进行证明。对于$k=0$ ，由于$x_0$ 是初始点，结论成立。假设$x_k$ 存在，定义函数${\phi }_k\left(x\right):{ℝ}^n\to \overline{ℝ}$ 如下：

由假设(H1)，$F\succcurlyeq 0$ ，由于$z_k\in {ℝ}_{+}^m\backslash \left\{0\right\}$ 且$\Vert z_k\Vert =1$ ，$\langle F(\cdot ),z_k\rangle$ 有下界，因此函数${\phi }_k$ 是真函数。由假设(H3)可知$\langle F(\cdot ),z_k\rangle$ 下半连续，且由命题2.2可知${\alpha }_k{\mathcal{D}}_{\varphi }\left(x,x_k\right)$ 局部Lipschitz连续。假设(H2)和(H3)意味着${\Omega }_k$ 是闭凸集，因此${\delta }_{{\Omega }_k}(\cdot )$ 凸且下半连续。于是有${\phi }_k$ 下半连续。此外，由命题2.2，可知${\mathcal{D}}_{\varphi }\left(\cdot ,x_k\right)$ 是强制的，那么${\phi }_k$ 也是强制的。因此，${\phi }_k$ 是下半连续且强制的真函数，那么由引理2.1可知，存在$x_{k+1}\in {\Omega }_k$ 是${\phi }_k$ 的极小值点。即通过命题2.1得到$x_{k+1}$ 满足

$\begin{array}{c}0\in \widehat{\partial }{\phi }_k\left(x_{k+1}\right)=\widehat{\partial }\left(\langle F(\cdot ),z_k\rangle +{\delta }_{{\Omega }_k}(\cdot )+{\alpha }_k{\mathcal{D}}_{\varphi }(\cdot ,x_k)\right)\left(x_{k+1}\right)\\ =\widehat{\partial }\left(\langle F(\cdot ),z_k\rangle +{\delta }_{{\Omega }_k}(\cdot )\right)\left(x_{k+1}\right)+{\alpha }_k\left(\nabla \varphi \left(x_{k+1}\right)-\nabla \varphi \left(x_k\right)\right)\\ \subseteq {\widehat{\partial }}_{{ϵ}_k}\left(\langle F(\cdot ),z_k\rangle +{\delta }_{{\Omega }_k}(\cdot )\right)\left(x_{k+1}\right)+{\alpha }_k\left(\nabla \varphi \left(x_{k+1}\right)-\nabla \varphi \left(x_k\right)\right).\end{array}$ (6)

即式(5)在$e_{k+1}=0$ 时成立。因此，ISPPMB算法的迭代步骤是良定的。

从命题3.1的证明中还可以看出，如果对某个$k$ ，有$x_{k+1}=x_k$ ，那么

$0\in \widehat{\partial }\left(\langle F(\cdot ),z_k\rangle +{\delta }_{{\Omega }_k}(\cdot )\right)\left(x_{k+1}\right),$

这意味着$x_{k+1}$ 是优化问题$\min \left\{\langle F(\cdot ),z_k\rangle :x\in {\Omega }_k\right\}$ 的临界点。此外，如果$x_{k+1}$ 是这个优化问题的极小值点，那么可以验证$x_{k+1}$ 是问题(4)的弱帕累托最优点。因此，我们假设对所有$k$ ，都有$x_{k+1}\ne x_k$ ，并且每次迭代的$x_k$ 都不是帕累托稳定点，也就是说，由ISPPMB算法生成的序列$\left\{x_k\right\}$ 是无穷的。

接下来，我们给出Fréchet$\epsilon$ -次微分的有用性质。命题3.2的证明参考[10]。

命题3.2 假设(H2)和(H3)满足。设$\epsilon \in {ℝ}_{+}$ ，$z\in {ℝ}^m\backslash \left\{0\right\}$ ，且$E\subset {ℝ}^n$ 是闭凸集。若$x\in \text{dom }F\cap E$ ，$q\in {\widehat{\partial }}_{\epsilon }\left(\langle F(\cdot ),z\rangle +{\delta }_{\Omega }(\cdot )\right)\left(x\right)$ ，且$F\left(y\right)\underset{\_}{\prec }F\left(x\right)$ (其中$y\in E$ )，则

$\langle q,y-x\rangle \le \epsilon \Vert y-x\Vert .$

定义集合

(7)

结合假设(H1)~(H4)，显然$\Omega$ 是闭凸集，$\Omega \subseteq {\Omega }_k$ 且$\Omega \ne \varnothing$ 。

引理3.1 设$F:{ℝ}^n\to {ℝ}^m$ 为满足(H1)、(H3)和(H4)的函数，$\left\{x_k\right\}$ 是由ISPPMB算法生成的序列。若$\widehat{x}$ 是$\left\{x_k\right\}$ 的一个聚点，则$\widehat{x}\in \Omega$ 。

证明：设$\widehat{x}\in {ℝ}^n$ 是序列$\left\{x_k\right\}$ 的一个聚点，那么存在子序列$\left\{x_{j_k}\right\}\subseteq \left\{x_k\right\}$ ，使得$x_{j_k}\to \widehat{x}$ 。下面将证明$\widehat{x}\in \Omega$ 。

任取$z\in {ℝ}_{+}^m\backslash \left\{0\right\}$ 。由于对每个$k\in \mathbb{N}$ ，都有$x_{k+1}\in {\Omega }_k$ ，由${\Omega }_k$ 的定义可得$F\left(x_k\right)\succcurlyeq F\left(x_{k+1}\right)$ 。于是：

这表明序列$\left\{\langle F\left(x_k\right),z\rangle \right\}$ 是递减的。进一步，由假设(H1)可知，序列$\left\{\langle F\left(x_k\right),z\rangle \right\}$ 有下界。因此，$\left\{\langle F\left(x_k\right),z\rangle \right\}$ 是收敛的，于是：

$\langle F\left(\widehat{x}\right),z\rangle =\underset{k\to +\infty }{\lim }\langle F\left(x_k\right),z\rangle =\underset{k\in \mathbb{N}}{\inf }\left\{\langle F\left(x_k\right),z\rangle \right\}\le \langle F\left(x_k\right),z\rangle .$

由上述不等式可得：

这意味着$F\left(x_k\right)-F\left(\widehat{x}\right)\in {ℝ}_{+}^m$ ，即对所有$k\in \mathbb{N}$ ，有$F\left(\widehat{x}\right)\underset{\_}{\prec }F\left(x_k\right)$ 。结合式(7)可得$\widehat{x}\in \Omega$ 。

4. 收敛性分析

在本节中，通过分别考虑两种误差准则(绝对误差和相对误差)，分析了ISPPMB算法两种变体的收敛性：当$F$ 拟凸且连续可微时，算法生成的序列收敛到问题(4)的帕累托稳定点；而当$F$ 伪凸且连续可微(或真凸且下半连续)时，该序列收敛到问题(4)的弱帕累托最优点。

4.1. 带有绝对误差准则的ISPPMB算法

在本小节中，假设ISPPMB算法生成的误差序列$\left\{e_{k+1}\right\}$ 满足以下估计准则：

$(\text{E}1){\displaystyle \sum _{k=0}^{+\infty }{\delta }_k}<+\infty ,其中{\delta }_k=\max \left\{\frac{\Vert e_{k+1}\Vert }{{\alpha }_k},\frac{{\epsilon }_k}{{\alpha }_k}\right\}.$

引理4.1 设$\left\{x_k\right\}$ 是由ISPPMB算法生成的序列。若假设(H1)~(H4)和(E1)成立，那么对于每个$\widehat{x}\in \Omega$ ，

${\mathcal{D}}_{\varphi }\left(\widehat{x},x_k\right)$ 收敛，且$\left\{x_k\right\}$ 是有界的。此外，$\underset{k\to +\infty }{\lim }{\mathcal{D}}_{\varphi }\left(x_{k+1},x_k\right)=0$ 。

证明：设$\widehat{x}\in \Omega$ 。由(5)可知，存在$q_{k+1}\in {\widehat{\partial }}_{{\epsilon }_k}\left(\langle F(\cdot ),z_k\rangle +{\delta }_{{\Omega }_k}(\cdot )\right)\left(x_{k+1}\right)$ ，使得

$e_{k+1}=q_{k+1}+{\alpha }_k\left(\nabla \varphi \left(x_{k+1}\right)-\nabla \varphi \left(x_k\right)\right).$ (8)

由命题3.2可得

$\langle q_{k+1},\widehat{x}-x_{k+1}\rangle \le {\epsilon }_k\Vert \widehat{x}-x_{k+1}\Vert .$ (9)

在式(2)中取$a=x_k$ ，$b=c=x_{k+1}$ ，$d=x$ ，得到：

(10)

对(8)两端与$x-x_{k+1}$ 作内积后，将(10)代入等式右端第二项，并令$x=\widehat{x}$ ，得到

$\langle e_{k+1},\widehat{x}-x_{k+1}\rangle =\langle q_{k+1},\widehat{x}-x_{k+1}\rangle +{\alpha }_k\left({\mathcal{D}}_{\varphi }\left(\widehat{x},x_k\right)-{\mathcal{D}}_{\varphi }\left(x_{k+1},x_k\right)-{\mathcal{D}}_{\varphi }\left(x,x_{k+1}\right)\right).$

上述等式结合(9)，得到

$\begin{array}{c}{\mathcal{D}}_{\varphi }\left(\widehat{x},x_k\right)={\mathcal{D}}_{\varphi }\left(x_{k+1},x_k\right)+{\mathcal{D}}_{\varphi }\left(\widehat{x},x_{k+1}\right)+\frac{1}{{\alpha }_k}\langle e_{k+1},\widehat{x}-x_{k+1}\rangle -\frac{1}{{\alpha }_k}\langle q_{k+1},\widehat{x}-x_{k+1}\rangle \\ \ge {\mathcal{D}}_{\varphi }\left(x_{k+1},x_k\right)+{\mathcal{D}}_{\varphi }\left(\widehat{x},x_{k+1}\right)-\frac{\Vert e_{k+1}\Vert }{{\alpha }_k}\Vert x_{k+1}-\widehat{x}\Vert -\frac{{\epsilon }_k}{{\alpha }_k}\Vert \widehat{x}-x_{k+1}\Vert \\ \ge {\mathcal{D}}_{\varphi }\left(x_{k+1},x_k\right)+{\mathcal{D}}_{\varphi }\left(\widehat{x},x_{k+1}\right)-2{\delta }_k\Vert x_{k+1}-\widehat{x}\Vert ,\end{array}$ (11)

其中第二个不等式由(E1)中${\delta }_k$ 的定义得到。注意到，对任意$a\in ℝ$ ，有$a\le a^2+\frac{1}{4}$ 。在(11)中令$a=\Vert x_{k+1}-\widehat{x}\Vert$ ，得到

$\begin{array}{c}{\mathcal{D}}_{\varphi }\left(\widehat{x},x_k\right)\ge {\mathcal{D}}_{\varphi }\left(x_{k+1},x_k\right)+{\mathcal{D}}_{\varphi }\left(\widehat{x},x_{k+1}\right)-2{\delta }_k{\Vert x_{k+1}-\widehat{x}\Vert }^2-\frac{1}{2}{\delta }_k\\ \ge {\mathcal{D}}_{\varphi }\left(x_{k+1},x_k\right)+\left(1-\frac{4}{\sigma }{\delta }_k\right){\mathcal{D}}_{\varphi }\left(\widehat{x},x_{k+1}\right)-\frac{1}{2}{\delta }_k.\end{array}$ (12)

其中第二个不等式由(3)得到。由此还可推出

${\mathcal{D}}_{\varphi }\left(\widehat{x},x_{k+1}\right)\le \left(1+\frac{\frac{4}{\sigma }{\delta }_k}{1-\frac{4}{\sigma }{\delta }_k}\right){\mathcal{D}}_{\varphi }\left(\widehat{x},x_k\right)+\frac{{\delta }_k}{2\left(1-\frac{4}{\sigma }{\delta }_k\right)}.$

由于假设(E1)保证了$\underset{k\to +\infty }{\lim }{\delta }_k=0$ ，那么对于固定常数$ϵ\in \left(0,\frac{\sigma }{4}\right)$ ，存在$k_0\in \mathbb{N}$ ，使得对任意$k\ge k_0$ ，有$0<\frac{1-4ϵ}{\sigma }<\frac{1-4{\delta }_k}{\sigma }<1$ ，进而$\frac{4{\delta }_k/\sigma }{1-4{\delta }_k/\sigma }<\frac{4{\delta }_k/\sigma }{1-4ϵ/\sigma }$ ，$\frac{{\delta }_k}{2\left(1-4{\delta }_k\right)}<\frac{{\delta }_k}{2\left(1-4ϵ/\sigma \right)}$ 。结合(E1)，有

${\displaystyle \sum _{k=1}^{+\infty }\frac{\frac{4}{\sigma }{\delta }_k}{1-\frac{4}{\sigma }{\delta }_k}}<+\infty 且{\displaystyle \sum _{k=k_0}^{+\infty }\frac{{\delta }_k}{2\left(1-\frac{4}{\sigma }{\delta }_k\right)}}<+\infty .$

因此，由[12]可知${\mathcal{D}}_{\varphi }\left(\widehat{x},x_k\right)$ 收敛，因此序列$\left\{x_k\right\}$ 是有界的。

最后，对(12)进行整理，有

${\mathcal{D}}_{\varphi }\left(x_{k+1},x_k\right)\le {\mathcal{D}}_{\varphi }\left(\widehat{x},x_k\right)-{\mathcal{D}}_{\varphi }\left(\widehat{x},x_{k+1}\right)+\frac{4}{\sigma }{\delta }_k{\mathcal{D}}_{\varphi }\left(\widehat{x},x_{k+1}\right)+\frac{1}{2}{\delta }_k.$

考虑到${\mathcal{D}}_{\varphi }\left(\widehat{x},x_k\right)$ 收敛，且$\underset{k\to +\infty }{\lim }{\delta }_k=0$ ，于是可得$\underset{k\to +\infty }{\lim }{\mathcal{D}}_{\varphi }\left(x_{k+1},x_k\right)=0$ 。

命题4.1 若假设(H1)~(H4)和(E1)成立，那么由ISPPMB算法生成的序列$\left\{x_k\right\}$ 收敛到$\Omega$ 中的某个点。

证明：由引理4.1可知，$\left\{x_k\right\}$ 有界，因此存在$\left\{x_k\right\}$ 的聚点$\widehat{x}$ 以及子序列$\left\{x_{j_k}\right\}\subseteq \left\{x_k\right\}$ ，使得$\underset{k\to +\infty }{\lim }{x}_{j_k}=\widehat{x}$ 。根据引理3.1，有$\widehat{x}\in \Omega$ 。然后再次应用引理4.1，可知${\mathcal{D}}_{\varphi }\left(\widehat{x},x_k\right)$ 收敛。因此，结合这一点以及$\underset{k\to +\infty }{\lim }{x}_{j_k}=\widehat{x}$ ，可直接得出$\underset{k\to +\infty }{\lim }{x}_k=\widehat{x}$ 。

接下来，证明当正则化参数$\left\{{\alpha }_k\right\}$ 有界时，由ISPPMB算法生成的序列$\left\{x_k\right\}$ 收敛到问题(4)的帕累托稳定点。为此，我们对$F$ 考虑以下假设：

(H5) $F:{ℝ}^n\to {ℝ}^m$ 是${ℝ}^n$ 上的连续可微函数。

定理4.1 假设(H1)、(H3)、(H4)、(H5)和(E1)成立，且存在正常数$\overline{\alpha }$ ，使得$0<{\alpha }_k\le \overline{\alpha }$ 。那么由ISPPMB算法生成的序列$\left\{x_k\right\}$ 收敛到问题(4)的帕累托稳定点。

证明：显然，假设(H5)比(H3)更强。那么，根据命题4.1，存在$\widehat{x}\in \Omega$ ，使得$\underset{k\to +\infty }{\lim }{x}_k=\widehat{x}$ 。此外，由于序列$\left\{z_k\right\}$ 是有界的，存在子序列$\left\{z_{j_k}\right\}\subseteq \left\{z_k\right\}$ ，使得$\underset{k\to +\infty }{\lim }{z}_{j_k}=\overline{z}$ ，其中$\overline{z}\in {ℝ}_{+}^m\backslash \left\{0\right\}$ 且$\Vert \overline{z}\Vert =1$ 。根据(5)，有

$e_{j_k+1}\in {\widehat{\partial }}_{{\epsilon }_{j_k}}\left(\langle F(\cdot ),z_{j_k}\rangle +{\delta }_{{\Omega }_{j_k}}(\cdot )\right)\left(x_{j_k+1}\right)+{\alpha }_{j_k}\left(\nabla \varphi \left(x_{j_k+1}\right)-\nabla \varphi \left(x_{j_k}\right)\right).$ (13)

由于$F$ 是连续可微的，根据(1)，有

${\widehat{\partial }}_{{\epsilon }_{j_k}}\left(\langle F(\cdot ),z_{j_k}\rangle +{\delta }_{{\Omega }_{j_k}}(\cdot )\right)\left(x_{j_k+1}\right)=\widehat{\partial }\left(\langle F(\cdot ),z_{j_k}\rangle +{\delta }_{{\Omega }_{j_k}}(\cdot )+{\epsilon }_{j_k}\Vert \cdot -x_{j_k+1}\Vert \right)\left(x_{j_k+1}\right)$

$\begin{array}{c}=\nabla \langle F(\cdot ),z_{j_k}\rangle \left(x_{j_k+1}\right)+\partial \left({\delta }_{{\Omega }_{j_k}}(\cdot )+{\epsilon }_{j_k}\Vert \cdot -x_{j_k+1}\Vert \right)\left(x_{j_k+1}\right)\\ ={\displaystyle \sum _{i=1}^m\nabla }{f}_i\left(x_{j_k+1}\right){\left(z_{j_k}\right)}_i+N_{{\Omega }_{j_k}}\left(x_{j_k+1}\right)+{\epsilon }_{j_k}B,\end{array}$

其中第三个等式由[13]以及$\partial \left(\Vert \cdot \Vert \right)\left(0\right)=B$ 成立。将上式应用于(13)，可知存在$v_{j_k}\in N_{{\Omega }_{j_k}}\left(x_{j_k+1}\right)$ 和$h_{j_k}\in B$ ，使得

$e_{j_k+1}={\displaystyle \sum _{i=1}^m\nabla }{f}_i\left(x_{j_k+1}\right){\left(z_{j_k}\right)}_i+v_{j_k}+{\epsilon }_{j_k}{h}_{j_k}+{\alpha }_{j_k}\left(\nabla \varphi \left(x_{j_k+1}\right)-\nabla \varphi \left(x_{j_k}\right)\right).$ (14)

由于$v_{j_k}\in N_{{\Omega }_{j_k}}\left(x_{j_k+1}\right)$ ，有

(15)

取$\overline{x}\in \Omega$ 。显然，$\overline{x}\in {\Omega }_{j_k}$ 。将式(14)两端同时与$\overline{x}-x_{j_k+1}$ 作内积

$\begin{array}{c}\langle e_{j_k+1},\overline{x}-x_{j_k+1}\rangle =\langle {\displaystyle \sum _{i=1}^m\nabla }{f}_i\left(x_{j_k+1}\right){\left(z_{j_k}\right)}_i,\overline{x}-x_{j_k+1}\rangle +\langle v_{j_k},\overline{x}-x_{j_k+1}\rangle \\ +\langle {\epsilon }_{j_k}{h}_{j_k},\overline{x}-x_{j_k+1}\rangle +{\alpha }_{j_k}\langle \nabla \varphi \left(x_{j_k+1}\right)-\nabla \varphi \left(x_{j_k}\right),\overline{x}-x_{j_k+1}\rangle .\end{array}$

在(10)和(15)中令$x=\overline{x}$ 并带入上式，同时注意到(E1)中${\delta }_k$ 的定义以及$0<{\alpha }_k\le \overline{\alpha }$ ，可得

$\begin{array}{c}0\le \langle {\displaystyle \sum _{i=1}^m\nabla }{f}_i\left(x_{j_k+1}\right){\left(z_{j_k}\right)}_i,\overline{x}-x_{j_k+1}\rangle +{\epsilon }_{j_k}\langle h_{j_k},\overline{x}-x_{j_k+1}\rangle \\ +{\alpha }_{j_k}\left({\mathcal{D}}_{\varphi }\left(\overline{x},x_{j_k}\right)-{\mathcal{D}}_{\varphi }\left(x_{j_k+1},x_{j_k}\right)-{\mathcal{D}}_{\varphi }\left(\overline{x},x_{j_k+1}\right)\right)-\langle e_{j_k+1},\overline{x}-x_{j_k+1}\rangle \\ \le \langle {\displaystyle \sum _{i=1}^m\nabla }{f}_i\left(x_{j_k+1}\right){\left(z_{j_k}\right)}_i,\overline{x}-x_{j_k+1}\rangle +{\epsilon }_{j_k}\Vert \overline{x}-x_{j_k+1}\Vert \\ +{\alpha }_{j_k}\left({\mathcal{D}}_{\varphi }\left(\overline{x},x_{j_k}\right)-{\mathcal{D}}_{\varphi }\left(\overline{x},x_{j_k+1}\right)\right)+\Vert e_{j_k+1}\Vert \Vert \overline{x}-x_{j_k+1}\Vert \\ \le \langle {\displaystyle \sum _{i=1}^m\nabla }{f}_i\left(x_{j_k+1}\right){\left(z_{j_k}\right)}_i,\overline{x}-x_{j_k+1}\rangle +2{\alpha }_{j_k}{\delta }_{j_k}\Vert \overline{x}-x_{j_k+1}\Vert +{\alpha }_{j_k}\left({\mathcal{D}}_{\varphi }\left(\overline{x},x_{j_k}\right)-{\mathcal{D}}_{\varphi }\left(\overline{x},x_{j_k+1}\right)\right)\\ \le \langle {\displaystyle \sum _{i=1}^m\nabla }{f}_i\left(x_{j_k+1}\right){\left(z_{j_k}\right)}_i,\overline{x}-x_{j_k+1}\rangle +2\sqrt{\frac{2}{\sigma }}\overline{\alpha }{\delta }_{j_k}\sqrt{{\mathcal{D}}_{\varphi }\left(\overline{x},x_{j_k+1}\right)}+\overline{\alpha }\left({\mathcal{D}}_{\varphi }\left(\overline{x},x_{j_k}\right)-{\mathcal{D}}_{\varphi }\left(\overline{x},x_{j_k+1}\right)\right),\end{array}$ (16)

其中，第四个不等式应用了(3)。在(16)中令$k\to +\infty$ ，并应用引理4.1和(E1)，可得

${\displaystyle \sum _{i=1}^m{\overline{z}}_i}\langle \nabla f_i\left(\widehat{x}\right),\overline{x}-\widehat{x}\rangle \ge 0.$ (17)

另一方面，由于$\overline{x}\in \Omega$ ，可得$F\left(\overline{x}\right)\underset{\_}{\prec }\underset{k\to +\infty }{\lim }F\left(x_k\right)=F\left(\widehat{x}\right)$ 。由$F$ 的拟凸性，对每个$i\in \left\{1,2,\cdots ,m\right\}$ ，有$\langle \nabla f_i\left(\widehat{x}\right),\overline{x}-\widehat{x}\rangle \le 0$ (参考[14])。据此以及(17)，同时注意到$\overline{z}\in {ℝ}_{+}^m\backslash \left\{0\right\}$ ，于是有

${\displaystyle \sum _{i=1}^m{\overline{z}}_i}\langle \nabla f_i\left(\widehat{x}\right),\overline{x}-\widehat{x}\rangle =0.$

因此，对任意$\overline{x}\in \Omega$ ，有

(18)

假设$\widehat{x}$ 不是问题(4)的帕累托稳定点。那么存在$v\in {ℝ}^n$ ，使得$J_F\left(\widehat{x}\right)v\in -{ℝ}_{++}^m$ ，即

(19)

所以，由$F$ 的连续可微性，存在$\overline{t}>0$ ，使得

这意味着$\widehat{x}+tv\in \Omega$ 。因此在(18)中取$\overline{x}=\widehat{x}+tv$ ，$t\in \left(0,\overline{\alpha }\right]$ ，对所有满足${\overline{z}}_i>0$ 的$i\in \left\{1,\cdots ,m\right\}$ ，有

$\langle \nabla f_i\left(\widehat{x}\right),\widehat{x}+tv-\widehat{x}\rangle =\langle \nabla f_i\left(\widehat{x}\right),tv\rangle =t\langle \nabla f_i\left(\widehat{x}\right),v\rangle =0,$

进而$\langle \nabla f_i\left(\widehat{x}\right),v\rangle =0$ ，这与(19)矛盾。因此，$\widehat{x}$ 是帕累托稳定点。

推论4.1 假设条件(H1)、(H4)、(H5)和(E1)成立，$F$ 是伪凸的，且存在正常数$\overline{\alpha }$ 使得$0<{\alpha }_k\le \overline{\alpha }$ 。那么由ISPPMB算法生成的序列$\left\{x_k\right\}$ 收敛到问题(4)的弱帕累托最优点。

证明：由注2.1可知，伪凸函数也是拟凸的，并且当$F$ 是伪凸函数时，问题(4)的帕累托稳定点也是它的弱帕累托最优点(见第2节)。因此，结论可直接由定理4.1推出。

4.2. 带有相对误差准则的ISPPMB算法

在本小节中，我们研究ISPPMB算法满足另一种误差准则时的收敛性质：设$\left\{x_{k+1}\right\}$ 和$\left\{e_{k+1}\right\}$ 是由ISPPMB算法生成的序列，且误差序列$\left\{e_{k+1}\right\}$ 满足以下条件：

$\begin{array}{l}\text{(E2)}\frac{{\Vert e_{k+1}\Vert }^2}{{\alpha }_k^2}\le {\eta }_k^2{\mathcal{D}}_{\varphi }\left(x_{k+1},x_k\right);\\ \text{(E2}\text{.1)}\frac{{\epsilon }_k^2}{{\alpha }_k^2}\le {\eta }_k^2{\mathcal{D}}_{\varphi }\left(x_{k+1},x_k\right);\\ \text{(E2}\text{.2)}{\displaystyle \sum _{k=1}^{+\infty }{\eta }_k^2}<+\infty .\end{array}$

引理4.2 设$\left\{x_k\right\}$ 是由ISPPMB算法生成的序列。若假设(H1)~(H4)以及(E2)、(E2.1)、(E2.2)成立，那么存在$k_0\in \mathbb{N}$ ，使得对于所有$k\ge k_0$ 和所有$\widehat{x}\in \Omega$ ，有

${\mathcal{D}}_{\varphi }\left(\widehat{x},x_{k+1}\right)\le \left(1+\frac{8{{\eta }^{\prime }}_k^2}{1-8{{\eta }^{\prime }}_k^2}\right){\mathcal{D}}_{\varphi }\left(\widehat{x},x_k\right)-\frac{1}{2}{\mathcal{D}}_{\varphi }\left(x_{k+1},x_k\right).$ (20)

其中${{\eta }^{\prime }}_k=\frac{{\eta }_k}{\sqrt{\sigma }}$ 。此外，对于所有$\widehat{x}\in \Omega$ ，${\mathcal{D}}_{\varphi }\left(\widehat{x},x_k\right)$ 收敛，$\left\{x_k\right\}$ 是有界的，且$\underset{k\to +\infty }{\lim }{\mathcal{D}}_{\varphi }\left(x_{k+1},x_k\right)=0$ 。

证明：通过使用引理4.1第一部分中直到(11)第一个不等式的证明过程，然后利用条件(E2)、(E2.1)和式(3)，对任意$\widehat{x}\in \Omega$ ，我们有：

$\begin{array}{c}{\mathcal{D}}_{\varphi }\left(\widehat{x},x_k\right)\ge {\mathcal{D}}_{\varphi }\left(x_{k+1},x_k\right)+{\mathcal{D}}_{\varphi }\left(\widehat{x},x_{k+1}\right)-\frac{\Vert e_{k+1}\Vert }{{\alpha }_k}\Vert x_{k+1}-\widehat{x}\Vert -\frac{{\epsilon }_k}{{\alpha }_k}\Vert \widehat{x}-x_{k+1}\Vert \\ \ge {\mathcal{D}}_{\varphi }\left(x_{k+1},x_k\right)+{\mathcal{D}}_{\varphi }\left(\widehat{x},x_{k+1}\right)-2\sqrt{\frac{2}{\sigma }}{\eta }_k\sqrt{{\mathcal{D}}_{\varphi }\left(x_{k+1},x_k\right){\mathcal{D}}_{\varphi }\left(\widehat{x},x_{k+1}\right)}.\end{array}$ (21)

令${{\eta }^{\prime }}_k=\frac{{\eta }_k}{\sqrt{\sigma }}$ ，注意到，对任意$a,b\in ℝ$ ，有$2ab\le a^2+b^2$ 。因此：

$\begin{array}{c}2\sqrt{2}{{\eta }^{\prime }}_k\sqrt{{\mathcal{D}}_{\varphi }\left(x_{k+1},x_k\right){\mathcal{D}}_{\varphi }\left(\widehat{x},x_{k+1}\right)}=\frac{2\sqrt{2}{{\eta }^{\prime }}_k}{2}\cdot 2\frac{1}{\sqrt{2\sqrt{2}{{\eta }^{\prime }}_k}}\sqrt{{\mathcal{D}}_{\varphi }\left(x_{k+1},x_k\right)}\cdot \sqrt{2\sqrt{2}{{\eta }^{\prime }}_k}\sqrt{{\mathcal{D}}_{\varphi }\left(\widehat{x},x_{k+1}\right)}\\ \le \frac{1}{2}{\mathcal{D}}_{\varphi }\left(x_{k+1},x_k\right)+8{{\eta }^{\prime }}_k^2{\mathcal{D}}_{\varphi }\left(\widehat{x},x_{k+1}\right).\end{array}$

将此关系代入(21)并整理各项，可得：

$\left(1-8{{\eta }^{\prime }}_k^2\right){\mathcal{D}}_{\varphi }\left(\widehat{x},x_{k+1}\right)\le {\mathcal{D}}_{\varphi }\left(\widehat{x},x_k\right)-\frac{1}{2}{\mathcal{D}}_{\varphi }\left(x_{k+1},x_k\right).$

由于(E2.2)保证了${{\eta }^{\prime }}_k=\frac{{\eta }_k}{\sqrt{\sigma }}\to 0$ ($\sigma >0$ )，存在$k_0\in \mathbb{N}$ ，使得对任意$k\ge k_0$ ，有$0<1-8{{\eta }^{\prime }}_k^2\le 1$ 。利用上述不等式，有

${\mathcal{D}}_{\varphi }\left(\widehat{x},x_{k+1}\right)\le \left(1+\frac{8{{\eta }^{\prime }}_k^2}{1-8{{\eta }^{\prime }}_k^2}\right){\mathcal{D}}_{\varphi }\left(\widehat{x},x_k\right)-\frac{1}{2}{\mathcal{D}}_{\varphi }\left(x_{k+1},x_k\right).$

因此不等式(20)得证。

显然，由(20)可知，对任意$\widehat{x}\in \Omega$ 和$k\ge k_0$ ，有以下式子成立

${\mathcal{D}}_{\varphi }\left(\widehat{x},x_{k+1}\right)\le \left(1+\frac{8{{\eta }^{\prime }}_k^2}{1-8{{\eta }^{\prime }}_k^2}\right){\mathcal{D}}_{\varphi }\left(\widehat{x},x_k\right).$

由于${{\eta }^{\prime }}_k^2=\frac{{\eta }_k^2}{\sigma }\to 0^{+}$ (由(E2.2))，对于所有$ϵ\in \left(0,\frac{1}{8}\right)$ ，存在$\widetilde{k_0}\in \mathbb{N}$ ，使得对所有$k\ge \widetilde{k_0}$ ，有$0<1-8ϵ<1-8{{\eta }^{\prime }}_k^2<1$ ，因此$\frac{8{{\eta }^{\prime }}_k^2}{1-8{{\eta }^{\prime }}_k^2}<\frac{8{{\eta }^{\prime }}_k^2}{1-8ϵ}$ 。再结合条件(E2.2)，意味着

${\displaystyle \sum _{k=1}^{+\infty }\frac{8{{\eta }^{\prime }}_k^2}{1-8{{\eta }^{\prime }}_k^2}}<+\infty .$

因此，由[12]可知${\mathcal{D}}_{\varphi }\left(\widehat{x},x_k\right)$ 收敛，因此序列$\left\{x_k\right\}$ 是有界的。

最后，再次由关系(20)，我们有

$\frac{1}{2}{\mathcal{D}}_{\varphi }\left(x_{k+1},x_k\right)\le \left(1+\frac{8{{\eta }^{\prime }}_k^2}{1-8{{\eta }^{\prime }}_k^2}\right){\mathcal{D}}_{\varphi }\left(\widehat{x},x_k\right)-{\mathcal{D}}_{\varphi }\left(\widehat{x},x_{k+1}\right).$

对上述不等式两边取极限，并考虑到${\mathcal{D}}_{\varphi }\left(\widehat{x},x_k\right)$ 收敛，且${{\eta }^{\prime }}_k\to 0$ ，于是可得$\underset{k\to +\infty }{\lim }{\mathcal{D}}_{\varphi }\left(x_{k+1},x_k\right)=0$ 。

下面命题4.2的证明与命题4.1类似，在证明过程中我们只需将引理4.2的应用改为引理4.2的应用。

命题4.2 若假设(H1)~(H4)以及(E2)、(E2.1)、(E2.2)成立，那么由ISPPMB算法生成的序列$\left\{x_k\right\}$ 收敛到$\Omega$ 中的某个点。

定理4.2 假设(H1)、(H2)、(H4)、(H5)以及(E2)、(E2.1)、(E2.2)成立，且存在正常数$\overline{\alpha }$ ，使得$0<{\alpha }_k\le \overline{\alpha }$ 。那么由ISPPMB算法生成的序列$\left\{x_k\right\}$ 收敛到问题(4)的帕累托稳定点。

证明：由命题4.2可知，存在$\widehat{x}\in \Omega$ ，使得$\underset{k\to +\infty }{\lim }{x}_k=\widehat{x}$ 。此外，由于序列$\left\{z_k\right\}$ 是有界的，存在子序列$\left\{z_{j_k}\right\}\subseteq \left\{z_k\right\}$ ，使得$\underset{k\to +\infty }{\lim }{z}_{j_k}=\overline{z}$ ，其中$\overline{z}\in {ℝ}_{+}^m\backslash \left\{0\right\}$ 且$\Vert \overline{z}\Vert =1$ 。然后，使用定理4.1中(16)第二个不等式的相同证明过程，对任意$\overline{x}\in \Omega$ ，我们可得：

$\begin{array}{c}0\le \langle {\displaystyle \sum _{i=1}^m\nabla }{f}_i\left(x_{j_k+1}\right){\left(z_{j_k}\right)}_i,\overline{x}-x_{j_k+1}\rangle +{\epsilon }_{j_k}\Vert \overline{x}-x_{j_k+1}\Vert \\ +{\alpha }_{j_k}\left({\mathcal{D}}_{\varphi }\left(\overline{x},x_{j_k}\right)-{\mathcal{D}}_{\varphi }\left(\overline{x},x_{j_k+1}\right)\right)+\Vert e_{j_k+1}\Vert \Vert \overline{x}-x_{j_k+1}\Vert \\ \le \langle {\displaystyle \sum _{i=1}^m\nabla }{f}_i\left(x_{j_k+1}\right){\left(z_{j_k}\right)}_i,\overline{x}-x_{j_k+1}\rangle +2\sqrt{\frac{2}{\sigma }}{\alpha }_{j_k}{\eta }_{j_k}\sqrt{{\mathcal{D}}_{\varphi }\left(x_{j_k+1},x_{j_k}\right){\mathcal{D}}_{\varphi }\left(\overline{x},x_{j_k+1}\right)}\\ +{\alpha }_{j_k}\left({\mathcal{D}}_{\varphi }\left(\overline{x},x_{j_k}\right)-{\mathcal{D}}_{\varphi }\left(\overline{x},x_{j_k+1}\right)\right)\end{array}$

$\begin{array}{c}\le \langle {\displaystyle \sum _{i=1}^m\nabla }{f}_i\left(x_{j_k+1}\right){\left(z_{j_k}\right)}_i,\overline{x}-x_{j_k+1}\rangle +2\sqrt{\frac{2}{\sigma }}\overline{\alpha }{\eta }_{j_k}\sqrt{{\mathcal{D}}_{\varphi }\left(x_{j_k+1},x_{j_k}\right){\mathcal{D}}_{\varphi }\left(\overline{x},x_{j_k+1}\right)}\\ +\overline{\alpha }\left({\mathcal{D}}_{\varphi }\left(\overline{x},x_{j_k}\right)-{\mathcal{D}}_{\varphi }\left(\overline{x},x_{j_k+1}\right)\right),\end{array}$ (22)

其中，第二个不等式应用了条件(E2)、(E2.1)和式(3)，第三个不等式考虑了$0<{\alpha }_k\le \overline{\alpha }$ 。在(22)中令$k\to +\infty$ ，并应用引理4.2和(E2.2)，可得

${\displaystyle \sum _{i=1}^m{\overline{z}}_i}\langle \nabla f_i\left(\widehat{x}\right),\overline{x}-\widehat{x}\rangle \ge 0.$

再次遵循定理4.1中(17)之后的证明过程，于是可得$\widehat{x}$ 是问题(4)的帕累托稳定点。

推论4.2 假设条件(H1)、(H4)、(H5)以及(E2)、(E2.1)、(E2.2)成立，$F$ 是伪凸的，且存在正常数$\overline{\alpha }$ 使得$0<{\alpha }_k\le \overline{\alpha }$ 。那么由ISPPMB算法生成的序列$\left\{x_k\right\}$ 收敛到问题(4)的弱帕累托最优点。

证明：通过采用与推论4.1的证明类似的讨论，可知所需结果可直接由定理4.2得到。

定理4.3 假设条件(H1)、(H3)、(H4)以及(E2)、(E2.1)、(E2.2)成立，$F$ 是凸的，且存在正常数$\overline{\alpha }$ 使得$0<{\alpha }_k\le \overline{\alpha }$ 。那么由ISPPMB算法生成的序列$\left\{x_k\right\}$ 收敛到问题(4)的弱帕累托最优点。

证明：与定理4.2证明的开头类似，我们有$\underset{k\to +\infty }{\lim }{x}_k=\widehat{x}$ (其中$\widehat{x}\in \Omega$ )，且存在子序列$\left\{z_{j_k}\right\}\subseteq \left\{z_k\right\}$ ，使得$\underset{k\to +\infty }{\lim }{z}_{j_k}=\overline{z}$ (其中$\overline{z}\in {ℝ}^m\backslash \left\{0\right\}$ 且$\Vert \overline{z}\Vert =1$ )。

注意到式(5)，有

$e_{j_k+1}=q_{j_k+1}+{\alpha }_{j_k}\left(\nabla \varphi \left(x_{j_k+1}\right)-\nabla \varphi \left(x_{j_k}\right)\right),$ (23)

其中$q_{j_k+1}\in {\widehat{\partial }}_{{\epsilon }_{j_k}}\left(\langle F(\cdot ),z_{j_k}\rangle +{\delta }_{{\Omega }_{j_k}}(\cdot )\right)\left(x_{j_k+1}\right)$ 。由于$F$ 是凸的，可得

$\begin{array}{c}{q}_{j_k+1}\in {\widehat{\partial }}_{{\epsilon }_{j_k}}\left(\langle F(\cdot ),z_{j_k}\rangle +{\delta }_{{\Omega }_{j_k}}(\cdot )\right)\left(x_{j_k+1}\right)\\ =\partial \left(\langle F(\cdot ),z_{j_k}\rangle +{\delta }_{{\Omega }_{j_k}}(\cdot )+{\epsilon }_{j_k}\Vert \cdot -x_{j_k+1}\Vert \right)\left(x_{j_k+1}\right).\end{array}$

然后，根据凸函数的次梯度不等式，对所有$x\in {\Omega }_{j_k}$ ，有

$\langle F\left(x\right)-F\left(x_{j_k+1}\right),z_{j_k}\rangle \ge \langle q_{j_k+1},x-x_{j_k+1}\rangle -{\epsilon }_{j_k}\Vert x-x_{j_k+1}\Vert .$ (24)

对式(23)两端与$x-x_{j_k+1}$ 做内积，容易验证对任意$x\in {ℝ}^n$ ，

$\begin{array}{c}\langle q_{j_k+1},x-x_{j_k+1}\rangle =\langle e_{j_k+1},x-x_{j_k+1}\rangle -{\alpha }_{j_k}\langle \nabla \varphi \left(x_{j_k+1}\right)-\nabla \varphi \left(x_{j_k}\right),x-x_{j_k+1}\rangle \\ \ge \langle e_{j_k+1},x-x_{j_k+1}\rangle -{\alpha }_{j_k}\left({\mathcal{D}}_{\varphi }\left(x,x_{j_k}\right)-{\mathcal{D}}_{\varphi }\left(x_{j_k+1},x_{j_k}\right)-{\mathcal{D}}_{\varphi }(x,x_{j_k+1})\right)\\ \ge -\Vert e_{j_k+1}\Vert \Vert x-x_{j_k+1}\Vert -{\alpha }_{j_k}\left({\mathcal{D}}_{\varphi }\left(x,x_{j_k}\right)-{\mathcal{D}}_{\varphi }\left(x,x_{j_k+1}\right)\right),\end{array}$

其中第二个不等式由(10)得到。将此关系代入式(24)，并考虑条件(E2)、(E2.1)、(3)以及关于参数$\left\{{\alpha }_k\right\}$ 的有界性假设，我们可得对所有$x\in {\Omega }_{j_k}$ ，

$\begin{array}{c}\langle F\left(x\right)-F\left(x_{j_k+1}\right),z_{j_k}\rangle \ge -\Vert e_{j_k+1}\Vert \Vert x-x_{j_k+1}\Vert -{\alpha }_{j_k}\left({\mathcal{D}}_{\varphi }\left(x,x_{j_k}\right)-{\mathcal{D}}_{\varphi }\left(x,x_{j_k+1}\right)\right)-{\epsilon }_{j_k}\Vert x-x_{j_k+1}\Vert \\ \ge -{\alpha }_{j_k}\left({\mathcal{D}}_{\varphi }\left(x,x_{j_k}\right)-{\mathcal{D}}_{\varphi }\left(x,x_{j_k+1}\right)\right)-2{\alpha }_{j_k}{\eta }_{j_k}\Vert x_{j_k}-x_{j_k+1}\Vert \Vert x-x_{j_k+1}\Vert \\ \ge -\overline{\alpha }\left({\mathcal{D}}_{\varphi }\left(x,x_{j_k}\right)-{\mathcal{D}}_{\varphi }\left(x,x_{j_k+1}\right)\right)-\frac{4}{\sigma }\overline{\alpha }{\eta }_{j_k}\sqrt{{\mathcal{D}}_{\varphi }\left(x_{j_k+1},x_{j_k}\right){\mathcal{D}}_{\varphi }\left(x,x_{j_k}\right)},\end{array}$ (25)

假设$\widehat{x}$ 不是问题(4)的弱帕累托最优点。那么，存在$\tilde{x}\in {ℝ}^n$ 使得$F\left(\tilde{x}\right)\prec F\left(\widehat{x}\right)$ ，这意味着$\tilde{x}\in \Omega$ ，因此$\tilde{x}\in {\Omega }_{j_k}$ 。将$x=\tilde{x}$ 代入式(25)，同时利用引理4.2和条件(E2.2)，令$k\to +\infty$ 可得

$\langle F\left(\tilde{x}\right)-F\left(\widehat{x}\right),\overline{z}\rangle \ge 0.$ (26)

然而，由$\overline{z}\in {ℝ}^m\backslash \left\{0\right\}$ 且$F\left(\tilde{x}\right)\prec F\left(\widehat{x}\right)$ ，可得$\langle F\left(\tilde{x}\right)-F\left(\widehat{x}\right),\overline{z}\rangle <0$ ，这与式(26)矛盾。因此，$\widehat{x}$ 是问题(4)的弱帕累托最优点。

注2.1 为了实现带有相对误差准则的ISPPMB算法，我们需要使用一些迭代算法来求解一个隐式包含问题，并验证条件(E2)、(E2.1)和(E2.2)是否满足(参见[9])。我们使用以下步骤来找到满足条件(5)、(E2)、(E2.1)和(E2.2)的$x_{k+1}$ 和$e_{k+1}$ 。

1) 选择序列$\left\{{\alpha }_k\right\}$ 和$\left\{{\eta }_k\right\}$ ，使得对于某个正实数$\overline{\alpha }$ ，有$0<{\alpha }_k\le \overline{\alpha }$ ，且${\displaystyle \sum _{k=0}^{+\infty }{\eta }_k^2}<+\infty$ 。此外，定义序列$\left\{z_k\right\}$ ，使得对于所有$k=0,1,\cdots$ ，都有$\Vert z_k\Vert =1$ 。

2) 寻找$x^{k+1}$ 。使用数值方法(例如，使用MATLAB软件工具中的fmincon或patternsearch函数)来找到问题的稳定点的近似点$x^{k+1}\in {\Omega }_k$ ，该问题为

$\min \left\{\langle F(\cdot ),z_k\rangle +{\alpha }_k{D}_{\varphi }\left(\cdot ,x_k\right):x\in {\Omega }_k\right\}.$

3) 计算$\partial f_i\left(x_{k+1}\right)$ (对于所有$i=1,\cdots ,m$ )以及$N_{{\Omega }_k}\left(x_{k+1}\right)$ 。注意，如果对于所有$i=1,\cdots ,m$ ，都有$f_i\left(x_{k+1}\right)<f_i\left(x_k\right)$ ，那么$N_{{\Omega }_k}\left(x_{k+1}\right)=0$ 。

4) 计算$E_{k+1}={\alpha }_k{\eta }_k\sqrt{D_{\varphi }\left(x_{k+1},x_k\right)}$ 。

5) 寻找$e_{k+1}$ 。找到$g_k^i\in \partial f_i\left(x_{k+1}\right)$ (对于所有$i=1,\cdots ,m$ )以及$p_k\in N_{{\Omega }_k}\left(x_{k+1}\right)$ ，使得：

$\Vert e_{k+1}\Vert \le E_{k+1},$

其中

$e_{k+1}={\displaystyle \sum _{i=1}^m{z}_k^i}{g}_k^i+{\alpha }_k\left(\nabla \varphi \left(x_{k+1}\right)-\nabla \varphi \left(x_k\right)\right)+p_k,$

上述误差向量的构造可转化为如下线性逆问题：

$Gb\le l,$

其中$G=\left[g_k^1{g}_k^2\cdots g_k^p{p}_k^1{e}^1{p}_k^2{e}^2\cdots p_k^n{e}^n\right]$ ，$e^i=\left(0,0,\cdots ,1,0,\cdots ,0\right)$ 是第$i$ 个位置为1的标准向量，$p_k=\left(p_k^1,\cdots ,p_k^n\right)$ 是未知的$n\times \left(p\times n\right)$ 矩阵，$b=\left(z_k^1,z_k^2,\cdots ,z_k^p,1,1,\cdots ,1\right)\in {ℝ}^{p+n}$ 是已知向量，且$l=\left(\frac{E_{k+1}}{\sqrt{p}}-c_k^1,\frac{E_{k+1}}{\sqrt{p}}-c_k^2,\cdots ,\frac{E_{k+1}}{\sqrt{p}}-c_k^n\right)\in {ℝ}^n$ 和$c_k={\alpha }_k\left(\nabla \varphi \left(x_{k+1}\right)-\nabla \varphi \left(x_k\right)\right)$ 也是已知的。

5. 收敛速度

在本节中，我们旨在估计ISPPMB算法满足相对误差准则时的收敛速率。为此，我们需要额外的假设。定义集合

$Z:=\Omega \cap S,$

其中$S$ 表示问题(4)的帕累托稳定点集。

2022年，Papa Quiroz和Cruzado[9]以及赵晓芃[11]等人在欧氏空间框架下，利用一类增长条件研究了多目标优化问题中非精确邻近点算法的收敛速度。受此启发，本文基于Bregman距离引入如下增长条件，以分析所提出算法ISPPMB的收敛速度：

(H6) 对于$\overline{x}\in Z$ 且$\underset{k\to +\infty }{\lim }{x}_k=\overline{x}$ ，存在$\delta =\delta \left(\overline{x}\right)>0$ 和$\tau =\tau \left(\overline{x}\right)>0$ ，使得对所有$w\in B\left(0,\delta \right)\subset {ℝ}^n$ ，以及所有满足$w\in {\widehat{\partial }}_{{\epsilon }_k}\left(\langle F(\cdot ),z_k\rangle +{\delta }_{{\Omega }_k}(\cdot )\right)\left(x_{k+1}\right)$ 的$x_{k+1}$ ，都有

${\mathcal{D}}_{\varphi }\left(\overline{x},x_{k+1}\right)\le \tau {\Vert w\Vert }^2.$

若对所有$x\in {ℝ}^n$ ，有$\varphi \left(x\right)=\frac{1}{2}{\Vert x\Vert }^2$ ，且

${\widehat{\partial }}_{{\epsilon }_k}\left(\langle F(\cdot ),z_k\rangle +{\delta }_{{\Omega }_k}(\cdot )\right)\left(x_{k+1}\right)=\partial °\left(\langle F(\cdot ),z_k\rangle \right)\left(x^{k+1}\right)+N_{{\Omega }_k}\left(x^{k+1}\right),$

那么假设(H6)就退化为参考文献[9]中所使用的增长条件。

定理5.1 设$\left\{x_k\right\}$ 和$\left\{e_{k+1}\right\}$ 是由ISPPMB算法生成的序列。假设(H1)-(H6)以及(E2)、(E2.1)、(E2.2)成立，且存在正常数$\overline{\alpha }$ ，使得$0<{\alpha }_k\le \overline{\alpha }$ 。那么序列$\left\{x_k\right\}$ 线性收敛到问题(4)的帕累托稳定点。此外，若$\underset{k\to +\infty }{\lim }{\alpha }_k=0$ ，则收敛是超线性的。

证明：根据定理4.2，我们可知$\left\{x_k\right\}$ 收敛到问题(4)的帕累托稳定点，记为$\overline{x}$ 。设$\delta$ 和$\tau$ 是假设(H6)中与$\overline{x}$ 对应的正常数。由(5)，存在$q_{k+1}\in {\widehat{\partial }}_{{\epsilon }_k}\left(\langle F(\cdot ),z_k\rangle +{\delta }_{{\Omega }_k}(\cdot )\right)\left(x_{k+1}\right)$ ，使得

$e_{k+1}=q_{k+1}+{\alpha }_k\left(\nabla \varphi \left(x_{k+1}\right)-\nabla \varphi \left(x_k\right)\right).$

然后，由假设(E2)和$0<{\alpha }_k\le \overline{\alpha }$ 可得：

$\begin{array}{c}\Vert q_{k+1}\Vert \le \Vert e_{k+1}\Vert +{\alpha }_k\Vert \nabla \varphi \left(x_k\right)-\nabla \varphi \left(x_{k+1}\right)\Vert \\ \le \left({\alpha }_k{\eta }_k+{\alpha }_{k}L\sqrt{\frac{2}{\sigma }}\right)\sqrt{{\mathcal{D}}_{\varphi }\left(x_{k+1},x_k\right)}\\ \le \overline{\alpha }\left({\eta }_k+L\sqrt{\frac{2}{\sigma }}\right)\sqrt{{\mathcal{D}}_{\varphi }\left(x_{k+1},x_k\right)},\end{array}$ (27)

其中，第二个不等式应用了假设(A1)。由于${\eta }_k\to 0$ (由(E2.2))且${\mathcal{D}}_{\varphi }\left(x_{k+1},x_k\right)\to 0$ (由引理4.2)，存在$k_1\in \mathbb{N}$ ，使得对任意$k\ge k_1$ ，有$\Vert q_{k+1}\Vert \le \delta$ 。因此，由(H6)和(27)第二个不等式，对任意$k\ge k_1$ ，有

${\mathcal{D}}_{\varphi }\left(\overline{x},x_{k+1}\right)\le \tau {\Vert q_{k+1}\Vert }^2\le \tau {\alpha }_k^2{\left({\eta }_k+L\sqrt{\frac{2}{\sigma }}\right)}^2{\mathcal{D}}_{\varphi }\left(x_{k+1},x_k\right),$

将此与引理4.2中的(20)结合，对于所有$k\ge \max \left\{k_0,k_1\right\}$ ，可得

$\left(1+\frac{1}{2\tau {\alpha }_k^2{\left({\eta }_k+L\sqrt{\frac{2}{\sigma }}\right)}^2}\right){\mathcal{D}}_{\varphi }\left(\overline{x},x_{k+1}\right)\le \left(\frac{1}{1-\frac{8}{\sigma }{\eta }_k^2}\right){\mathcal{D}}_{\varphi }\left(\overline{x},x_k\right),$

即

(28)

其中

${\beta }_k=\frac{1}{1-\frac{8}{\sigma }{\eta }_k^2}\frac{2{\tau }^2{\left({\eta }_k+L\sqrt{\frac{2}{\sigma }}\right)}^2}{2{\tau }^2{\left({\eta }_k+L\sqrt{\frac{2}{\sigma }}\right)}^2+\frac{1}{{\alpha }_k^2}}.$ (29)

由于对所有$k\in \mathbb{N}$ ，有$0<{\alpha }_k\le \overline{\alpha }$ ，我们有

${\beta }_k\le r_k:=\frac{1}{1-\frac{8}{\sigma }{\eta }_k^2}\frac{2{\tau }^2{\left({\eta }_k+L\sqrt{\frac{2}{\sigma }}\right)}^2}{2{\tau }^2{\left({\eta }_k+L\sqrt{\frac{2}{\sigma }}\right)}^2+\frac{1}{{\overline{\alpha }}^2}}.$

显然，由于${\eta }_k\to 0$ ，有

$r_k\to 1+\frac{4{\tau }^2\frac{L^2}{\sigma }}{4{\tau }^2\frac{L^2}{\sigma }+\frac{1}{{\overline{\alpha }}^2}}.$

于是，存在$k_2\in \mathbb{N}$ ，使得对于所有$k\ge k_2$ ，有

${\beta }_k\le r_k<\frac{1}{2}\left(1+\frac{4{\tau }^2\frac{L^2}{\sigma }}{4{\tau }^2\frac{L^2}{\sigma }+\frac{1}{{\overline{\alpha }}^2}}\right)<1.$

这一点，结合(28)，意味着对于所有$k\ge \max \left\{k_0,k_1,k_2\right\}$ ，有

${\mathcal{D}}_{\varphi }\left(\overline{x},x_{k+1}\right)\le \frac{1}{2}\left(1+\frac{4{\tau }^2\frac{L^2}{\sigma }}{4{\tau }^2\frac{L^2}{\sigma }+\frac{1}{{\overline{\alpha }}^2}}\right){\mathcal{D}}_{\varphi }\left(\overline{x},x_k\right),$

即$\left\{x_k\right\}$ 线性收敛到$\overline{x}$ 。

此外，若$\underset{k\to +\infty }{\lim }{\alpha }_k=0$ ，则应用这一点以及$\underset{k\to +\infty }{\lim }{\eta }_k=0$ 在(29)中，可得$\underset{k\to +\infty }{\lim }{\beta }_k=0$ ，这与(28)一起意味着

收敛是超线性的。

结合定理4.3，通过使用与定理5.1类似的证明方法，我们可得到以下结果，因此此处省略证明。

定理5.2 假设(H1)、(H3)、(H4)、(H6)以及(E2)、(E2.1)、(E2.2)成立，$F$ 是凸的，且存在正常数$\overline{\alpha }$ 使得$0<{\alpha }_k\le \overline{\alpha }$ 。那么由算法3.1生成的序列$\left\{x_k\right\}$ 线性收敛到问题(4)的一个弱帕累托最优点。此外，若$\underset{k\to +\infty }{\lim }{\alpha }_k=0$ ，则收敛是超线性的。

6. 总结

本文提出了一种基于Bregman距离的非精确邻近点算法，用于求解无约束拟凸多目标优化问题。该方法引入Fréchet次微分的非精确计算，并结合绝对误差与相对误差两种准则，建立了算法的收敛性理论。结果表明，在适当假设下，算法生成的序列可收敛至帕累托稳定点或弱帕累托最优点。进一步地，在附加增长条件下，证明了相对误差准则下的算法具有线性收敛速率，且当正则化参数趋于零时可实现超线性收敛。

本文的理论分析基于若干关键假设，这些假设在保证理论严密性的同时，也带来了一定的应用局限性。未来的研究方向之一是将帕累托稳定点的概念推广至不可微情形，弱化现有假设以拓展算法的适用性。该工作将进一步丰富拟凸多目标优化的理论体系，并推动其在机器学习等领域的实际应用。