一种非精确邻近梯度算法

An Inexact Proximal Gradient Algorithm

摘要: 邻近点算法(PPA)是求解非光滑优化问题的一种有效的迭代算法，对特殊结构问题的求解非常高效，但在实际问题中求解大规模可分离问题时花费很大。为解决上述问题且同时又保持PPA算法的优点，本文给出了一种非精确邻近梯度算法。该算法结合了线搜索法与邻近梯度下降算法的思想，在子问题的求解过程中采用近似的梯度，且不需要Lipschitz常数已知。基于以上思想，首先我们给出算法的伪代码，然后建立了算法收敛性的充分条件，最后证明在该条件下，算法迭代所产生序列的每个极限点是原问题的临界点。

Abstract: The Proximity Algorithm (PPA) is an effective iterative algorithm for solving non-smooth optimization problems, which is very efficient in solving special structural problems, but it is expensive to solve large-scale separable problems in practical problems. In order to solve the above problems and maintain the advantages of PPA algorithm, an inexact proximity gradient algorithm is proposed. The algorithm combines the ideas of the line search method and the proximity gradient descent algorithm, and adopts the approximate gradient in the solution of the sub-problem, and does not need the Lipschitz constant to be known. Based on the above ideas, firstly, we give the pseudocode of the algorithm, then establish the sufficient conditions for the convergence of the algorithm, and finally prove that under this condition, each limit point of the sequence generated by the algorithm iteration is the critical point of the original problem.

1. 引言

本文考虑如下优化问题

$\underset{x\in R^m}{\min }F\left(x\right),$ (1)

其中 $F:R^m\to R\cup \left\{+\infty \right\}$ 是定义在欧氏空间 $R^m$ 上的下半连续凸函数，求解问题(1)的算法有很多，当问题(1)为一般优化问题且目标函数F光滑时，可利用梯度法进行求解。当目标函数F不具有光滑性时，可采用次

梯度算法、邻近点算法等进行求解。当目标函数F为大规模可分离优化问题时，即 $F\left(x\right):=f\left(x\right)=\frac{1}{n}{\displaystyle \underset{i=1}{\overset{n}{\sum }}{f}_i\left(x\right)}$ ，

其中 $n\ge 1$ ，其中每个 $f_i:R^m\to R\cup \left\{+\infty \right\}$ 可都是下半连续的凸函数且可微，这类优化问题可用一阶/二阶随机优化算法求解，如Robbins等人(1951)提出了随机梯度算法(SGD) [1] 与基于SGD的随机方差减小的梯度下降算法 [2] 。二阶算法由于使用了更多信息，通常可得到更快的收敛速度，常用的算法有子样本牛顿算法(Newsamp) [3] ，近似估计Heesian矩阵的Lissa算法 [4] ，对梯度与Heesian矩阵进行完全随机抽样的SSN算

法 [5] 。此外，当函数包含不可微项时，即 $F\left(x\right)=\frac{1}{n}{\displaystyle \underset{i=1}{\overset{n}{\sum }}{f}_i\left(x\right)}+h\left(x\right)$ ，其中 $h:R^m\to R\cup \left\{+\infty \right\}$ 是定义在欧氏

空间 $R^m$ 上的下半连续凸函数，这类问题的应用也较为广泛，如图像恢复 [6] 、信号处理 [7] 、机器学习 [8] 等。本文将在邻近梯度算法的基础上引入线搜索思想对该问题做系列分析，该算法的迭代格式如下

$\begin{array}{l}{J}_k:=pro{x}_h\left(x^k-\nabla f\left(x^k\right)\right):=\underset{y\in R^m}{\arg \min }\nabla f\left(x^k\right)\left(y-x^k\right)+h\left(y\right)+\frac{1}{2}{\Vert y-x^k\Vert }^2,\\ x^{k+1}=x^k-{\beta }_k\left(x^k-J_k\right).\end{array}$

其中 ${\beta }_k>0$ ，称 $\text{pro}{\text{x}}_h$ 为邻近算子。

邻近点算法的思想可追溯到 [9] [10] ，1970年，Martinet最早提出了邻近点算法，1976年，Rockafellar在文 [11] [12] 利用它来求解极大单调算子的零点问题，1991年，Guler又进一步讨论了正常下半连续极小化问题的邻近点算法及其收敛性质。后Beck和Teboulle [7] 将邻近点算法与梯度下降算法相结合，这也就是邻近梯度算法，这类算法主要用于解决确定的复合优化问题，并且在目标函数凸或非凸时，分析了算法的收敛性和收敛速度。由于上述算法的迭代过程依赖可微函数的Lipschitz常数，因此Bello在文 [13] 中引入了线搜索的思想，提出了带线搜索的邻近梯度算法，该算法不仅保留了邻近梯度算法的优点，还不依赖于Lipschitz常数。在带有大规模可分离优化问题时，作者在文 [14] 中利用随机逼近(SA)方法解决优化问题(1)，并分析了随机梯度下降算法的收敛性。

