求解区间优化问题的一种谱梯度法

A Kind of Spectral Gradient Method for Interval-Valued Optimization Problems

摘要: 本文主要研究区间约束优化问题的求解算法。基于广义Hukuhara导数的Karush-Kuhn-Tucker条件，结合互补结构，利用Fischer-Burmeister函数，将原区间约束优化问题转化为无约束优化问题，并给出一种谱梯度法求解转化后的问题。最后，数值实验验证了算法的有效性。

Abstract: This paper concentrates on designing an algorithm for solving interval constrained optimization problems. Based on the Karush-Kuhn-Tucker conditions utilizing generalized Hukuhara derivatives, and incorporating complementary structure, the Fischer-Burmeister function is employed to transform the original interval constrained optimization problem into an unconstrained one. A spectral gradient method for solving the transformed problem is presented. Numerical experiments verify the effectiveness of this algorithm.

1. 引言

在数学优化领域，学者们对目标函数为区间的优化问题兴趣浓厚，而传统确定性数值估计易致误差，区间方法能有效描述不确定性数据，简化误差处理，而区间优化问题作为集值优化特例，对处理数值精度不足的数据至关重要。在应用方面，区间优化在工程领域具有重要意义，在航空航天、多属性决策、电荷输运等问题中具有广泛应用[1]-[3]。

众多学者深入研究区间优化问题。该问题的求解方法一般分为直接求解和转化法求解两类方法。直接求解法中，一般是定义新的区间序关系，并在此基础上进行直接求解。Inuiguchi等提出基于最大最小遗憾准则的目标区间函数系数规划方法[4]，并通过重复运用单纯性法得到解。Gong等人[5]基于区间可能度定义区间数的优劣关系，定义了基于区间数的拥挤距离，并基于排序关系和拥挤距离选择最优解。在这类方法中，对区间数排序的比较策略依赖性强，不同的比较策略会影响进化算法搜索最优解的性能。而转化法则是通过不同的转化策略将不确定优化问题转化为确定性优化问题，再用现有成熟的确定性方法进行求解。Ishibuchi等引入了区间偏序关系，将不确定区间优化问题转化为多目标确定性优化问题[6]。在文献[7]-[9]中，Wu给出了区间函数及其Pareto最优解定义，并研究多目标区间优化问题的Karush-Kuhn-Tucker最优性条件。Sun等定义区间规划的“LU”最优解，给出Fritz-John和Kuhn-Tucker最优性条件[10]。Villanueva等人研究目标函数为区间值且约束函数为实值的优化问题，提出基于广义Hukuhara次梯度和广义Hukuhara方向导数的最优性条件[11]。

谱梯度法因其几乎对所有初始值都成立以及不需要求解目标函数的Hessian矩阵的优点被广泛使用。谱梯度法的理论雏形最早可回溯至1988年，由Barzilai和Borwein在研究严格凸二次规划问题时首次提出[12]。其创新性核心思想在于：利用原问题矩阵的Rayleigh商与单位矩阵乘积所形成的标量矩阵，构造出一种近似Hessian矩阵的有效策略，进而推导出两种固定形式的步长计算公式，并且证明了对于二维凸二次函数，Barzilai和Borwein法超线性收敛于最优解。数值结果表明Barzilai和Borwein法优于普通的最速下降法，为后续优化算法的发展奠定了关键基础。在1993年，Raydan证明，目标函数为严格凸二次函数时，Barzilai和Borwein法是全局收敛的[13]，而在同样前提下，Dai和Liao于2002年证明了Barzilai和Borwein法是R-线性收敛的[14]。Xiao等人通过考虑一些修正的拟牛顿方程对这种步长选择给出了两个注释，并且给出了另外两种步长选择[15]。

由于问题的复杂性，对区间优化问题有效的求解算法一直较少，并且还没有学者将谱梯度法应用于区间优化问题。本文针对区间优化问题，旨在为区间优化问题的求解提供一种新思路，利用Villanueva等人提出的Karush-Kuhn-Tucker条件，引入线性互补问题概念，利用Fischer-Burmeister函数，将原问题转化为无约束优化问题，结合无约束优化问题的特征，提出一种谱梯度法求解，数值实验验证了转化技术与算法的有效性。

2. 预备知识

令${\mathcal{K}}_C\left(ℝ\right)$ 表示所有实数紧区间的集合。若$C\in {\mathcal{K}}_C\left(ℝ\right)$ ，则$C$ 可表示为$\left[\underset{\_}{c},\overline{c}\right]$ ，其中$\underset{\_}{c}$ 和$\overline{c}$ 分别表示$C$ 的下界和上界。令$d_H$ 表示Pompeiu-Hausdorff距离，定义为：

$d_H\left(C,D\right)=\max \left\{\left|\underset{\_}{c}-\underset{\_}{d}\right|,\left|\overline{c}-\overline{d}\right|\right\}$ ，

