非光滑约束优化基于非精确数据的改进水平束方法

A Modified Level Bundle Method with Inexact Data for Nonsmooth Constrained Optimization

摘要: 本文提出了一个求解非光滑约束优化问题基于非精确数据的改进水平束方法。该方法引入了非精确数据及相应的近似改进函数。此外，通过在投影子问题中引入Bregman距离以代替传统的欧氏距离，从而可以充分利用可行集的几何集合，减少算法的计算量。最后证明了算法的全局收敛性并分析了迭代复杂度。

Abstract: This paper presents a modified level bundle method with inexact data for nonsmooth constrained optimization. In the method, the inexact data and the approximate improvement function are in-troduced. Moreover, in the projection subproblem, the Bregman distance is used to replace the classical Euclidean distance, in order that the geometric structure of the feasible set can be taken into account, which can reduce the computation of the algorithm. Global convergence of the algo-rithm is proved and the iterative complexity is analyzed.

1. 引言

本文研究求解以下非光滑约束凸优化问题:

$\begin{array}{l}{f}^{\ast }:=\min f\left(x\right)\\ \text{s}\text{.t}\text{.}c\left(x\right)\le 0,\\ x\in X,\end{array}$ (1)

其中， $f,c$ 均为上的非光滑凸函数， $X\subseteq R^n$ 为非空紧凸集。

束方法是求解一般非光滑优化问题最有效的方法之一。求解约束问题(1)的束方法可细分为罚函数法 [1] ，滤子法 [2] ，改进函数法 [3] 等。罚函数法的基本思想是在目标函数中增加一个惩罚项，从而构造出新的目标函数，通过求罚函数的最优解得到原问题的最优解。但是在具体的算法实现中，罚参数选取较困难，如果选取不当，则导致算法效率较差，为避免罚参数的选取问题，Fletcher和Leyffer [4] 提出了滤子法来求解约束优化问题，其基本思想是当目标函数或者约束函数值有一个减少时，迭代点将被滤子接收。但滤子法的缺点是算法结构复杂，理论分析难度较大。为此，本文将基于改进函数法思想研究相应的水平束方法。考虑如下改进函数：

$h\left(x;f^{\ast }\right)=\max \left\{f\left(x\right)-f^{\ast },c\left(x\right)\right\}.$ (2)

从而求解问题(1)转化为在X上极小化改进函数(2)。但是在实际问题中最优值 $f^{\ast }$ 通常是不知道的，Lemaréchal等 [3] 提出了用最优值 $f^{\ast }$ 的下界 $f_{\text{low}}^k$ 近似替代 $f^{\ast }$，并通过算法的不断迭代，使得产生下界序列逼近最优解。Ackooij和De Oliveira [5] 基于改进函数(2)提出了一种限制存储信息的水平束方法，确保每一步迭代计算量较小且不影响算法的收敛性。

文献 [5] 中的投影子问题采用了传统的欧氏距离，为了充分利用可行集的几何结构，本文将利用Bregman距离代替传统的欧氏距离。此前，Kiwiel [6] 在邻近束方法中引入Bregman距离代替二次项，提出基于Bregman距离函数的邻近束方法。Ben-Tal和Nemirovski [7] 提出了非欧氏限制存储的水平束方法，可以根据可行集的几何结构选取合适的邻近函数。

另一方面，在很多实际问题中，往往很难精确计算函数值和次梯度，或者计算成本较高。因此，设计基于非精确数据的有效算法具有重要的理论意义和实用价值。最近，梁玲 [8] 提出了非光滑优化基于非精确的加速水平束方法。陈韵梅和张维 [9] 提出了基于近似一阶信息的加速水平束方法，并分析了算法的一致最优迭代复杂度。

本文针对非光滑约束优化问题(1)，对文 [5] 的工作进行改进和推广，提出了基于非欧氏距离的非精确约束水平束方法。该方法能够有效处理非精确数据，并且通过引入Bregman距离代替传统的欧氏距离，在计算时能充分利用可行集的几何结构，选取合适的邻近函数，提升计算效率。该方法利用多面体模型近似原问题的目标函数和约束函数，并引入非精确的改进函数作为近似最优性判别函数。最后证明了算法的全局收敛性并分析了迭代复杂度。

2. 算法设计

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

