0 引言

考虑求解如下非光滑凸优化问题

$ {f^ * } = \inf \left\{ {f\left( x \right):x \in X} \right\}, $

(0.1)

其中, f:Rⁿ→R为非光滑凸函数, X$ \subseteq $Rⁿ为非空闭凸集.

非光滑优化是最优化研究^[1-3]的重要分支, 其在数据挖掘^[4]、图像恢复^[5]及机器学习^[6]等领域有着广泛应用.束方法是求解非光滑优化最有效的方法之一^[7-9].传统束方法包括邻近束方法^[10]、水平束方法^[11]和信赖域束方法^[12]等.最近, De Oliveira和Solodov^[13]结合邻近束方法与水平束方法的稳定性, 提出求解问题(0.1)的一个双稳定束方法, 其通过求解如下子问题产生新迭代点x_k+1：

$ \begin{array}{l} \min \\ \left\{ {\mathop {{f_k}}\limits^ \vee \left( x \right) + \frac{1}{{2{\tau _k}}}{{\left\| {x - {{\hat x}_k}} \right\|}^2}:\mathop {{f_k}}\limits^ \vee \left( x \right) \le {l_k},x \in X} \right\}, \end{array} $

(0.2)

其中, $\mathop {{f_k}}\limits^ \vee \left( x \right)$是在第k次迭代时产生的f(x)的割平面模型, 且满足$\mathop {{f_k}}\limits^ \vee \left( x \right) \le f\left( x \right)$, ${\hat x_k}$为当前稳定中心, τ_k > 0为邻近参数, l_k∈R为水平参数.

注意到子问题(0.2)的邻近项采用的是经典的欧氏距离, 为充分利用可行集的几何结构, 加快收敛速度, 提升数值效果, 许多方法引入了非欧氏距离.沈洁等^[14]在文献[13]中引入矩阵范数, 应用对偶思想进行求解, 分析算法的全局收敛性.Kiwiel等在邻近点算法中引入Bregman距离替代邻近项, 获得算法的全局收敛性^[15]; 在邻近束方法中引入Bregman距离替代邻近项, 允许求解子问题时出现近似解, 获得算法的全局收敛性^[16].

本文基于邻近函数, 引入非欧氏距离, 对子问题(0.2)进行改进, 提出一个带非欧氏范数的双稳定束方法.该方法充分吸收了传统邻近束方法和水平束方法的优势, 在产生新迭代点的二次规划子问题中引入邻近函数代替传统的欧氏距离, 使得在计算上可充分利用可行集的几何结构, 获得优良的数值效果.

本文符号说明.凸函数f在x处的次微∂f(x)={g:f(y)≥f(x)+〈g, y-x〉, ∀y}, ε-次微分记为∂_εf(x)={g:f(y)≥f(x)+〈g, y-x〉-ε, ∀y}.N_X(x)表示X在点x处的法锥, 即N_X(x)={y:〈y, z-x〉≤0, ∀z∈X}.i_X(x)为指示函数, 即:若x∈X, 则i_X(x)=0;否则i_X(x)=+∞.

1 算法与性质

引入邻近函数^[17]

$ D\left( {x,y} \right) = h\left( x \right) - h\left( y \right) - \left\langle {\nabla h\left( y \right),x - y} \right\rangle . $

为叙述简便, 假设h:X→R为一阶连续可微的强凸函数, 满足

$ \begin{array}{l} h\left( y \right) \ge h\left( x \right) + \left\langle {\nabla h\left( y \right),y - x} \right\rangle + \frac{{{\sigma _h}}}{2}\\ {\left\| {y - x} \right\|^2},\forall x,y \in X, \end{array} $

(1.1)

其中σ_h > 0为函数h的凸性参数.

将子问题(0.2)推广如下:

$ \min \left\{ {\mathop {{f_k}}\limits^ \vee \left( x \right) + \frac{1}{{{\tau _k}}}D\left( {x,{{\hat x}_k}} \right):\mathop {{f_k}}\limits^ \vee \left( x \right) \le {l_k},x \in X} \right\}, $

(1.2)

其中$\mathop {{f_k}}\limits^ \vee \left( x \right)=\mathop {\max }\limits_{j \in {B_k}} \left\{ {{{\bar f}_j}\left( x \right):=f\left( {{x_j}} \right) + {g_j}, x - {x_j}} \right\}$, 指标集B_k$ \subseteq ${1, …, k}, x_j为迭代点, g_j∈∂f(x_j).当$h\left( \cdot \right)=\frac{1}{2}\left\| \cdot \right\|$时, 子问题(1.2)变为子问题(0.2).