基于上述这些论文的启发，本文将提出求解大规模复合凸优化问题的带线搜索的非精确邻近梯度算法，在算法的迭代过程中，对目标函数中的可分离部分采用非精确梯度，非精确邻近梯度算法不仅保留了邻近梯度算法易计算的优点，还在迭代过程中减小了数据储存量，提高了算法的效率。

2. 预备知识

本节将介绍一些必要的预备知识，包括一些符号、定义以及算法的分析证明过程中所要用到的概念、引理。在文中， $R,R_{++}$ 分别表示实数集，正实数集。用小写字母表示欧式空间 $R^m$ 中的向量，例如， $v\in R^m$ 。空间 $R^m$ 中的内积和2-范数分别用 $\langle \cdot ,\cdot \rangle$ 和 $\Vert \cdot \Vert$ 表示。

设 $f:R^m\to R\cup \left\{+\infty \right\}$ 为定义在 $R^m$ 上的广义实值函数，其定义域为：

$domf:=\left\{x\in R^m:f\left(x\right)<+\infty \right\},$

若 $domf\ne \varnothing$ ，则称函数f是真的。函数f的上图定义为

$epif:=\left\{\left(x,r\right)\in R^{m+1}:f\left(x\right)\le r\right\}.$

如果 $epif$ 在 $R^{m+1}$ 上是闭的，则称f是下半连续的。假设f为下半连续真凸函数，则函数f在点x处沿方向 $d\in R^m$ 的方向导数的定义为

$f^{\prime }\left(x;d\right):=\underset{t\to 0^{+}}{\lim }\frac{f\left(x+td\right)-f\left(x\right)}{t}.$

f在x处的次微分定义为

$\partial f\left(x\right):=\left\{v\in R^m:\langle v,y-x\rangle \le f\left(y\right)-f\left(x\right)\forall y\in \text{dom}f\right\}.$ (2)

如果 $x\notin \text{dom}f$ ，则 $\partial f\left(x\right)=\varnothing$ 。

定义1 定义邻近算子 $\text{pro}{\text{x}}_h:R^m\to \text{dom}h$ 如下：

$\text{pro}{\text{x}}_h\left(z\right)={\left(Id+\partial h\right)}^{-1}\left(z\right),z\in R^m,$

即 $\text{pro}{\text{x}}_h\left(z\right)=\left\{y\in R^m:y+\partial h\left(y\right)=z\right\}$ 。通过变形可得到其满足

$z-\text{pro}{\text{x}}_h\left(z\right)\in \partial h\left(\text{pro}{\text{x}}_h\left(z\right)\right)\forall z\in R^m.$ (3)

引理1 ( [15] , Proposition 17.2)设 $h:R^m\to R\cup \left\{+\infty \right\}$ 为一个下半连续真凸函数，则对任意 $x\in domh$ 与 $y\in R^m$ 满足

(1) $h^{\prime }\left(x;y\right)$ 存在且 $h^{\prime }\left(x;y\right)=\underset{t\in R_{++}}{\inf }\left(\frac{h\left(x+ty\right)-h\left(x\right)}{t}\right)$ 。

(2) $h^{\prime }\left(x;y-x\right)+h\left(x\right)\le h\left(y\right)$ 。

引理2 设 $f,h:R^m\to R\cup \left\{+\infty \right\}$ 为下半连续真凸函数，则对任意的 $x\in domf$ 与 $y\in R^m$ ，下列结论成立：

(1) $\partial f\left(x\right)$ 为非空有界闭凸集。

(2) 若函数f在点x处可微，则有 $\partial f\left(x\right)=\left\{\nabla f\left(x\right)\right\}$ ，其中 $\nabla f$ 表示函数f在点x的梯度。

(3) 设 $x\in domf\cap domh$ ，则有 $\partial f\left(x\right)+\partial h\left(x\right)\subseteq \partial \left(f+h\right)\left(x\right)$ 。若 $x\in \mathrm{int}\left(domf\right)\cap domh$ ，则等号成立。