$\{\begin{array}{l}f\left(x\right)\ge f_x\ge f\left(x\right)-{\epsilon }_f^x,{\tilde{g}}_f^x\in {\partial }_{{\epsilon }_f^x}f\left(x\right),\\ c\left(x\right)\ge c_x\ge c\left(x\right)-{\epsilon }_c^x,{\tilde{g}}_c^x\in {\partial }_{{\epsilon }_c^x}c\left(x\right),\end{array}$ (3)

其中， $f_x,c_x,{\tilde{g}}_f^x$ 和 ${\tilde{g}}_c^x$ 分别表示函数 $f,c$ 在点x的近似函数值和近似次梯度，误差 ${\epsilon }_f^x,{\epsilon }_c^x\ge 0$， $\delta$ -次微分 ${\partial }_{\delta }f\left(x\right)$ 定义如下：

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

根据(3)可得

$f(\cdot )\ge f\left(x\right)+\langle {\tilde{g}}_f^x,\cdot -x\rangle -{\epsilon }_f^x,c(\cdot )\ge c\left(x\right)+\langle {\tilde{g}}_c^x,\cdot -x\rangle -{\epsilon }_c^x.$

假设每一个估计的误差都是有界的，即存在常数 ${\eta }_f,{\eta }_c\ge 0$ 使得

${\epsilon }_f^x\le {\eta }_f,{\epsilon }_c^x\le {\eta }_c,\forall x\in X.$

为简便，分别用 ${\tilde{g}}_f^k,{\tilde{g}}_c^k$ 表示函数 $f,c$ 在 $x^k$ 处的近似次梯度， ${\epsilon }_f^k,{\epsilon }_c^k$ 表示相应的误差。定义邻近函数：

$\phi \left(x;\hat{x}\right):=\omega \left(x\right)-\omega \left(\hat{x}\right)-\langle \nabla \omega \left(\hat{x}\right),x-\hat{x}\rangle ,$

其中，函数 $\omega :R^n\to R$ 是集合X上系数为 ${\sigma }_{\omega }>0$ 可微强凸函数，即

$\omega \left(y\right)\ge \omega \left(x\right)+\langle \nabla \omega \left(x\right),y-x\rangle +\frac{{\sigma }_{\omega }}{2}{\Vert y-x\Vert }^2,\forall x,y\in X.$

易知， $\phi \left(x;\hat{x}\right)\ge 0$， $\phi \left(\hat{x};\hat{x}\right)=0$ 及

$\langle \nabla \omega \left(x\right)-\nabla \omega \left(z\right),x-z\rangle \ge {\sigma }_{\omega }{\Vert x-z\Vert }^2,\forall x,z\in X.$

在实际计算中，可根据X的特殊结构选择适当的 $\omega \left(x\right)$，以提高计算效率。

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

$D_{\omega ,X}^2:=\max \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\}.$ (4)

因此，可以得到

${\Vert x-z\Vert }^2\le \frac{2}{{\sigma }_{\omega }}{D}_{\omega ,X}^2=:{\Omega }_{\omega ,X},\forall x,z\in X.$ (5)

根据函数的非精确信息，定义近似线性化函数：

