基于近似一阶信息的改进的加速水平束方法

An Modified Accelerated Level Bundle Method Based on Approximate First Order Information

摘要: 本文提出了一个近似一阶信息的改进的加速水平束方法，该方法结合多步加速策略，引入了三个迭代点序列进行求解，通过引入非欧氏距离代替传统的欧式距离，从而可以充分利用可行集的几何集合，与Lan的方法相比，本文提出的方法仅需求解一个子问题，从而可以减少算法的计算量。最后对所提出的算法进行收敛性分析以及计算相应的迭代复杂度。

Abstract: In this paper, we propose an improved acceleration level bundle method with approximate first-order information, which combines the multistep acceleration strategy and introduces three iterative point sequences to solve, and can make full use of the geometric set of feasible sets by introducing non-Euclidean distances instead of traditional Euclidean distances. Finally, Global convergence of the algorithm is proved and the iterative complexity is analyzed.

1. 引言

本文考虑以下凸优化问题：

$f^{*}:=\underset{x\in X}{\min }f\left(x\right)$ (1.1)

其中 $X\subseteq R^n$ 是非空紧凸集，函数 $f:R^n\to R$ 是一个闭凸函数。假设上述优化问题的解集 $X^{\ast }$ 非空，则对于 $\forall x\in X$ ，目标函数f满足如下不等式：

$$ (1.2)

其中目标函数f在此点的函数值为 $f\left(x\right)$ ，次梯度为 $f^{\prime }\left(x\right)\in \partial f\left(x\right)$ ，且常数 $M>0$ ， $\rho \in \left[0,1\right]$ ， $\Vert \cdot \Vert$ 是定义在 $R^n$ 上的范数， $\langle \cdot ,\cdot \rangle$ 表示相应的内积。当 $\rho =0$ 时，函数 $f\left(x\right)$ 是非光滑函数；当 $\rho =1$ 时，函数 $f\left(x\right)$ 是光滑函数；当 $\rho \in \left(0,1\right)$ 时，函数 $f\left(x\right)$ 是弱光滑函数。文献 [1] [2] [3] [4] 证明了对任意的 $\epsilon >0$ ，任何的一阶算法为找到(1.1)的一个 $\epsilon$ -解，即可以找到一个点p使得 $f\left(p\right)-f^{\ast }\le \epsilon$ ，算法所需要计算f的一阶信息即次梯度的次数无法小于 $O\left(1/{\epsilon }^{\frac{2}{1+3\rho }}\right)$ 。

本文主要讨论水平束类算法，该类算法利是用当前所有迭代点处的函数值和次梯度产生线性化函数，通过对这些线性化函数取最大，产生一系列近似凸多面体称切平面模型，再极小化割平面模型来逼近原目标函数，并利用切平面模型来产生一系列关于最优值 $f^{\ast }$ 的上界和下界，该类方法主要是通过迭代不断压缩上下界的间隙来找到原问题的一个近似解。然而，在很多实际问题中，函数在某点的精确的一阶信息(函数值和次梯度)可能比较难甚至是无法计算。因此，设计有效的算法利用近似的一阶信息求解目标函数并使其具有理论上最优的迭代复杂度的近似算法具有重要的理论意义和实际应用价值。目前，关于近似水平束类算法已经有了很多的研究，梁玲 [5] 提出了非光滑优化基于非精确的加速水平束方法，陈韵梅和张维 [6] 提出了基于近似一阶信息的加速水平束方法，近似解达到了最佳精度以及相应的迭代复杂度。本文主要基于Lan [7] 引入的多步加速策略和采用的非欧式距离函数结合陈韵梅 [6] 提出的基于近似一阶信息的加速水平束方法，提出了基于近似一阶信息的改进的加速水平束方法，简记为“IMAPL”。该方法采用非欧几里得距离代替水平束方法中的欧氏距离，从而可以充分利用可行集的几何结构，大大提高了计算速度。文献 [5] “IAPL”非精确数据的加速邻近水平束方法有效性依赖于两个子问题的求解：第一是为了计算原问题的最优值的下界需要求解一个线性规划问题；第二个是为了更新迭代点需要去求解一个二次规划问题。本文对近似一阶信息的加速邻近水平束方法进行改进，去掉了第一个子问题的求解，第二个子问题用来定义新的迭代点和更新下界，并且可以根据可行集具体的几何结构选择合适的邻近函数。

2. 算法设计

本文采用非精确的一阶信息，即在每一次迭代中，对 $\forall x\in X$ ，产生函数f满足以下条件的近似一阶信息：