对于凸函数f，如果 $0\in \partial f\left(x_{*}\right)$ ，则 $x_{*}$ 是f函数值的最小点，即 $f\left(x_{*}\right)={\min }_{x\in R^m}f\left(x\right)$ 下面定义优化问

题的 $\epsilon$ -近似解。

定义2 ( $\epsilon$ -近似解)设f为下半连续真凸函数， $\epsilon >0$ 。我们称点 $x_{*}\in domf$ 是优化问题 ${\min }_{x\in R^m}f\left(x\right)$ 的 $\epsilon$ -近似解，如果满足 $d_{\partial f\left(x_{*}\right)}\left(0\right):={\min }_{v\in \partial f\left(x_{*}\right)}\Vert v\Vert \le \epsilon$ 。

对问题(1)的大规模可分离凸优化形式：

$\underset{x\in R^m}{\min }\frac{1}{n}{\displaystyle \underset{i=1}{\overset{n}{\sum }}{f}_i\left(x\right)}+h\left(x\right).$

我们总假设上述问题有解，解集记为 $S^{*}$ ，记 $\psi :=\left\{1,2,\cdots ,n\right\}$ 为指标集，则 $f:=\frac{1}{n}{\displaystyle {\sum }_{i\in \psi }{f}_i}$ 。且满足

假设(H)

(C1) $h,f_i\left(\forall i\in \psi \right)$ 为下半连续真凸函数且 $domh\subseteq \mathrm{int}\left({\cap }_{i\in \psi }domf\right)$ 。

(C2)函数 $f_i$ 在包含 $domh$ 的开集上是连续可微的。

注：由假设(H)和引理2 (3)，对任意 $x\in domh$ ，有 $\partial \left(f+h\right)\left(x\right)$ 为有界闭凸集且 $\partial \left(f+h\right)\left(x\right)=\nabla f\left(x\right)+\partial h\left(x\right)$ 。

在下面的非精确邻近梯度算法中，我们将用近似梯度g代替全梯度 $\nabla f$ 。下面考虑用随机抽样产生近似梯度：

$g\left(x\right):=\frac{1}{\left|\xi \right|}{\displaystyle \underset{j\in \xi }{\sum }\nabla f_j\left(x\right)}x\in domh,$

其中 $\xi$ 和 $\left|\xi \right|$ 分别表示抽样样本和样本个数。以下引理说明，在抽样的样本数充分大时，g可在一定概率意义下达到预设的与全梯度的近似程度。

引理3 [16] 设 ${\epsilon }_1,\lambda \in \left(0,1\right)$ 假设存在函数 $Q:R^n\to R$ 满足对任意 $i\in \psi$ ，有

$\Vert \nabla f_i\left(x\right)\Vert \le Q\left(x\right)\forall x\in R^n.$

假设对指标集 $\psi$ 进行放回或者不放回的随机等可能抽样，且样本个数 $\left|\xi \right|$ 满足 $\left|\xi \right|\ge Q{\left(x\right)}^2{\left(1+\sqrt{8\ln \left(1/\lambda \right)}\right)}^2/{\epsilon }_1^2$ ，则有

$\mathrm{Pr}\left(\Vert \nabla f\left(x\right)-g\left(x\right)\Vert \le {\epsilon }_1\right)\ge 1-\lambda .$

定义3 设S为 $R^m$ 的一个非空子集，序列 $\left\{x^k\right\}\subset R^m$ 。若存在一个数列 $\left\{{\omega }_k\right\}$ 满足 ${\displaystyle \underset{k=0}{\overset{\infty }{\sum }}{\omega }_k}<\infty$ 使对任意

以 $x\in S$ 下不等式成立：

得 ${\Vert x^{k+1}-x\Vert }^2\le {\Vert x^k-x\Vert }^2+{\omega }_k$ $k\in N,$

则称序列 $\left\{x^k\right\}$ quasi-Fejér收敛到S。

引理4 ( [17] , Theorem 4.1)若 $\left\{x^k\right\}$ quasi-Fejér收敛到S，则下列结论成立：

(1) 序列 $\left\{x^k\right\}$ 是有界的。

(2) 若序列 $\left\{x^k\right\}$ 有极限点 $x_{*}\in S$ ，则有 $\underset{k\to \infty }{\lim }{x}^k=x_{*}$ 。

引理5 设 $\left\{a_k\right\},\left\{b_k\right\},\left\{c_k\right\}\subset \left[0,+\infty \right)$ 为非负序列，其中 $A={\displaystyle \underset{k=0}{\overset{\infty }{\sum }}{a}_k}<+\infty$ ， $B={\displaystyle \underset{k=0}{\overset{\infty }{\sum }}{b}_k}<+\infty$ ，且 $c_0>0$ 。如

