西南石油大学理学院，四川 成都

收稿日期：2023年4月28日；录用日期：2023年5月21日；发布日期：2023年5月29日

摘要

本文引入一种新的算法：极大型投影梯度算法，它是将解决带约束向量优化问题的投影梯度算法和极大型非单调线搜索技术相结合的一种算法。下降方向通过由解决单目标规划的投影梯度算法推广到向量优化的投影梯度算法来得到，而在步长选择上采用经典的单调线搜索技术容易陷入局部收敛的困境，与非单调技术结合以后，可以摆脱这一困境。在合适的条件下，证明了算法的全局收敛和线性收敛性。

关键词

向量优化，投影梯度算法，非单调线搜索技术，全局收敛，线性收敛

A Nonmonotone Projected Gradient Algorithm for Solving Vector Optimization Problems

Xue Liu, Liwen Zhou

School of Science, Southwest Petroleum University, Chengdu Sichuan

Received: Apr. 28^th, 2023; accepted: May 21^st, 2023; published: May 29^th, 2023

ABSTRACT

This paper introduces a new algorithm: the max-type projected gradient algorithm, which combines the projected gradient algorithm for solving constrained vector optimization problems with the max-type nonmonotone line search technology. The Descent direction is obtained by extending the projection gradient algorithm for solving single objective programming to the projection gradient algorithm for vector optimization, while the classical monotone line search technology in step size selection is easy to fall into the dilemma of local convergence, which can be overcome by combining with nonmonotone technology. Under milder conditions, the global and linear convergences of the algorithm were demonstrated, and numerical experiments were conducted to verify its effectiveness.

Keywords:Vector Optimization, Projected Gradient Algorithm, Nonmonotone Line Search Technology, Global Convergence, Linear Convergence

Copyright © 2023 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

本文考虑如下约束向量优化问题(constraint vector optimization，简记CVOP)：

$\{\begin{array}{l}\min F\left(x\right),\\ \text{s}\text{.t}.x\in C,\end{array}$

C是 $R^n$ 中的非空闭凸子集， $F:R^n\to R^m$ 是连续可微的，且 $F\left(x\right)=\left(f_1\left(x\right),\cdots ,f_m\left(x\right)\right)$ ， $f_i\left(x\right):R^n\to R$ ， $\forall i\in \left\{1,\cdots ,m\right\}$ ， $F\left(x\right)$ 是连续可微的意味着它的每一个分量 $f_i\left(x\right)$ 都是连续的。这种类型的问题在金融、环境分析和管理学等领域都有所涉及，见文献 [1] [2] [3] 。

在求解向量优化问题的众多方法中，主要分成两类：标量化方法和下降方法。

标量化方法的基础思想是通过特定的参数将向量值问题转化为标量值问题。其中，著名的加权求和方法是通过对各个目标函数进行线性组合来得到一个单目标优化，新问题的最优解亦可看成是原始问题的最优解，如 [4] 。

向量优化的下降方法不需要提前知晓任何的参数信息，而且关于收敛性有理论的证明。它们是从单目标非线性规划的算法中拓展而来的。当向量优化无约束的时候，即如下形式：

$\min F(\; x\; )$

有下面几种方法被提出：

Jörg Fliege和Benar Fux Svaiter [5] 提出解决向量优化的最速下降法，下降方向定义如下：

$v\left(x\right):=\arg \min \left\{\nabla f\left(v\right)+\frac{1}{2}{\Vert v\Vert }^2\right\}$

在解决约束向量优化问题时，目标函数是Lipschitz连续的条件下，证明了该算法收敛到一个满足某些一阶必要条件的点。

Fliege, J.等人 [6] 提出解决向量优化的牛顿法，下降方向定义如下：

$v\left(x\right):=\arg \underset{s\in R^n,j=1,\cdots ,m}{\min \max }\left\{\nabla f_j{\left(x_k\right)}^{\text{T}}s+\frac{1}{2}{s}^{\text{T}}{\nabla }^2{f}_j\left(x_k\right)s\right\}.$

文中也证明了在目标函数满足二阶连续可微的条件下，该算法生成的序列点是局部超线性收敛到最优点的。

对于带约束的向量优化问题，2004年，Graña Drummond和Iusem [7] 提出了解决向量优化的投影梯度算法(projected gradient method，简记为PGM)，下降方向定义如下：

$v\left(x\right):=\arg \underset{v\in C_x}{\min }\left\{{\Vert v\Vert }^2/2+\beta \underset{y\in G}{\max }\left(y^{\text{T}}JF\left(x\right)v\right)\right\}.$

其中， $JF\left(x\right)$ 表示的是F在x处的雅可比矩阵， $C_x=C-x=\left\{z-x:z\in C\right\}$ ， $G=\left\{y\in K^{*}:\Vert y\Vert =1\right\}$ 。上面几种方法可以通过选择适合的初始点来找到帕累托最优点，并且它们都是迭代型的算法，每次迭代的时候选择的下降方向都是通过解决一个目标函数是强凸的单目标优化来得到的，这样保证了下降方向是唯一的。特别地，Graña Drummond和Iusem也就投影梯度算法的两个方面给出了收敛性分析。一个是加上平方和步长和凸假设，他们证明了算法收敛到一个弱帕累托解。另一个则是给定目标函数是凸函数的假设，但是没有额外加步长，此时，他们证明了聚点是驻点。作为一种经典而有效的方法，投影梯度算法被广泛研究和应用在各种多目标规划中。关于固定步长的投影梯度算法，也有一些重要的工作。针对非可微凸向量优化问题，Bello Cruz等人 [8] 提出投影次梯度算法，并且证明了由算法生成的序列的聚点是弱帕累托解。最近，通过使用标量化的方法，Brito等人 [9] 和Bento等人 [10] 使用带权重的次梯度算法来解决非可微凸向量优化问题，并且获得了收敛到帕累托解的结果。虽然上述方法没有使用单调线搜索技术，但是它们依然有着很强的收敛结果。

在迭代过程中，改变步长能否对算法进行改进是一个值得研究的问题。本文受此启发，引入非单调步长来得到非单调投影梯度算法，并在合适的条件下证明算法的有效性。

2. 相关定义和引理

定义2.1 集合C被称为是锥，如果对任意的 $\alpha \in \left(0,+\infty \right)$ 和 $x\in C$ ，都有 $\alpha x\in C$ .进一步，集合C被称为是尖锥，如果它是锥，并且满足 $-C\cap C=\left\{0\right\}$ .

定义2.2 令集合K是非空闭尖凸锥，偏序“ $\prec \left(\underset{\_}{\prec }\right)$ ”的定义如下：

$z\prec \left(\underset{\_}{\prec }\right)z^{\prime }\iff z^{\prime }-z\in K\left(\mathrm{int}K\right).$

定义 2.3 集合 $K^{*}$ 称为集合K的极锥，如果它满足：

$K^{*}=\left\{y\in R^n:\langle y,x\rangle \ge 0,\forall x\in K\right\}.$

定义2.4 设集合C是一个非空的集合。

1) $x^{*}\in C$ 被称为是帕累托最优，如果不存在 $y\in C$ 使得