$\{\begin{array}{l}{f}_{\delta }\in \left[f\left(x\right)-\delta ,f\left(x\right)\right],\\ g_{\delta }\in {\partial }_{\delta }f\left(x\right).\end{array}$ (2.1)

其中， $f_{\delta }$ 和 $g_{\delta }$ 分别叫做函数f在点x的近似函数值和近似次梯度， ${\partial }_{\delta }f\left(x\right)$ 的定义如下：

${\partial }_{\delta }f\left(x\right)=\left\{g\in R^n:f\left(y\right)\ge f_{\delta }+\langle g,y-x\rangle -\delta ,\forall x\in X\right\}.$ (2.2)

根据(2.1)和f的凸性可以得到

$f(\cdot )\ge f_{\delta }\left(x\right)+\langle g_{\delta }\left(x\right),\cdot -x\rangle -\delta ,f_{\delta }\left(x\right)\in \left[f\left(x\right)-\delta ,f\left(x\right)\right].$ (2.3)

假设目标函数(1.2)的近似一阶信息满足下面条件，即对 $\forall x\in X$ ，函数f在这点的近似一阶信息 $\left(f_{\delta }\left(x\right),g_{\delta }\left(x\right)\right)$ 满足如下不等式：

$f\left(y\right)-f_{\delta }\left(x\right)-\langle g_{\delta }\left(x\right),y-x\rangle \le \frac{L}{2}{\Vert y-x\Vert }^2+\delta ,\forall x,y\in X,$ (2.4)

为了方便算法的描述和定理的证明的需要，下面给出一些基本知识。

定义邻近函数：

$\phi \left(x_0,x\right)=\omega \left(x\right)-\left[\omega \left(x_0\right)+\langle {\omega }^{\prime }\left(x_0\right),x-x_0\rangle \right],\forall x\in X,$ (2.5)

其中，函数 $\omega :R^n\to R$ 是集合X上系数为 ${\sigma }_{\omega }$ 强凸函数， $x_0=\underset{x\in X}{\arg \min }\phi \left(x_0,x\right)$ 为函数 $\phi \left(x_0,x\right)$ 的邻近中心。

记集合X对应于函数 $\omega \left(x\right)$ 的大小为：

$D_{\omega ,X}:=\left\{\omega \left(x\right)-\left[\omega \left(z\right)+\langle \nabla \omega \left(z\right),x-z\rangle \right],\forall x,z\in X\right\},$ (2.6)

记 $L_f\left(l\right):=\left\{x\in X:f\left(x\right)\le l\right\}$ 为函数f在X上的水平集，假如存在一个紧凸集 $X^{\prime }$ ，满足 $L_f\left(l\right)\subseteq X^{\prime }\subseteq X$ ，则称集合 $X^{\prime }$ 为水平集 $L_f\left(l\right)$ 的一个定位器。

定义间隙为：

${\Delta }_k:={\bar{f}}_k-{\underset{\_}{f}}_k$ . (2.7)

根据 ${\Delta }_k$ 的定义易知 ${\Delta }_k$ 是非负的，通过不断压缩间隙 ${\Delta }_k$ ，寻找原问题(1.1)的近似最优解。该算法的主要思想是利用目标函数的近似一阶信息来产生线性化，进而产生最优值 $f^{\ast }$ 的上下界，然后不断压缩上下界的间隙来得到给定精度的最优解，算法由外迭代和内迭代子程序构成，每调用一次内迭代子程序，最优值上下界之间的间隙都会随着减少一个常数倍，下面给出算法的具体步骤：

算法

步骤0 (参数选取) 给定精度 $\epsilon >0$ ，选取参数 $\lambda ,\theta \in \left(0,1\right)$ ，初始模型精度 ${\delta }_0$ 。

步骤1 (初始化) 给定初始点 $p_0\in X$ ，令 $p_1\in \underset{x\in X}{\arg \min }{h}_{{\delta }_0}\left(p_0,x\right)$ ， ${\text{ub}}_1:=\min \left\{f_{{\delta }_0}\left(p_0\right),f_{{\delta }_0}\left(p_1\right)\right\}+{\delta }_0$ ， ${\text{lb}}_1:=h_{{\delta }_0}\left(p_0,p_1\right)$ ，令 $s:=1$ 。

步骤2 (终止准则) 如果 ${\text{ub}}_s-{\text{lb}}_s\le \epsilon$ ，则终止算法，输出近似解 $p_s$ 。

步骤3 (调用子程序) 令 $\left(p_{s+1},{\text{lb}}_{s+1}\right)={\varsigma }_{\text{IMAPL}}\left(p_s,{\text{lb}}_s,\lambda ,\theta ,{\delta }_s\right)$ ， ${\delta }_s$ 为当前模型精度， ${\text{ub}}_{s+1}:=f_{{\delta }_s}\left(p_{s+1}\right)+{\delta }_s$ 。

步骤4 (循环) 令 $s:=s+1$ ，返回步骤2。

注1：(1) $\lambda$ 是在内循环时计算水平参数的一个参数，每当s增加1，算法IMAPL进入下一个阶段，该算法的每一次外迭代主要判断最优值的上下界间隙与给定精度的大小，若间隙大于给定精度，则调用子程序来压缩间隙，否则，终止算法，输出近似最优解。

下面给出算法的内迭代子程序的具体过程，选定一个搜索点p和最优值 $f^{\ast }$ 的下界 $\text{lb}$ ，输出新的搜索点 $p^{\text{+}}$ 和新的下界 ${\text{lb}}^{\text{+}}$ 满足 $f\left(p^{+}\right)-{\text{lb}}^{+}\le q\left[f\left(p\right)-\text{lb}\right]$ ，其中 $q\in \left(0,1\right)$ 且依赖于算法外迭代的输入参数 $\lambda ,\theta$ 。

算法内迭代子程序： $\left(p^{+},{\text{lb}}^{+}\right)={\varsigma }_{\text{IMAPL}}\left(p,\text{lb},\lambda ,\theta ,\delta \right)$ 。

步骤0 (初始化)令 $x_0^u=p$ ， ${\bar{f}}_0:=f\left(x_0^u\right)=\text{ub}$ ， ${\underset{\_}{f}}_0\text{:}=\text{lb}$ ， $l=\lambda {\underset{\_}{f}}_0+\left(1-\lambda \right){\bar{f}}_0$ 。选取 $x_0\in X$ ， ${X^{\prime }}_0=X$ ，考虑由(2.5)定义的邻近函数 $\phi \left(x_0,x\right)$ ，令 $k:=1$ 。

步骤1 (更新割平面模型)令

$x_k^l:=\left(1-{\alpha }_k\right)x_{k-1}^u+{\alpha }_k{x}_{k-1}$ (2.8)

$h_{\delta }\left(x_k^l,x\right):=f_{\delta }\left(x_k^l\right)+\langle g_{\delta }\left(x_k^l\right),x-x_k^l\rangle$ (2.9)

${\underset{\_}{X}}_k:=\left\{x\in {X^{\prime }}_{k-1}:h_{\delta }\left(x_k^l,x\right)\le l\right\}$ (2.10)

步骤2 (更新迭代点和下界)令

$x_k:=\underset{x\in {\underset{\_}{X}}_k}{\arg \min }\phi \left(x_0,x\right)$ (2.11)

若 ${\underset{\_}{X}}_k=\varnothing$ ，则终止程序，输出 $p^{+}=x_{k-1}^u$ ， ${\text{lb}}^{+}=l$ 。

步骤3 (更新上界)令

${\tilde{x}}_k^u:=\left(1-{\alpha }_k\right)x_{k-1}^u+{\alpha }_k{x}_{k-1}$ (2.12)

$x_k^u=\{\begin{array}{l}{\tilde{x}}_k^u如果f_{\delta }\left({\tilde{x}}_k^u\right)+\delta <{\bar{f}}_{k-1},\\ x_{k-1}^u否则,\end{array}$ (2.13)

令 ${\bar{f}}_k:=f_{\delta }\left(x_k^u\right)+\delta$ ，如果 ${\bar{f}}_k\le l+\theta \left({\bar{f}}_0-l\right)$ ，则终止程序，并输出 $p^{+}=x_k^u$ ， ${\text{lb}}^{+}=\text{lb}$ 。

步骤4 (更新定位器)选取任意多面体集 ${X^{\prime }}_k$ 满足 ${\underset{\_}{X}}_k\subseteq {X^{\prime }}_k\subseteq {\bar{X}}_k$ ，其中

${\bar{X}}_k:=\left\{x\in X,\langle \nabla \phi \left(x_0,x_k\right),x-x_k\rangle \ge 0\right\}$ (2.14)

步骤5 (循环)令 $k:=k+1$ ，返回步骤1。

注2：步骤0中初始上下界来自于算法的外循环，水平值是初始上下界的凸组合，是固定不变的；步骤1中为了保证算法有限次终止，算法中步长 $\left\{{\alpha }_k\right\}$ 的选取需要满足一定的条件；该算法在步骤2和步骤3分别有终止出口，当上界有显著下降或者下界有显著上升，则终止内循环；步骤4中定位器的更新是可以任意选取集合 ${X^{\prime }}_k$ 满足 ${\underset{\_}{X}}_k\subseteq {X^{\prime }}_k\subseteq {\bar{X}}_k$ ，我们选取 ${X^{\prime }}_k$ 在这两个集合中间，能够控制(2.10)中约束的数目，减少迭代次数。

引理2.1 对内迭代子程序 ${\varsigma }_{\text{IMAPL}}\left(p,\text{lb},\lambda ,\theta ,\delta \right)$ 由下列结论成立：

(a) ${\left\{{X^{\prime }}_k\right\}}_{k\ge 0}$ 是水平集 $L_f\left(l\right)$ 的定位器，即 $L_f\left(l\right)\subseteq {X^{\prime }}_k$ ， $\forall k\ge 0$ 成立。

(b) 对任意的 $k\ge 1$ ，有 ${\bar{f}}_0\ge {\bar{f}}_1\ge \cdots \ge {\bar{f}}_k\ge f^{\ast }$ 。

(c) 如果 $L_f\left(l\right)\ne \varnothing$ ，则对任意的 $k\ge 1$ ，可以找到 ${X^{\prime }}_k$ 使得 $L_f\left(l\right)\subseteq {\underset{\_}{X}}_k\subseteq {X^{\prime }}_k\subseteq {\bar{X}}_k$ 成立。

(d) 如果 ${\underset{\_}{X}}_k\ne \varnothing$ ，则子问题(2.11)有唯一解。如果程序在步骤2终止，则水平值l为最优值的一个下界，即 $l\le f^{\ast }$ 成立。

证明：(a) 用数学归纳法：

1) 当 $k=0$ 时，显然有 $L_f\left(l\right)\subseteq X={X^{\prime }}_0$ 成立；

2) 假设 $k-1$ 时，有 $L_f\left(l\right)\subseteq {X^{\prime }}_{k-1}$ 成立，往证 $L_f\left(l\right)\subseteq {X^{\prime }}_k$ ；