果存在常数 $\beta \le 1$ ，使得

$c_{k+1}^2-c_k^2\le a_k+\beta c_k{b}_k\forall k\in N,$ (4)

则序列 $\left\{c_k\right\}$ 有界。

证明：注意到 $c_0>0$ ，所以存在常数 $M\ge 1$ ，使即 $c_0^2{M}^2+2c_0\beta BM+2A+c_0^2\ge 0$ ，即

$c_0^2+A+c_0\beta BM\le {\left(M{c}_0\right)}^2.$ (5)

下面我们证明

$c_k\le M{c}_0\forall k\in N.$ (6)

显然当 $k=0$ 时，(6)成立。假设当 $k\le m$ 时(6)成立，即

$c_k\le M{c}_0\forall k\le m.$

由(4)，我们有

${\displaystyle \underset{k=0}{\overset{m}{\sum }}\left(c_{k+1}^2-c_k^2\right)}\le {\displaystyle \underset{k=0}{\overset{m}{\sum }}{a}_k}+{\displaystyle \underset{k=0}{\overset{m}{\sum }}\beta c_k{b}_k}\le A+\beta c_{0}MB.$

于是

$c_{m+1}^2\le c_0^2+A+\beta c_{0}MB\le {\left(M{c}_0\right)}^2.$

由(5)可得 $c_m\le M{c}_0$ 。由归纳法证明可得(6)。

3. 算法及收敛性分析

在对问题(1)中的大规模可分离部分进行求解时，为了保留邻近梯度算法的优点且不依赖Lipschitz常数，受 [13] [14] [16] 的启发，我们提出带线搜索的非精确邻近梯度算法。具体地，与 [14] 类似，我们在子问题求解过程中也采用的是非精确梯度，其中对梯度近似求解的思路参考了 [16] ，线搜索的思想主要来自( [13] , Lemma 3.2)。

3.1. 非精确邻近梯度算法

Algorithm 1. Inexact proximity gradient algorithm

算法1. 非精确邻近梯度算法

由算法1可知，若在迭代过程的第2步采用全梯度，则算法1为精确的线搜索邻近梯度算法，即与( [13] , Method 3)相同。下面的各类命题与定理中，都假设序列 $\left\{x^k\right\}$ 由算法1所产生。

命题1 设 $k\in N$ ， ${\beta }_k$ 为算法1第k次迭代的Step 3中生成的步长，则对任意 $x\in domh$ ，有：

$\begin{array}{c}{\Vert x^{k+1}-x\Vert }^2-{\Vert x^k-x\Vert }^2\le 2\left[\left(f+h\right)\left(x^k\right)-\left(f+h\right)\left(x^{k+1}\right)\right]+2{\beta }_k\left[\left(f+h\right)\left(x\right)-\left(f+h\right)\left(x^k\right)\right]\\ +2{\beta }_k\Vert x-x^k\Vert \Vert \nabla f\left(x^k\right)-g_k\left(x^k\right)\Vert .\end{array}$ (10)

证明：对任意 $x\in domh$ ，设

$A_k:={\Vert x^{k+1}-x^k\Vert }^2+{\Vert x^k-x\Vert }^2-{\Vert x^{k+1}-x\Vert }^2=2\langle x^k-x^{k+1},x^k-x\rangle .$

由(9)可得

$\begin{array}{c}\frac{A_k}{2{\beta }_k}=\frac{2}{2{\beta }_k}\langle x^k-x^{k+1},x^k-x\rangle =\langle x^k-J_k,x^k-x\rangle \\ =\langle x^k-J_k-g_k\left(x^k\right),x^k-x\rangle +\langle g_k\left(x^k\right),x^k-x\rangle \\ =\langle x^k-J_k-g_k\left(x^k\right),J_k-x\rangle +\langle x^k-J_k-g_k\left(x^k\right),x^k-J_k\rangle +\langle g_k\left(x^k\right),x^k-x\rangle \\ =\langle x^k-J_k-g_k\left(x^k\right),J_k-x\rangle +{\Vert x^k-J_k\Vert }^2-\langle g_k\left(x^k\right),x^k-J_k\rangle +\langle g_k\left(x^k\right),x^k-x\rangle .\end{array}$

由(3)与(7)可得： $x^k-J_k-g_k\left(x^k\right)\in \partial h(\; J\; k\; )$

