多目标优化非单调线性加权牛顿算法

Nonmonotone Linear Weighted Newton Algorithm for Multi-Objective Optimization

摘要: 本文提出了一种求解多目标优化问题的非单调线性加权牛顿算法。在目标函数有下界且梯度Lipschitz连续的条件下证明了算法的全局收敛性。在目标函数满足二次连续可微且局部强凸的条件下，证明了该算法具有局部超线性收敛速度。数值实验结果表明，相比于单调线性加权牛顿算法，该算法能够更加高效地求解多目标优化问题。

Abstract: This paper introduces a nonmonotone linear weighted Newton algorithm for solving multi-objective optimization problems. It is shown that the algorithm achieves global convergence under the assumption of a lower bound on the objective function and a Lipschitz continuous gradient. Furthermore, under the conditions of quadratic continuous differentiability and local strong convexity, the algorithm demonstrates local superlinear convergence. Numerical experiments demonstrate that this algorithm outperforms the monotone linear weighted Newton algorithm in efficiently solving multi-objective optimization problems.

1. 引言

多目标优化是最优化理论的一个分支，它与非线性规划、泛函分析以及矩阵论等有着密切的关系，在金融投资、物流网络及国防军事等方面有着广泛的应用需求。鉴于多目标优化在实际生活中的重要作用，学者们自上世纪七十年代以来，针对多目标优化问题开展了大量研究。到目前为止，多目标优化在理论方面已经取得很多重要成果，一套平行于单目标最优化的理论体系正日趋完善[1]，这为后续求解多目标优化问题提供了指导方向。

牛顿法具有较快的收敛速度，是求解单目标优化问题常用的方法之一。2009年，Fliege [2]首次将牛顿法推广到多目标优化问题中。Fliege通过求解一个极大极小问题来构造搜索方向，并且证明了当目标函数的二阶导数Lipschitz连续时，算法具有二阶收敛速度。虽然Fliege提出的多目标优化牛顿算法具有较快的收敛速度，但是在求解极大极小问题时的计算量较多，且计算难度大。Jiang [3]对Fliege提出的牛顿法进行改进，采用线性标量化方法，对目标函数的二次近似形式进行线性加权，将它们的和作为新的搜索方向，这样能够充分减少计算量，且算法在一定条件下同样具有二阶收敛速度。除牛顿法之外，最速下降法[4]、投影梯度法[5]、共轭梯度法[6]以及拟牛顿法[7]也已被扩展到多目标优化领域。

上述算法都是运用单调线搜索方法确定步长。对于单目标优化问题而言，单调线搜索方法非常有效，但是对于多目标优化问题来说，很难做到让每一个目标函数值在每一次迭代中都减小，且强制单调性会减慢求解方法的收敛速度，而非单调线搜索方法能有效避免这些不足。Zhang和Hager [8]提出一种平均值类型的非单调线搜索方法，并且证明了这种方法比单调线搜索方法和极大值非单调线搜索方法[9]更有效。

本文结合非单调线搜索技术，对Jiang [3]提出的单调算法进行改进，提出了非单调线性加权牛顿法。在一定的假设条件下证明了算法的收敛性，数值实验结果表明，在相同的条件下，本文提出的算法在求解多目标优化问题时的迭代次数及时间更少，能更加有效地求解多目标优化问题。

本文考虑如下多目标优化问题：

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

其中，$F:U\to {ℝ}^m$ ，$F\left(x\right)=\left(F_1\left(x\right),F_2\left(x\right),\cdots ,F_m\left(x\right)\right)$ ，$U\subset {ℝ}^n$ 为开集。

在本文中，矩阵$A\in {ℝ}^{m\times n}$ 的像空间用Im(A)表示，$\text{Im}\left(A\right)=\left\{Ax|x\in {ℝ}^n\right\}$ 。$DF\left(x\right)\in {ℝ}^{m\times n}$ 表示目标函数F在x处的Jacobian矩阵，$\nabla F_j\left(x\right)$ 表示第j个目标函数在x处的梯度，${\nabla }^2{F}_j\left(x\right)$ 表示第j个目标函数在x处的Hessian矩阵，${\lambda }_j$ 表示目标函数的第j个分量对应的权重系数，${\displaystyle \sum _{j=1}^m{\lambda }_j}=1$ 且${\lambda }_j>0$ $\left(j=1,2,\cdots ,m\right)$ 。

在本文中，假设F在U上二次连续可微且目标函数每个分量F_j的Hessian矩阵都为正定矩阵，即

$F\in C^2\left(U,{ℝ}^m\right),$

${\nabla }^2{F}_j\left(x\right)>0,\forall x\in U,j=1,2,\cdots ,m.$

在多目标优化问题中，考虑如下偏序关系：

$\begin{array}{l}\forall x,y\in {ℝ}^n,x=y\iff x_i=y_i,i=1,2,\cdots ,n.\\ x<y\iff x_i<y_i,i=1,2,\cdots ,n.\\ x\le y\iff x_i\le y_i,但x\ne y,i=1,2,\cdots ,n.\end{array}$

以下定义及引理均来源于文献[2]。

定义1.1 设$x^{\ast }\in U$ ，若不存在$x\in U$ ，使得$F\left(x\right)\le F\left(x^{\ast }\right)\left(F\left(x\right)<F\left(x^{\ast }\right)\right)$ ，则$x^{\ast }$ 是问题(1.1)的Pareto最优解或有效解(弱Pareto最优解或弱有效解)。

定义1.2 设$x^{\ast }\in U$ ，若存在$x^{\ast }$ 的一个邻域$V\subseteq U$ ，且不存在$x\in U\cap V$ ，使得$F\left(x\right)\le F\left(x^{\ast }\right)\left(F\left(x\right)<F\left(x^{\ast }\right)\right)$ ，则$x^{\ast }$ 是问题(1.1)的局部Pareto最优解或局部有效解(局部弱Pareto最优解或局部弱有效解)。