通过引入一个变量t, 问题(1.2)可写成:

$ \begin{array}{l} \mathop {\min }\limits_{\left( {x,t} \right) \in {R^{n + 1}}} \\ \left\{ {t + \frac{1}{{{\tau ^k}}}D\left( {x,{{\hat x}_k}} \right):\mathop {{f_k}}\limits^ \vee \left( x \right) \le t,t \le {l_k},x \in X} \right\}, \end{array} $

(1.3)

易知问题(1.2)与问题(1.3)关于x部分的解是等价的.

以下引理给出子问题(1.2)的性质.

引理1.1  若X_k={x∈X:$\mathop {{f_k}}\limits^ \vee \left( x \right)$≤l_k}≠Ø, 则子问题(1.2)有唯一解x_k+1.此外, 若X为多面体或者riX∩{x∈Rⁿ: $\mathop {{f_x}}\limits^ \vee \left( x \right)$≤l_k}≠Ø, 则存在s_k+1∈∂$\mathop {{f_k}}\limits^ \vee $(x_k+1), p_k+1∈N_X(x_k+1)=∂i_X(x_k+1)和拉格朗日乘子μ_k≥1, λ_k≥0使得

$ \nabla h\left( {{x_{k + 1}}} \right) = \nabla h\left( {{{\hat x}_k}} \right) - {\tau _k}{\mu _k}{{\hat g}_k}, $

(1.4)

$ {{\hat g}_k} = {s_{k + 1}} + \frac{1}{{{\mu _k}}}{p_{k + 1}},{\mu _k} = {\lambda _k} + 1, $

(1.5)

$ {\mu _k}\left( {\mathop {{f_k}}\limits^ \vee \left( {{x_{k + 1}}} \right) - {t_{k + 1}}} \right) = 0,{\lambda _k}\left( {\mathop {{f_k}}\limits^ \vee \left( {{x_{k + 1}}} \right) - {l_k}} \right) = 0 $

成立.此外, 对于任意的x∈X, 定义聚集线性化函数

$ \bar f_k^a\left( x \right): = \mathop {{f_k}}\limits^ \vee \left( {{x_{k + 1}}} \right) + \left\langle {{{\hat g}_k},x - {x_{k + 1}}} \right\rangle , $

(1.6)

则

$ \bar f_k^a\left( x \right) \le \mathop {{f_k}}\limits^ \vee \left( x \right) \le f\left( x \right),x \in X. $

(1.7)

证明: 由于问题(1.2)的目标函数是强凸函数且可行集非空, 故存在唯一最优解x_k+1.根据问题(1.3)的最优性条件, 存在最优解(x_k+1, t_k+1)及拉格朗日乘子μ_k≥0和λ_k≥0使得

$ \begin{array}{l} 0 \in \frac{1}{{{\tau _k}}}\left( {\nabla h\left( {{x_{k + 1}}} \right) - \nabla h\left( {{{\hat x}_k}} \right)} \right) + {\mu _k}\partial \mathop {{f_k}}\limits^ \vee \left( {{x_{k + 1}}} \right) + \\ {N_X}\left( {{x_{k + 1}}} \right), \end{array} $

(1.8)

$ 0 = 1 - {\mu _k} + {\lambda _k}, $

$ {\mu _k}\left( {\mathop {{f_k}}\limits^ \vee \left( {{x_{k + 1}}} \right) - {t_{k + 1}}} \right) = 0,\;\;\;\;{\lambda _k}\left( {{t_{k + 1}} - {l_k}} \right) = 0. $

由μ_k=1+λ_k≥1, 可知$\mathop {{f_k}}\limits^ \vee $(x_k+1)=t_k+1.由公式(1.8)可知, 存在s_k+1∈∂$\mathop {{f_k}}\limits^ \vee $(x_k+1), p_k+1∈N_X(x_k+1)使得

$ \begin{array}{l} \nabla h\left( {{x_{k + 1}}} \right) - \nabla h\left( {{{\hat x}_k}} \right) - {\tau _k}\left( {{\mu _k}{s_{k + 1}} + {p_{k + 1}}} \right) = \\ \nabla h\left( {{{\hat x}_k}} \right) - {\tau _k}{\mu _k}{{\hat g}_k}. \end{array} $

对于任意的x∈X, 结合公式(1.5), (1.6)及p_k+1∈N_X(x_k+1), s_k+1∈∂ $\mathop {{f_k}}\limits^ \vee $(x_k+1), 有