又f是光滑的凸函数，所以

$\begin{array}{c}f\left(x\right)-f\left(y\right)\ge \langle \nabla f\left(y\right),x-y\rangle \\ =\langle \nabla f\left(y\right)-g\left(y\right),x-y\rangle +\langle g\left(y\right),x-y\rangle \\ \ge -\Vert x-y\Vert \Vert \nabla f\left(y\right)-g\left(y\right)\Vert +\langle g\left(y\right),x-y\rangle .\end{array}$

结合算法的第3步，并令 $y:=x^k$ ，得

$\begin{array}{c}\frac{A_k}{2{\beta }_k}\ge h\left(J_k\right)-h\left(x\right)+\frac{1}{{\beta }_k}\left[\left(f+h\right)\left(x^{k+1}\right)-\left(f+h\right)\left(x^k\right)\right]+h\left(x^k\right)-h\left(J_k\right)+\frac{1}{2}{\Vert x^k-J_k\Vert }^2\\ +f\left(x^k\right)-f(x)-\Vert x-x^k\Vert \Vert \nabla f\left(x^k\right)-g_k\left(x^k\right)\Vert \\ =\left[\left(f+h\right)\left(x^k\right)-\left(f+h\right)\left(x\right)\right]+\frac{1}{{\beta }_k}\left[\left(f+h\right)\left(x^{k+1}\right)-\left(f+h\right)\left(x^k\right)\right]+\frac{1}{2}{\Vert x^k-J_k\Vert }^2\\ -\Vert x-x^k\Vert \Vert \nabla f\left(x^k\right)-g_k\left(x^k\right)\Vert .\end{array}$

于是

$\begin{array}{c}{\Vert x^{k+1}-x\Vert }^2-{\Vert x^k-x\Vert }^2\le {\Vert x^{k+1}-x^k\Vert }^2+2{\beta }_k\left[\left(f+h\right)\left(x\right)-\left(f+h\right)\left(x^k\right)\right]+2\left[\left(f+h\right)\left(x^k\right)-\left(f+h\right)\left(x^{k+1}\right)\right]\\ -{\beta }_k{\Vert x^k-J_k\Vert }^2+2{\beta }_k\Vert x-x^k\Vert \Vert \nabla f\left(x^k\right)-g_k\left(x^k\right)\Vert .\end{array}$

又由于 $x^k-x^{k+1}={\beta }_k\left(J_k-x^k\right)$ ，且 ${\beta }_k\in \left(0,1\right)$ ，则 ${\beta }_k^2\le {\beta }_k$ 。即 ${\Vert x^k-x^{k+1}\Vert }^2-{\beta }_k{\Vert J_k-x^k\Vert }^2\le 0$ 。

从而(10)得证。

特别地，当 $x=x^k$ 时，由(10)有

$\left(f+h\right)\left(x^k\right)-\left(f+h\right)\left(x^{k+1}\right)\ge \frac{1}{2}{\Vert x^{k+1}-x\Vert }^2\ge 0.$ (11)

从而序列 $\left\{\left(f+h\right)\left(x^k\right)\right\}$ 单调减少，这说明算法1为下降算法。

关于算法1，有以下收敛性结论。

定理1 设解集 $S_{*}\ne \varnothing$ ， $\left\{x^k\right\}$ 和 $\left\{{\beta }_k\right\}$ 为算法1所产生的序列。记 $d_0:=\text{dist}\left(x^0,S_{*}\right)$ ，假设近似梯度 $g_k$ 连续且存在 $a\ge 1$ 满足

$\Delta :={\displaystyle \underset{k=0}{\overset{\infty }{\sum }}\Vert \nabla f\left(x^k\right)-g_k\left(x^k\right)\Vert }<+\infty ,$ (12)

则序列 $\left\{x^k\right\}$ 收敛于 $S_{*}$ 中一点，即存在 $\bar{x}\in S_{*}$ ，使得

$\underset{k\to \infty }{\lim }{x}^k=\bar{x}.$ (13)

证明：在(7)中令 $x=x_{*}\in S_{*}$ ，有

${\Vert x^{k+1}-x_{*}\Vert }^2-{\Vert x^k-x_{*}\Vert }^2\le 2\left[\left(f+h\right)\left(x^k\right)-\left(f+h\right)\left(x^{k+1}\right)\right]+2{\beta }_k\Vert x_{*}-x^k\Vert \cdot \Vert \nabla f\left(x^k\right)-g_k\left(x^k\right)\Vert ,\forall k\in N.$ (14)