3) 由 $h_{\delta }$ 的定义(2.9)和f的凸性可知， $h_{\delta }\left(x_k^l,x\right)\le f\left(x\right)\le l$ 成立，结合ii)对 $\forall x\in L_f\left(l\right)$ 有 $x\in {X^{\prime }}_{k-1}$ 且 $h_{\delta }\left(x_k^l,x\right)\le f\left(x\right)\le l$ 成立，根据 ${\underset{\_}{X}}_k$ 的定义(2.10)可得 $L_f\left(l\right)\subseteq {\underset{\_}{X}}_k$ ，又因为 ${\underset{\_}{X}}_k\subseteq {X^{\prime }}_k$ 可知 $L_f\left(l\right)\subseteq {X^{\prime }}_k$ ，综上可知， ${\left\{{X^{\prime }}_k\right\}}_{k\ge 0}$ 是水平集 $L_f\left(l\right)$ 的定位器。

(b) 由内迭代子程序的步骤3可以知道， ${\bar{f}}_k:=\min \left\{{\bar{f}}_{k-1},f_{\delta }\left({\tilde{x}}_k^u\right)+\delta \right\}\le {\bar{f}}_{k-1}$ ，故对任意的 $k\ge 1$ 时，有 $f^{\ast }\le {\bar{f}}_k\le {\bar{f}}_{k-1}\le \cdots \le {\bar{f}}_1\le {\bar{f}}_0$ 。