$F\left(y\right)\underset{\_}{\prec }F\left(x^{*}\right)$ 和 $F\left(y\right)=F\left(x^{*}\right).$

2) $x^{*}\in C$ 被称为是弱帕累托最优，如果不存在 $y\in C$ 使得

$F\left(y\right)\prec F\left(x^{*}\right).$

3) $x^{*}\in C$ 被称为是F的驻点，如果满足

$JF\left(x^{*}\right)\left(C-x^{*}\right)\cap \left(-\mathrm{int}K\right)=\varphi ,$

其中， $JF\left(x^{*}\right)\left(C-x^{*}\right):=\left\{JF\left(x^{*}\right)\left(x-x^{*}\right):x\in C\right\}$ 。

很多情况下，(弱)帕累托解很难被证明，许多学者会考虑证明生成的序列收敛到驻点来取代证明收敛到(弱)帕累托解。根据驻点的定义，我们知道如果 $\bar{x}$ 不是驻点，那么，存在 $x\in C$ 使得 $JF\left(\bar{x}\right)\left(x-\bar{x}\right)\in -\mathrm{int}K$ ，这等价于 $JF\left(\bar{x}\right)\left(x-\bar{x}\right)\prec 0$ ，取 $K=R_{+}^m$ 时，这进一步等价于如下表达式：

${\left(\nabla f_i\left(\bar{x}\right)\right)}^{\text{T}}\left(x-\bar{x}\right)<0,\forall i\in \left\{1,\cdots ,m\right\}.$

又F是连续可微的函数，故

$\underset{\gamma \to 0^{+}}{\lim }\left(f_i\left(\bar{x}+\gamma \left(x-\bar{x}\right)\right)-f_i\left(\bar{x}\right)\right)/\gamma ={\left(\nabla f_i\left(\bar{x}\right)\right)}^{\text{T}}\left(x-\bar{x}\right)<0,$

此式说明 $x-\bar{x}$ 在 $\bar{x}$ 处是一个下降方向，即不是驻点就存在下降方向，反之，不存在下降方向的点就是驻点。

定义2.5 映射F在H上是L-Lipschitz连续映射，当且仅当存在常数 $L>0$ 使得映射F满足

$\Vert F\left(x\right)-F\left(y\right)\Vert \le L\Vert x-y\Vert ,\forall x,y\in H.$

如果 $L=1$ ，则称F是非扩张的；如果 $L\in \left(0,1\right)$ ，则称F是压缩的。

定义2.6 (收敛速度)设序列 $\left\{x_k\right\}$ 是 $R^n$ 中的序列，并且满足依范数收敛到 $x^{*}\in R^n$ ，称序列 $\left\{x_k\right\}$ 具有Q-线性收敛率，如果存在 $\theta \in \left(0,1\right)$ 使得当下标k充分大时，有

$\Vert x_{k+1}-x^{*}\Vert \le \theta \Vert x_k-x^{*}\Vert .$

下面给出一些引理用于后面算法的收敛性证明。

引理 2.7 [11] 令C是一个锥，则对于任意的 $x,y\in C$ ，有 $x+y\in C$ .

引理2.8 [12] 对于问题(CVOP)，如果 $x\in R^n$ 是帕累托最优点，则x也是驻点。

3. 算法及其收敛性

3.1. 算法描述

步骤1初始化：给定初始点 $x_0\in C$ ，参数 $\sigma \in \left(0,1\right)$ ， $\rho >1$ ， $\mu \in \left(0,1\right]$ ， $\epsilon >0$ 以及非负整数M和N，令 $k=0$ 和 $m\left(k\right)=0$ ；

步骤2确定寻找方向：计算

$v\left(x_k\right):=\arg \underset{v\in C_{x_k}}{\min }\left\{\frac{{\Vert v\Vert }^2}{2}+\beta \underset{y\in G}{\max }\left(y^{\text{T}}JF\left(x_k\right)v\right)\right\};$ (3-1)

步骤3停止准则：如果迭代次数 $k>N$ 或者 $\Vert v\left(x_k\right)\Vert <\epsilon$ ，停止；否则，继续步骤4；

步骤4令 $m\left(k\right)=\min \left\{m\left(k-1\right)+1,M\right\}$ 和 $C_k$ ：

$C_{i,k}:=\underset{0\le j\le m\left(k\right)}{\max }{f}_i\left(x_{k-j}\right),i\in \left\{1,\cdots ,m\right\};$ (3-2)

步骤5确定步长：取 ${\gamma }_k=\mu {\rho }^{-h_k}$ ，其中 $h_k$ 是使得下面不等式成立的最小非负整数：