由于序列 $\left\{\left(f+h\right)\left(x^k\right)\right\}$ 单调递减，则

${\displaystyle \underset{k=0}{\overset{\infty }{\sum }}\left[\left(f+h\right)\left(x^k\right)-\left(f+h\right)\left(x^{k+1}\right)\right]}\le \left(f+h\right)\left(x^0\right)-\left(f+h\right)\left(x_{*}\right)<+\infty .$

由(12)与引理5 (用 $\left(f+h\right)\left(x^k\right)-\left(f+h\right)\left(x^{k+1}\right)$ ， $\Vert \nabla f\left(x^k\right)-g_k\left(x^k\right)\Vert$ 和 $\Vert x^k-x_{*}\Vert$ 代替 $a_k,b_k$ 和 $c_k$ )可知序列 $\left\{\Vert x^k-x_{*}\Vert \right\}$ 有界，从而有

$\begin{array}{l}2{\displaystyle \underset{k=0}{\overset{\infty }{\sum }}\left[\left(f+h\right)\left(x^k\right)-\left(f+h\right)\left(x^{k+1}\right)\right]}+2{\displaystyle \underset{k=0}{\overset{\infty }{\sum }}{\beta }_k\Vert x_{*}-x^k\Vert \cdot \Vert \nabla f\left(x^k\right)-g_k\left(x^k\right)\Vert }\\ \le 2\left[\left(f+h\right)\left(x^0\right)-\left(f+h\right)\left(x_{*}\right)\right]+2{\displaystyle \underset{k=0}{\overset{\infty }{\sum }}{\beta }_k\Vert x_{*}-x^k\Vert \cdot \Vert \nabla f\left(x^k\right)-g_k\left(x^k\right)\Vert }<+\infty .\end{array}$

结合(14)与定义3可知序列 $\left\{x^k\right\}$ quasi-Fejér收敛到 $S_{*}$ 。又由引理4知序列 $\left\{x^k\right\}$ 有界，假设 $\bar{x}$ 为 $\left\{x^k\right\}$ 的一个聚点，下面证明 $\bar{x}\in S_{*}$ 。令

${\hat{\beta }}_k:=\frac{{\beta }_k}{\theta }>{\beta }_k>0,$

${\hat{y}}_k:=x^k-{\hat{\beta }}_k\left(x^k-J_k\right)=\left(1-{\hat{\beta }}_k\right)x^k+{\hat{\beta }}_k{J}_k.$ (15)

由算法1的step3可知

$\left(f+h\right)\left({\hat{y}}_k\right)>\left(f+h\right)\left(x^k\right)-{\hat{\beta }}_k\left[h\left(x^k\right)-h\left(J_k\right)\right]-{\hat{\beta }}_k\langle g_k\left(x^k\right),x^k-J_k\rangle +\frac{{\hat{\beta }}_k}{2}{\Vert x^k-J_k\Vert }^2.$

结合(2)和(15)可得

$\begin{array}{c}0>\left(f+h\right)\left(x^k\right)-\left(f+h\right)\left({\hat{y}}_k\right)-{\hat{\beta }}_k\left[h\left(x^k\right)-h\left(J_k\right)\right]-{\hat{\beta }}_k\langle g_k\left(x^k\right),x^k-J_k\rangle +\frac{{\hat{\beta }}_k}{2}{\Vert x^k-J_k\Vert }^2\\ \ge \langle g_k\left({\hat{y}}_k\right),x^k-{\hat{y}}_k\rangle +\langle \nabla f\left({\hat{y}}_k\right)-g_k\left({\hat{y}}_k\right),x^k-{\hat{y}}_k\rangle +h\left(x^k\right)-\left(1-{\hat{\beta }}_k\right)h\left(x^k\right)-{\hat{\beta }}_{k}h\left(J_k\right)\\ -{\hat{\beta }}_k\left[h\left(x^k\right)-h\left(J_k\right)\right]-{\hat{\beta }}_k\langle g_k\left(x^k\right),x^k-J_k\rangle +\frac{{\hat{\beta }}_k}{2}{\Vert x^k-J_k\Vert }^2\\ ={\hat{\beta }}_k\langle g_k\left({\hat{y}}_k\right)-g_k\left(x^k\right),x^k-J_k\rangle +{\hat{\beta }}_k\langle \nabla f\left({\hat{y}}_k\right)-g_k\left({\hat{y}}_k\right),x^k-J_k\rangle +\frac{{\hat{\beta }}_k}{2}{\Vert x^k-J_k\Vert }^2.\end{array}$