$\{\begin{array}{l}{l}_f^k(\cdot ):=f_{x^k}+\langle {\tilde{g}}_f^k,\cdot -x^k\rangle ,\\ l_c^k(\cdot ):=c_{x^k}+\langle {\tilde{g}}_c^k,\cdot -x^k\rangle .\end{array}$

由函数的凸性可得 $l_f^k(\cdot )\le f(\cdot )$， $l_c^k(\cdot )\le c(\cdot )$，并且在点 $x^k$ 处有 $l_f^k\left(x^k\right)=f_{x^k}$， $l_c^k\left(x^k\right)=c_{x^k}$ 成立。定义函数 $f\left(x\right),c\left(x\right)$ 在第k次迭代的多面体模型：

${\hat{f}}^k\left(x\right):=\underset{j\in J_f^k}{\max }{l}_f^j\left(x\right),{\hat{c}}^k\left(x\right):=\underset{j\in J_c^k}{\max }{l}_c^j\left(x\right),$

其中， $J_f^k,J_c^k\subseteq \left\{1,\cdots ,k\right\}$ 分别是线性化函数 $l_f^j\left(x\right),l_c^j\left(x\right)$ 对应的某些迭代指标构成的集合。根据多面体模型的定义可以得到：

(6)

设 $f_{\text{low}}^k\left(\le f^{*}\right)$ 是问题最优值的一个下界，定义非精确改进函数如下：

$\tilde{h}\left(x;f_{\text{low}}^k\right)=\max \left\{f_x-f_{\text{low}}^k,c_x\right\}.$ (7)

用以上函数作为近似最优性判别函数，并采用如下方式记录改进函数当前的最小值和相应的迭代点：

$h_{\text{rec}}^k:=\{\begin{array}{l}\tilde{h}\left(x^0;f_{\text{low}}^0\right),k=0,\\ \min \left\{\underset{j\in J_f^k\cap J_c^k}{\min }\tilde{h}\left(x^j;f_{\text{low}}^k\right),h_{\text{rec}}^{k-1}\right\},k>0,\end{array}$ (8)

$x_{\text{rec}}^k\in {\left\{x^j\right\}}_{j\le k}\text{s}\text{.t}\text{.}\tilde{h}\left(x_{\text{rec}}^k;f_{\text{low}}^j\right)=h_{\text{rec}}^k,$ (9)

由(8)和(9)易知 $\left\{h_{\text{rec}}^k\right\}$ 是单调不增的序列。

设 $f_{\text{lev}}^k$ 为当前水平值，采用上述邻近函数代替欧氏距离，本文算法每次迭代求解如下子问题：

$x^{k+1}:=\arg \underset{x\in X^k}{\min }\phi \left(x;{\hat{x}}^k\right),$ (10)

其中， ${\hat{x}}^k$ 为当前稳定中心，水平集 $X^k$ 定义如下：

$X^k:=\left\{x\in X:{\hat{f}}^k\left(x\right)\le f_{\text{lev}}^k,{\hat{c}}^k\left(x\right)\le 0\right\}.$ (11)

以下引理启发了下界 $f_{\text{low}}^k$ 的一个更新规则：当 $X^k$ 是空集时，可用当前的水平值 $f_{\text{lev}}^k$ 来更新下界，即令 $f_{\text{low}}^k=f_{\text{lev}}^k$。

引理1 [5] ：如果水平集 $X^k$ 是空集，则水平值 $f_{\text{lev}}^k$ 是问题(1)的最优值的下界。

下面将给出子问题(10)的最优解的一些重要性质，其证明是文献 [5] 命题1的推广。

命题1：假设约束规格 $X^k\cap riX\ne \varnothing$ 成立，则 $x^{k+1}$ 为子问题(10)最优解的充要条件是 $x^{k+1}\in X$， ${\hat{f}}^k\left(x^{k+1}\right)\le f_{\text{lev}}^k$， ${\hat{c}}^k\left(x^{k+1}\right)\le 0$，并且存在向量 $s^k\in N_X\left(x^{k+1}\right)$， ${\hat{g}}_f^k\in \partial {\hat{f}}^k\left(x^{k+1}\right)$， ${\hat{g}}_c^k\in \partial {\hat{c}}^k\left(x^{k+1}\right)$ 和 ${\mu }_f^k,{\mu }_c^k\ge 0$ 使得

$\nabla \phi \left(x^{k+1};{\hat{x}}^k\right)+s^k+{\mu }_f^k{\hat{g}}_f^k+{\mu }_c^k{\hat{g}}_c^k=0,{\mu }_f^k\left({\hat{f}}^k\left(x^{k+1}\right)-f_{\text{lev}}^k\right)=0,{\mu }_c^k{\hat{c}}^k\left(x^{k+1}\right)=0.$ (12)

此外，聚集线性化

${\bar{f}}^{a_k}\left(x\right):={\hat{f}}^k\left(x^{k+1}\right)+\langle {\hat{g}}_f^k,x-x^{k+1}\rangle$ 满足 ${\bar{f}}^{a_k}\left(x\right)\le {\hat{f}}^k\left(x\right)\le f\left(x\right),\forall x\in X,$ (13)

${\bar{c}}^{a_k}\left(x\right):={\hat{c}}^k\left(x^{k+1}\right)+\langle {\hat{g}}_c^k,x-x^{k+1}\rangle$ 满足 ${\bar{c}}^{a_k}\left(x\right)\le {\hat{c}}^k\left(x\right)\le c\left(x\right),\forall x\in X.$ (14)

同时，有

$\underset{x\in X^k}{\arg \min }\phi \left(x;{\hat{x}}^k\right)=\underset{x\in X^{a_k}}{\arg \min }\phi \left(x;{\hat{x}}^k\right)$ (15)

成立。其中，聚集水平集 $X^{a_k}$ 定义为 $X^{a_k}:=\left\{x\in X:{\bar{f}}^{a_k}\left(x\right)\le f_{\text{lev}}^k,{\bar{c}}^{a_k}\left(x\right)\le 0\right\}$。

下面给出本文算法的具体步骤：

算法1：

步骤0 (初始化)：选取初始点 $x^0\in X$，参数 $\gamma \in \left(0,1\right)$，终止参数 ${\delta }_{\text{Tol}}\ge 0$，束的最大容量 $\text{nb}\ge 2$。选取初始下界 $f_{\text{low}}^0\le f^{\text{*}}$，计算初始近似函数值和近似次梯度 $\left(f_{x^0},{\tilde{g}}_f^0\right)$， $\left(c_{x^0},{\tilde{g}}_c^0\right)$。令 ${\hat{x}}^0=x^0$， $k=0$， $l=0$， $k\left(l\right)=0$， $J_f^0=\left\{0\right\}$， $J_c^0=\left\{0\right\}$。

步骤1 (更新记录值)：分别通过(8)和(9)更新 $h_{\text{rec}}^k$ 和 $x_{\text{rec}}^k$。

步骤2 (终止测试)：如果 $h_{\text{rec}}^k\le {\delta }_{\text{Tol}}$，则算法终止并输出 $x_{\text{rec}}^k$。

步骤3 (下降测试)：如果 $h_{\text{rec}}^k\le \left(1-\gamma \right)h_{\text{rec}}^{k\left(l\right)}$，则令 $l:=l+1$， $k\left(l\right):=k$，并选取 ${\hat{x}}^k\in \left\{x^j:j\in J_f^k\cap J_c^k\right\}$。

步骤4 (更新水平集)：令 $f_{\text{lev}}^k:=f_{\text{low}}^k+\gamma h_{\text{rec}}^k$，更新水平集 $X^k$。

步骤5 (可行性检测)：如果 $X^k$ 为非空集，则转到步骤6；否则，转步骤7。

步骤6 (子问题求解)：求解(10)产生新迭代点 $x^{k+1}$，并计算相应的近似函数值和近似次梯度 $\left(f_{x^{k+1}},{\tilde{g}}_f^{k+1}\right)$， $\left(c_{x^{k+1}},{\tilde{g}}_c^{k+1}\right)$。令 $f_{\text{low}}^{k+1}:=f_{\text{low}}^k$， ${\hat{x}}^{k+1}:={\hat{x}}^k$。

步骤7 (更新下界)：令 $l:=l+1$， $k\left(l\right):=k$， $f_{\text{low}}^k:=f_{\text{lev}}^k$，选择 ${\hat{x}}^k\in \left\{x^j:j\in J_f^k\cap J_c^k\right\}$，返回步骤1。

步骤8 (束管理)：如果 $\left|J_f^k\right|<\text{nb}$，则 $J_f^{k+1}=J_f^k\cup \left\{k+1\right\}$ ；否则选择指标集 $I_f\subseteq J_f^k$， $\left|I_f\right|\ge 2$，更新束 $J_f^{k+1}=J_f^k\backslash I_f\cup \left\{k+1,a_k\right\}$。如果 $\left|J_c^k\right|<\text{nb}$，则 $J_c^{k+1}=J_c^k\cup \left\{k+1\right\}$ ；否则选择指标集 $I_c\subseteq J_c^k$， $\left|I_c\right|\ge 2$，更新束 $J_c^{k+1}=J_c^k\backslash I_c\cup \left\{k+1,a_k\right\}$。

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

注1：令 $K^l$ 为第l个循环的指标集，由算法可知对任意的 $k\in K^l$，稳定中心 ${\hat{x}}^k$ 和下界 $f_{\text{low}}^k$ 不变。因此，对每一个固定的l，序列 ${\left\{f_{\text{lev}}^j\right\}}_{j\in K^l}$ 是非增的。

下面我们分别讨论误差固定不变和随着迭代趋近于零两种情况，即

情形I： ${\epsilon }_f^k\equiv {\epsilon }_f\ge 0,{\epsilon }_c^k\equiv {\epsilon }_c\ge 0,\forall k$ ；

情形II： ${\epsilon }_f^k\to 0,{\epsilon }_c^k\to 0,k\to \infty$。

引理2：假设 $\underset{k\to \infty }{\lim }{h}_{\text{rec}}^k\le 0$，则

a) 对于情形I，序列 $\left\{x_{\text{rec}}^k\right\}$ 的任意聚点都是问题(1)的 $\epsilon$ 最优解，其中 $\epsilon :=\max \left\{{\epsilon }_f,{\epsilon }_c\right\}$ ；

b) 对于情形II，序列 $\left\{x_{\text{rec}}^k\right\}$ 的任意聚点都是问题(1)的最优解。