其中对任意$C=\left[\underset{\_}{c},\overline{c}\right],D=\left[\underset{\_}{d},\overline{d}\right]\in {\mathcal{K}}_C\left(ℝ\right)$ 。

为简化符号，用$\left[d\vee \overline{d}\right]$ 表示$\left[\min \left\{\underset{\_}{d},\overline{d}\right\},\max \left\{\underset{\_}{d},\overline{d}\right\}\right]$ ，其中$\underset{\_}{d},\overline{d}\in ℝ$ 。

对$\forall C,D\in {\mathcal{K}}_C\left(ℝ\right)$ ，定义如下运算：

1) $C+D=\left\{c+d:c\in C,d\in D\right\}=\left[\underset{\_}{c}+\underset{\_}{d},\overline{c}+\overline{d}\right]$ ；

2) $-C=\left\{-c:c\in C\right\}=\left[-\overline{c},-\underset{\_}{c}\right]$ ；

3) $C-D=\left\{c-d:c\in C且d\in D\right\}=\left[\underset{\_}{c}-\overline{d},\overline{c}-\underset{\_}{d}\right]$；

4) $k+C=\left[\underset{\_}{k}+\underset{\_}{c},\overline{k}+\overline{c}\right]$ ($k$ 为实数，可视为区间$\left[\underset{\_}{k},\overline{k}\right]$ )；

5) $kC=\left[k\underset{\_}{c},k\overline{c}\right]$ 。

由于区间不能像实数一样比较大小，于是给出区间的偏序关系的定义[9] [16]：给定区间$C=\left[\underset{\_}{c},\overline{c}\right]$ 和$D=\left[\underset{\_}{d},\overline{d}\right]\in {\mathcal{K}}_C\left(ℝ\right)$ ，我们称$C{<}_{LU}D$ 当且仅当$\underset{\_}{c}<\underset{\_}{d}$ 且$\overline{c}<\overline{d}$ 。

在区间值优化问题中，区间可用中心–半径形式表示，即$A=\left(a^C,a^R\right)$ ，定义如下：中心$a^C$ 为区间A的上下界的平均值，即：$a^C=\frac{\underset{\_}{a}+\overline{a}}{2}$ ，半径$a^R$ 为上下界差的一半，即：$a^R=\frac{\overline{a}-\underset{\_}{a}}{2}$ 。因此，两种表示方法的转换可表示为：$\underset{\_}{a}=a^C-a^R$ ，$\overline{a}=a^C+a^R$ 。于是，我们可以将区间A表示为中心–半径形式$A=\left(a^C;a^R\right)$ 。

在此背景下，Stefanini和Arana-Jiménez [17]给出了广义Hukuhara可微、广义Hukuhara导数、广义Hukuhara梯度的定义如下：

定义2.1：设函数$F:S\subseteq {ℝ}^n\to {\mathcal{K}}_C$ ，其中：

$F\left(x\right)=\left(f^C\left(x\right);f^R\left(x\right)\right)=\left[f^C\left(x\right)-f^R\left(x\right),f^C\left(x\right)+f^R\left(x\right)\right]$ ，

给定$\delta >0$ ，对$\forall x_0\in S$ ，满足当$\forall h=\left(h_1,\cdots ,h_n\right)\in {ℝ}^n$ ，$\Vert h\Vert <\delta$ 时，有$x_0+h\in S$ 。若存在向量$w^C,w^R\in {ℝ}^n$ ，$w^C=\left(w_1^C,\cdots ,w_n^C\right)$ ，$w^R=\left(w_1^R,\cdots ,w_n^R\right)$ ，以及函数${\epsilon }^C,{\epsilon }^R:{ℝ}^n\to ℝ$ 满足$\underset{h\to 0}{\lim }{\epsilon }^C\left(h\right)=\underset{h\to 0}{\lim }{\epsilon }^R\left(h\right)=0$ ，使得对于所有$h\ne 0$ ，有：

$f^C\left(x_0+h\right)-f^C\left(x_0\right)={\displaystyle \sum _{i=1}^n{w}_i^C}{h}_i+\Vert h\Vert {\epsilon }^C\left(h\right),$

$\left|f^R\left(x_0+h\right)-f^R\left(x_0\right)\right|=\left|{\displaystyle \sum _{i=1}^n{w}_i^R}{h}_i+\Vert h\Vert {\epsilon }^R\left(h\right)\right|.$

则称函数$F$ 在$x_0$ 处广义Hukuhara可微。

定义2.2：$F$ 在$x_0$ 处的广义Hukuhara导数记为$D_{gH}F(x_0):{ℝ}^n\to {\mathcal{K}}_C$ ，定义如下：

$D_{g_H}F\left(x_0\right)\left(h\right)=\left({\displaystyle \sum _{i=1}^n{w}_i^C}{h}_i,\left|{\displaystyle \sum _{i=1}^n{w}_i^R}{h}_i\right|\right),\forall h=\left(h_1,\cdots ,h_n\right)\in {ℝ}^n.$