整理可得

$\frac{1}{2}\Vert x^k-J_k\Vert \le \Vert g_k\left({\hat{y}}_k\right)-g_k\left(x^k\right)\Vert +\Vert \nabla f\left({\hat{y}}_k\right)-g_k\left({\hat{y}}_k\right)\Vert .$ (16)

由于算子 ${\text{prox}}_h(\cdot )$ 的非扩张性，由(7)可知 $\Vert J_k-J_0\Vert \le \Vert x^k-x^0\Vert +\Vert g\left(x^k\right)-g\left(x^0\right)\Vert$ 。

由(15)可知当 ${\beta }_k\to 0$ 时，有 $\underset{k\to \infty }{\lim }\Vert {\hat{y}}_k-x^k\Vert =0$ ，由g的连续性可知当 $k\to \infty$ 时 $\Vert g_k\left({\hat{y}}_k\right)-g_k\left(x^k\right)\Vert \to 0$ 。

结合引理3可知 $\Vert \nabla f\left({\hat{y}}_k\right)-g_k\left({\hat{y}}_k\right)\Vert \to 0$ ，这表明了

$\underset{k\to \infty }{\lim }\Vert x^k-J_k\Vert =0$ . (17)

注意 $\bar{x}$ 为 $\left\{x^k\right\}$ 的一个聚点，即存在子序列 $\left\{x^{k_j}\right\}$ 收敛到 $\bar{x}$ ，则 $\left\{J_{k_j}\right\}$ 也收敛到 $\bar{x}$ ，则又由引理3有

$\underset{j\to \infty }{\lim }\Vert g_{k_j}\left(x^{k_j}\right)-\nabla f\left(J_{k_j}\right)\Vert =0.$ (18)

故在(3)中令 $z=x^{k_j}-g_{k_j}\left(x^{k_j}\right)$ 可得到

$x^{k_j}-J_{k_j}-g_{k_j}\left(x^{k_j}\right)+\nabla f\left(J_{k_j}\right)\in \partial h\left(J_{k_j}\right)+\nabla f\left(J_{k_j}\right)=\partial \left(f+h\right)\left(J_{k_j}\right).$

令 $j\to \infty$ ，由(17)及(18)可得 $0\in \partial \left(f+h\right)\left(\bar{x}\right)$ ，从而 $\bar{x}\in S_{*}$ ，由引理4可得(13)。

3.2. 算法1的迭代复杂度

在本小节中，我们将分析算法1的迭代复杂性。下面的定理表示当线搜索步长 $\left\{{\beta }_k\right\}$ 有正的下界时，函数值的收敛速度为 $o\left(k^{-1}\right)$ ，这与( [13] , Method3)中的(精确)邻近梯度算法的迭代复杂度类似。

定理2设定理1中的假设成立，且满足 $\underset{k\in N}{\inf }{\beta }_k\ge \beta >0$ ，则下列估计式成立：

$\underset{k\to \infty }{\lim }k\left[\left(f+h\right)\left(x^k\right)-\underset{x\in R^m}{\min }\left(f+h\right)\left(x\right)\right]=0.$

证明：由定理1可设

$\underset{k\to \infty }{\lim }{x}^k=x_{*}\in S_{*},$

因此对任意 $\epsilon >0$ ，存在 $K>0$ 使得

$\Vert x^k-x_{*}\Vert \le \epsilon$ 和 $\left(f+h\right)\left(x^k\right)-\left(f+h\right)\left(x_{*}\right)\le \epsilon \forall k\ge K.$ (19)

由命题1 (10) (令 $x=x_{*}$ )，对任意 $l\in N$ 有

$\begin{array}{c}0\ge \left(f+h\right)\left(x_{*}\right)-\left(f+h\right)\left(x^l\right)\\ \ge \frac{1}{2{\beta }_l}\left({\Vert x^{l+1}-x_{*}\Vert }^2-{\Vert x^l-x_{*}\Vert }^2+2\left[\left(f+h\right)\left(x^{l+1}\right)-\left(f+h\right)\left(x^l\right)\right]-2{\beta }_l\Vert x_{*}-x^l\Vert \cdot \Vert \nabla f\left(x^l\right)-g_k\left(x^l\right)\Vert \right)\\ \ge \frac{1}{{\beta }_l}\left({\Vert x^{l+1}-x_{*}\Vert }^2-{\Vert x^l-x_{*}\Vert }^2+2\left[\left(f+h\right)\left(x^{l+1}\right)-\left(f+h\right)\left(x^l\right)\right]-2{\beta }_l\Vert x_{*}-x^l\Vert \cdot \Vert \nabla f\left(x^l\right)-g_k\left(x^l\right)\Vert \right).\end{array}$