特别地，如果对某个k，有 $h_{\text{rec}}^k\le 0$，则对于情形I， $x_{\text{rec}}^k$ 是问题(1)的一个 $\epsilon$ 最优解；对于情形II， $x_{\text{rec}}^k$ 是问题(1)的一个 ${\epsilon }^{j_k}$ 最优解，其中 ${\epsilon }^{j_k}:=\max \left\{{\epsilon }_f^{j_k},{\epsilon }_c^{j_k}\right\}$， $j_k\left(\le k\right)$ 是使得 $h_{\text{rec}}^k=\tilde{h}\left(x_{\text{rec}}^k;f_{\text{low}}^{j_k}\right)$ 成立的某个指标。

证明：由 $h_{\text{rec}}^k$ 的定义(8)和(9)以及X有界，可以得到序列 $\left\{h_{\text{rec}}^k\right\}$ 单调有界，因此必有极限。故不失一般性，可设序列 $\left\{f_{x_{\text{rec}}^k}\right\}$， $\left\{c_{x_{\text{rec}}^k}\right\}$ 有极限。由假设 $\underset{k\to \infty }{\lim }{h}_{\text{rec}}^k\le 0$，可得

$0\ge \underset{k}{\lim }\left(f_{x_{\text{rec}}^k}-f_{\text{low}}^{j_k}\right)\ge \underset{k}{\lim }\left(f\left(x_{\text{rec}}^k\right)-{\epsilon }_f^{j_k}-f_{\text{low}}^{j_k}\right)\ge \underset{k}{\lim }\left(f\left(x_{\text{rec}}^k\right)-{\epsilon }_f^{j_k}-f^{\text{*}}\right),$