定义1.3 设$\tilde{x}\in U$ ，若$\text{Im}\left(DF\left(\tilde{x}\right)\right)\cap \left(-{ℝ}_{++}^m\right)=\varnothing$，则$\tilde{x}$ 为F的临界点(稳定点)。

引理1.1 设$\overline{x}\in U$ ，$F\in C^1\left(U,{ℝ}^m\right)$ ，则有如下结论：

1) 若$\overline{x}$ 是局部弱Pareto最优解，则$\overline{x}$ 是F的一个稳定点。

2) 若U是凸集，F是凸向量函数，则当$\overline{x}$ 是F的稳定点时，$\overline{x}$ 是弱Pareto最优解。

3) 若$\forall x\in U$ ，有${\nabla }^2{F}_j\left(x\right)>0\left(j=1,2,\cdots ,m\right)$ 其中，U是凸集，$F\in C^2\left(U,{ℝ}^m\right)$ ，则当$\overline{x}\in U$ 是F的稳定点时，$\overline{x}$ 是Pareto最优解。

2. 非单调线性加权牛顿算法

考虑多目标优化问题(1.1)，在文献[2]中，定义x处的牛顿方向为$s_N$ ，$s_N$ 是如下无约束优化问题的最优解

$\{\begin{array}{l}\min \underset{j=1,2,\cdots ,m}{\max }\nabla F_j{\left(x\right)}^{\text{T}}{s}_N+\left(1/2\right)s_N^{\text{T}}{\nabla }^2{F}_j\left(x\right)s_N\\ \text{s}\text{.t}.s_N\in {ℝ}^n.\end{array}$ (2.1)

在上述问题中，$\nabla F_j{\left(x\right)}^{\text{T}}{s}_N+\left(1/2\right)s_N^{\text{T}}{\nabla }^2{F}_j\left(x\right)s_N$ 是增量$F_j\left(x+s_N\right)-F\left(x\right)$ 的二次近似，我们需要在增量最大的情况下求得最小的搜索方向$s_N$ 。Fliege [2]将上述问题转化为约束优化问题，运用拉格朗日乘子法求得$s_N$ 。对于多目标优化问题来说，这种求解搜索方向的方法较为复杂，所需的计算量也比较大。

本文采用加权系数法求解搜索方向s，能够减少计算工作量，求解过程更加简便高效。考虑如下无约束优化问题：

$\{\begin{array}{l}\min {\displaystyle \sum _{j=1}^m{\lambda }_j\left(\nabla F_j{\left(x\right)}^{\text{T}}s+\left(1/2\right)s^{\text{T}}{\nabla }^2{F}_j\left(x\right)s\right)}\\ \text{s}\text{.t}.s\in {ℝ}^n.\end{array}$ (2.2)

由假设，${\nabla }^2{F}_j\left(x\right)\left(j=1,2,\cdots ,m\right)$ 正定，这说明${\displaystyle \sum _{j=1}^m{\lambda }_j\left(\nabla F_j{\left(x\right)}^{\text{T}}s+\left(1/2\right)s^{\text{T}}{\nabla }^2{F}_j\left(x\right)s\right)}$ 是强凸的，从而问题(2.2)存在唯一的极小值点。

用$\theta \left(x\right)$ 表示问题(2.2)的最优值，则有

$s\left(x\right)=\arg \underset{s\in {ℝ}^n}{\min }{\displaystyle \sum _{j=1}^m{\lambda }_j\left(\nabla F_j{\left(x\right)}^{\text{T}}s+\left(1/2\right)s^{\text{T}}{\nabla }^2{F}_j\left(x\right)s\right)}$ (2.3)

$\theta \left(x\right)=\underset{s\in {ℝ}^n}{\min }{\displaystyle \sum _{j=1}^m{\lambda }_j\left(\nabla F_j{\left(x\right)}^{\text{T}}s+\left(1/2\right)s^{\text{T}}{\nabla }^2{F}_j\left(x\right)s\right)}$ (2.4)

基于上述讨论，我们将给出求解多目标优化问题的非单调线性加权牛顿算法(Nonmonotone Linear Weighted Newton)，我们将它简称为NLWN算法，它的具体步骤如下：

算法2.1 (NLWN方法)

步1 选取初始点$x_0\in U$ ，选取参数$\sigma \in \left(0,1\right)$ ，$\mu >0$ ，$\rho \in \left(0,1\right)$ ，$\eta \in \left[0,1\right]$ ，$k=0$ ，$C^0=F\left(x_0\right)$ ，$q_0=1$ 。

步2 由和，分别求出$s\left(x_k\right)$ 和$\theta \left(x_k\right)$ 。

步3 若$\theta \left(x_k\right)=0$ ，终止算法；否则，转步4。

步4 记$h_k$ 是使得下式成立的最小非负整数h：

$F_j\left(x_k+\mu {\rho }^{h}s\left(x_k\right)\right)\le C_j^k+\sigma \mu {\rho }^h\theta \left(x_k\right),j=1,2,\cdots ,m.$ (2.5)

步5 令${\alpha }_k=\mu {\rho }^{h_k}$ ，$x_{k+1}=x_k+{\alpha }_{k}s\left(x_k\right)$ 。

步6 更新$q_k$ 和$C_j^k$ ：

$q_{k+1}=\eta q_k+1,$ (2.6)

$C_j^{k+1}=\eta q_k{C}_j^k+F_j\left(x_{k+1}\right)/q_{k+1}.$ (2.7)

令$k=k+1$ ，转步2。

注记2.1 当$\eta =0$ 时，则有$C_j^{k+1}=F_j\left(x_{k+1}\right)$ 。此时非单调线搜索退化成Armijo线搜索。

对于算法2.1，我们有以下引理。

引理2.1 [10]对于算法2.1的每一次迭代，总有$F\left(x_k\right)\le C^k$ 。

引理2.2 [10]设$\left\{x_k\right\}$ 是由算法2.1产生的序列。若$x_k$ 不是稳定点，则存在步长${\alpha }_k>0$ 满足(2.5)中的非单调线搜索准则。

下面的引理给出$\theta \left(x\right)$ 与$s\left(x\right)$ 的性质。

引理2.3 [2]在本文的假设下，有以下结论：

1) $\forall x\in U$ ，$\theta \left(x\right)\le 0$ 。

2) 以下三个说法是等价的：