定义2.3：$F$ 在$x_0$ 处的广义Hukuhara梯度记作${\nabla }_{gH}F\left(x_0\right)$ ，定义为以下$n$ 元组区间：${\nabla }_{gH}F\left(x_0\right)=\left(w_1,\cdots ,w_n\right)$ ，其中每个分量$w_j$ 表示为$w_j=\left(w_j^C;\left|w_j^R\right|\right)$ ，对所有$j\in \left\{1,\cdots ,n\right\}$ 。

定义2.4：对$\forall x\in {ℝ}^n$ ，若满足以下条件：

$x\ge 0,ℒ\left(x\right)\ge 0,x^{\text{T}}ℒ\left(x\right)=0,$

我们称$x$ 和$ℒ$ 互补，其中$ℒ\left(x\right):{ℝ}^n\to {ℝ}^n$ 为连续可微函数。

3. 区间优化问题

本节讨论如下的区间优化问题：

$\begin{array}{l}\text{Minimize}F\left(x\right)=\left[\underset{\_}{f}\left(x\right),\overline{f}\left(x\right)\right]\\ \text{subject to}{g}_j\left(x\right)\ge 0,j\in \left\{1,\cdots ,m\right\},x\in S\subseteq {ℝ}^n,\end{array}$(1)

其中，对每个$j\in \left\{1,\cdots ,m\right\}$ ，都有$g_j:S\to ℝ$ ，且$S$ 为开集。我们用集合$I=\left\{1,\cdots ,m\right\}$ 表示指标集，并定义所有可行点的集合为：

$\mathcal{X}=\left\{x\in S:g_j\left(x\right)\ge 0,\forall j\in I\right\}.$

对于任意可行点$x\in \mathcal{X}$ ，在$x$ 处的有效约束集为：

$I\left(x\right)=\left\{j\in I:g_j\left(x\right)=0\right\}.$

给定$\epsilon >0$ ，$\forall x^{*}\in {ℝ}^n$ 的$\epsilon$ -邻域表示为：

$N_{\epsilon }\left(x^{*}\right)=\left\{x\in {ℝ}^n:\Vert x-x^{*}\Vert <\epsilon \right\}.$

定义3.1：设$x^{*}\in \mathcal{X}$ ，若$\exists \epsilon >0$ ，对$\forall x\in \mathcal{X}\cap N_{\epsilon }\left(x^{*}\right)$ ，都满足$F\left(x\right){\ge }_{LU}F\left(x^{*}\right)$ ，则称$x^{*}$ 为问题的局部弱LU解。

下面介绍Karush-Kuhn-Tucker最优性条件。通常，推导Karush-Kuhn-Tucker条件需要特定的正则性约束条件，我们采用正线性独立约束条件，即Mangasarian-Fromovitz约束条件[18]：

定义3.2：若在可行解$x^{*}\in \mathcal{X}$ 处，不存在全零的非负系数${\beta }_j\ge 0$ ($j\in I\left(x^{*}\right)$ )使得下式成立：

${\displaystyle \sum _{j\in I\left(x^{*}\right)}{\beta }_j}\nabla g_j\left(x^{*}\right)=0_{{ℝ}^n},$

则称问题(1)的约束条件在$x^{*}$ 处满足正线性独立约束条件(PLICQ)。其中，$\nabla g_j\left(x^{*}\right)$ 表示第$j$ 个约束函数在$x^{*}$ 处的梯度。

基于PLICQ以及基于广义Hukuhara微分给出了区间优化问题的Karush-Kuhn-Tucker条件[11]：

定理3.1：设$x^{*}\in \mathcal{X}$ 为问题(3.1)的弱LU解。若问题(1)的约束条件在$x^{*}$ 处满足PLICQ，则存在$\mu ={\left({\mu }_1,\cdots ,{\mu }_m\right)}^{\text{T}}\in {ℝ}^m$ 使得：

$0_{{ℝ}^n}\in {\nabla }_{gH}F\left(x^{*}\right)\oplus {\displaystyle \sum _{j=1}^m{\mu }_j}\nabla g_j\left(x^{*}\right),$ (2)

${\mu }_j{g}_j\left(x^{*}\right)=0,\forall j\in I,$ (3)

${\mu }_j\ge 0,\forall j\in I.$ (4)

显然，KKT条件中的条件(3)和(4)构成一个互补问题：

${\mu }^{\text{T}}g\left(x^{*}\right)=0,\mu \ge 0,g\left(x^{*}\right)\ge 0,$ (5)

其中，$\mu ={\left({\mu }_1,\cdots ,{\mu }_m\right)}^{\text{T}}$ 且$g\left(x\right)={\left(g_1\left(x\right),g_2\left(x\right),\cdots ,g_m\left(x\right)\right)}^{\text{T}}$ 。