(c) 由(a)的证明可知， $L_f\left(l\right)\subseteq {\underset{\_}{X}}_k$ 成立，根据子程序的步骤4可知 ${X^{\prime }}_k\ne \varnothing$ ，否则子程序在步骤2终止，下证 ${\underset{\_}{X}}_k\subseteq {\bar{X}}_k$ 成立。

根据子问题(2.11)的一阶最优性条件可知： $0\in \nabla \phi \left(x_0,x_k\right)+N_{{\underset{\_}{X}}_k}\left(x_k\right)$ ，即 $-\nabla \phi \left(x_0,x_k\right)\in N_{{\underset{\_}{X}}_k}\left(x_k\right)$ ，由法锥的定义有 $\langle \nabla \phi \left(x_0,x_k\right),x-x_k\rangle \ge 0$ ， $\forall x\in {\underset{\_}{X}}_k$ 。再根据 ${\bar{X}}_k$ 的定义(2.14)可知，对 $\forall x\in {\underset{\_}{X}}_k$ 有 $x\in {\bar{X}}_k$ ，所以 ${\underset{\_}{X}}_k\subseteq {\bar{X}}_k$ ，即存在 ${X^{\prime }}_k$ 满足 $L_f\left(l\right)\subseteq {\underset{\_}{X}}_k\subseteq {X^{\prime }}_k\subseteq {\bar{X}}_k$ ， $\forall k\ge 1$ 。

(d) 根据 ${\underset{\_}{X}}_k$ 的定义(2.10)和X的紧凸集可知 ${\underset{\_}{X}}_k$ 是紧凸集，又因为 $\phi \left(x_0,x\right)$ 是强凸函数，如果 ${\underset{\_}{X}}_k\ne \varnothing$ ，则子问题(2.11)存在唯一解，如果程序在步骤2终止，那么意味着 ${\underset{\_}{X}}_k=\varnothing$ ，并且根据(a)可知 $L_f\left(l\right)\subseteq {\underset{\_}{X}}_k$ ，所以 $L_f\left(l\right)=\varnothing$ ，于是对 $\forall x\in X$ ，有 $l\le f\left(x\right)$ 成立，从而 $l\le f^{\ast }\le f\left(x\right)$ ， $\forall x\in X$ ，即l是 $f^{\ast }$ 的一个下界。□

为了保证内迭代子程序 ${\varsigma }_{\text{IMAPL}}$ 能够终止且达到最优的迭代复杂度，需要选取合适的步长 $\left\{{\alpha }_k\right\}$ ，Lan在文献 [6] 中给出了序列 $\left\{{\alpha }_k\right\}$ 的一个广义的选取规则。Chen等 [7] 提出了一种更为简洁的选取方法，即序列 $\left\{{\alpha }_k\right\}$ 需要满足如下条件：

${\alpha }_1=1,0<{\alpha }_k\le 1,{\alpha }_k<\frac{C_1}{k},\frac{1-{\alpha }_{k+1}}{{\alpha }_{k+1}^2}\le \frac{1}{{\alpha }_k^2}$ 且 ${\alpha }_k^2{\displaystyle \underset{i=1}{\overset{k}{\sum }}\frac{1}{{\alpha }_i^2}}\le C_{2}k,\forall k\ge 1$ ， (2.15)

其中， $C_1,C_2>0$ 且为常数，下面提供两个具体的 $\left\{{\alpha }_k\right\}$ 的选取的例子，可类似文献 [7] 来验证这两个例子满足(2.15)。

引理2.2 [8] (1) 若选取 ${\alpha }_k=2/\left(k+1\right),k=1,2,\cdots$ ，取 $C_1=2,C_2=2$ ，条件(2.15)满足。(2) 若选取 $\left\{{\alpha }_k\right\}$ 满足以下递归关系：