a) x不是稳定点。

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

c) $s\left(x\right)\ne 0$ 。

3) 由(2.3)给定的函数$s:U\to {ℝ}^n$ 在紧集上有界，由(2.4)给定的函数$\theta :U\to ℝ$ 在U上连续。

3. 全局收敛性

在这一小节，我们将证明算法2.1的全局收敛性。在证明算法2.1的全局收敛性之前，给出如下假设和引理：

假设3.1 $\forall x\in {ℝ}^n$ ，$\nabla F_j\left(x\right)\left(j=1,2,\cdots ,m\right)$ Lipschitz连续。

引理3.1 当假设3.1成立，且${\alpha }_k$ 满足非单调线搜索条件(2.5)时，下面的不等式成立：

${\alpha }_k\ge \min \left\{\rho ,2\rho \left(1-\sigma \right)\left|\theta \left(x_k\right)\right|/L{\Vert s\left(x_k\right)\Vert }^2\right\}.$ (3.1)

证 若${\alpha }_k\ge \rho$ ，则(3.1)成立。

若${\alpha }_k<\rho$ ，由${\alpha }_k$ 满足(2.5)式可知，$\exists j_0\in \left\{1,2,\cdots ,m\right\}$ ，有

$F_{j_0}\left(x_k+\left({\alpha }_k/\rho \right)s\left(x_k\right)\right)>F_{j_0}\left(x_k\right)+\sigma \left({\alpha }_k/\rho \right)\theta \left(x_k\right).$ (3.2)

由假设3.1，$\nabla F_j\left(j=1,2,\cdots ,m\right)$ Lipschitz连续，则有

$\begin{array}{l}{F}_{j_0}\left[x_k+\left({\alpha }_k/\rho \right)s\left(x_k\right)\right]-F_j\left(x_k\right)\\ =\left({\alpha }_k/\rho \right)\nabla F_{j_0}{\left(x_k\right)}^{\text{T}}s\left(x_k\right)+{\displaystyle {\int }_0^{{\alpha }_k/\rho }{\left[\nabla F_{j_0}\left(x_k+ts\left(x_k\right)\right)-\nabla F_{j_0}\left(x_k\right)\right]}^{\text{T}}s\left(x_k\right)\text{d}t}\\ \le \left({\alpha }_k/\rho \right)\theta \left(x_k\right)+{\displaystyle {\int }_0^{{\alpha }_k/\rho }tL{\Vert s\left(x_k\right)\Vert }^{\text{2}}\text{d}t}\\ =\left({\alpha }_k/\rho \right)\theta \left(x_k\right)+L{\alpha }_k^2{\Vert s\left(x_k\right)\Vert }^2/\left(2{\rho }^2\right).\end{array}$ (3.3)

由(3.2)和(3.3)式可得

$\sigma \left({\alpha }_k/\rho \right)\theta \left(x_k\right)<\left({\alpha }_k/\rho \right)\theta \left(x_k\right)+L{\alpha }_k^2{\Vert s\left(x_k\right)\Vert }^2/\left(2{\rho }^2\right).$

整理后可得

${\alpha }_k>2\rho \left(\sigma -1\right)\theta \left(x_k\right)/L{\Vert s\left(x_k\right)\Vert }^2.$ (3.4)

由引理2.3有$\theta \left(x\right)\le 0$ ，从而$\left|\theta \left(x\right)\right|=-\theta \left(x\right)$ 。此时(3.4)可写成

${\alpha }_k>2\rho \left(1-\sigma \right)\left|\theta \left(x_k\right)\right|/L{\Vert s\left(x_k\right)\Vert }^2.$

故引理3.1成立。

定理3.1 假设$F_j\left(x\right)$ 有下届$\left(j=1,2,\cdots ,m\right)$ ，$x\in {ℝ}^n$ ，$\eta <1$ 。当假设3.1成立，且存在一个常数$c_1>0$ 使得下面的不等式成立时，

$\left|\theta \left(x_k\right)\right|\ge c_1{\Vert s\left(x_k\right)\Vert }^2,\forall k=1,2,\cdots$ (3.5)

由算法2.1产生的序列$\left\{x_k\right\}$ 的任一极限点都是问题(1.1)的Pareto最优解。

证 首先证明下面的不等式，其中，$\beta =\min \left\{\sigma \rho ,2\sigma \rho c_1\left(1-\sigma \right)/L\right\}$ 。

$F_j\left(x_{k+1}\right)\le C_j^k-\beta \left|\theta \left(x_k\right)\right|\left(j=1,2,\cdots ,m\right)$ (3.6)

考虑下面两种情况：

(i) 使用非单调线搜索条件(2.5)及${\alpha }_k\ge \rho$ ，可得

$F_j\left(x_{k+1}\right)\le C_j^k+\sigma {\alpha }_k\theta \left(x_k\right)=C_j^k-\sigma {\alpha }_k\left|\theta \left(x_k\right)\right|\le C_j^k-\sigma \rho \left|\theta \left(x_k\right)\right|\left(j=1,2,\cdots ,m\right)$