针对该问题，采用Fischer-Burmeister (FB)函数[19]。函数$h\left(a,b\right)$ 定义如下：

$h\left(a,b\right)=\left(a+b\right)-\sqrt{a^2+b^2}.$

文献[19]证明了函数$h\left(a,b\right)$ 是全局Lipschitz连续的、定向可微的和强半光滑的。于是函数$h\left(a,b\right)$ 的广义梯度$\partial h\left(a,b\right)$ 可表示为所有$\left({\sigma }_a,{\tau }_b\right)$ 组成的集合

$\left({\sigma }_a,{\tau }_b\right)=\{\begin{array}{ll}\begin{array}{l}\left(1-\frac{a}{\sqrt{a^2+b^2}},1-\frac{b}{\sqrt{a^2+b^2}}\right)\hfill \end{array}\hfill & {\mu }_j\ne 0或g_j\left(x\right)\ne 0,\hfill \\ \left(1-\varsigma ,1-\xi \right)\hfill & {\mu }_j=g_j\left(x\right)=0,\hfill \end{array}$

其中$\left({\sigma }_a,{\tau }_b\right)$ 是满足${\sigma }_a^2+{\tau }_b^2=1$ 的任意向量。

于是，利用以上函数，将(5)转化为：

$H\left(x,\mu \right)=\left(\begin{array}{c}\left({\mu }_1+g_1\left(x\right)\right)-\sqrt{{\mu }_1^2+g_1{\left(x\right)}^2}\\ \left({\mu }_2+g_2\left(x\right)\right)-\sqrt{{\mu }_2^2+g_2{\left(x\right)}^2}\\ ⋮\\ \left({\mu }_m+g_m\left(x\right)\right)-\sqrt{{\mu }_m^2+g_m{\left(x\right)}^2}\end{array}\right)=0.$

设$x\in \mathcal{X}$ ，(5)的解$x^{*}$ 满足$H\left(x^{*},\mu \right)=0$ 。于是，$H\left(x,\mu \right)$ 的广义梯度$\partial H\left(x,\mu \right)$ 可表示为所有$\left({\sigma }_{\mu },{\tau }_g\right)$ 组成的集合：

$\left({\sigma }_{\mu },{\tau }_g\right)=\{\begin{array}{ll}\begin{array}{l}\left(\nabla g_j\left(x\right)-\frac{g_j\left(x\right)\nabla g_j\left(x\right)}{\sqrt{{\left({\mu }_j\right)}^2+{\left(g_j\left(x\right)\right)}^2}},1-\frac{{\mu }_j}{\sqrt{{\left({\mu }_j\right)}^2+{\left(g_j\left(x\right)\right)}^2}}\right)\hfill \end{array}\hfill & {\mu }_j\ne 0或g_j\left(x\right)\ne 0,\hfill \\ \left(1-\varsigma ,1-\xi \right)\hfill & {\mu }_j=g_j\left(x\right)=0,\hfill \end{array}$ (6)

其中$\left({\sigma }_{\mu },{\tau }_g\right)$ 是满足${\sigma }_{\mu }^2+{\tau }_g^2=1$ 的任意向量。

经过上述转化过程，令$z=\left(\begin{array}{c}x\\ \mu \end{array}\right)$ ，则求解问题(1)等价于求解$\varphi \left(z\right)=0$ ，其中：

$\varphi \left(z\right)=\left(\begin{array}{c}W\\ V\end{array}\right).$

其中，$W\in {\nabla }_{gH}F\left(z\right)\oplus {\displaystyle \sum _{j=1}^m{\mu }_j}\nabla g_j\left(z\right)$ ，$V=H\left(z\right)$ ，令$\varphi \left(z\right)$ 的价值函数为$B\left(z\right)=\frac{1}{2}{\Vert \varphi \left(z\right)\Vert }^2$ 。于是，求解区间值优化问题转化为求解如下无约束优化问题：

$\min B\left(z\right).$ (7)

$B\left(z\right)$ 的梯度由下式给出：

$\begin{array}{l}\nabla B\left(z\right)=\nabla \varphi {\left(z\right)}^{\text{T}}\varphi \left(z\right)\\ =\left(\begin{array}{cc}w& v\end{array}\right)\left(\begin{array}{c}W\\ V\end{array}\right),\end{array}$

其中，$w\in {\nabla }_{gH}^{2}f\left(z\right)\oplus {\displaystyle \sum _{j=1}^m{\mu }_j}{\nabla }^2{g}_j\left(z\right)$ ，$v\in \partial H\left(z\right)$ ，$W\in {\nabla }_{gH}F\left(z\right)\oplus {\displaystyle \sum _{j=1}^m{\mu }_j}\nabla g_j\left(z\right)$ ，$V=H\left(z\right)$ ，且$\partial H\left(z\right)$ 由式(6)给出。

4. 谱梯度方法

谱梯度方法(又名两点步长法)是一种重要的梯度类优化算法，其本质可归结为以下迭代过程：

$x_{k+1}=x_k-{\alpha }_k{g}_k.$

在此式中，$g_k$ 表示目标函数$f\left(x\right)$ 在点$x_k$ 处的梯度方向，${\alpha }_k$ 则为沿负梯度方向$-g_k$ 的步长，该方法相较于传统共轭梯度法展现出更为显著的数值收敛优势。

以下基于文献[20]，我们给出了求解问题(7)的谱梯度方法：

算法4.1 (谱梯度方法)：

输入：$x_0\in {ℝ}^n,{\mu }_0\in {ℝ}^m,0<\nu <1,0<{\epsilon }_1<{\epsilon }_2,0<\beta <1$ 。令$z_0=\left(\begin{array}{c}{x}_0\\ {\mu }_0\end{array}\right),\epsilon ={10}^{-5},k=0,{\gamma }_0=1$ 。

步1：计算$\Vert \nabla B\left(z_k\right)\Vert$ ，若$\Vert \nabla B\left(z_k\right)\Vert \le \epsilon$ ，则终止算法，否则转至步2。

步2：计算下降方向$d_k=-\frac{1}{{\gamma }_k}\nabla B\left(z_k\right)$ 。

步3：计算$t_k={\beta }^l$ ，其中$l$ 是满足以下条件的最小非负整数：

$B\left(z_k+t_k{d}_k\right)\le B\left(z_k\right)+\nu t_k\nabla B{\left(z_k\right)}^{\text{T}}{d}_k.$ (8)

步4：令$z_{k+1}=z_k+t_k{d}_k$ ，计算$B\left(z_{k+1}\right)$ 。

步5：计算公式(10)获得${\gamma }_{k+1}$ ，若${\gamma }_{k+1}<{\epsilon }_1$ ，则设${\gamma }_{k+1}={\epsilon }_1$ ；若${\gamma }_{k+1}>{\epsilon }_2$ ，则设${\gamma }_{k+1}={\epsilon }_2$ 。

步6：令$k=k+1$ ，转至步2。

注1：步5的目的是调整上升方向并保持序列$\left\{{\gamma }_k\right\}$ 的一致有界性。事实上，对于所有$k$ ，有：

$0<{\epsilon }_1\le {\gamma }_k\le {\epsilon }_2.$ (9)

注2：为了确定步5中的参数${\gamma }_k$ ，Zhou [20]通过将Dennis和Wolkowicz [21]以及Yuan [22]对拟牛顿方程的修改进行线性组合，得到了参数$\gamma$ 的表达式：设参数$\theta$ 为：$\theta =\frac{\sigma }{\lambda +\sigma }$ ，其中$\lambda +\sigma \ne 0$

${\gamma }_{k+1}\left(\theta \right)=\frac{s_k^{\text{T}}{y}_k+\theta \left[2\left(B\left(z_k\right)-B\left(z_{k+1}\right)\right)+{\left(\nabla B\left(z_k\right)+\nabla B\left(z_{k+1}\right)\right)}^{\text{T}}{s}_k\right]}{s_k^{\text{T}}{s}_k}=\frac{s_k^{\text{T}}{y}_k+\theta {\Delta }_k}{s_k^{\text{T}}{s}_k},$ (10)

其中，${\Delta }_k=2\left(B\left(z_k\right)-B\left(z_{k+1}\right)\right)+{\left(\nabla B\left(z_k\right)+\nabla B\left(z_{k+1}\right)\right)}^{\text{T}}{s}_k$ ，$s_k=z_{k+1}-z_k$ ，$y_k=\nabla B\left(z_{k+1}\right)-\nabla B\left(z_k\right)$ 。

下面讨论${\gamma }_{k+1}\left(\theta \right)$ 的性质：

定理4.1：设$B\left(z\right)$ 充分光滑。若$\Vert s_k\Vert$ 足够小，则有

$s_k^{\text{T}}{\nabla }^{2}B\left(z_{k+1}\right)s_k-{\gamma }_{k+1}\left(\theta \right)s_k^{\text{T}}{s}_k=\left(\frac{1}{2}-\frac{\theta }{6}\right){\nabla }^{3}B\left(z_{k+1}\right)\otimes s_k^3-\left(\frac{1}{6}-\frac{\theta }{12}\right){\nabla }^{4}B\left(z_{k+1}\right)\otimes s_k^4+O\left({\Vert s_k\Vert }^5\right),$ (11)

其中$\otimes$ 为张量积，${\nabla }^{3}B\left(z_{k+1}\right)\in {ℝ}^{n\times n\times n}$ 和${\nabla }^{4}B\left(z_{k+1}\right)\in {ℝ}^{n\times n\times n\times n}$ 是$B\left(z\right)$ 在$z_{k+1}$ 处的张量，满足

${\nabla }^{3}B\left(z_{k+1}\right)\otimes s_k^3={\displaystyle \sum _{i,j,l=1}^n\frac{{\partial }^{3}B\left(z_{k+1}\right)}{\partial z^i\partial z^j\partial z^l}{s}_k^i{s}_k^j{s}_k^l},$ (12)

以及

${\nabla }^{4}B\left(z_{k+1}\right)\otimes s_k^4={\displaystyle \sum _{i,j,l,m=1}^n\frac{{\partial }^{4}B\left(z_{k+1}\right)}{\partial z^i\partial z^j\partial z^l\partial z^m}{s}_k^i{s}_k^j{s}_k^l{s}_k^m}.$ (13)

证明：利用泰勒公式，可得

$B\left(z_k\right)=B\left(z_{k+1}\right)-\nabla B^{\text{T}}\left(z_{k+1}\right)s_k+\frac{1}{2}{s}_k^{\text{T}}{\nabla }^{2}B\left(z_{k+1}\right)s_k-\frac{1}{6}{\nabla }^{3}B\left(z_{k+1}\right)\otimes s_k^3+\frac{1}{24}{\nabla }^{4}B\left(z_{k+1}\right)\otimes s_k^4+O\left({\Vert s_k\Vert }^5\right),$

以及

$\nabla B^{\text{T}}\left(z_k\right)s_k=\nabla B^{\text{T}}\left(z_{k+1}\right)s_k-s_k^{\text{T}}{\nabla }^{2}B\left(z_{k+1}\right)s_k+\frac{1}{2}{\nabla }^{3}B\left(z_{k+1}\right)\otimes s_k^3-\frac{1}{6}{\nabla }^{4}B\left(z_{k+1}\right)\otimes s_k^4+O\left({\Vert s_k\Vert }^5\right).$

由(10)、(12)和(13)式可得

$\begin{array}{l}{s}_k^{\text{T}}{\nabla }^{2}B\left(z_{k+1}\right)s_k-{\gamma }_{k+1}\left(\theta \right)s_k^{\text{T}}{s}_k\\ =s_k^{\text{T}}{\nabla }^{2}B\left(z_{k+1}\right)s_k-s_k^{\text{T}}{y}_k-\theta \left[2\left(B\left(z_k\right)-B\left(z_{k+1}\right)\right)+{\left(\nabla B\left(z_k\right)+\nabla B\left(z_{k+1}\right)\right)}^{\text{T}}{s}_k\right]\\ =\left(\frac{1}{2}-\frac{\theta }{6}\right){\nabla }^{3}B\left(z_{k+1}\right)\otimes s_k^3-\left(\frac{1}{6}-\frac{\theta }{12}\right){\nabla }^{4}B\left(z_{k+1}\right)\otimes s_k^4+O\left({\Vert s_k\Vert }^5\right).\end{array}$

证明完毕。

下面考虑$\theta$ 的几种可能的取值的情况：

当$\theta =0$ 时，有${\gamma }_{k+1}\left(0\right)=\frac{s_k^{\text{T}}{y}_k}{s_k^{\text{T}}{s}_k}$ ，此时${\gamma }_{k+1}$ 的定义与Barzilai和Borwein法的定义相同。由(11)式可得

$s_k^{\text{T}}{\nabla }^{2}B\left(z_{k+1}\right)s_k-{\gamma }_{k+1}\left(0\right)s_k^{\text{T}}{s}_k=\frac{1}{2}{\nabla }^{3}B\left(z_{k+1}\right)\otimes s_k^3-\frac{1}{6}{\nabla }^{4}B\left(z_{k+1}\right)\otimes s_k^4+O\left({\Vert s_k\Vert }^5\right).$

令$\theta =1$ ，此时${\gamma }_{k+1}\left(1\right)=\frac{s_k^{\text{T}}{y}_k+{\Delta }_k}{s_k^{\text{T}}{s}_k}$ ，由(11)式可得

$s_k^{\text{T}}{\nabla }^{2}B\left(z_{k+1}\right)s_k-{\gamma }_{k+1}\left(1\right)s_k^{\text{T}}{s}_k=\frac{1}{3}{\nabla }^{3}B\left(z_{k+1}\right)\otimes s_k^3-\frac{1}{12}{\nabla }^{4}B\left(z_{k+1}\right)\otimes s_k^4+O\left({\Vert s_k\Vert }^5\right).$

令$\theta =3$ ，此时${\gamma }_{k+1}\left(3\right)=\frac{s_k^{\text{T}}{y}_k+3{\Delta }_k}{s_k^{\text{T}}{s}_k}$ 。由(11)式可得

$s_k^{\text{T}}{G}_{k+1}{s}_k-{\gamma }_{k+1}\left(3\right)s_k^{\text{T}}{s}_k=\frac{1}{12}{\nabla }^{4}B\left(z_{k+1}\right)\otimes s_k^4+O\left({\Vert s_k\Vert }^5\right).$

求解如下极小化问题：

$\underset{\theta }{\min }{\left(\frac{1}{2}-\frac{\theta }{6}\right)}^2+{\left(\frac{1}{6}-\frac{\theta }{12}\right)}^2,$

得到$\theta =\frac{14}{5}$ ，并有${\gamma }_{k+1}\left(\frac{14}{5}\right)=\frac{s_k^{\text{T}}{y}_k+\frac{14}{5}{\Delta }_k}{s_k^{\text{T}}{s}_k}$ 。由(11)式可得

$s_k^{\text{T}}{\nabla }^{2}B\left(z_{k+1}\right)s_k-{\gamma }_{k+1}\left(\frac{14}{5}\right)s_k^{\text{T}}{s}_k=\frac{1}{30}{\nabla }^{3}B\left(z_{k+1}\right)\otimes s_k^3+\frac{1}{15}{\nabla }^{4}B\left(z_{k+1}\right)\otimes s_k^4+O\left({\Vert s_k\Vert }^5\right).$

与文献[14]和[20]类似，我们可以得到算法4.1是R-线性收敛的，下面给出算法4.1的收敛性结果，首先给出如下假设。

假设1：水平集$L\left(z_0\right)=\left\{x\in {ℝ}^n|B\left(z\right)\le B\left(z_0\right)\right\}$ 是有界的。

引理4.1：当假设1成立时，并且序列$\left\{d_k\right\}$ 由算法4.1产生，则$d_k$ 满足以下条件：

$\nabla B{\left(z_k\right)}^{\text{T}}{d}_k\le -c_1{\Vert \nabla B\left(z_k\right)\Vert }^2,$ (14)

$\Vert d_k\Vert \le c_2\Vert \nabla B\left(z_k\right)\Vert .$ (15)

其中，$c_1$ 和$c_2$ 是两个正实常数。

证明：先证(15)式：

对算法4.1中的步2两端求范数，可得：

$\Vert d_k\Vert =\frac{1}{{\gamma }_k}\Vert \nabla B\left(z_k\right)\Vert ,$

结合(9)，有：

$0<{\epsilon }_1\le \frac{\Vert \nabla B\left(z_k\right)\Vert }{\Vert d_k\Vert },$

两边同时乘以$\frac{\Vert d_k\Vert }{{\epsilon }_1}$ ，可得：

$\Vert d_k\Vert \le \frac{1}{{\epsilon }_1}\Vert \nabla B\left(z_k\right)\Vert ,$

令$c_2=\frac{1}{{\epsilon }_1}$ 即可。

下面证明(14)式：

对算法4.1中的步2两端左乘$\nabla B{\left(z_k\right)}^{\text{T}}$ ，并在等式两端求范数，可得：

$\Vert \nabla B{\left(z_k\right)}^{\text{T}}{d}_k\Vert =-\nabla B{\left(z_k\right)}^{\text{T}}{d}_k=\frac{1}{{\gamma }_k}{\Vert \nabla B\left(z_k\right)\Vert }^2,$

结合(9)，有：

$-\frac{{\Vert \nabla B\left(z_k\right)\Vert }^2}{\nabla B{\left(z_k\right)}^{\text{T}}{d}_k}\le {\epsilon }_2,$

两端同时乘$\frac{\nabla B{\left(z_k\right)}^{\text{T}}{d}_k}{{\epsilon }_2}$ ，可得

$\nabla B{\left(z_k\right)}^{\text{T}}{d}_k\le -\frac{1}{{\epsilon }_2}{\Vert \nabla B\left(z_k\right)\Vert }^2,$

令$c_1=\frac{1}{{\epsilon }_2}$ 即可。

定理4.2：设$\left\{z_k\right\}$ 是由算法1生成的序列，则下列结论之一成立：

存在某个$k$ 使得$\Vert \nabla B\left(z_k\right)\Vert =0$ ；

序列$\left\{z_k\right\}$ 的每个极限点都是稳定点。

证明：若算法在有限次迭代内终止，即$\left\{z_k\right\}$ 是有限序列，则存在$k$ 使得$\Vert \nabla B\left(z_k\right)\Vert =0$ ，于是由此可得$z_k$ 是$B\left(z\right)$ 的稳定点。

若$\left\{z_k\right\}$ 是无限序列，则存在子列${\left\{z_k\right\}}_{K_1}\subset \left\{z_k\right\}$ 使得：

$\underset{k\in K_1,k\to \infty }{\lim }{z}_k=\tilde{z}.$

根据(8)可知：

$\underset{k\to \infty }{\lim }{t}_k\nabla B{\left(z_k\right)}^{\text{T}}{d}_k=0,$

结合(14)可得：

$\underset{k\to \infty }{\lim }{t}_k{\Vert \nabla B\left(z_k\right)\Vert }^2=0.$

由此可以得到两种情况：

1) 目标函数的梯度满足：

$\underset{k\in K_1,k\to \infty }{\lim }\Vert \nabla B\left(z_k\right)\Vert =0$ .(16)

2) 存在$K_2\subset K_1$ 使得：