上式不等式对 $l=K,K+1,\cdots ,K+k-1$ 求和得

$\begin{array}{l}k\left(f+h\right)\left(x_{*}\right)-{\displaystyle \underset{l=K}{\overset{K+k-1}{\sum }}\left(f+h\right)\left(x^l\right)}\\ \ge \frac{1}{2{\beta }_l}({\Vert x^{K+k}-x_{*}\Vert }^2-{\Vert x^K-x_{*}\Vert }^2+2\left[\left(f+h\right)\left(x^{K+k}\right)-\left(f+h\right)\left(x^K\right)\right]\begin{array}{c}\\ \end{array}\\ -{\displaystyle \underset{l=K}{\overset{K+k-1}{\sum }}2{\beta }_l\Vert x_{*}-x^l\Vert \cdot \Vert \nabla f\left(x^l\right)-g_k\left(x^l\right)\Vert }).\end{array}$ (20)

即注意到 $\left\{\left(f+h\right)\left(x^k\right)\right\}$ 单调减少，我们有

${\displaystyle \underset{l=K}{\overset{K+k-1}{\sum }}\left(f+h\right)\left(x^l\right)}\le k\left(f+h\right)\left(x^K\right),\left(f+h\right)\left(x^{K+k}\right)-\left(f+h\right)\left(x^K\right)\ge \left(f+h\right)\left(x_{*}\right)-\left(f+h\right)\left(x^K\right).$

这和(20)一起表明

$\begin{array}{c}k\left[\left(f+h\right)\left(x_{*}\right)-\left(f+h\right)\left(x^{K+k}\right)\right]\ge -\frac{1}{2{\beta }_l}{\Vert x^K-x_{*}\Vert }^2-\frac{1}{{\beta }_l}\left[\left(f+h\right)\left(x^K\right)-\left(f+h\right)\left(x_{*}\right)\right]\\ -{\displaystyle \underset{l=K}{\overset{K+k-1}{\sum }}\Vert x_{*}-x^l\Vert \cdot \Vert \nabla f\left(x^l\right)-g_k\left(x^l\right)\Vert }\\ \ge -\left(\frac{{\epsilon }^2}{2\beta }+\frac{\epsilon }{\beta }+\epsilon \Delta \right),\end{array}$

其中最后一个不等式因为(12)，(19)和 $\underset{k\in N}{\inf }{\beta }_k\ge \beta$ 。由于 $\epsilon >0$ 的任意性，我们有

$\underset{k\to \infty }{\lim \sup }k\left[\left(f+h\right)\left(x^k\right)-\left(f+h\right)\left(x_{*}\right)\right]\le 0$ .

又 $\left(f+h\right)\left(x^k\right)-\left(f+h\right)\left(x_{*}\right)\ge 0$ ，所以定理结论成立。

下列命题表明在 $\nabla f_i$ ( $i\in \psi$ )的Lipschitz连续假设条件下， $\left\{{\beta }_k\right\}$ 有正的下界。证明思路与( [13] , Proposition 5.4)类似，所以我们省略了它的证明。

命题2 设 $\left\{{\beta }_k\right\}$ 为线搜索1的算法1所产生的序列，设 $x_{*}$ 是 $\left\{x^k\right\}$ 的极限点，即 $\underset{k\to \infty }{\lim }{x}^k=x_{*}$ ，近似梯度

序列 $\left\{g_k\right\}$ 为抽样产生。若对每个 $i\in \psi$ ， $\nabla f_i$ 在点 $x_{*}$ 是常数为 $L_i\left(x_{*}\right)>0$ 的局部Lipschitz连续的，则

$\underset{k\to \infty }{\lim \inf }{\beta }_k\ge \min \left\{1,\frac{\theta }{2L\left(x_{*}\right)}\right\},$

其中 $L\left(x_{*}\right):=\underset{i\in \psi }{\max }{L}_i\left(x_{*}\right)$ 。

4. 结论

本文介绍了一种求解大规模复合凸优化的非精确邻近梯度算法，算法不依赖可微函数的Lipschitz常数，并分析了算法的收敛性。接下来，我们可以构造求解大规模优化问题的非精确求解其他方法，得到高效的算法。

基金项目

国家自然科学基金(No. 12161017)；贵州省科技厅科技计划项目(No. ZK[2022]110)。