$F\left(x_k+{\gamma }_{k}v\left(x_k\right)\right)\underset{\_}{\prec }{C}_k+\sigma {\gamma }_{k}JF\left(x_k\right)v\left(x_k\right);$ (3-3)

步骤6令 $x_{k+1}=x_k+{\gamma }_{k}v\left(x_k\right),k=k+1$ ，并返回到步骤2。

注3.1：当 $\left\{x_k\right\}$ 是由算法1生成的序列时，由(3-2)可以推导出 $F\left(x_k\right)\underset{\_}{\prec }{C}_k$ 。

首先，定义函数 $\phi :R^m\to R$ 如下：

$\phi \left(x\right):=\underset{y\in G}{\max }\left(y^{\text{T}}x\right).$ (3-4)

结合极锥 $K^{*}$ 和集合G的定义，集合 $-K$ 和 $-\mathrm{int}K$ 可以转化下面两个形式：

$-K=\left\{y\in R^m:\phi \left(y\right)\le 0\right\},$ (3-5)

和

$-\mathrm{int}K=\left\{y\in R^m:\phi \left(y\right)<0\right\}.$ (3-6)

下面一个引理说明函数 $\phi$ 的一些性质。

引理3.1 ( [7] Proposition 2) $\phi$ 的定义如(3-4)所示，下面几个性质成立：

1) 函数 $\phi$ 具有一阶正齐次性，即 $\phi \left(kx\right)=k\phi \left(x\right),\forall x\in R^m,k\ge 0$ ；

2) 对于所有的 $x,z\in R^m$ ， $\phi \left(x+z\right)\le \phi \left(x\right)+\phi \left(z\right)$ 和 $\phi \left(x\right)-\phi \left(z\right)\le \phi \left(x-z\right)$ 都成立；

3) 对于所有的 $x,z\in R^m$ ，若 $x\prec z$ (或者 $x\underset{\_}{\prec }z$ )，则 $\phi \left(x\right)<\phi \left(z\right)$ (或者 $\phi \left(x\right)\le \phi \left(z\right)$ )；

4) 函数 $\phi :R^m\to R$ 是Lipschitz连续的，且Lipschitz常数 $L=1$ 。

其次，将(3-1)中目标函数记为 $\theta :C\to R$ ：

$\theta \left(x\right):=\frac{{\Vert v\left(x\right)\Vert }^2}{2}+\beta \underset{y\in G}{\max }\left(y^{\text{T}}JF\left(x\right)v\left(x\right)\right).$ (3-7)

其中， $v\left(x\right)\in C_x=\left\{z-x|z\in C\right\}$ ，且 $v\left(x\right)$ 是使得 $\theta \left(x\right)$ 取值最小的一个向量。

下面的引理则陈述关于此函数的一些性质，这些性质对于算法的收敛性证明非常有用。

引理3.2 ( [7] Proposition 3) v和 $\theta$ 的定义分别如(3-1)和(3-7)所示，下面几个结论成立：

(1) $\theta \left(x\right)\le 0,\forall x\in C$ ；

(2) 当 $x\in C$ 时，下面几个条件等价：

(a) x不是F的驻点；

(b) $\theta \left(x\right)<0$ ；

(c) $v\left(x\right)\ne 0$ .

注3.2：(1) 由命题3.2(1)和 $\theta$ 的定义知 $\phi \left(JF\left(x\right)v\left(x\right)\right)\le 0$ ，由 $\phi$ 的定义知 $JF\left(x\right)v\left(x\right)\underset{\_}{\prec }0$ ，从而知 $v\left(x\right)$ 是一个下降方向；

(2) 从引理3.2(2)可以推导出 $x\in C$ 是F的驻点 $\iff \theta \left(x\right)=0\iff v\left(x\right)=0$ .

在步骤3的停止准则中，其中一个是要求 $\Vert v\left(x_k\right)\Vert <\epsilon$ 。一般来说，参数 $\epsilon$ 是任意小的，所以从注3.2(2)可知此条件意味着 $x_k$ 是驻点。

命题3.3对于给定的点 $x\in C$ ， $v\left(x\right)$ 定义如(3-1)，则它满足下面两个不等式：

${\Vert v\left(x\right)\Vert }^2\le -2\beta \phi \left(JF\left(x\right)v\left(x\right)\right),$ (3-8)

$\Vert v\left(x\right)\Vert \le 2\beta \Vert JF\left(x\right)\Vert ,\forall i\in \left\{1,\cdots ,m\right\}.$ (3-9)

证明：第一个不等式根据 $\theta \left(x\right)$ 的定义和命题3.2(1)可以得到。再利用 $\phi$ 的定义和柯西-施瓦茨不等式，有

$-2\beta \phi \left(JF\left(x\right)v\left(x\right)\right)\le 2\beta \Vert JF\left(x\right)\Vert \Vert v\left(x\right)\Vert .$

将此与第一个不等式相结合即可得到第二个不等式。

下面的引理给出了函数 $\theta$ 的连续性性质。

引理3.4 ( [7] , Proposition 4) 函数 $\theta$ 在C中是连续的。

下面的引理说明极大型线搜索策略和投影梯度算法结合是可行的。

引理3.5 (1) 算法1是有意义的；

(2) 令 $\left\{x_k\right\}$ 是算法1生成的序列，则 $\left\{x_k\right\}\subseteq C$ 。

证明：(1) 显然函数 $\theta \left(x\right)$ 是一个强凸函数，则下降方向 $v\left(x\right)$ 可以得到且唯一。由注3.1可知(3-3)是有意义的。故结论成立。

(2) 下面用数学归纳法来证明结论。

当下标 $k=0$ 时，由算法1的初始化步骤可知 $x_0\in C$ ，结论成立；

假设当下标 $k=k^{\prime }$ 时， $x_{k^{\prime }}\in C$ ，由下降方向 $v\left(x_k\right)$ 的定义知， $v\left(x_{k^{\prime }}\right)+x_{k^{\prime }}\in C$ ，而