$ \begin{array}{l} \bar f_k^a\left( x \right) = \mathop {{f_k}}\limits^ \vee \left( {{x_{k + 1}}} \right) + < {s_{k + 1}},x - {x_{k + 1}} > + \frac{1}{{{\mu _k}}} < {p_{k + 1}},\\ x - {x_{k + 1}} > \le \mathop {{f_k}}\limits^ \vee \left( {{x_{k + 1}}} \right) + < {s_{k + 1}},x - {x_{k + 1}} > \le \\ \mathop {{f_k}}\limits^ \vee \left( x \right) \le f\left( x \right). \end{array} $

基于文献[13]中的算法1及子问题(1.3), 下面给出带非欧氏范数的双稳定束方法.

算法1 (带非欧氏范数的双稳定束方法)

步骤0  (初始化)取参数β, m_l ∈(0, 1), 终止参数Tol_Δ, Tol_e, Tol_g > 0.取x₁∈X, 令${\hat x_1}$=x₁.若f^*的一个下界f₁^low可获得, 令v₁^l=(1-m_l)(f(${\hat x_1}$)-f₁^low); 否则, 令f₁^low=-∞, 并取v₁^l > 0.选取τ_min > 0, τ₁≥τ_min, 令k：=1.

步骤1  (第一终止测试)令Δ_k=f(${\hat x_k}$)-f_k^low.若Δ_k≤Tol_Δ, 终止算法.

步骤2  (可行性检测)计算水平参数l_k=f(${\hat x_k}$)-v_k^l.若水平集X_k为空, 令f_k^low=l_k, v_k^l=(1-m_l)(f(${\hat x_k}$)-f_k^low), 返回步骤1.

步骤3  (寻找新迭代点)解问题(1.3)得(x_k+1, t_k+1)及相应于水平参数t≤l_k的乘子λ_k, 且有μ_k=λ_k+1, v_k^τ=f(${\hat x_k}$)-t_k+1, ${{\hat g}_k} = \frac{1}{{{\tau _k}{\mu _k}}}\left( {\nabla h\left( {{{\hat x}_k}} \right) - \nabla h\left( {{x_{k + 1}}} \right)} \right)$, ${{\hat e}_k}{\rm{ = }}v_k^\tau - \left\langle {{{\hat g}_k}, {{\hat x}_k} - {x_{k + 1}}} \right\rangle $.

步骤4  (第二终止测试)若${{\hat e}_k}$≤Tol_e且$\left\| {{{\hat g}_k}} \right\| \le To{l_g}$, 终止算法.

步骤5  (下降测试)取f_k+1^low∈[f_k^low, f^*], 若

$ f\left( {{x_{k + 1}}} \right) \le f\left( {{{\hat x}_k}} \right) - \beta v_k^\tau $

(1.9)

成立, 转至步骤5.1(下降步); 否则转至步骤5.2(无效步).

步骤5.1  (下降步)令${{\hat x}_{k + 1}}$=x_k+1, τ_k+1=τ_kμ_k和v_k+1^l=min{v_k^l, (1-m_l)(f(${{\hat x}_{k + 1}}$)-f_k+1^low)}.

选取模型${{\overset{\vee }{\mathop{f}}\,}_{k+1}}$满足${{\overset{\vee }{\mathop{f}}\,}_{k+1}}$(·)≤f(·).

步骤5.2  (无效步)令${{\hat x}_{k + 1}} = {{\hat x}_k}$, 取τ_k+1∈[τ_min, τ_k].若μ_k > 1, 令v_k+1^l=m_l v_k^l; 否则令v_k+1^l=v_k^l.

选取模型${{\overset{\vee }{\mathop{f}}\,}_{k+1}}$满足$\max \left\{ {{{\bar f}_{k + 1}}\left( \cdot \right), \bar f_k^a\left( \cdot \right)} \right\} \le {{\overset{\vee }{\mathop{f}}\,}_{k+1}}\left( \cdot \right) \le f\left( \cdot \right)$.

步骤6  (循环)令k=：k+1, 返回步骤1.

以下引理给出算法的近似最优性条件, 其证明类似文献[13].

引理1.2  聚集线性化误差${{\hat e}_k}$, 满足

$ {{\hat e}_k} \ge 0,{{\hat e}_k} + < {{\hat g}_k},{{\hat x}_k} - {x_{k + 1}} > = v_k^\tau \ge v_k^l. $

(1.10)