令$\beta =\sigma \rho$ ，即得(3.6)。

(ii) 使用非单调线搜索条件(2.5)及${\alpha }_k<\rho$ ，由引理3.1，可得

${\alpha }_k\ge 2\rho \left(1-\sigma \right)\left|\theta \left(x_k\right)\right|/L{\Vert s\left(x_k\right)\Vert }^2.$

再由(3.5)得

$\begin{array}{l}{F}_j\left(x_{k+1}\right)\le C_j^k+\sigma {\alpha }_k\theta \left(x_k\right)=C_j^k-\sigma {\alpha }_k\left|\theta \left(x_k\right)\right|\\ \le C_j^k-2\sigma \rho \left(1-\sigma \right){\left|\theta \left(x_k\right)\right|}^2/L{\Vert s\left(x_k\right)\Vert }^2\\ \le C_j^k-2\sigma \rho c_1\left(1-\sigma \right)\left|\theta \left(x_k\right)\right|/L\left(j=1,2,\cdots ,m\right)\end{array}$

令$\beta =2\sigma \rho c_1\left(1-\sigma \right)/L$ ，即得(3.6)。

设$\widehat{x}$ 是$\left\{x_k\right\}$ 的极限点，接下来证明$\widehat{x}$ 收敛到问题(1.1)的Pareto最优解。

由$q_k$ 及$C_j^k$ 的更新公式(2.6)、(2.7)，以及(3.6)，有

$q_{k+1}=1+{\displaystyle \sum _{i=0}^k{\eta }^{i+1}}.$ (3.7)

$\begin{array}{l}{C}_j^{k+1}=\left[\eta q_k{C}_j^k+F_j\left(x_{k+1}\right)\right]/q_{k+1}\\ \le \left[\eta q_k{C}_j^k+C_j^k-\beta \left|\theta \left(x_k\right)\right|\right]/q_{k+1}\\ =\left[\left(\eta q_k+1\right)C_j^k-\beta \left|\theta \left(x_k\right)\right|\right]/q_{k+1}\\ =\left[q_{k+1}{C}_j^k-\beta \left|\theta \left(x_k\right)\right|\right]/q_{k+1}\\ =C_j^k-\beta \left|\theta \left(x_k\right)\right|/q_{k+1}\left(j=1,2,\cdots ,m\right)\end{array}$ (3.8)

由已知条件，$F_j\left(x\right)$ 有下届。由引理2.1，有$F_j\left(x_k\right)\le C_j^k$ ，从而$C_j^k$ 也有下界。$\left(j=1,2,\cdots ,m\right)$

对(3.8)的前n + 1项求和，得到

${\displaystyle \sum _{k=0}^n\left|\theta \left(x_k\right)\right|/q_{k+1}}\le \left(1/\beta \right)\left(C_j^0-C_j^{n+1}\right).$

令$n\to +\infty$ ，得到

${\displaystyle \sum _{k=0}^{+\infty }\left|\theta \left(x_k\right)\right|/q_{k+1}}<\infty$ (3.9)

$\widehat{x}$ 是$\left\{x_k\right\}$ 的极限点，设K是一个无限指标集，则有$\underset{k\in K}{\lim }{x}_k=\widehat{x}$ 。我们要证明$\widehat{x}$ 是Paroto最优解，即证$\theta \left(\widehat{x}\right)=0$ ，用反证法证明。

假设$\theta \left(\widehat{x}\right)<0$ ，即

$\exists {\epsilon }_0>0$ ，${\delta }_0>0$ ，$0<\delta <{\delta }_0$ ，$\forall k\in K$ ，$\Vert x_k-\widehat{x}\Vert \le \delta$ 时，有$\left|\theta \left(x_k\right)\right|\ge {\epsilon }_0$ 。

从而有

${\displaystyle \sum _{k=0}^{+\infty }\left|\theta \left(x_k\right)\right|/q_{k+1}}\ge {\displaystyle \sum _{k\in K,\Vert x_k-\widehat{x}\Vert \le \delta }{\epsilon }_0/q_{k+1}}.$ (3.10)

由(3.7)可得

$q_{k+1}=1+{\displaystyle \sum _{i=0}^k{\eta }^{i+1}}<{\displaystyle \sum _{i=0}^{+\infty }{\eta }^i}=1/\left(1-\eta \right).$ (3.11)

由(3.10)和(3.11)可得

${\displaystyle \sum _{k=0}^{+\infty }\left|\theta \left(x_k\right)\right|/q_{k+1}}\ge {\displaystyle \sum _{k\in K,\Vert x_k-\widehat{x}\Vert \le \delta }{\epsilon }_0/q_{k+1}}>{\displaystyle \sum _{k\in K,\Vert x_k-\widehat{x}\Vert \le \delta }{\epsilon }_0}\left(1-\eta \right)=+\infty .$

这与(3.9)矛盾，从而假设不成立，即$\theta \left(\widehat{x}\right)=0$ 。由引理1.1和引理2.3可知，$\widehat{x}$ 是问题(1.1)的Paroto最优解，也即，算法2.1产生的序列$\left\{x_k\right\}$ 的任一极限点都是问题(1.1)的Pareto最优解，故定理3.1成立。

4. 局部超线性收敛速度

我们在本小节给出算法2.1具有局部超线性收敛速度的证明。在证明之前先给出下面的引理及假设。

引理4.1 [2]设$x\in U\subset {ℝ}^n$ ，$a,b\in ℝ$ ，且$0<a\le b$ 。若$aI\le {\nabla }^2{F}_j\left(x\right)\le bI\left(j=1,2,\cdots ,m\right)$ ，则