$\underset{k\in K_2,k\to \infty }{\lim }{t}_k=0.$

对于上述两种情况，第一种情况下由(16)可知$\nabla B\left({\tilde{z}}_k\right)=0$ 。第二种情况下，根据$t_k$ 的定义，存在$k\ge \tilde{k}$ 且$k\in K_2$ 满足：

$\begin{array}{c}B\left(z_k+\frac{t_k}{\beta }{d}_k\right)>B\left(z_k\right)+\mu \frac{t_k}{\beta }\nabla B{\left(z_k\right)}^{\text{T}}{d}_k\\ =B\left(z_k-\frac{t_k}{\beta {\gamma }_k}\nabla B\left(z_k\right)\right)\\ >B\left(z_k\right)-\mu \frac{t_k}{\beta {\gamma }_k}\nabla B{\left(z_k\right)}^{\text{T}}\nabla B\left(z_k\right).\end{array}$ (17)

其中，$d_k=-\frac{1}{{\gamma }_k}\nabla B\left(z_k\right)$ 。利用泰勒定理展开(17)的左侧并合并同类项，可得：

$o\left(t_k\right)>\left(1-\mu \right)\frac{t_k}{\beta {\gamma }_k}\nabla B{\left(z_k\right)}^{\text{T}}{\nabla }_{gH}{F}_k=\left(1-\mu \right)\frac{t_k}{\beta {\gamma }_k}{\Vert \nabla B\left(z_k\right)\Vert }^2.$ (18)