$0\ge \underset{k}{\lim }{c}_{x_{\text{rec}}^k}\ge \underset{k}{\lim }\left(c\left(x_{\text{rec}}^k\right)-{\epsilon }_c^{j_k}\right).$

设 $\bar{x}$ 是序列 $\left\{x_{\text{rec}}^k\right\}$ 的一个聚点，对于情形I，由以上两个不等式可以得到 $f\left(\bar{x}\right)\le f^{*}+{\epsilon }_f$ 和 $c\left(\bar{x}\right)\le {\epsilon }_c$，因此 $\bar{x}$ 是问题(1)的 $\epsilon$ 最优解。对于情形II，再次利用以上两个不等式可得 $f\left(\bar{x}\right)\le f^{\text{*}}$ 和 $c\left(\bar{x}\right)\le 0$，故 $\bar{x}$ 是问题(1)的最优解。

特别地，如果对某个k， $h_{\text{rec}}^k\le 0$ 成立，类似以上分析可知，对于情形I有： $f\left(x_{\text{rec}}^k\right)\le f^{\text{*}}+{\epsilon }_f$ 和 $c\left(x_{\text{rec}}^k\right)\le {\epsilon }_c$，故 $x_{\text{rec}}^k$ 是问题(1)的 $\epsilon$ 最优解；对于情形II，有 $f\left(x_{\text{rec}}^k\right)\le f^{\text{*}}+{\epsilon }_f^{j_k}$ 和 $c\left(x_{\text{rec}}^k\right)\le {\epsilon }_c^{j_k}$，从而 $x_{\text{rec}}^k$ 是问题(1)的一个 ${\epsilon }^{j_k}$ 最优解。 $\square$

3. 收敛性与复杂度分析

本节将证明算法1的全局收敛性并分析其计算复杂度。记 $\Lambda$ 为近似次梯度的上界，即 $\Vert {\tilde{g}}_f^k\Vert \le \Lambda$， $\Vert {\tilde{g}}_c^k\Vert \le \Lambda ,\forall k$。由算法步骤2和引理2可知，若 $h_{\text{rec}}^k\le 0$，则算法终止，并且 $x_{\text{rec}}^k$ 是问题(1)的近似最优解，因此在下面分析中将假设 $h_{\text{rec}}^k>0,\forall k$。下面引理给出相邻两个迭代点之间距离的下界，其证明类似于文 [5] 的引理6。

引理3：算法1产生的迭代点满足下列关系：

$\Vert x^{k+1}-x^k\Vert \ge \frac{1-\gamma }{\Lambda }{h}_{\text{rec}}^k,k>k\left(l\right),$

$\Vert x^{k+1}-{\hat{x}}^k\Vert \ge \frac{1-\gamma }{\Lambda }{h}_{\text{rec}}^k,k=k\left(l\right).$

证明：对于任意的k和 $j\in J_f^k\cap J_c^k$，根据子问题 $x^{k+1}:=\underset{x\in X^k}{\arg \min }\phi \left(x;{\hat{x}}^k\right)$ 可以得到 $x^{k+1}\in X^k$。由 $X^k$ 的定义(11)结合(3)式，可得

$f_{x^j}+\langle {\tilde{g}}_f^j,x^{k+1}-x^j\rangle \le f_{\text{lev}}^k,$

$c_{x^j}+\langle {\tilde{g}}_c^j,x^{k+1}-x^j\rangle \le 0.$

即

$f_{x^j}-f_{\text{lev}}^k\le \langle {\tilde{g}}_f^j,x^{k+1}-x^j\rangle ,$