若μ_k > 1, 则v_k^τ=v_k^l.此外, 对于任意的x∈X, 有

$ f\left( {{{\hat x}_k}} \right) + < {{\hat g}_k},x - {{\hat x}_k} > - {{\hat e}_k} \le f\left( x \right). $

(1.11)

2 收敛性分析

根据算法1的步骤可知在迭代过程中必定会出现以下3种情况之一:水平集X_k=Ø出现无限次; 水平集X_k=Ø出现有限次时, 算法1产生有限多下降步; 水平集X_k=Ø出现有限次时, 算法1产生无限多下降步.

首先讨论水平集X_k=Ø出现无限次的情形.

定理2.1^[13]  假设X_k=Ø出现无限次, 则Δ_k→0, {f(${{\hat x}_k}$)}→f^*, 且序列{${{\hat x}_k}$}的每个聚点(若存在)都是问题(0.1)的解; 或者当{${{\hat x}_k}$}有限时, 最后一个迭代点${{\hat x}_k}$是问题(0.1)的解.

下面讨论X_k=Ø出现有限次的情形.不失一般性, 假设X_k≠Ø, ∀k≥1.

首先讨论算法1产生有限多下降步的情形.

对于x∈X, 定义函数

$ {{\bar \phi }_k}\left( x \right): = \bar f_k^a\left( x \right) + \frac{1}{{{\tau _k}}}D\left( {x,{{\hat x}_k}} \right), $

(2.1)

$ \mathop {{\phi _k}}\limits^ \vee \left( x \right): = \mathop {{f_k}}\limits^ \vee \left( x \right) + \frac{1}{{{\tau _k}}}D\left( {x,{{\hat x}_k}} \right). $

(2.2)

引理2.3  若μ_k=1, 则

$ \begin{array}{l} D\left( {x,{x_{k + 1}}} \right) + D\left( {{x_{k + 1}},{{\hat x}_k}} \right) - D\left( {x,{{\hat x}_k}} \right) = < \\ \nabla h\left( {{{\hat x}_k}} \right) - \nabla h\left( {{x_{k + 1}}} \right),x - {x_{k + 1}} > = {\tau _k} < {{\hat g}_k},x - \\ {x_{k + 1}} > , \end{array} $

(2.3)

$ {{\bar \phi }_k}\left( x \right) = {{\bar \phi }_k}\left( {{x_{k + 1}}} \right) + \frac{1}{{{\tau _k}}}D\left( {x,{x_{k + 1}}} \right). $

(2.4)

证明: 由公式(1.4)有

$ \begin{array}{l} D\left( {x,{x_{k + 1}}} \right) + D\left( {{x_{k + 1}},{{\hat x}_k}} \right) - D\left( {x,{{\hat x}_k}} \right) = < \\ \nabla h\left( {{{\hat x}_k}} \right) - \nabla h\left( {{x_{k + 1}}} \right),x - {x_{k + 1}} > = {\tau _k} < {{\hat g}_k},x - \\ {x_{k + 1}} > . \end{array} $

根据公式(1.6), (2.1)与(2.3)有

$ \begin{array}{l} {{\bar \phi }_k}\left( x \right) = \mathop {{f_k}}\limits^ \vee \left( {{x_{k + 1}}} \right) + < {{\hat g}_k},x - {x_{k + 1}} > + \frac{1}{{{\tau _k}}}D\left( {x,} \right.\\ \left. {{x_k}} \right) = \bar f_k^a\left( {{x_{k + 1}}} \right) + < {{\hat g}_k},x - {x_{k + 1}} > + \frac{1}{{{\tau _k}}}D\left( {x,{{\hat x}_k}} \right) = \\ {{\bar \phi }_k}\left( {{x_{k + 1}}} \right) - \frac{1}{{{\tau _k}}}D\left( {{x_{k + 1}},{{\hat x}_k}} \right) + \frac{1}{{{\tau _k}}}\left( {D\left( {x,{x_{k + 1}}} \right) + D\left( {{x_{k + 1}},} \right.} \right.\\ \left. {\left. {{{\hat x}_k}} \right) - D\left( {x,{{\hat x}_k}} \right)} \right) + \frac{1}{{{\tau _k}}}D\left( {x,{{\hat x}_k}} \right) = {{\bar \phi }_k}\left( {{x_{k + 1}}} \right) + \frac{1}{{{\tau _k}}}D\left( {x,} \right.\\ \left. {{x_{k + 1}}} \right). \end{array} $

引理2.4  假设存在k₁≥1, 对任意k≥k₁, 下降测试公式(1.9)不成立, 即产生的都是无效步.若μ_k=1, 则