$x_{k^{\prime }+1}=x_{k^{\prime }}+{\gamma }_{k^{\prime }}v\left(x_{k^{\prime }}\right)$ ，

以及 ${\gamma }_{k^{\prime }}\in \left(0,1\right]$ 和C是一个闭凸集合，所以

$x_{k^{\prime }+1}={\gamma }_{k^{\prime }}\left(x_{k^{\prime }}+v\left(x_{k^{\prime }}\right)\right)+\left(1-{\gamma }_{k^{\prime }}\right)x_{k^{\prime }}\in C.$

结论成立。

3.2. 全局收敛

命题3.6 假设F连续可微有下界，序列 $\left\{x_k\right\}$ 是由算法1生成的，则序列 $\left\{C_k\right\}$ 是单调非增的，并且存在极限。

证明：因为 $v\left(x_k\right)$ 是一个下降方向，故 $JF\left(x_k\right)v\left(x_k\right)\underset{\_}{\prec }0$ 对所有的 $k\in N$ 均成立，将其带入到(3-3)中，有 $F\left(x_{k+1}\right)\underset{\_}{\prec }{C}_k$ 。

当序列 $\left\{x_k\right\}$ 是由算法1生成的序列时，根据(3-2)和 $m\left(k+1\right)\le m\left(k\right)+1$ ，对于向量的每一个分量i和迭代次数k，有

$\begin{array}{c}{C}_{i,k+1}=\underset{0\le j\le m\left(k+1\right)}{\max }{f}_i\left(x_{k+1-j}\right)\\ \le \underset{0\le j\le m\left(k\right)+1}{\max }{f}_i\left(x_{k+1-j}\right)\\ =\underset{0\le j\le m\left(k\right)+1}{\max }\left\{C_{i,k},f_i\left(x_{k+1}\right)\right\}=C_{i,k}.\end{array}$

这也就说明了序列 $\left\{C_k\right\}$ 是单调非增的。同时考虑到 $C_k\underset{\_}{\succ }F\left(x_k\right)$ 和F是有下界的，根据单调有界定理知序列 $\left\{C_k\right\}$ 存在极限。证毕。

引理3.7 假设F有下界且连续可微，序列 $\left\{x_k\right\}$ 是由算法1生成的，那么，

$\underset{k\to \infty }{\lim }{\gamma }_k\phi \left(JF\left(x_k\right)v\left(x_k\right)\right)=0.$

证明：对于任意迭代次数k和 $i\in \left\{1,\cdots ,m\right\}$ ，令 $l_i\left(k\right)$ 为使得下面两个条件成立的整数：

$k-m\left(k\right)\le l_i\left(k\right)\le k,$ (3-10)

$C_{i,k}=f_i\left(x_{l_i\left(k\right)}\right).$ (3-11)

利用(3-3)和 $x_k$ 的迭代公式，有

$\begin{array}{c}{C}_{i,k}=f_i\left(x_{l_i\left(k\right)}\right)\\ =f_i\left(x_{l_i\left(k\right)-1}+{\gamma }_{l_i\left(k\right)-1}v\left(x_{l_i\left(k\right)-1}\right)\right)\\ \le C_{i,l_i\left(k\right)-1}+\sigma {\gamma }_{l_i\left(k\right)-1}{\left(\nabla f_i\left(x_{l_i\left(k\right)-1}\right)\right)}^{\text{T}}v\left(x_{l_i\left(k\right)-1}\right).\end{array}$ (3-12)

对于条件(3-10)，可得 $k-m\left(k\right)-1\le l_i\left(k\right)-1\le k-1<k$ ，当k足够大时 $m\left(k\right)$ 取常数，再根据命题3.6，有

$\underset{k\to \infty }{\lim }\left(C_{i,k}-C_{i,l_i\left(k\right)-1}\right)=0.$

又因为 ${\gamma }_{l_i\left(k\right)-1}>0$ 和 $\nabla f_i\left(x_{l_i\left(k\right)-1}\right)v\left(x_{l_i\left(k\right)-1}\right)\le 0$ ，结合(3-12)可得

$\underset{k\to \infty }{\lim }{\gamma }_{l_i\left(k\right)-1}{\left(\nabla f_i\left(x_{l_i\left(k\right)-1}\right)\right)}^{\text{T}}v\left(x_{l_i\left(k\right)-1}\right)=0.$ (3-13)

因为 $i\in \left\{1,\cdots ,m\right\}$ 是任意取的，进一步可得

$\underset{k\to \infty }{\lim }{\gamma }_{l_i\left(k\right)-1}JF\left(x_{l_i\left(k\right)-1}\right)v\left(x_{l_i\left(k\right)-1}\right)=0.$

从而

$\underset{k\to \infty }{\lim }{\gamma }_{l_i\left(k\right)-1}\phi \left(JF\left(x_{l_i\left(k\right)-1}\right)v\left(x_{l_i\left(k\right)-1}\right)\right)=0.$ (3-14)

定义

${\hat{l}}_i\left(k\right):=l_i\left(k+M+2\right).$

显然 ${\left\{{\hat{l}}_i\left(k\right)\right\}}_k\subseteq {\left\{l_i\left(k\right)\right\}}_k$ ，在证明结论之前，先证明下面两个结果：对任意给定的 $j\ge 1$ ，有

$\underset{k\to \infty }{\lim }{\gamma }_{{\hat{l}}_i\left(k\right)-j}\phi \left(JF\left(x_{{\hat{l}}_i\left(k\right)-j}\right)v\left(x_{{\hat{l}}_i\left(k\right)-j}\right)\right)=0,$ (3-15)

$\underset{k\to \infty }{\lim }{C}_{i,k}=\underset{k\to \infty }{\lim }{f}_i\left(x_{{\hat{l}}_i\left(k\right)-j}\right).$ (3-16)