${\alpha }_1=1,{\alpha }_{k+1}^2=\left(1-{\alpha }_{k+1}\right){\alpha }_k^2,\forall k\ge 1$ ，则当 $C_1=2,C_2=2$ ，条件(2.15)满足。

引理2.3 [7] 当程序 ${\varsigma }_{\text{IMAPL}}$ 终止时，有 $f\left(p^{+}\right)-l{b}^{+}\le q\left(f\left(p\right)-lb\right)$ 。其中，

$q\equiv q\left(\lambda ,\theta \right)=\max \left\{\lambda ,1-\lambda \left(1-\theta \right)\right\}$ (2.16)

注意到 $f\left(p\right)$ 和 $f\left(p^{+}\right)$ 分别表示子程序 ${\varsigma }_{\text{IMAPL}}$ 输入和输出最优值 $f^{\ast }$ 的上界，引理2.3说明了每当程序 ${\varsigma }_{\text{IMAPL}}$ 终止时，最优值 $f^{\ast }$ 的上界和下界的差值总是减少了一个常数倍。

3. 收敛性与复杂度分析

本节将分析IMAPL算法的全局收敛性以及证明该算法终止时总的迭代复杂度。

定理3.1 在 ${\varsigma }_{\text{IMAPL}}$ 中，如果步长 $\left\{{\alpha }_k\right\}$ 满足条件(2.15)，那么对 $\forall K\ge 1$ ，若 ${\varsigma }_{\text{IMAPL}}$ 在第K次迭代没有终止，则下面结论成立：

${\bar{f}}_K-l\le \frac{C_{1}L{D}_{\omega ,X}}{K^2{\sigma }_{\omega }}+2C_{2}K\delta .$ (3.1)

证明：假设内迭代子程序 ${\varsigma }_{\text{IMAPL}}$ 在第 $K\left(>0\right)$ 次迭代没有终止，由(2.10)，(2.11)可知 $x_k\in {\underset{\_}{X}}_k\subseteq X_{k-1}\subseteq {\bar{X}}_{k-1},\forall 2\le k\le K$ ，同时由 $x_1\in {X^{\prime }}_0$ ， $x_0=\underset{x\in {X^{\prime }}_0}{\arg \min }\phi \left(x_0,x\right)$ ，有

$\phi \left(x_0,x\right)\ge \frac{{\sigma }_{\omega }}{2}{\Vert x-x_0\Vert }^2\mathrm{.}$ (3.2)

另外，由 ${\bar{X}}_k$ 的定义有 $\langle \nabla \phi \left(x_0,x_k\right),x-x_k\rangle \ge 0,\forall x\in {\bar{X}}_k$ ，又因为 ${X^{\prime }}_k\subseteq {\bar{X}}_k$ ，显然 $\langle \nabla \phi \left(x_0,x_k\right),x-x_k\rangle \ge 0,\forall x\in {X^{\prime }}_k$ 成立，根据子问题(2.11)可知 $x_{k\text{+}1}\in {\underset{\_}{X}}_{k+1}\subseteq {X^{\prime }}_k$ ，所以 $\langle \nabla \phi \left(x_0,x_k\right),x_{k+1}-x_k\rangle \ge 0$ ，所以结合 $\phi \left(x_0,x\right)$ 的强凸性和子问题的最优性条件可以得到

$\begin{array}{c}\frac{{\sigma }_{\omega }}{2}{\Vert x_k-x_{k-1}\Vert }^2\le \phi \left(x_0,x_k\right)-\phi \left(x_0,x_{k-1}\right)-\langle \nabla \phi \left(x_0,x_{k-1}\right),x_k-x_{k-1}\rangle \\ \le \phi \left(x_0,x_k\right)-\phi \left(x_0,x_{k-1}\right).\end{array}$ (3.3)

所以，

$\begin{array}{c}\frac{{\sigma }_{\omega }}{2}{\displaystyle \underset{i=1}{\overset{k}{\sum }}{\Vert x_i-x_{i-1}\Vert }^2}\le \phi \left(x_0,x_k\right)-\phi \left(x_0,x_0\right)\\ \le \phi \left(x_0,x_k\right)\\ =\underset{y\in X}{\max }\phi \left(x_0,y\right)\\ \le \underset{x,y\in X}{\max }\phi \left(x,y\right)\\ =D_{\omega ,X}.\end{array}$ (3.4)

由 ${\bar{f}}_k$ 的定义及(2.4)和(2.12)即知对 $\forall k\ge 1$ ，有

${\bar{f}}_k=f_{\delta }\left(x_k^u\right)+\delta =f_{\delta }\left({\tilde{x}}_k^u\right)+\delta \le f\left({\tilde{x}}_k^u\right)+\delta$

$\le f_{\delta }\left(x_k^l\right)+\langle g_{\delta }\left(x_k^l\right),{\tilde{x}}_k^u-x_k^l\rangle +\frac{L}{2}{\Vert {\tilde{x}}_k^u-x_k^l\Vert }^2+2\delta$ 由(2.4)