将(18)两边除以$\left(1-\mu \right)\frac{t_k}{\beta {\gamma }_k}$ ，并令$k\to \infty ,k\in K_2$ ，可得：

${\Vert \nabla B\left({\tilde{z}}_k\right)\Vert }^2\le 0.$

由此可知$\nabla B\left({\tilde{z}}_k\right)=0$ ，这表明$\tilde{z}$ 是稳定点。

5. 数值算例

为验证算法4.1的有效性，本节求解文献[11]中的区间优化问题的数值例子。

算法4.1的终止条件设为$\Vert \nabla B_{\tau }\left(z\right)\Vert \le \epsilon$ 。计算过程在MATLAB (R2023a)上实现，参数设置如下：$\theta =14/5$ ，$\beta =0.5$ ，$\nu =0.4$ ，$\epsilon ={10}^{-3}$ ，${\epsilon }_1=0.01$ ，${\epsilon }_2=100$ 。向量$\mu$ 的初始值的各分量为区间$\left(0,1\right)$ 内的随机数。

在表1中，$x_0$ 表示初始点，$k$ 表示迭代次数，$x^{*}$ 表示最优解，Val表示$B\left(z\right)$ 的值。

例5.1：

$\begin{array}{cc}\min & \left[x_1\vee 2x_2\right]\\ \text{ s}\text{.t}\text{. }& x_1^2-2x_1-x_2\le 0,\\ & x_1^2-2x_1+x_2\le 0,\\ & -x_1+x_2^2\le 0,\\ & \left(x_1,x_2\right)\in S={ℝ}^2.\end{array}$