$c_{x^j}\le \langle {\tilde{g}}_c^j,x^{k+1}-x^j\rangle .$

结合Cauchy-Schwarz不等式可以得到

$f_{x^j}-f_{\text{lev}}^k\le \langle {\tilde{g}}_f^j,x^{k+1}-x^j\rangle \le \Vert {\tilde{g}}_f^j\Vert \Vert x^{k+1}-x^j\Vert \le \Lambda \Vert x^{k+1}-x^j\Vert .$

类似的，可以得到

$c_{x^j}\le \langle {\tilde{g}}_c^j,x^{k+1}-x^j\rangle \le \Vert {\tilde{g}}_c^j\Vert \Vert x^{k+1}-x^j\Vert \le \Lambda \Vert x^{k+1}-x^j\Vert .$

再结合 $f_{\text{lev}}^k=f_{\text{low}}^k+\gamma h_{\text{rec}}^k$ 及 $h_{\text{rec}}^k>0$，可得

$\begin{array}{c}\Lambda \Vert x^{k+1}-x^j\Vert \ge \max \left\{f_{x^j}-f_{\text{low}}^k-\gamma h_{\text{rec}}^k,c_{x^j}\right\}\\ \ge \max \left\{f_{x^j}-f_{\text{low}}^k-\gamma h_{\text{rec}}^k,c_{x^j}-\gamma h_{\text{rec}}^k\right\}\\ =-\gamma h_{\text{rec}}^k+\max \left\{f_{x^j}-f_{\text{low}}^k,c_{x^j}\right\}\end{array}$

$=-\gamma h_{\text{rec}}^k+\tilde{h}\left(x^j;f_{\text{low}}^k\right)$ 由(7)

$=\left(1-\gamma \right)h_{\text{rec}}^k.$ 由(8)

当 $k>k\left(l\right)$，则束管理确保 $k\in J_f^k\cap J_c^k$。故令使得 $\Vert x^{k+1}-x^k\Vert \ge \frac{1-\gamma }{\Lambda }{h}_{\text{rec}}^k$ 成立，当 $k=k\left(l\right)$ 时，选取 ${\hat{x}}^k$ 为稳定中心，故存在 $j\in J_f^k\cap J_c^k$ 使得 $x^j={\hat{x}}^k$，即 $\Vert x^{k+1}-{\hat{x}}^k\Vert \ge \frac{1-\gamma }{\Lambda }{h}_{\text{rec}}^k$ 成立。

下面将证明每一个循环 $K^l$ 中的迭代次数是有限的。

引理4：对于任意的 $l\ge 0$，在第l个循环中的迭代指标 $k\left(k\in K^l\right)$ 满足：

$k-k\left(l\right)+1\le {\Omega }_{\omega ,X}{\left(\frac{\Lambda }{\left(1-\gamma \right)h_{\text{rec}}^k}\right)}^2+1.$

证明：对任意的 $k>k\left(l\right)$，由子问题(10)知 $x^k=\underset{x\in X^{k-1}}{\arg \min }\phi \left(x;{\hat{x}}^{k-1}\right)$，故由一阶最优性条件可得：

$\langle \nabla \phi \left(x^k;{\hat{x}}^{k-1}\right),x-x^k\rangle \ge 0,\forall x\in X^{k-1}.$ (16)

i) 假如在第 $k-1$ 步到第k步没有束压缩机制，那么根据 ${\hat{f}}^k\left(x\right)$ 的定义(6)可知 ${\hat{f}}^k\left(x\right)\ge {\hat{f}}^{k-1}\left(x\right)$， ${\hat{c}}^k\left(x\right)\ge {\hat{c}}^{k-1}\left(x\right),\forall x\in R^n$。根据注1可得 $f_{\text{lev}}^k\le f_{\text{lev}}^{k-1}$，从而 $X^k\subseteq X^{k-1}$。因为 $k\in K^l$，所以有 $X^k$ 非空，并且 $x^{k+1}\in X^k$。又因为在每个 $l$ 循环中稳定中心不变，即： ${\hat{x}}^{k-1}={\hat{x}}^k$，从而可以得到 $\langle \nabla \phi \left(x^k;{\hat{x}}^k\right),x^{k+1}-x^k\rangle \ge 0$。

ii) 若在第 $k-1$ 步到第k步有束压缩，则聚集指标 $a_k\in J_f^k$， $a_k\in J_c^k$，故 ${\hat{f}}^k\left(x\right)\ge {\bar{f}}^{a_k}\left(x\right)$， ${\hat{c}}^k\left(x\right)\ge {\bar{c}}^{a_k}\left(x\right)$， $\forall x\in R^n$，从而 $X^k\subseteq X^{a_k}$。由(15)可知 $x^k=\arg \min \left\{\phi \left(x;{\hat{x}}^{k-1}\right),x\in X^{a_k}\right\}$，根据一阶最优性条件有：