$\left(a/2\right){\Vert s\left(x\right)\Vert }^2\le \left|\theta \left(x\right)\right|\le \left(b/2\right){\Vert s\left(x\right)\Vert }^2.$

引理4.2 [2]设$x\in U\subset {ℝ}^n$ ，$a>0$ 。若$aI\le {\nabla }^2{F}_j\left(x\right)\left(j=1,2,\cdots ,m\right)$ ，则

$\left|\theta \left(x\right)\right|\le \left(1/2a\right){\Vert {\displaystyle \sum _{j=1}^m{\lambda }_j\nabla F_j\left(x\right)}\Vert }^2.$

引理4.3 [2]设$\widehat{x}\in U$ ，定义${\widehat{x}}_{+}=\widehat{x}+s\left(\widehat{x}\right)$ 。若$a,r,\delta ,\epsilon >0$ ，且满足

1) $\forall x\in B\left[\widehat{x},r\right]$ ，有$aI\le {\nabla }^2{F}_j\left(x\right)\left(j=1,2,\cdots ,m\right)$ ；

2) $\forall x,y\in B\left[\widehat{x},r\right]$ ，$\Vert x-y\Vert <\delta$ ，有$\Vert {\nabla }^2{F}_j\left(x\right)-{\nabla }^2{F}_j\left(y\right)\Vert <\epsilon \left(j=1,2,\cdots ,m\right)$ ；

3) $B\left[\widehat{x},r\right]\subset U$ ；

4) $\Vert s\left(\widehat{x}\right)\Vert \le \min \left\{\delta ,r\right\}$ ；

则$\Vert s\left({\widehat{x}}_{+}\right)\Vert \le \left(\epsilon /a\right)\Vert s\left(\widehat{x}\right)\Vert$ 。

假设4.1 $\forall \epsilon >0$ ，$\exists \delta >0$ ，$\forall x,y\in V$ ，$\Vert x-y\Vert <\delta$ ，有$\Vert {\nabla }^2{F}_j\left(x\right)-{\nabla }^2{F}_j\left(y\right)\Vert \le \epsilon$ 。

假设4.2 $\forall x\in V$ ，有$aI\le {\nabla }^2{F}_j\left(x\right)\le bI$ 。

假设4.3 $B\left[x_0,r\right]\subset V$ 。

假设4.4 $\epsilon /a\le 1-\sigma$ 。

假设4.5 $\Vert s\left(x_0\right)\Vert \le \min \left\{\delta ,r\left(1-\epsilon /a\right)\right\}$ 。

在上面的假设中，$a,b,r,\delta ,\epsilon >0$ ，$V\subset U$ ，$j=1,2,\cdots ,m$ 。

下面给出算法2.1的局部超线性收敛定理及证明。

定理4.1 设$\left\{x_k\right\}$ 是算法2.1产生序列，若假设4.1~4.5成立，则序列$\left\{x_k\right\}$ 超线性收敛于问题(1.1)的局部Pareto最优解。

证 首先证明当k充分大时，${\alpha }_k=1$ 。

将$F_j\left(x_k+s\left(x_k\right)\right)\left(j=1,2,\cdots ,m\right)$ 在$x_k$ 处二阶泰勒展开，得到

$F_j\left(x_k+s\left(x_k\right)\right)=F_j\left(x_k\right)+\nabla F_j{\left(x_k\right)}^{\text{T}}s\left(x_k\right)+\left(1/2\right)s{\left(x_k\right)}^{\text{T}}{\nabla }^2{F}_j\left(x_k\right)s\left(x_k\right)+o\left({\Vert s\left(x_k\right)\Vert }^2\right).$

由引理2.1及$\theta \left(x_k\right)$ 的定义，上式可写为

$\begin{array}{l}{F}_j\left(x_k+s\left(x_k\right)\right)\le C_j^k+\theta \left(x_k\right)+o\left({\Vert s\left(x_k\right)\Vert }^2\right)\\ =C_j^k+\sigma \theta \left(x_k\right)+\left(1-\sigma \right)\theta \left(x_k\right)+\left(\epsilon /2\right){\Vert s\left(x_k\right)\Vert }^2.\end{array}$

又由引理4.1，上式可写为

$\begin{array}{l}{F}_j\left(x_k+s\left(x_k\right)\right)\le C_j^k+\sigma \theta \left(x_k\right)-\left(1-\sigma \right)\left(a/2\right){\Vert s\left(x_k\right)\Vert }^2+\left(\epsilon /2\right){\Vert s\left(x_k\right)\Vert }^2\\ =C_j^k+\sigma \theta \left(x_k\right)+\left[\epsilon -a\left(1-\sigma \right)\right]{\Vert s\left(x_k\right)\Vert }^2/2.\end{array}$ (4.1)

由假设4.4可得$\epsilon -a\left(1-\sigma \right)\le 0$ ，

则(4.1)可写为

$F_j\left(x_k+s\left(x_k\right)\right)\le C_j^k+\sigma \theta \left(x_k\right)\left(j=1,2,\cdots ,m\right)$

上式说明，当k充分大时，${\alpha }_k=1$ 。

其次，证明算法2.1产生的序列$\left\{x_k\right\}$ 收敛于问题(1.1)的局部Pareto最优解。

由第一部分的证明，当k充分大时，${\alpha }_k=1$ 。即存在充分大的$k_0$ ，$\forall k>k_0$ ，有

$x_{k+1}=x_k+{\alpha }_{k}s\left(x_k\right)=x_k+s\left(x_k\right).$

下面用归纳法证明：

1)$\Vert x_k-x_0\Vert \le \Vert s\left(x_0\right)\Vert \left[1-{\left(\epsilon /a\right)}^k\right]/\left(1-\epsilon /a\right)$ (4.2)