$ f\left( {{x_{k + 1}}} \right) - \mathop {{f_k}}\limits^ \vee \left( {{x_{k + 1}}} \right) \to 0, $

(2.5)

此外, 当{τ_k}→τ_∞ > 0时, 有

$ \begin{array}{l} {x_{k + 1}} \to {x_\infty }: = {\rm{Arg}}\min \left\{ {f\left( x \right) + \frac{1}{{{\tau _\infty }}}D\left( {x,{{\hat x}_{{k_1}}}} \right),} \right.\\ \left. {x \in X} \right\}. \end{array} $

(2.6)

证明: 对任意的k≥k₁, 由公式(1.7), (2.1), (2.2)和(2.4)可得

$ \begin{array}{l} f\left( {{{\hat x}_{{k_1}}}} \right) \ge {{\overset{\vee }{\mathop{f}}\,}_{k+1}} \left( {{\hat x_{{k_1}}}} \right) = \overset{\vee }{\mathop{\phi }}\,{{}_{k+1}}\left( {{{\hat x}_{{k_1}}}} \right) \ge \overset{\vee }{\mathop{\phi }}\,{{}_{k+1}}\left( {{x_{k + 2}}} \right) = \\ {{\bar \phi }_{k + 1}}\left( {{x_{k + 2}}} \right) \ge {{\bar \phi }_k}\left( {{x_{k + 2}}} \right) \ge {{\bar \phi }_k}\left( {{x_{k + 1}}} \right) + \\ \frac{1}{{{\tau _k}}}D\left( {{x_{k + 2}},{x_{k + 1}}} \right) \ge {{\bar \phi }_k}\left( {{x_{k + 1}}} \right). \end{array} $

因为${{\hat x}_{{k_1}}}$是固定的, 由单调有界定理可知序列{ϕ_k(x_k+1)}收敛, 再结合τ_min≤τ_k+1≤ τ_k可得{D(x_k+2, x_k+1)}→0.进而由公式(1.1)有x_k+2-x_k+1→0.在公式(2.4)中固定x, 结合{ϕ_k(x_k+1)}收敛, 可知{x_k+1}有界.由算法1步骤5.2, 有

f(x_k+2)-f(x_k+1)≥${{\overset{\vee }{\mathop{f}}\,}_{k+1}}$(x_k+2)-f(x_k+1)≥ < g_k+1, x_k+2-x_k+1 > , 其中g_k+1∈∂ f(x_k+1).结合{x_k+1}有界和g_k+1的有界性有${{\overset{\vee }{\mathop{f}}\,}_{k+1}}$(x_k+2)-f(x_k+1)→0, 即$\mathop {{f_x}}\limits^ \vee $(x_k+1)-f(x_k+1)→0.

设x为{x_k+1}的任一聚点, 则存在无限指标集K^′, 使得x_k+1→x, k∈K^′.由公式(1.7), (2.1)和(2.4)有

$ \begin{array}{l} f\left( x \right) + \frac{1}{{{\tau _k}}}D\left( {x,{{\hat x}_{{k_1}}}} \right) \ge \bar f_k^a\left( {{x_{k + 1}}} \right) + \frac{1}{{{\tau _k}}}D\left( {x,{{\hat x}_{{k_1}}}} \right) = \\ {{\bar \phi }_k}\left( x \right) \ge {{\bar \phi }_k}\left( {{x_{k + 1}}} \right) = \bar f_k^a\left( {{x_{k + 1}}} \right) + \frac{1}{{{\tau _k}}}D\left( {{x_{k + 1}},{{\hat x}_{{k_1}}}} \right) = \\ f\left( {{x_{k + 1}}} \right) + \left( {\mathop {{f_k}}\limits^ \vee \left( {{x_{k + 1}}} \right) - f\left( {{x_{k + 1}}} \right)} \right) + \frac{1}{{{\tau _k}}}\left( {h\left( {{x_{k + 1}}} \right) - } \right.\\ \left. {h\left( {{{\hat x}_{{k_1}}}} \right) - < \nabla h\left( {{{\hat x}_{{k_1}}}} \right),{x_{k + 1}} - {{\hat x}_{{k_1}}} > } \right),x \in X. \end{array} $

上式对k∈K^′, k→∞取极限有

$ \begin{array}{l} f\left( x \right) + \frac{1}{{{\tau _\infty }}}D\left( {x,{{\hat x}_{{k_1}}}} \right) \ge f\left( {\bar x} \right) + \frac{1}{{{\tau _\infty }}}D\left( {\bar x,{{\hat x}_{{k_1}}}} \right),\\ x \in X. \end{array} $