$\langle \nabla \phi \left(x^k;{\hat{x}}^{k-1}\right),x-x^k\rangle \ge 0,\forall x\in X^{a_k}.$ (17)

类似地，可利用稳定中心在同一个l循环中不变，即 ${\hat{x}}^{k-1}={\hat{x}}^k$，并且 $x^{k+1}\in X^{a_k}$，结合 (17) 得到 $\langle \nabla \phi \left(x^k;{\hat{x}}^k\right),x^{k+1}-x^k\rangle \ge 0$。又因为 $k\in K^l$， $h_{\text{rec}}^k>{\delta }_{\text{Tol}}$，算法不终止且，于是

$\langle \nabla \phi \left(x^k;{\hat{x}}^{k\left(l\right)}\right),x^{k+1}-x^k\rangle \ge 0.$

由 $\phi \left(x;{\hat{x}}^{k\left(l\right)}\right)$ 是强凸函数，有

$\frac{\sigma }{2}{\Vert x^{k+1}-x^k\Vert }^2\le \phi \left(x^{k+1};{\hat{x}}^{k\left(l\right)}\right)-\phi \left(x^k;{\hat{x}}^{k\left(l\right)}\right)-\langle \nabla \phi \left(x^k;{\hat{x}}^{k\left(l\right)}\right),x^{k+1}-x^k\rangle \le \phi \left(x^{k+1};{\hat{x}}^{k\left(l\right)}\right)-\phi \left(x^k;{\hat{x}}^{k\left(l\right)}\right).$

从而有

$\frac{\sigma }{2}{\Vert x^{k+1}-x^k\Vert }^2\le \phi \left(x^{k+1};{\hat{x}}^{k\left(l\right)}\right)-\phi \left(x^k;{\hat{x}}^{k\left(l\right)}\right).$

对上式从 $k\left(l\right)+1$ 到k求和，得到：

$\frac{\sigma }{2}{\displaystyle \underset{{}^{j=k\left(l\right)+1}}{\overset{k}{\sum }}{\Vert x^{j+1}-x^j\Vert }^2}\le \phi \left(x^{k+1};{\hat{x}}^{k\left(l\right)}\right)-\phi \left(x^{k\left(l\right)+1};{\hat{x}}^{k\left(l\right)}\right).$ (18)

对不等式(18)左边缩小，结合引理3可得

$\frac{\sigma }{2}{\displaystyle \underset{{}^{j=k\left(l\right)+1}}{\overset{k}{\sum }}{\Vert x^{j+1}-x^j\Vert }^2}\ge \frac{\sigma }{2}{\displaystyle \underset{{}^{j=k\left(l\right)+1}}{\overset{k}{\sum }}{\left(\frac{1-\gamma }{\Lambda }{h}_{\text{rec}}^j\right)}^2}\ge \frac{\sigma }{2}{\displaystyle \underset{{}^{j=k\left(l\right)+1}}{\overset{k}{\sum }}{\left(\frac{1-\gamma }{\Lambda }{h}_{\text{rec}}^k\right)}^2}.$

对不等式(18)右边放大，由 $\phi \left(x;\hat{x}\right)$ 的性质以及(4)可得

$\begin{array}{l}\phi \left(x^{k+1};{\hat{x}}^{k\left(l\right)}\right)-\phi \left(x^{k\left(l\right)+1};{\hat{x}}^{k\left(l\right)}\right)\\ \le \phi \left(x^{k+1};{\hat{x}}^{k\left(l\right)}\right)\le \underset{x\in X}{\max }\left\{\phi \left(x;{\hat{x}}^{k\left(l\right)}\right)\right\}\le \underset{x,y\in X}{\max }\left\{\phi \left(x;y\right)\right\}=D_{\omega ,X}^2.\end{array}$

于是

$D_{\omega ,X}^2\ge \frac{\sigma }{2}{\displaystyle \underset{{}^{j=k\left(l\right)+1}}{\overset{k}{\sum }}{\left(\frac{1-\gamma }{\Lambda }{h}_{\text{rec}}^k\right)}^2}=\frac{\sigma }{2}\left(k-k\left(l\right)\right){\left(\frac{1-\gamma }{\Lambda }{h}_{\text{rec}}^k\right)}^2,$

从而结合(5)有

$k-k\left(l\right)\le \frac{2D_{\omega ,X}^2}{\sigma }{\left(\frac{\Lambda }{\left(1-\gamma \right)h_{\text{rec}}^k}\right)}^2={\Omega }_{\omega ,X}{\left(\frac{\Lambda }{\left(1-\gamma \right)h_{\text{rec}}^k}\right)}^2.$