2)$\Vert s\left(x_k\right)\Vert \le {\left(\epsilon /a\right)}^k\Vert s\left(x_0\right)\Vert$ (4.3)

当$k=0$ 时，经计算可知(4.2)，(4.3)都成立。

假设当$k=n$ 时，(4.2)，(4.3)成立，即$\Vert x_n-x_0\Vert \le \Vert s\left(x_0\right)\Vert \left[1-{\left(\epsilon /a\right)}^n\right]/\left(1-\epsilon /a\right)$ ，$\Vert s\left(x_n\right)\Vert \le {\left(\epsilon /a\right)}^n\Vert s\left(x_0\right)\Vert$ 。

对(4.2)，当$k=n+1$ 时：

$\begin{array}{l}\Vert x_{n+1}-x_0\Vert =\Vert x_n+s\left(x_n\right)-x_0\Vert \\ \le \Vert x_n-x_0\Vert +\Vert s\left(x_n\right)\Vert \\ =\Vert s\left(x_0\right)\Vert \left[1-{\left(\epsilon /a\right)}^k{}^n\right]/\left(1-\epsilon /a\right)+\Vert s\left(x_0\right)\Vert {\left(\epsilon /a\right)}^n\\ =\Vert s\left(x_0\right)\Vert \left[1-{\left(\epsilon /a\right)}^k{}^{n+1}\right]/\left(1-\epsilon /a\right).\end{array}$

从而(4.2)对$\forall k\in \mathbb{N}$ 都成立。

由(4.2)及假设4.5可得$x_k\in B\left[x_0,r\right]$ 。又由假设4.1~4.5及引理4.3，得到

$\Vert s\left(x_{k+1}\right)\Vert \le \left(\epsilon /a\right)\Vert s\left(x_k\right)\Vert .$ (4.4)

对(4.3)，结合(4.4)，当$k=n+1$ 时，有

$\Vert s\left(x_{n+1}\right)\Vert \le \left(\epsilon /a\right)\Vert s\left(x_n\right)\Vert \le \left(\epsilon /a\right){\left(\epsilon /a\right)}^n\Vert s\left(x_0\right)\Vert =\Vert s\left(x_0\right)\Vert {\left(\epsilon /a\right)}^{n+1}.$

从而(4.3)对$\forall k\in \mathbb{N}$ 都成立。

由(4.2)，(4.3)可得

${\displaystyle \sum _{k=0}^{+\infty }\Vert x_{k+1}-x_k\Vert }={\displaystyle \sum _{k=0}^{+\infty }\Vert s\left(x_k\right)\Vert }\le \Vert s\left(x_0\right)\Vert {\displaystyle \sum _{k=0}^{+\infty }{\left(\epsilon /a\right)}^k}<\infty ,$ (4.5)

从而$\left\{x_k\right\}$ 是柯西序列，存在$x^{\ast }\in {ℝ}^n$ ，使得$\underset{k\to \infty }{\lim }{x}_k=x^{\ast }$ 。

对(4.2)中的不等式两边同时取极限可得

$\Vert x^{\ast }-x_0\Vert \le \Vert s\left(x_0\right)\Vert /\left(1-\epsilon /a\right).$ (4.6)

由(4.5)可知，$\left\{\Vert s\left(x_k\right)\Vert \right\}$ 收敛到0。由假设4.2及引理4.1可得$\underset{k\to \infty }{\lim }\left|\theta \left(x_k\right)\right|=0$ 。又由引理2.3，得到$\left|\theta \left(x^{\ast }\right)\right|=0$ ，即$x^{\ast }$ 是问题(1.1)的稳定点，由引理1.1可知，$x^{\ast }$ 是问题(1.1)的局部Pareto最优解。

最后，我们证明$\left\{x_k\right\}$ 超线性收敛到$x^{\ast }$ 。

定义$r_k=\Vert s\left(x_0\right)\Vert {\left(\epsilon /a\right)}^k/\left(1-\epsilon /a\right)$ ，${\delta }_k=\Vert s\left(x_0\right)\Vert {\left(\epsilon /a\right)}^k$ ，$k=0,1,2,\cdots$ 。$\forall \gamma >0$ ，令$\widehat{\epsilon }=\min \left\{a\gamma /\left(1+2\gamma \right),\epsilon \right\}$ 。$\widehat{r}=r_k$ ，$\widehat{\delta }={\delta }_k$ ，${\widehat{x}}_0=x_k$ 。

$\forall x\in B\left[x_k,r_k\right]$ ，则$\Vert x-x_k\Vert \le r_k=\Vert s\left(x_0\right)\Vert {\left(\epsilon /a\right)}^k/\left(1-\epsilon /a\right)$ 。

由(4.3)和假设4.5可得，$x_k\in B\left[x_0,r\right]$ 。

由三角不等式可得

$\begin{array}{l}\Vert x-x_0\Vert \le \Vert x-x_k\Vert +\Vert x_k-x_0\Vert \\ \le \Vert s\left(x_0\right)\Vert \left[{\left(\epsilon /a\right)}^k+1-{\left(\epsilon /a\right)}^k\right]/\left(1-\epsilon /a\right)\\ =\Vert s\left(x_0\right)\Vert /\left(1-\epsilon /a\right)\\ \le r\left(1-\epsilon /a\right)/\left(1-\epsilon /a\right)=r\end{array}$

即$x\in B\left[x_0,r\right]$ 。又$x\in B\left[x_k,r_k\right]$ 且$B\left[x_0,r\right]\subset V$ ，从而$B\left[x_k,r_k\right]\subset B\left[x_0,r\right]\subset V$ 。

下面证明假设4.1~4.5对$\widehat{\epsilon },\widehat{r},\widehat{\delta },{\widehat{x}}_0$ 也成立。