由问题(2.6)解的唯一性知x=x_∞, 因此结合{x_k+1}的有界性及的任意性可得{x_k+1}→x_∞.

定理2.2  设存在k₁≥1, 当k≥k₁时, 下降测试公式(1.9)不成立, 则集合K：={k:μ_k > 1}为无限集, 且${{\hat x}_{{k_1}}}$为问题(0.1)的最优解.

证明: 根据算法1知序列{v_k^l}是非增的, 由步骤5.1有v_k+1^l=m_lv_k^l, ∀k∈K.

反证法, 假设K是有限集.由引理1.2, 存在k₂≥k₁使得

$ {\mu _k} = 1,{\lambda _k} = 0,v_k^l = v_{{k_2}}^l > 0,\forall k \ge {k_2}. $

结合引理2.4, 得{f(x_k+1)}→f(x_∞).若下降测试公式(1.9)不成立, 则有

$ \begin{array}{l} f\left( {{x_{k + 1}}} \right) - \mathop {{f_k}}\limits^ \vee \left( {{x_{k + 1}}} \right) > \mathop {{f_k}}\limits^ \vee \left( {{{\hat x}_{{k_1}}}} \right) - \beta v_k^\tau - \\ \mathop {{f_k}}\limits^ \vee \left( {{x_{k + 1}}} \right) = \left( {1 - \beta } \right)v_k^\tau ,\forall k \ge {k_1}. \end{array} $

由β∈(0, 1), 结合公式(2.5), 可知v_k^τ→0, 这与v_k^τ≥v_k^l=v^l_k2 > 0, ∀k≥k₂矛盾.因此, K为无限集.

由K为无限集, 根据算法1步骤5.1有v_k+1^l=m_lv_k^l, ∀ k ∈ K, 因为m_l∈(0, 1)且{v_k^l}单调非增, 所以v_k^l→0, k→∞.由引理1.2知, v_k^τ=v_k^l, k ∈ K.因此{v_k^τ}→0, k∈K.由h的强凸性, 根据文献[18]定理2.1.9有

$ \begin{array}{l} < \nabla h\left( {{{\hat x}_{{k_1}}}} \right) - \nabla h\left( {{x_{k + 1}}} \right),{{\hat x}_{{k_1}}} - {x_{k + 1}} > \ge \\ {\sigma _h}{\left\| {{{\hat x}_{{k_1}}} - {x_{k + 1}}} \right\|^2}, \end{array} $

(2.7)

结合公式(1.4), (1.10)和(2.7), 有

$ \begin{array}{l} v_k^\tau = {{\hat e}_k} + < {{\hat g}_k},{{\hat x}_{{k_1}}} - {x_{k + 1}} > = {{\hat e}_k} + \frac{1}{{{\tau _k}{\mu _k}}} < \\ \nabla h\left( {{{\hat x}_{{k_1}}}} \right) - \nabla h\left( {{x_{k + 1}}} \right),{{\hat x}_{{k_1}}} - {x_{k + 1}} > \ge {{\hat e}_k} + \frac{{{\sigma _h }}}{{{\tau _k}{\mu _k}}}\\ {\left\| {{{\hat x}_{{k_1}}} - {x_{k + 1}}} \right\|^2} \ge 0,k \in K. \end{array} $

所以${{\hat e}_k}$→0, ${{\hat x}_{{k_1}}}$-x_k+1→0, k∈K.由公式(1.4), ∇h(x)连续可知${{{\hat g}_k}}$→0, k∈K, 结合公式(1.11)可知${{\hat x}_{{k_1}}}$是问题(0.1)的解.

接下来讨论算法1产生无限多下降步的情形.

定理2.3  假设算法1产生无限多下降步, 则{f(${{\hat x}_k}$)}→f^*且序列{${{\hat x}_k}$}的任意一个聚点都是问题(0.1)的解.

证明: 记{${{\hat x}_{k\left( j \right)}}$}为{${{\hat x}_k}$}的一个子列, k(j)表示第j次下降步的指标, 定义i(j)=k(j+1)-1, ∀j≥1.由公式(1.4), (1.11)和引理1.2有

$ \nabla h\left( {{{\hat x}_{k\left( {j + 1} \right)}}} \right) = \nabla h\left( {{{\hat x}_{k\left( j \right)}}} \right) - {\tau _{i\left( j \right)}}{\mu _{i\left( j \right)}}{{\hat g}_{i\left( j \right)}}, $