接下来用数学归纳法来证明这两个结果。

当 $j=1$ 时，结合(3-14)与 ${\left\{{\hat{l}}_i\left(k\right)\right\}}_k\subseteq {\left\{l_i\left(k\right)\right\}}_k$ ，可得(3-15)。考虑到(3-9)和 $\left\{x_k\right\}$ 的迭代公式，有

$\Vert x_{{\hat{l}}_i\left(k\right)}-x_{{\hat{l}}_i\left(k\right)-1}\Vert =\Vert {\gamma }_{{\hat{l}}_i\left(k\right)-1}v\left(x_{{\hat{l}}_i\left(k\right)-1}\right)\Vert \le {\Vert -2\beta {\gamma }_{{\hat{l}}_i\left(k\right)-1}^2\phi \left(JF\left(x_{{\hat{l}}_i\left(k\right)-1}\right)v\left(x_{{\hat{l}}_i\left(k\right)-1}\right)\right)\Vert }^{1/2}.$ (3-17)

因为 ${\gamma }_{{\hat{l}}_i\left(k\right)-1}\in \left(0,\mu \right]$ ，在等式两端同时对k取极限，并将(3-15)带入可得

$\underset{k\to \infty }{\lim }\Vert x_{{\hat{l}}_i\left(k\right)}-x_{{\hat{l}}_i\left(k\right)-1}\Vert =0.$

又 $f_i$ 是连续函数，故

$\underset{k\to \infty }{\lim }{f}_i\left(x_{{\hat{l}}_i\left(k\right)-1}\right)=\underset{k\to \infty }{\lim }{f}_i\left(x_{{\hat{l}}_i\left(k\right)}\right)=\underset{x\to \infty }{\lim }{C}_{i,k},$

后一等式的成立利用了 $C_k$ 的定义(3-2)。因此，(3-16)成立。

假设当 $j=\bar{j}$ 时，(3-15)和(3-16)成立。利用(3-3)，有

$f_i\left(x_{{\hat{l}}_i\left(k\right)-\bar{j}}\right)\le C_{i,{\hat{l}}_i\left(k\right)-\bar{j}-1}+\sigma {\gamma }_{{\hat{l}}_i\left(k\right)-\bar{j}-1}{\left(\nabla f_i\left(x_{{\hat{l}}_i\left(k\right)-\bar{j}-1}\right)\right)}^{\text{T}}v\left(x_{{\hat{l}}_i\left(k\right)-\bar{j}-1}\right),$ (3-18)

注意到 $\underset{k\to \infty }{\lim }\left({\hat{l}}_i\left(k\right)-\bar{j}-1\right)=\infty$ 和(3-18)在 $j=\bar{j}$ 时成立，利用命题3.6， $\sigma >0$ ， ${\gamma }_{{\hat{l}}_i\left(k\right)-\bar{j}-1}>0$ 和 ${\left(\nabla f_i\left(x_{{\hat{l}}_i\left(k\right)-\bar{j}-1}\right)\right)}^{\text{T}}v\left(x_{{\hat{l}}_i\left(k\right)-\bar{j}-1}\right)\le 0$ ，由(3-18)可以推导出

$\underset{k\to \infty }{\lim }{\gamma }_{{\hat{l}}_i\left(k\right)-\bar{j}-1}{\left(\nabla f_i\left(x_{{\hat{l}}_i\left(k\right)-\left(\bar{j}+1\right)}\right)\right)}^{\text{T}}v\left(x_{{\hat{l}}_i\left(k\right)-\left(\bar{j}+1\right)}\right)=0.$

由i的任意性有

$\underset{k\to \infty }{\lim }{\gamma }_{{\hat{l}}_i\left(k\right)-\bar{j}-1}JF\left(x_{{\hat{l}}_i\left(k\right)-\left(\bar{j}+1\right)}\right)v\left(x_{{\hat{l}}_i\left(k\right)-\left(\bar{j}+1\right)}\right)=0.$

利用命题3.1，上式可以进一步变为

$\underset{k\to \infty }{\lim }{\gamma }_{{\hat{l}}_i\left(k\right)-\bar{j}-1}\phi \left(JF\left(x_{{\hat{l}}_i\left(k\right)-\left(\bar{j}+1\right)}\right)v\left(x_{{\hat{l}}_i\left(k\right)-\left(\bar{j}+1\right)}\right)\right)=0,$ (3-19)

则(3-15)成立。

根据命题3.3和 $x_k$ 的迭代公式，有

$\begin{array}{c}\Vert x_{{\hat{l}}_i\left(k\right)-\bar{j}}-x_{{\hat{l}}_i\left(k\right)-\left(\bar{j}+1\right)}\Vert =\Vert {\gamma }_{{\hat{l}}_i\left(k\right)-\left(\bar{j}+1\right)}v\left(x_{{\hat{l}}_i\left(k\right)-\left(\bar{j}+1\right)}\right)\Vert \\ \le {\Vert -2\beta {\gamma }_{{\hat{l}}_i\left(k\right)-\left(\bar{j}+1\right)}^2\phi \left(JF\left(x_{{\hat{l}}_i\left(k\right)-\left(\bar{j}+1\right)}\right)v\left(x_{{\hat{l}}_i\left(k\right)-\left(\bar{j}+1\right)}\right)\right)\Vert }^{1/2}.\end{array}$

将(3-19)与上式相结合，可推导出

$\underset{k\to \infty }{\lim }\Vert x_{{\hat{l}}_i\left(k\right)-\bar{j}}-x_{{\hat{l}}_i\left(k\right)-\left(\bar{j}+1\right)}\Vert =0.$

又因为 $f_i$ 是连续函数，故

$\underset{k\to \infty }{\lim }{f}_i\left(x_{{\hat{l}}_i\left(k\right)-\left(\bar{j}+1\right)}\right)=\underset{k\to \infty }{\lim }{f}_i\left(x_{{\hat{l}}_i\left(k\right)-\bar{j}}\right)=\underset{x\to \infty }{\lim }{C}_{i,k}.$