假设4.1 的结论对$\forall x,y\in V,\Vert x-y\Vert \le \delta$ 成立，又$B\left[x_k,r_k\right]\subset B\left[x_0,r\right]\subset V$ ，$\widehat{\delta }<\delta$ ，故假设4.1对$\widehat{\epsilon },\widehat{\delta }$ 也成立。

假设4.2 的结论对$\forall x\in V$ 成立，而${\widehat{x}}_0=x_k\in B\left[x_k,r_k\right]\subset B\left[x_0,r\right]\subset V$ ，故假设4.2对${\widehat{x}}_0$ 也成立。

由$\widehat{\epsilon }$ 的定义可知$\widehat{\epsilon }\le \epsilon$ ，从而$\widehat{\epsilon }/a\le \epsilon /a\le 1-\sigma$ ，故假设4.3对$\widehat{\epsilon }$ 也成立。

已知$B\left[x_0,r\right]\subset V$ ，又$B\left[{\widehat{x}}_0,\widehat{r}\right]=B\left[x_k,r_k\right]\subset B\left[x_0,r\right]$ ，即$B\left[{\widehat{x}}_0,\widehat{r}\right]\subset V$ ，故假设4.4对${\widehat{x}}_0,\widehat{r}$ 也成立。

对假设4.5，由${\widehat{x}}_0,\widehat{\delta }$ 的定义及可得

$\Vert s\left({\widehat{x}}_0\right)\Vert =\Vert s\left(x_k\right)\Vert \le \Vert s\left(x_0\right)\Vert {\left(\epsilon /a\right)}^k={\delta }_k=\widehat{\delta }.$ (4.7)

由$\widehat{r},\widehat{\epsilon }$ 的定义可得

$\begin{array}{c}\widehat{r}\left(1-\widehat{\epsilon }/a\right)=r_k\left(1-\widehat{\epsilon }/a\right)\\ =\Vert s\left(x_0\right)\Vert {\left(\epsilon /a\right)}^k\left(1-\widehat{\epsilon }/a\right)/\left(1-\epsilon /a\right)\\ \ge \Vert s\left(x_0\right)\Vert {\left(\epsilon /a\right)}^k\left(1-\epsilon /a\right)/\left(1-\epsilon /a\right)\\ =\Vert s\left(x_0\right)\Vert {\left(\epsilon /a\right)}^k\end{array}$

又由(4.3)，有

$\Vert s\left({\widehat{x}}_0\right)\Vert =\Vert s\left(x_k\right)\Vert \le \Vert s\left(x_0\right)\Vert {\left(\epsilon /a\right)}^k\le \widehat{r}\left[1-\left(\widehat{\epsilon }/a\right)\right]$ (4.8)

结合(4.7)，有$\Vert s\left({\widehat{x}}_0\right)\Vert \le \min \left\{\widehat{\delta },\widehat{r}\left[1-\left(\widehat{\epsilon }/a\right)\right]\right\}$，故假设4.5对$\widehat{\epsilon },\widehat{r},\widehat{\delta },{\widehat{x}}_0$ 成立。

综上，假设4.1~4.5对$\widehat{\epsilon },\widehat{r},\widehat{\delta },{\widehat{x}}_0$ 成立。

由假设4.1~4.5对$\widehat{\epsilon },\widehat{r},\widehat{\delta },{\widehat{x}}_0$ 成立可知，(4.6)对${\widehat{x}}_0$ 和$\widehat{\epsilon }$ 也成立，又${\widehat{x}}_0=x_k$ ，则有

$\Vert x^{\ast }-x_k\Vert \le \Vert s\left(x_k\right)\Vert /\left(1-\widehat{\epsilon }/a\right).$ (4.9)

由(4.4)和(4.9)可得

$\Vert x^{\ast }-x_{k+1}\Vert \le \Vert s\left(x_{k+1}\right)\Vert /\left(1-\widehat{\epsilon }/a\right)\le \Vert s\left(x_k\right)\Vert \left(\widehat{\epsilon }/a\right)/\left(1-\widehat{\epsilon }/a\right)$ (4.10)

由(4.10)及三角不等式可得

$\begin{array}{l}\Vert x^{\ast }-x_k\Vert \ge \Vert x_{k+1}-x_k\Vert -\Vert x^{\ast }-x_{k+1}\Vert \\ \ge \Vert s\left(x_k\right)\Vert -\Vert s\left(x_k\right)\Vert \left(\widehat{\epsilon }/a\right)/\left(1-\widehat{\epsilon }/a\right)\\ =\Vert s\left(x_k\right)\Vert \left(1-2\widehat{\epsilon }/a\right)/\left(1-\widehat{\epsilon }/a\right).\end{array}$(4.11)

由$\widehat{\epsilon }$ 的定义，(4.10)和(4.11)可得

$\Vert x^{\ast }-x_{k+1}\Vert \le \Vert x^{\ast }-x_k\Vert \left(\widehat{\epsilon }/a\right)/\left(1-2\widehat{\epsilon }/a\right)\le \gamma \Vert x^{\ast }-x_k\Vert$

又$\gamma$ 是任意一个大于0的常数，故$\left\{x_k\right\}$ 超线性收敛到$x^{\ast }$ 。

5. 数值实验

本小节给出一些数值结果，以表明所提出的非单调线性加权牛顿法对求解多目标优化问题的有效性。实验使用MATLAB2016A软件，使用MATLAB中的FMINCON函数求解子问题从而获取搜索方向。在终止准则为$\left|\theta \left(x_k\right)\right|<{10}^{-3}$ 或最大迭代次数为500的条件下，将本文中的算法2.1与文献[3]中的算法(为方便起见，将文献[3]的算法记为算法2.2)作比较，在同样的参数设置下(具体的参数设置为：$\sigma =0.55$ ，$\mu =0.6$ ，$\rho =0.2$ ，$\eta =0.5$ )，比较两个算法求解同一个多目标优化问题的迭代次数及时间。算法2.1与算法2.2的数值实验结果对比情况如表1所示。