$\begin{array}{l}=\left(1-{\alpha }_k\right)\left[f_{\delta }\left(x_k^l\right)+\langle g_{\delta }\left(x_k^l\right),x_{k-1}^u-x_k^l\rangle \right]+{\alpha }_k\left[f_{\delta }\left(x_k^l\right)+\langle g_{\delta }\left(x_k^l\right),x_k-x_k^l\rangle \right]\\ +\frac{L{\alpha }_k^2}{2}{\Vert x_k-x_{k-1}\Vert }^2+2\delta \end{array}$ 由(2.12)

$\le \left(1-{\alpha }_k\right)f\left(x_{k-1}^u\right)+{\alpha }_{k}l+\frac{L{\alpha }_k^2}{2}{\Vert x_k-x_{k-1}\Vert }^2+2\delta$ 由(2.3)和(2.10)

$\le \left(1-{\alpha }_k\right)\left[f_{\delta }\left(x_{k-1}^u\right)+\delta \right]+{\alpha }_{k}l+\frac{L{\alpha }_k^2}{2}{\Vert x_k-x_{k-1}\Vert }^2+2\delta$ 由(2.1)

$=\left(1-{\alpha }_k\right){\bar{f}}_{k-1}+{\alpha }_{k}l+\frac{L{\alpha }_k^2}{2}{\Vert x_k-x_{k-1}\Vert }^2+2\delta .$ 由 ${\bar{f}}_k$ 的定义

对上式两边都减去l可得

${\bar{f}}_k-l\le \left(1-{\alpha }_k\right)\left({\bar{f}}_{k-1}-l\right)+\frac{L{\alpha }_k^2}{2}{\Vert x_k-x_{k-1}\Vert }^2+2\delta$ (3.5)

对式(3.5)两边都除以 ${\alpha }_k^2$ 可得

$\frac{{\bar{f}}_k-l}{{\alpha }_k^2}\le \frac{1-{\alpha }_k}{{\alpha }_k^2}\left({\bar{f}}_{k-1}-l\right)+\frac{L}{2}{\Vert x_k-x_{k-1}\Vert }^2+\frac{2\delta }{{\alpha }_k^2}$ (3.6)

当 $k=1$ 时， ${\alpha }_1=1$ ，上式(3.6)为

$\frac{{\bar{f}}_1-l}{{\alpha }_1^2}\le \frac{L}{2}{\Vert x_1-x_0\Vert }^2+\frac{2\delta }{{\alpha }_1^2}$ (3.7)

对 $\forall k>1$ ，由(2.15)知 $\frac{1-{\alpha }_{k+1}}{{\alpha }_{k+1}^2}\le \frac{1}{{\alpha }_k^2}$ ，上式(3.6)为

$\frac{{\bar{f}}_k-l}{{\alpha }_k^2}\le \frac{1}{{\alpha }_{k-1}^2}\left({\bar{f}}_{k-1}-l\right)+\frac{L}{2}{\Vert x_k-x_{k-1}\Vert }^2+\frac{2\delta }{{\alpha }_k^2}$ (3.8)

对(3.8)从1到K求和再与(3.7)求和，有

$\frac{{\bar{f}}_K-l}{{\alpha }_K^2}\le \frac{L}{2}{\displaystyle \underset{i=1}{\overset{K}{\sum }}{\Vert x_k-x_{k-1}\Vert }^2+2\delta {\displaystyle \underset{i=1}{\overset{K}{\sum }}\frac{1}{{\alpha }_i^2}}}$

所以， ${\bar{f}}_K-l\le \frac{L{\alpha }_K^2}{2}{\displaystyle \underset{i=1}{\overset{K}{\sum }}{\Vert x_i-x_{i-1}\Vert }^2}+2\delta {\alpha }_K^2{\displaystyle \underset{i=1}{\overset{K}{\sum }}\frac{1}{{\alpha }_i^2}}$ ，结合(2.15)和(3.4)可得

${\bar{f}}_K-l\le \frac{C_{1}L{D}_{\omega ,X}}{K^2{\sigma }_{\omega }}+2C_{2}K\delta$

□

由上述定理，我们已经得到了 ${\bar{f}}_K-l$ 上界的一个估计，下面的定理将使用该估计来进一步计算子程序 ${\varsigma }_{\text{IMAPL}}$ 满足步骤3中终止条件所需要的迭代次数。由于加速一阶算法无法避免受到误差累积效应的影响，在L、R和 $\delta$ 固定的情况下， ${\bar{f}}_K-l$ 并不能无限递减至零，而是存在着一个关于这些参数的一个最小值，以下定理说明了，在 $\delta$ 满足一定的条件下，内迭代子程序 ${\varsigma }_{\text{IMAPL}}$ 的迭代次数有一个上界。

定理3.2 在 ${\varsigma }_{\text{IMAPL}}$ 中，如果步长 $\left\{{\alpha }_k\right\}$ 满足条件(2.15)，且 $\delta$ 满足如下条件

$\delta \le {\delta }_{\Delta }:=\frac{{\left(\frac{1}{3}\lambda \theta \Delta \right)}^{\frac{3}{2}}\sqrt{{\sigma }_{\omega }}}{\sqrt{L{D}_{\omega ,X}}{C}_1{C}_2}$ (3.9)