于是，(3-15)和(3-16)对任意给定的 $j\ge 1$ 都成立。

对所有的迭代次数 $k>0$ ，有

$x_{k+1}=x_{{\hat{l}}_i\left(k\right)}-{\displaystyle {\sum }_{j=1}^{{\hat{l}}_i\left(k\right)-k-1}{\gamma }_{{\hat{l}}_i\left(k\right)-j}v}\left(x_{{\hat{l}}_i\left(k\right)-j}\right).$ (3-20)

注意到 ${\hat{l}}_i\left(k\right)-k-1\le M+1$ ，利用命题3.3和式(3-15)、(3-20)，整理有

$\underset{k\to \infty }{\lim }\Vert x_{k+1}-x_{{\hat{l}}_i\left(k\right)}\Vert =0.$

再一次用到 $f_i$ 的连续性，得 ${\lim }_{k\to \infty }{f}_i\left(x_{{\hat{l}}_i\left(k\right)}\right)={\lim }_{k\to \infty }{f}_i\left(x_{k+1}\right)={\lim }_{k\to \infty }{C}_{i,k}$ ，将此带入到不等式(3-3)中即可得到结论。证毕。

定理3.8 假设F是有下界且连续可微的。序列 $\left\{x_k\right\}$ 是算法1生成的序列，如果序列 $\left\{x_k\right\}$ 存在聚点，那么此聚点是F的驻点。

证明：记 $\bar{x}$ 是序列 $\left\{x_k\right\}$ 的聚点，因为 $\left\{x_k\right\}\subseteq C$ 以及集合C是一个闭凸集，故 $\bar{x}\in C$ 。同时，序列 $\left\{x_k\right\}$ 存在一个子序列 ${\left\{x_k\right\}}_{k\in I}$ 收敛到 $\bar{x}$ ，其中 $I\subseteq N$ 是一个指标集。由引理3.7可以得到

$\underset{k\to \infty }{\lim }{\gamma }_k\phi \left(JF\left(x_k\right)v\left(x_k\right)\right)=0.$ (3-21)

此式可以拆解成两种情况：

(1) $\underset{k\to \infty }{\lim }\phi \left(JF\left(x_k\right)v\left(x_k\right)\right)=0$ ；

(2) $\underset{k\to \infty }{\lim }{\gamma }_k=0$ 。

当情况(1)成立时，由引理3.4知 是连续的，则 $\theta \left(\bar{x}\right)=\underset{k\in I,k\to \infty }{\lim }\theta \left(x_k\right)$ 。又

$0\ge \underset{k\to \infty }{\lim }\theta \left(x_k\right)=\underset{k\to \infty }{\lim }\left\{\frac{{\Vert v\left(x_k\right)\Vert }^2}{2}+\beta \phi \left(JF\left(x_k\right)v\left(x_k\right)\right)\right\}=\underset{k\to \infty }{\lim }\frac{{\Vert v\left(x_k\right)\Vert }^2}{2}\ge 0.$

则

$\theta \left(\bar{x}\right)=\underset{k\in I,k\to \infty }{\lim }\theta \left(x_k\right)=0.$

再根据注3.2(2)可知 $\bar{x}$ 是驻点。

当情况(2)成立时，存在一个指标 $\bar{k}$ 使得 ${\gamma }_k<\mu$ 对所有的 $k\ge \bar{k}$ 和 $k\in I$ 成立。 ${\gamma }_k$ 是满足条件(3-3)的步长，故

$F\left(x_k+\rho {\gamma }_{k}v\left(x_k\right)\right)\cancel{\underset{\_}{\prec }}{C}_k+\sigma \rho {\gamma }_{k}JF\left(x_k\right)v\left(x_k\right),$

也就是

$C_k+\sigma \rho {\gamma }_{k}JF\left(x_k\right)v\left(x_k\right)-F\left(x_k+\rho {\gamma }_{k}v\left(x_k\right)\right)\notin K.$ (3-22)

而左边又可以写成如下形式：

$\begin{array}{l}{C}_k+\sigma \rho {\gamma }_{k}JF\left(x_k\right)v\left(x_k\right)-F\left(x_k+\rho {\gamma }_{k}v\left(x_k\right)\right)\\ =\left[C_k-F\left(x_k\right)\right]+\left[F\left(x_k\right)+\sigma \rho {\gamma }_{k}JF\left(x_k\right)v\left(x_k\right)-F\left(x_k+\rho {\gamma }_{k}v\left(x_k\right)\right)\right].\end{array}$ (3-23)

又因为 $F\left(x_k\right)\underset{\_}{\prec }{C}_k$ ，即

$C_k-F\left(x_k\right)\in K,$

而K是一个锥，结合引理2.7可得

$F\left(x_k\right)+\sigma \rho {\gamma }_{k}JF\left(x_k\right)v\left(x_k\right)-F\left(x_k+\rho {\gamma }_{k}v\left(x_k\right)\right)\notin K.$ (3-24)

根据中值定理，可知存在 $u_k=x_k+\frac{{\omega }_k}{\Vert v\left(x_k\right)\Vert }\rho {\gamma }_{k}v\left(x_k\right)\left(\frac{{\omega }_k}{\Vert v\left(x_k\right)\Vert }\in \left[0,1\right]\right)$ 满足

$F\left(x_k\right)-F\left(x_k+\rho {\gamma }_{k}v\left(x_k\right)\right)=-\rho {\gamma }_{k}JF\left(u_k\right)v\left(x_k\right),$

将此带入到(3-24)中，并在两边同时除以 $\rho {\gamma }_k$ ，整理得

$\sigma JF\left(x_k\right)v\left(x_k\right)-JF\left(u_k\right)v\left(x_k\right)\notin K.$ (3-25)