Table 1. Comparison of numerical experimental results between Algorithm 2.1 and Algorithm 2.2

表1. 算法2.1与算法2.2数值实验结果的对比情况

算例名称	初始点$x_0^{\text{T}}$	算法2.1		算法2.2
		迭代次数n	CPU时间t	迭代次数n	CPU时间t
DGO1 [11]	0	4	0.0310	13	0.0870
	π/6	5	0.0421	15	0.0986
	π/9	8	0.0930	18	0.1142
MHHM1 [12]	0	4	0.0511	8	0.0751
	0.3	4	0.0410	11	0.0776
	0.5	3	0.0317	7	0.0509
SSFYY2 [13]	0	3	0.0311	202	1.3550
	−1	4	0.0481	212	1.3723
	−0.25	4	0.0403	215	1.3910
BK1 [14]	(0, 2)	5	0.0368	23	0.2134
	(0, −1)	67	0.4232	500	4.9268
	(−1, 2)	5	0.0485	197	1.9371
LRS1 [15]	(1, 2)	5	0.0362	97	0.6231
	(9, 5)	7	0.0476	420	2.5258
	(−2, 4)	6	0.0422	500	2.9715
MHHM2 [12]	(0.4, 0.1)	4	0.0322	12	0.0836
	(1, 1)	3	0.0267	8	0.0546
	(0.5, 0.2)	4	0.0534	11	0.0797
MOP5 [16]	(1, 2)	52	0.5662	276	3.6353
	(π/6, π/6)	6	0.0617	500	4.6164
	(1, 1.5)	89	0.8493	445	3.8441
PNR [17]	(1, 0.7)	5	0.0828	17	0.1892
	(1.2, 1)	7	0.1264	23	0.2575
	(−1, 1)	7	0.0852	74	0.6424
SP1 [18]	(2, 1)	5	0.0487	12	0.1026
	(−1, 1)	5	0.0569	37	0.3020
	(−3, 0)	6	0.0570	60	0.4823
T5 [19]	(1, 1)	5	0.0986	12	0.1172
	(2, 3)	10	0.1125	47	0.419
	(9, 4)	11	0.1616	57	0.5487
VFM1 [20]	(0.2, 0)	3	0.0297	283	1.8009
	(1, 0.8)	97	0.6974	500	3.2561
	(1, 1)	100	0.6881	500	3.4263
AP4 [21]	(1, 1, 2)	50	0.7091	500	6.3972
	(1, 0.5, 2)	89	1.2459	500	5.5488
	(0.5, 1, 2)	47	0.644	500	6.2969
T8 [19]	(1, 0, 1)	5	0.0921	16	0.2274
	(1, 0, 2)	7	0.1301	374	5.4864
	(2, 0, 5)	10	0.1596	25	0.3842
TRIDIA [10]	(0.1, −0.2, 0.4)	4	0.0770	181	2.8785
	(−0.1, 0.2, 0.5)	66	0.9319	378	5.3868
	(0, 0.1, 0.2)	70	1.1856	355	5.5894
ROSEN BROCK [10]	(0.97, 0.94, 0.99, 0.98)	24	0.6158	258	6.0115
	(1.25, 1.3, 1.35, 1.4)	9	0.2246	25	0.5857
	(2, 1.98, 1.96, 2)	14	0.3259	223	4.8018
SD [22]	(1, $\sqrt{2}$ , $\sqrt{2}$ , $\sqrt{2}$ )	11	0.2120	500	7.1499
	(1, $\sqrt{2}$ , $\sqrt{2}$ , 1)	11	0.1964	500	6.2174
	(1, 1.45, 1.45, 1)	15	0.2960	500	6.1492
Shifted-TRIDIA [10]	(−1, 1, −1, 1)	7	0.1571	326	6.3939
	(0.1, 0.3, 0.2, 0.1)	4	0.0979	78	1.7083
	(−0.4, −0.3, 0.5, 0.5)	96	2.0398	500	9.8446
TOINT [10]	(0, −1, −1, 4)	6	0.0958	25	0.3197
	(−1, −1, 3, 2)	5	0.0841	22	0.2644
	(3, 3, 1, 4)	7	0.1149	30	0.3474
DD1 [23]	(0, 0, 1, 1, 1)	5	0.0416	18	0.2402
	(1, 2, 3, 0, 0)	6	0.0477	85	0.6142
	(0, 2, 2, −1, −1)	5	0.0482	77	0.5736
JOS1 [24]	(0, −1, 1, 0, 0)	4	0.0681	94	2.6891
	(−0.3, 0.2, 0.1, 0.4, 0.5)	67	0.4709	160	1.1145
	(0.3, 0.3, −0.1, 0.8, 0.9)	4	0.0337	85	0.6184

表1列举出了算法2.1和算法2.2关于20个测试问题在不同初始点的数值结果。由表1可知，虽然算法2.1和算法2.2都能求解测试问题，但是算法2.1的数值表现优于算法2.2。在相同的条件下，算法2.1求解多目标优化测试问题的迭代次数以及CPU时间都远小于算法2.2，算法2.1能更高效地求解问题。

6. 结论

本文基于线性加权牛顿算法，结合非单调线性搜索技术，提出了求解无约束多目标优化问题的非单调线性加权牛顿算法(NLWN)。当目标函数二阶连续可微且局部强凸时，证明了由该算法产生的序列局部超线性收敛于多目标优化问题的Pareto最优解。最后，通过数值试验来评估算法的有效性，将它与单调线性加权牛顿算法进行比较，数值结果表明NLWN算法具有较好的数值表现。