其中，根据间隙的定义(2.7)， $\Delta$ 表示每次调用 ${\varsigma }_{\text{IMAPL}}$ 时输入的上界和下界的差值，即 $\Delta =ub-lb$ ，则内迭代子程序的迭代次数不超过

$K\left(\Delta \right):=\frac{C_1}{\sqrt{\frac{\lambda \theta }{3}}}\cdot \sqrt{\frac{L{D}_{\omega ,X}}{\Delta {\sigma }_{\omega }}}+1$ (3.10)

证明：由(3.1)结合 $\delta \le {\delta }_{\Delta }$ 可得，

${\bar{f}}_K-l\le \frac{C_{1}L{D}_{\omega ,X}}{K^2{\sigma }_{\omega }}+2C_{2}K\delta \le \frac{C_{1}L{D}_{\omega ,X}}{K^2{\sigma }_{\omega }}+2C_{2}K{\delta }_{\Delta }$ (3.11)

不等式右边达到最小时

$K={\left(\frac{C_1^{2}L{D}_{\omega ,X}}{C_2{\delta }_{\Delta }{\sigma }_{\omega }}\right)}^{\frac{1}{3}}$ (3.12)

将式(3.12)代入式(3.11)可得

${\bar{f}}_k-l\le \frac{C_1^{2}L{D}_{\omega ,X}}{{\left(\frac{C_1^{2}L{D}_{\omega ,X}}{C_2{\delta }_{\Delta }{\sigma }_{\omega }}\right)}^{\frac{2}{3}}{\sigma }_{\omega }}+2C_2{\left(\frac{C_1^{2}L{D}_{\omega ,X}}{C_2{\delta }_{\Delta }{\sigma }_{\omega }}\right)}^{\frac{1}{3}}{\delta }_{\Delta }$

解得， ${\delta }_{\Delta }\le \frac{{\left(\frac{1}{3}\lambda \theta \Delta \right)}^{\frac{3}{2}}\sqrt{{\sigma }_{\omega }}}{\sqrt{L{D}_{\omega ,X}}{C}_1{C}_2}$ 。

因此(3.11)右边达到最小时，

$K^{\ast }:={\left(\frac{C_1^{2}L{D}_{\omega ,X}}{C_2{\delta }_{\Delta }{\sigma }_{\omega }}\right)}^{\frac{1}{3}}=\frac{C_1}{\sqrt{\frac{\lambda \theta }{3}}}\cdot \sqrt{\frac{L{D}_{\omega ,X}}{\Delta {\sigma }_{\omega }}}$

因此有

${\bar{f}}_{K^{\ast }}-l\le {\left(3C_1{C}_2{\delta }_{\Delta }\right)}^{\frac{2}{3}}{\left(\frac{L{D}_{\omega ,X}}{{\sigma }_{\omega }}\right)}^{\frac{1}{3}}=\lambda \theta \Delta$ (3.13)

观察内迭代子程序步骤3中终止条件 ${\bar{f}}_k\le l+\theta \left({\bar{f}}_0-l\right)$ 和水平值l的定义可知，

${\bar{f}}_k-l\le \theta \left({\bar{f}}_0-l\right)=\theta \lambda \left({\bar{f}}_0-{\underset{\_}{f}}_0\right)=\theta \lambda \left(ub-lb\right)=\theta \lambda \Delta$ (3.14)

即步骤3的终止条件等价于(3.14)，因此，由(3.13)可知，至少在第 $K^{\ast }$ 次迭代后内循环终止。所以，内循环或者在满足步骤2中终止条件时提前终止或者最多在第 $K^{\ast }$ 次迭代后满足步骤3中终止条件而终止，即内循环的迭代次数的上界 $K\left(\Delta \right)=K^{\ast }+1$ 。 □

以下定理讨论算法的收敛性和迭代复杂度。

定理3.3 对于任意给定的 $\epsilon >0$ ，如果算法中步长 $\left\{{\alpha }_k\right\}$ 选取满足条件(2.15)，且对于任意的 $s\ge 1$ 均有 ${\delta }_s\le {\delta }_{{\Delta }_s}$ ，其中 ${\delta }_{{\Delta }_s}$ 在(3.9)中定义，则算法将收敛到(1.1)的一个 $\epsilon$ 解，且以下结论成立：

1) 调用内循环的次数不超过

$S\left(\epsilon \right):=\lceil \max \left\{0,{\log }_{\frac{1}{q}}\frac{D_{\omega ,X}L+2{\delta }_0{\sigma }_{\omega }}{\epsilon {\sigma }_{\omega }}\right\}\rceil$ (3.15)

2) IMAPL算法总的迭代次数不找过

$S\left(\epsilon \right)+\frac{\sqrt{3}{C}_1\sqrt{L{D}_{\omega ,X}}}{\sqrt{\lambda \theta {\sigma }_{\omega }\epsilon }}\cdot \frac{1}{1-\sqrt{q}}$ (3.16)

证明：(1) 观察算法IMAPL的步骤1，并结合 $f_{{\delta }_0}\left(p_1\right)\le f\left(p_1\right)$ 和(2.4)容易得到

${\Delta }_1={\text{ub}}_1-{\text{lb}}_1$ 由(2.7)