序列 $\left\{\frac{v\left(x_k\right)}{\Vert v\left(x_k\right)\Vert }\right\}$ 是一个有界序列，则该序列存在一个收敛的子序列，即存在指标集 $\bar{K}\subseteq I$ 使得

$\underset{k\in \bar{K},k\to \infty }{\lim }{x}_k=\bar{x},\underset{k\in \bar{K},k\to \infty }{\lim }\frac{v\left(x_k\right)}{\Vert v\left(x_k\right)\Vert }=\bar{v}.$

利用 $\underset{k\to \infty }{\lim }{\gamma }_k=0$ ，有

$\underset{k\in \bar{K},k\to \infty }{\lim }{u}_k=\underset{k\in \bar{K},k\to \infty }{\lim }{x}_k+\underset{k\in \bar{K},k\to \infty }{\lim }\rho {\gamma }_k{\omega }_k\frac{v\left(x_k\right)}{\Vert v\left(x_k\right)\Vert }=\bar{x}.$

在(3-25)两端同时除以 $\Vert v\left(x_k\right)\Vert$ ，并对 $k\in \bar{K}$ 中的k取极限，可得

$\left(\sigma -1\right)JF\left(\bar{x}\right)\bar{v}\notin \mathrm{int}K.$

考虑到 $\sigma \in \left(0,1\right)$ ，故 $JF\left(\bar{x}\right)\bar{v}\notin -\mathrm{int}K$ ，又 $v\left(x_k\right)\ne 0$ 是一个下降方向，故 $JF\left(x_k\right)v\left(x_k\right)\prec 0$ ，即 $JF\left(x_k\right)v\left(x_k\right)\in -\mathrm{int}K$ ，而K是一个闭凸尖锥，可得 $JF\left(\bar{x}\right)\bar{v}=0$ ，从而 $\phi \left(JF\left(\bar{x}\right)\bar{v}\right)=0$ ，再利用 $\theta$ 的定义，有

$0=\beta \phi \left(JF\left(\bar{x}\right)\bar{v}\right)\le \theta \left(\bar{x}\right).$

另一方面，由命题3.2(1)知 $\theta \left(\bar{x}\right)\le 0$ ，故 $\theta \left(\bar{x}\right)=0$ ，因此 $\bar{x}$ 是F的驻点，证毕。

3.3. 线性收敛

本小节假设以下条件成立：

(A1) $\nabla f_i\left(i\in \left\{1,\cdots ,m\right\}\right)$ 是L-Lipschitz连续的；

(A2) 存在一个正数c满足下面的不等式成立：

${\left(\nabla f_i\left(x\right)\right)}^{\text{T}}v\left(x\right)\le -c{\Vert \nabla f_i\left(x\right)\Vert }^2,i\in \left\{1,\cdots ,m\right\};$

(A3) 令 $\bar{x}$ 是F的驻点，存在正常数 ${\lambda }_1$ 和 ${\lambda }_2$ 满足：

${\lambda }_1{\Vert \nabla f_i\left(x\right)\Vert }^2\le f_i\left(x\right)-f_i\left(\bar{x}\right)\le {\lambda }_2{\Vert \nabla f_i\left(x\right)\Vert }^2,i\in \left\{1,\cdots ,m\right\}.$

下面的引理证明了极大型和平均型非单调线搜索生成的步长是有下界的。

引理3.9 假设(A1)成立，则对于任意的迭代次数k都存在一个正常数 ${\gamma }_{\min }$ 使得 ${\gamma }_k>{\gamma }_{\min }$ 。

证明：任取迭代次数 $k\in N$ 并将其固定，再根据 ${\gamma }_k$ 的相关定义可得

$F\left(x_k+\rho {\gamma }_{k}v\left(x_k\right)\right)\cancel{\underset{\_}{\prec }}{C}_k+\sigma \rho {\gamma }_{k}JF\left(x_k\right)v\left(x_k\right).$

故存在 $i\left(k\right)\in \left\{1,\cdots ,m\right\}$ 使得

$\begin{array}{c}{f}_{i\left(k\right)}\left(x_k+\rho {\gamma }_{k}v\left(x_k\right)\right)>C_{i\left(k\right),k}+\sigma \rho {\gamma }_k{\left(\nabla f_{i\left(k\right)}\left(x_k\right)\right)}^{\text{T}}v\left(x_k\right)\\ \ge f_{i\left(k\right)}\left(x_k\right)+\sigma \rho {\gamma }_k{\left(\nabla f_{i\left(k\right)}\left(x_k\right)\right)}^{\text{T}}v\left(x_k\right),\end{array}$ (3-26)

第二个不等式的成立是依据(3-2)和注3.1和注3.3。再利用(A1)和F是连续可微的函数的条件，可得

$\begin{array}{l}{f}_{i\left(k\right)}\left(x_k+\rho {\gamma }_{k}v\left(x_k\right)\right)-f_{i\left(k\right)}\left(x_k\right)\\ =\rho {\gamma }_k{\left(\nabla f_{i\left(k\right)}\left(x_k\right)\right)}^{\text{T}}v\left(x_k\right)+{\displaystyle \underset{0}{\overset{\rho {\gamma }_k}{\int }}{\left(\nabla f_{i\left(k\right)}\left(x_k+tv\left(x_k\right)\right)-\nabla f_{i\left(k\right)}\left(x_k\right)\right)}^{\text{T}}v\left(x_k\right)\text{d}t}\\ \le \rho {\gamma }_k{\left(\nabla f_{i\left(k\right)}\left(x_k\right)\right)}^{\text{T}}v\left(x_k\right)+{\displaystyle \underset{0}{\overset{\rho {\gamma }_k}{\int }}tL{\Vert v\left(x_k\right)\Vert }^2\text{d}t}\\ =\rho {\gamma }_k{\left(\nabla f_{i\left(k\right)}\left(x_k\right)\right)}^{\text{T}}v\left(x_k\right)+\frac{1}{2}{\rho }^2{\gamma }_k^{2}L{\Vert v\left(x_k\right)\Vert }^2.\end{array}$