(2.8)

$ {{\hat g}_{i\left( j \right)}} \in {\partial _{{{\hat e}_{k\left( j \right)}}}}\left( {f + {i_X}} \right)\left( {{{\hat x}_{k\left( j \right)}}} \right), $

(2.9)

$ \begin{array}{l} {\tau _{i\left( j \right)}}{\mu _{i\left( j \right)}} \ge {\tau _{{m }{in}}},\\ f\left( {{{\hat x}_{k\left( j \right)}}} \right) - f\left( {{{\hat x}_{k\left( {j + 1} \right)}}} \right) \ge \beta v_{i\left( j \right)}^\tau . \end{array} $

(2.10)

由算法1知{f(${{\hat x}_{k\left( j \right)}}$)}是下降序列.若{f(${{\hat x}_{k\left( j \right)}}$)} →-∞, 证毕, 以下不妨假设{f(${{\hat x}_{k\left( j \right)}}$)}有界.

由τ_i(j)μ_i(j)≥τ_min > 0, ∀j≥1, 有

$ \sum\limits_{j = 1}^\infty {{\tau _{i\left( j \right)}}{\mu _{i\left( j \right)}}} = + \infty . $

(2.11)

结合β∈(0, 1)和{f(${{\hat x}_{k\left( j \right)}}$)}是单调有界序列, 由公式(2.10)可得到v_i(j)^τ→0, j→∞.再由公式(1.10), (2.7)和(2.8)有

$ \begin{array}{l} v_{i\left( j \right)}^\tau = {{\hat e}_{i\left( j \right)}} + < {{\hat g}_{i\left( j \right)}},{{\hat x}_{k\left( j \right)}} - {{\hat x}_{k\left( {j + 1} \right)}} > = {{\hat e}_{i\left( j \right)}} + \\ \frac{1}{{{\tau _{i\left( j \right)}}{u_{i\left( j \right)}}}} < \nabla h\left( {{{\hat x}_{k\left( j \right)}}} \right) - \nabla h\left( {{{\hat x}_{k\left( {j + 1} \right)}}} \right),{{\hat x}_{k\left( j \right)}} - {{\hat x}_{k\left( {j + 1} \right)}} > \ge \\ {{\hat e}_{i\left( j \right)}} + \frac{{{\sigma _h}}}{{{\tau _{i\left( j \right)}}{u_{i\left( j \right)}}}}{\left\| {{{\hat x}_{k\left( j \right)}} - {{\hat x}_{k\left( {j + 1} \right)}}} \right\|^2} \ge 0, \end{array} $

所以

$ {{\hat e}_{i\left( j \right)}} \to 0,{{\hat x}_{k\left( j \right)}} - {{\hat x}_{k\left( {j + 1} \right)}} \to 0,j \to \infty . $

(2.12)

因为下降序列{f(${{\hat x}_{k\left( j \right)}}$)}有界, 不妨假设它收敛到f.要证{f(${{\hat x}_{k\left( j \right)}}$)}→f^*, 因为f≥f^*, 需证f≤f^*.反证法, 假设f > f^*, 则存在ζ > 0和z∈X, 使得f(z)+ζ < f(${{\hat x}_{k\left( j \right)}}$).结合公式(1.4), (2.3), (2.8)和(2.9)有