$\le f_{{\delta }_0}\left(p_1\right)+{\delta }_0-h_{{\delta }_0}\left(p_0,p_1\right)$ 由 ${\text{ub}}_1,{\text{lb}}_1$ 的定义

$\le \frac{L}{2}{\Vert p_0-p_1\Vert }^2+2{\delta }_0$ 由(2.4)

$\le \frac{L{D}_{\omega ,X}}{{\sigma }_{\omega }}+2{\delta }_0$ 由(3.4)

同时，根据引理3.2可知， ${\Delta }_{s+1}\le q{\Delta }_s$ ， $\forall s\ge 1$ ，根据递推关系可以得到

${\Delta }_{s+1}\le q{\Delta }_s\le q^2{\Delta }_{s-1}\le \cdots \le q^s{\Delta }_1$ ， $\forall s\ge 1$ (3.17)

容易看都 ${\left\{{\Delta }_s\right\}}_{s=1}^{\infty }$ 几何级数递减并必将最终小于 $\epsilon$ ，因此可以假设在第 $S\left(\epsilon \right)$ 次调用 ${\varsigma }_{\text{IMAPL}}$ 后首次得到一个 $\epsilon$ 解，即算法在 $s:=S\left(\epsilon \right)+1$ 时终止，则

${\Delta }_{S\left(\epsilon \right)+1}\le \epsilon <{\Delta }_{S\left(\epsilon \right)}$ (3.18)

结合 ${\Delta }_1\le \frac{L{D}_{\omega ,X}}{{\sigma }_{\omega }}+2{\delta }_0$ 和(3.17)可以得到，

$\epsilon <q^{S\left(\epsilon \right)-1}{\Delta }_1\le q^{S\left(\epsilon \right)-1}\left(\frac{L{D}_{\omega ,X}}{{\sigma }_{\omega }}+2{\delta }_0\right)$ (3.19)

因此，

${\left(\frac{1}{q}\right)}^{S\left(\epsilon \right)-1}\le \frac{D_{\omega ,X}L+2{\delta }_0{\sigma }_{\omega }}{{\sigma }_{\omega }\epsilon }$

即，

$S\left(\epsilon \right)=\lceil \max \left\{0,{\log }_{\frac{1}{q}}\frac{D_{\omega ,X}L+2{\delta }_0{\sigma }_{\omega }}{{\sigma }_{\omega }\epsilon }\right\}\rceil$

(2) 假设IMAPL算法已经调用了 $S\left(\epsilon \right)$ 次子程序，对于 $1\le s\le S\left(\epsilon \right)$ ，根据(3.17)、(3.18)可得

$\epsilon <{\Delta }_{S\left(\epsilon \right)}\le q{\Delta }_{S\left(\epsilon \right)-1}\le q^2{\Delta }_{S\left(\epsilon \right)-2}\le \cdots \le q^{S\left(\epsilon \right)-s}{\Delta }_s$

即

${\Delta }_s\ge \epsilon q^{s-S\left(\epsilon \right)}$ ， $s=1,2,\cdots ,S(\; \epsilon \; )$

则

${\displaystyle \underset{s=1}{\overset{S\left(\epsilon \right)}{\sum }}{\Delta }_s^{-\frac{1}{2}}}<{\displaystyle \underset{s=1}{\overset{S\left(\epsilon \right)}{\sum }}{\epsilon }^{-\frac{1}{2}}{q}^{\frac{S\left(\epsilon \right)-s}{2}}}={\displaystyle \underset{t=0}{\overset{S\left(\epsilon \right)-1}{\sum }}{\epsilon }^{-\frac{1}{2}}{q}^{\frac{t}{2}}}\le \frac{1}{\sqrt{\epsilon }\left(1-\sqrt{q}\right)}$

结合引理2.1和(3.10)，将调用子程序的所有迭代次数相加，得到算法IMAPL的总迭代次数不超过

$\begin{array}{c}{\displaystyle \underset{s=1}{\overset{S\left(\epsilon \right)}{\sum }}{K}_s}\le {\displaystyle \underset{s=1}{\overset{S\left(\epsilon \right)}{\sum }}K\left({\Delta }_s\right)}\le S\left(\epsilon \right)+{\displaystyle \underset{s=1}{\overset{S\left(\epsilon \right)}{\sum }}\frac{C_1}{\sqrt{\frac{\lambda \theta }{3}}}}\cdot \sqrt{\frac{L{D}_{\omega ,X}}{{\Delta }_s{\sigma }_{\omega }}}\\ \le S\left(\epsilon \right)+\frac{\sqrt{3}{C}_1\sqrt{L{D}_{\omega ,X}}}{\sqrt{\lambda \theta {\sigma }_{\omega }\epsilon }}\cdot \frac{1}{1-\sqrt{q}}.\end{array}$

其中， $K_s$ 表示算法第s次调用子程序时的迭代次数。

4. 结束语

本文提出了一个近似一阶信息的改进的加速水平束方法，该方法结合多步加速策略，引入了三个迭代点序列进行求解，并且通过引入邻近函数代替传统的欧式距离，进而充分利用可行集的几何集合，加快算法的收敛速度，并且与文献 [5] [6] 相比，减少了一个子问题的求解，从而可以减少算法的计算量。最后证明了算法的全局收敛性并分析了迭代复杂度。