将上式与(3-26)相结合，可得

${\gamma }_k\ge \frac{2\left(\sigma -1\right){\left(\nabla f_{i\left(k\right)}\left(x_k\right)\right)}^{\text{T}}v\left(x_k\right)}{\rho L{\Vert v\left(x_k\right)\Vert }^2}.$ (3-27)

考虑到 $\sigma \in \left(0,1\right)$ 和 ${\left(\nabla f_{i\left(k\right)}\left(x_k\right)\right)}^{\text{T}}v\left(x_k\right)\le 0$ ，再将(3-27)和(3-8)相结合可得

${\gamma }_k\ge \frac{\left(1-\sigma \right){\left(\nabla f_{i\left(k\right)}\left(x_k\right)\right)}^{\text{T}}v\left(x_k\right)}{\beta \rho L\underset{y\in G}{\max }\left\{y^{\text{T}}JF\left(x_k\right)v\left(x_k\right)\right\}}\ge \frac{1-\sigma }{\beta \rho L},$

这也就证明了结论。

在单目标规划中，Y.H. Dai等人 [13] 证明了极大型线搜索算法的线性收敛性质，其中要求目标函数是光滑和一致凸。受此启发，将这一性质扩展到多目标规划中并建立相关的线性收敛性，依然在目标函数是连续可微和一致凸的条件下。下面是关于算法1的线性收敛性分析。

定理3.10 设条件(A1)、(A2)和(A3)成立，则由算法1生成的序列 $\left\{x_k\right\}$ 满足：存在 $a\in \left(0,1\right)$ 使得

$F\left(x_k\right)-F\left(\bar{x}\right)\underset{\_}{\prec }{a}^k\left(F\left(x_0\right)-F\left(\bar{x}\right)\right),$ (3-28)

其中 $\bar{x}$ 表示的是序列 $\left\{x_k\right\}$ 的聚点。

证明：(3-28)等价于下面的不等式：

$f_i\left(x_k\right)-f_i\left(\bar{x}\right)\le a^k\left(f_i\left(x_0\right)-f_i\left(\bar{x}\right)\right),\forall i\in \left\{1,\cdots ,m\right\}.$ (3-29)

在证明结论之前，先证明下面的不等式对所有的 $j=0,\cdots ,m\left(k+1\right)$ 都成立：

$f_i\left(x_{k+1-j}\right)\le C_{i,k}+\sigma {\gamma }_{k-j}{\left(\nabla f_i\left(x_{k-j}\right)\right)}^{\text{T}}v\left(x_{k-j}\right),\forall i\in \left\{1,\cdots ,m\right\}.$ (3-30)

下面用数学归纳法来证明：

当 $j=0$ 时，(3-30)可以依据(3-3)得到。

假设(3-30)在 $j\in \left[0,m\left(k+1\right)-1\right]$ 处成立，考虑到 ${\left(\nabla f_i\left(x_{k-j}\right)\right)}^{\text{T}}v\left(x_{k-j}\right)\le 0$ 、 $\sigma >0$ 和 ${\gamma }_{k-j}>0$ ，有

$\underset{0\le l\le j}{\max }{f}_i\left(x_{k+1-l}\right)\le C_{i,k}=\underset{0\le l\le m\left(k\right)}{\max }{f}_i\left(x_{k-l}\right),\forall i\in \left\{1,\cdots ,m\right\}.$ (3-31)

将(3-3)，(3-2)以及 $m\left(k\right)$ 的定义与上式相结合，可得

$\begin{array}{c}{f}_i\left(x_{k+1-\left(j+1\right)}\right)\le C_{i,k-j-1}+\sigma {\gamma }_{k-j-1}{\left(\nabla f_i\left(x_{k-j-1}\right)\right)}^{\text{T}}v\left(x_{k-j-1}\right)\\ =\underset{0\le l\le m\left(k-j-1\right)}{\max }{f}_i\left(x_{k-j-1-l}\right)+\sigma {\gamma }_{k-j-1}{\left(\nabla f_i\left(x_{k-j-1}\right)\right)}^{\text{T}}v\left(x_{k-j-1}\right)\\ \le \max \left\{\underset{0\le l\le j}{\max }{f}_i\left(x_{k+1-l}\right),\underset{0\le l\le m\left(k\right)}{\max }{f}_i\left(x_{k-l}\right)\right\}+\sigma {\gamma }_{k-j-1}{\left(\nabla f_i\left(x_{k-j-1}\right)\right)}^{\text{T}}v\left(x_{k-j-1}\right)\\ =\underset{0\le l\le m\left(k\right)}{\max }{f}_i\left(x_{k-l}\right)+\sigma {\gamma }_{k-j-1}{\left(\nabla f_i\left(x_{k-j-1}\right)\right)}^{\text{T}}v\left(x_{k-j-1}\right)\\ =C_{i,k}+\sigma {\gamma }_{k-j-1}{\left(\nabla f_i\left(x_{k-j-1}\right)\right)}^{\text{T}}v\left(x_{k-j-1}\right),\forall i\in \left\{1,\cdots ,m\right\}.\end{array}$

即可证明了(3-30)对所有的 $j=0,\cdots ,m\left(k+1\right)$ 都成立。在式(3-30)两边同时关于 $j\in \left[0,m\left(k+1\right)\right]$ 取最大值，该式即可变成

$\begin{array}{c}{C}_{i,k+1}=\underset{0\le j\le m\left(k+1\right)}{\max }{f}_i\left(x_{k+1-j}\right)\\ \le C_{i,k}+\underset{0\le j\le m\left(k+1\right)}{\max }\sigma {\gamma }_{k-j}\nabla f_i\left(x_{k-j}\right)v\left(x_{k-j}\right),\forall i\in \left\{1,\cdots ,m\right\}.\end{array}$