$ \begin{array}{l} D\left( {z,{{\hat x}_{k\left( {j + 1} \right)}}} \right) = D\left( {z,{{\hat x}_{k\left( j \right)}}} \right) - D\left( {{{\hat x}_{k\left( {j + 1} \right)}},{{\hat x}_{k\left( j \right)}}} \right) + < \\ \nabla h\left( {{{\hat x}_{k\left( j \right)}}} \right) - \nabla h\left( {{{\hat x}_{k\left( {j + 1} \right)}}} \right),z - {{\hat x}_{k\left( {j + 1} \right)}} > = D\left( {z,{{\hat x}_{k\left( j \right)}}} \right) - \\ D\left( {{{\hat x}_{k\left( {j + 1} \right)}},{{\hat x}_{k\left( j \right)}}} \right) + {\tau _{i\left( j \right)}}{\mu _{i\left( j \right)}} < {{\hat g}_{i\left( j \right)}},z - {{\hat x}_{k\left( {j + 1} \right)}} > \le \\ D\left( {z,{{\hat x}_{k\left( j \right)}}} \right) - D\left( {{{\hat x}_{k\left( {j + 1} \right)}},{{\hat x}_{k\left( j \right)}}} \right) + {\tau _{i\left( j \right)}}{\mu _{i\left( j \right)}}\left( {f\left( z \right) - } \right.\\ \left. {f\left( {{{\hat x}_{k\left( j \right)}}} \right) + {{\hat e}_{i\left( j \right)}}} \right) + {\tau _{i\left( j \right)}}{\mu _{i\left( j \right)}} < {{\hat g}_{i\left( j \right)}},{{\hat x}_{k\left( j \right)}} - {{\hat x}_{k\left( {j + 1} \right)}} > = \\ D\left( {z,{{\hat x}_{k\left( j \right)}}} \right) - D\left( {{{\hat x}_{k\left( {j + 1} \right)}},{{\hat x}_{k\left( j \right)}}} \right) + {\tau _{i\left( j \right)}}{\mu _{i\left( j \right)}}\left( {f\left( z \right) - } \right.\\ \left. {f\left( {{{\hat x}_{k\left( j \right)}}} \right) + {{\hat e}_{i\left( j \right)}}} \right) + < \nabla h\left( {{{\hat x}_{k\left( j \right)}}} \right) - \nabla h\left( {{{\hat x}_{k\left( {j + 1} \right)}}} \right),{{\hat x}_{k\left( j \right)}} - \\ {{\hat x}_{k\left( {j + 1} \right)}} > \le D\left( {z,{{\hat x}_{k\left( j \right)}}} \right) + {\tau _{i\left( j \right)}}{\mu _{i\left( j \right)}}\left( {\frac{1}{{{\tau _{i\left( j \right)}}{\mu _{i\left( j \right)}}}} < } \right.\\ \nabla h\left( {{{\hat x}_{k\left( j \right)}}} \right) - \nabla h\left( {{{\hat x}_{k\left( {j + 1} \right)}}} \right),{{\hat x}_{k\left( j \right)}} - {{\hat x}_{k\left( {j + 1} \right)}} > - \\ \left. {\frac{1}{{{\tau _{i\left( j \right)}}{\mu _{i\left( j \right)}}}}D\left( {{{\hat x}_{k\left( {j + 1} \right)}},{{\hat x}_{k\left( j \right)}}} \right) - \zeta + {{\hat e}_{i\left( j \right)}}} \right). \end{array} $

由公式(2.12), 可得

$ \begin{array}{l} \frac{1}{{{\tau _{i\left( j \right)}}{\mu _{i\left( j \right)}}}} < \nabla h\left( {{{\hat x}_{k\left( j \right)}}} \right) - \nabla h\left( {{{\hat x}_{k\left( {j + 1} \right)}}} \right),{{\hat x}_{k\left( j \right)}} - \\ {{\hat x}_{k\left( {j + 1} \right)}} > - \frac{1}{{{\tau _{i\left( j \right)}}{\mu _{i\left( j \right)}}}}D\left( {{{\hat x}_{k\left( {j + 1} \right)}},{{\hat x}_{k\left( j \right)}}} \right) + {{\hat e}_{i\left( j \right)}} \to 0. \end{array} $

因此存在正整数q使得

$ \begin{array}{l} D\left( {z,{{\hat x}_{k\left( {j + 1} \right)}}} \right) \le D\left( {z,{{\hat x}_{k\left( j \right)}}} \right) - \frac{\zeta }{2}{\tau _{i\left( j \right)}}{\mu _{i\left( j \right)}},\\ \forall j \ge q. \end{array} $

对上式求和有0≤D(z, ${{\hat x}_{k\left( {j{\rm{ + }}1} \right)}}$)≤D(z, ${{\hat x}_{k\left( q \right)}}$)-$\frac{\zeta }{2}\sum\limits_{p = q}^j {{\tau _{i\left( p \right)}}{\mu _{i\left( p \right)}}} $, ∀j≥q.令j→+∞, 有

$ \sum\limits_{p = q}^{ + \infty } {{\tau _{i\left( p \right)}}{\mu _{i\left( p \right)}}} \le \frac{{2D\left( {z,{{\hat x}_{k\left( q \right)}}} \right)}}{\zeta } < + \infty , $

与公式(2.11)矛盾, 所以{f(${{\hat x}_{k\left( j \right)}}$)}→f^*, 即{f(${{\hat x}_k}$)}→f^*.

设x^*是{${{\hat x}_k}$}的任一聚点, 由X是非空闭凸集可知x^*∈X, 因此x^*是问题(0.1)的解.