数值结果如表1及图1所示。

由以上数值算例结果可知，谱梯度法在求解区间优化问题中有较好的数值表现。

6. 总结与展望

本文对区间优化问题的求解算法进行了研究，借助区间优化问题的KKT条件，我们引入了互补问题以及次梯度的概念，利用Fischer-Burmeister函数，将区间优化问题转化为无约束优化问题。根据问题结构我们给出了一类谱梯度算法，并进行了收敛性分析，相关的数值实验结果表明算法的有效性。但是

Table 1. The numerical results of example 5.1

表1. 例5.1的数值结果

$x_0$	$k$	$x^{*}$	Val
${\left(0.5383;0.9961\right)}^{\text{T}}$	46	${\left(1.9168\times {10}^{-6};2.8061\times {10}^{-4}\right)}^{\text{T}}$	$2.9373\times {10}^{-7}$
${\left(0.8173;0.8687\right)}^{\text{T}}$	28	${\left(1.7651\times {10}^{-5};2.1348\times {10}^{-4}\right)}^{\text{T}}$	$3.1067\times {10}^{-7}$
${\left(0.1818;0.2638\right)}^{\text{T}}$	22	${\left(4.2169\times {10}^{-5};1.7796\times {10}^{-4}\right)}^{\text{T}}$	$1.8094\times {10}^{-7}$

Figure 1. Objective function value descent plot of example 5.1

图1. 例5.1的目标函数值下降图

本文主要考虑区间线性优化问题，对于区间非线性优化问题以及其他类型的区间优化问题还需要结合其他求解技术进一步研究。