$\square$

以下定理给出了算法1的全局收敛性。。

定理1：假设 ${\delta }_{\text{Tol}}=0$ 且算法不终止，则 ${\lim }_k{h}_{\text{rec}}^k\le 0$，并且

a) 如果 ${\epsilon }_f^k\equiv {\epsilon }_f\ge 0$， ${\epsilon }_c^k\equiv {\epsilon }_c\ge 0$， $\forall k$，则序列 $\left\{x_{\text{rec}}^k\right\}$ 的任意聚点是问题(1)的 $\epsilon$ 最优解，其中 $\epsilon :=\max \left\{{\epsilon }_f,{\epsilon }_c\right\}$。

b) 如果 ${\epsilon }_f^k\to 0$， ${\epsilon }_c^k\to 0$， $k\to \infty$，则序列 $\left\{x_{\text{rec}}^k\right\}$ 的任意聚点是问题(1)的最优解。

证明：首先，类似于文献 [5] 中的定理4，可以证明 ${\lim }_k{h}_{\text{rec}}^k\le 0$。其次，根据引理2易知定理成立。

$\square$

下面给出算法1的计算复杂度。

定理2：设 $-\infty <f_{\text{low}}^0\le f^{\text{*}}$， ${\delta }_{\text{Tol}}>0$，且不考虑步骤3，则算法1执行的迭代次数的上界为：

$\left(1+\frac{f^{*}-f_{\text{low}}^0}{\gamma {\delta }_{\text{Tol}}}\right)\left({\Omega }_{\omega ,X}{\left(\frac{\Lambda }{\left(1-\gamma \right){\delta }_{\text{Tol}}}\right)}^2+1\right).$

证明：根据算法1可知，当 $X^k$ 为空集时，最优值 $f^{\text{*}}$ 的下界 $f_{\text{low}}^k$ 增加了 $\gamma h_{\text{rec}}^k\left(>\gamma {\delta }_{\text{Tol}}\right)$。即

$f^{\text{*}}\ge f_{\text{low}}^0+\gamma h_{\text{rec}}^1+\cdots +\gamma h_{\text{rec}}^k\ge f_{\text{low}}^0+\gamma {\delta }_{\text{Tol}}+\cdots +\gamma {\delta }_{\text{Tol}}.$

因为 $f_{\text{low}}^0$ 是有限的，所以 $X^k$ 出现空集的次数也是有限的，令N为出现空集的次数，即N是有限的。因此， $N\cdot \gamma {\delta }_{\text{Tol}}\le f^{\text{*}}-f_{\text{low}}^0$，从而有：

$N\le \frac{f^{\text{*}}-f_{\text{low}}^0}{\gamma {\delta }_{\text{Tol}}}.$

若算法在第k次迭代不终止，有 $h_{\text{rec}}^k>{\delta }_{\text{Tol}}$，根据引理4可知算法中每个 $K^l$ 至多有 ${\Omega }_{\omega ,X}{\left(\frac{\Lambda }{\left(1-\gamma \right)h_{\text{rec}}^k}\right)}^2+1$ 次迭代。那么有：

${\Omega }_{\omega ,X}{\left(\frac{\Lambda }{\left(1-\gamma \right)h_{\text{rec}}^k}\right)}^2+1\le {\Omega }_{\omega ,X}{\left(\frac{\Lambda }{\left(1-\gamma \right){\delta }_{\text{Tol}}}\right)}^2+1.$

令 $k_{{\delta }_{\text{Tol}}}$ 是使得 $h_{\text{rec}}^k>{\delta }_{\text{Tol}}$ 成立的最大指标集，那么

$k_{{\delta }_{\text{Tol}}}\le \left(1+\frac{f^{*}-f_{\text{low}}^0}{\gamma {\delta }_{\text{Tol}}}\right)\left({\Omega }_{\omega ,X}{\left(\frac{\Lambda }{\left(1-\gamma \right){\delta }_{\text{Tol}}}\right)}^2+1\right).$

$\square$

4. 结束语

本文提出了一个基于非精确数据的带有非欧氏距离的约束水平束方法，该方法结合非精确信息并引入Bregman距离代替传统的欧氏距离，充分利用可行集的几何集合，加快算法的收敛速度，减少计算量。最后证明了算法的全局收敛性并分析了迭代复杂度。

基金项目

获国家自然科学基金项目(11761013，71861002)；广西自然科学基金项目(2018GXNSFFA281007；2017GXNSFBA198238)资助。

参考文献

NOTES

*通讯作者