0 引言

考虑如下非线性不等式约束优化问题

${\mathop {\min }\limits_{x \in {R^n}} f\left( x \right)}$

(0.1)

${{\rm{s}}.{\rm{t}}.{c_i}\left( x \right) \le 0,i \in I \buildrel \Delta \over = \left\{ {1, \ldots ,m} \right\},}$

其中$f:{^n} \to $是凸函数但不一定光滑,c_i(i∈I):${^n} \to $是连续可微的凸函数.

在一些实际问题中,有时很难精确计算f的函数值.例如,f是如下max-型函数

$f\left( x \right) = \max \{ {F_u}\left( x \right):u \in U\} ,$

(0.2)

其中对任意给定的u∈U,F_u:${^n} \to $是凸函数,U是一个无限集,此时无法计算f的精确值.然而,对于任意正数ε,可以在有限的时间内找出(0.2)的一个ε-解,即找出一个u_ε∈U满足F_uε(x)≥f(x)-ε,从而得到f(x)的近似值.因此,研究基于非精确数据的优化方法具有重要的意义^[1-3].

文献[4]基于精确数据,提出一个求解问题(0.1)的强次可行方向法,其优点在于能接受不可行的初始点,且一旦产生一个可行迭代点,即自动变为可行下降算法.此外,算法可保证迭代点的强次可行性,同时能防止目标函数过度增大.文献[2]中提出一种非精确数据的思想，即假设对于给定的点x和误差限ε≥0,能够计算得到近似的函数值f_ε(x)≈f(x)和一个近似的次梯度g_ε≈g∈${\partial f\left( x \right)}$满足:

$\begin{array}{*{20}{l}} {{f_\varepsilon }\left( x \right) \in \left[ {f\left( x \right) - \varepsilon ,f\left( x \right) + \varepsilon } \right],}\\ \begin{array}{l} {g_\varepsilon } \in {\partial _\varepsilon }f\left( x \right) = \left\{ {g:f\left( y \right) \ge f\left( x \right) + \langle {\rm{ }}g,y - x\rangle - } \right.\\ \left. {\varepsilon ,\forall y \in {^n}} \right\}. \end{array} \end{array}$

本研究旨在对文献[4]的方法进行改进,结合文献[2]的思想,提出一个基于非精确 数据的非光滑优化强次可行方向法.

1 算法

假设y^j,j=1,…,k为试探点列,ε^j≥0为相应的误差限,${f_{{\varepsilon ^j}}}({y^j})$和$g_{{\varepsilon ^j}}^j$分别为y^j处函数值和次梯度的近似,满足f_ε^j(y^j)∈[f(y^j)-ε^j,f(y^j)+ε^j]及$g_{{\varepsilon ^j}}^j$∈$\partial $_ε^jf(y^j).记g^j=$g_{{\varepsilon ^j}}^j$,因此f在y^j处的近似线性化可定义为^[2]

${f_j}\left( x \right) = {f_{{\varepsilon ^j}}}({y^j}) + \langle {g^j},x - {y^j}\rangle - 2{\varepsilon ^j}.$

(1.1)

由g^j∈$\partial $_ε^jf(y^j) 和f(y^j)≥ f_ε^j(y^j)-ε^j可知

${f_j}\left( x \right) \le {\rm{ }}f\left( x \right),\forall x \in {^n}.$

(1.2)

进而可定义f的近似割平面模型

${{\hat f}^k}\left( x \right) = \max \{ {f_j}\left( x \right),j = 1, \ldots ,k\} .$

记问题(0.1)的可行集F={x∈${{^n}}$:c_i(x)≤0,i∈I}.定义指标集I_-(x)={i∈I:c_i(x)≤0},I₊(x)={i∈I:c_i(x)＞0},约束违反函数φ(x)=max{0,c_i(x),i∈I}.引入改进函数^[4]:

$\begin{array}{l} H\left( {y;x} \right) = \max \{ f\left( y \right) - f\left( x \right) - \delta \left( x \right);{c_i}\left( y \right),i \in \\ {I_ - }\left( x \right);{\rm{ }}{c_i}\left( y \right) - \varphi \left( x \right),i \in {I_ + }\left( x \right)\} , \end{array}$

其中δ(x):${{^n}}$→[0,+∞)连续,并满足δ(x)=0 当且仅当x∈F.对于第k次迭代,缩写${I^k}_ - = {I_ - }({x^k}),I_ + ^k = {I_ + }({x^k}),{\varphi ^k} = \varphi ({x^k}),{\delta ^k} = \delta ({x^k})$.

下面给出改进函数的性质.

引理1.1^[4] 若问题(0.1)满足Slater约束规格,即存在一个向量x′∈${{\mathbb{R}}^{n}}$满足 c_i(x′)＜0,$\partial $i∈I,则以下3个命题等价：(i)x是问题(0.1)的最优解;(ii) min{H(y;x):y∈${{\mathbb{R}}^{n}}$=H(x;x)=0;(iii) 0∈$\partial $H(x;x).

基于引理1.1,并结合邻近点方法思想^[5],选取新的试探点如下:

$\begin{array}{l} {y^{k + 1}} = \arg \min \{ H(y;{x^k}) + \frac{1}{2}{\rho ^k}y - {x^k}{^2}:y \in \\ {^n}\} , \end{array}$

(1.3)

其中ρ^k＞0是邻近参数,x^k∈{y^j}_j=1^k为邻近中心点.然而,问题(1.3)的求解较困难.因此,基于非精确数据,并结合文献[4]的思想,本文提出如下寻找搜索方向子问题:

$\begin{array}{l} \mathop {\min }\limits_{d \in {^n},z \in } z + \frac{1}{2}{\rho ^k}d{^2},\\ {\rm{s}}.{\rm{t}}. - {\alpha ^k}_j + \langle {\rm{ }}{g^j},d\rangle \le z + {\delta ^k},j \in {J^k},\\ - \alpha _s^k + \langle {\rm{ }}{s^{k - 1}},d\rangle \le z + {\delta ^k},\\ {c_i}\left( {{x^k}} \right) + \langle \nabla {c_i}\left( {{x^k}} \right),d\rangle \le z,i \in I_ - ^k\\ {c_i}\left( {{x^k}} \right) + \langle \nabla {c_i}\left( {{x^k}} \right),d\rangle \le z + {\varphi ^k},i \in I_ + ^k \end{array}$

(1.4)

其中z∈R是一个辅助变量,${{J}^{k}}\subseteq \left\{ 1,\ldots ,k \right\},\alpha _{j}^{k}={{f}_{\varepsilon }}({{x}^{k}})-f_{j}^{k}+\varepsilon ,$ $\alpha _{s}^{k}={{f}_{\varepsilon }}({{x}^{k}})-f_{s}^{k}+\varepsilon ,f_{j}^{k}={{f}_{j}}({{x}^{k}});{{s}^{k-1}}$和f_s^k分别为过往的近似函数值和次梯度的聚集(具体将在算法中明确),文献[6]中证明存在λ_j≥0,j=1,…,k-1,使得

$({s^{k - 1}},f_s^k) = \sum\limits_{j = 1}^{k - 1} {{{\bar \lambda }_j}({g^j},f_j^k)} ,\sum\limits_{k - 1}^{j = 1} {{{\bar \lambda }_j} = 1} .$

(1.5)

设(d^k,z^k)是(1.4)式的最优解.由于(1.4)式是一个带线性约束的凸规划,故(d^k,z^k)亦为(1.4)式的KKT点,即存在乘子λ_j^k,j∈J^k,λ_s^k,μ_i^k,i∈I,使得

$\begin{array}{l} {\rho ^k}{d^k} + \sum\limits_{j \in {J^k}} {\lambda _j^k} {g^j} + \lambda _s^k{s^{k - 1}} + {\rm{ }}\sum\limits_{i \in I} {\mu _i^k} \nabla {\rm{ }}{c_i}\left( {{x^k}} \right) = 0,\\ \sum\limits_{j \in {J^k}} {\lambda _j^k + \lambda _s^k} + \sum\limits_{i \in I} {\mu _i^k = 1} ,\\ 0 \le \lambda _j^k \bot \left( { - \alpha _j^k + \langle {g^j},{d^k}\rangle - {z^k} - {\delta ^k}} \right) \le 0,\\ j \in {J^k},\\ 0 \le \lambda _s^k \bot \left( { - \alpha _s^k + \left\langle {{s^{k - 1}},{d^k}} \right\rangle - {z^k} - {\delta ^k}} \right) \le 0,\\ 0 \le \mu _j^k \bot \left( {{c_i}\left( {{x^k}} \right) + \left\langle {{\nabla _i}\left( {{x^k}} \right),{d^k}} \right\rangle - {z^k}} \right) \le 0,\\ i \in I_ - ^k,\\ 0 \le {\mu ^k}_i \bot \left( {{c_i}\left( {{x^k}} \right) + \left\langle {\nabla {c_i}\left( {{x^k}} \right),{d^k}} \right\rangle - {z^k} - {\varphi ^k}} \right) \le 0,\\ i \in I_ + ^k. \end{array}$

(1.6)

更新聚集次梯度如下:

$({s^k},_s^k) = \frac{1}{{{\theta ^k}}}(\sum\limits_{j \in {J^k}} {\lambda _j^k({g^j},f_j^k)} + \lambda _s^k({s^{k - 1}},f_s^k)),$

(1.7)

其中${\theta ^k} = \sum\limits_{j \in {J^k}} {\lambda _j^k + } \lambda _s^k$(不失一般性假设θ^k＞0).

记$\overset{\vee }{\mathop{\text{ }a}}\,_{s}^{k}={{f}_{\varepsilon }}({{x}^{k}})-\overset{\vee }{\mathop{\text{ }f}}\,_{s}^{k}+\varepsilon $,有 $\sum\limits_{j\in {{J}^{k}}}{\lambda _{j}^{k}\alpha _{j}^{k}+\lambda _{s}^{k}\alpha _{j}^{k}={{\theta }^{k}}\overset{\vee }{\mathop{\text{ }a}}\,_{j}^{k}}$.

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

引理1.2 设(d^k,z^k)是问题(1.4)的最优解,则

$(\text{i}){{z}^{k}}=-({{\rho }^{k}}{{\left\| {{d}^{k}} \right\|}^{2}}+{{\overset{\vee }{\mathop{\text{ }a}}\,}^{k}}),$

(1.8)

其中,

${{\overset{\vee }{\mathop{\text{ }a}}\,}^{k}}={{\theta }^{k}}(\overset{\vee }{\mathop{\text{ }a}}\,_{s}^{k}+{{\delta }^{k}})-\sum\limits_{i\in I_{-}^{k}}{{{\mu }^{k}}_{i}{{c}_{i}}({{x}^{k}})}-\sum\limits_{i\in I_{+}^{k}}{{{\mu }^{k}}_{i}{{c}_{i}}({{x}^{k}})}-{{\varphi }^{k}}).$

(1.9)

$\begin{array}{*{35}{l}} (\text{ii}){{g}^{j}}\in {{\partial }_{\in }}f\left( {{x}^{k}} \right),\in =\alpha _{j}^{k},j=1,\ldots ,k, \\ {{s}^{k}}\in {{\partial }_{\in }}f\left( {{x}^{k}} \right),\in =\overset{\vee }{\mathop{\text{ }a}}\,_{s}^{k}, \\ -{{\rho }^{k}}{{d}^{k}}\in {{\partial }_{\in }}H\left( {{x}^{k}};{{x}^{k}} \right),\in ={{\overset{\vee }{\mathop{\text{ }a}}\,}^{k}}. \\ \end{array}$

(1.10)

(iii) 如果z^k=0,则d^k=0,且x^k是问题(0.1)的一个最优解.

证明 (i) 由KKT条件(1.6)中的互补关系和(1.7)式有

$\begin{align} & {{z}^{k}}=-{{\rho }^{k}}{{\left\| {{d}^{k}} \right\|}^{2}}+\sum\limits_{j\in {{J}^{k}}}{\lambda _{j}^{k}}\left( -\alpha _{j}^{k}-{{\delta }^{k}} \right)+ \\ & \lambda _{s}^{k}(-\alpha _{s}^{k}-{{\delta }^{k}})+\sum\limits_{i\in I_{-}^{k}}{\mu _{j}^{k}}{{c}_{i}}({{x}^{k}})+\sum\limits_{i\in I_{+}^{k}}{\mu _{j}^{k}}({{c}_{i}}({{x}^{k}})- \\ & {{\varphi }^{k}})=-{{\rho }^{k}}{{\left\| {{d}^{k}} \right\|}^{2}}-{{\theta }^{k}}(\overset{\vee }{\mathop{\text{ }a}}\,_{s}^{k}+{{\delta }^{k}})+\sum\limits_{i\in I_{-}^{k}}{\mu _{j}^{k}}{{c}_{i}}({{x}^{k}})+ \\ & \sum\limits_{i\in I_{+}^{k}}{\mu _{j}^{k}}({{c}_{i}}({{x}^{k}})-{{\varphi }^{k}})=-({{\rho }^{k}}{{\left\| {{d}^{k}} \right\|}^{2}}+{{\overset{\vee }{\mathop{\text{ }a}}\,}^{k}}). \\ \end{align}$

故(1.8)式成立.

(ii) 由(1.2)式知,

$\begin{array}{l} f\left( x \right) \ge {f_j}\left( x \right) = f_j^k + \left\langle {{g^j},x - {x^k}} \right\rangle = f\left( {{x^k}} \right) - \\ f\left( {{x^k}} \right) + f_j^k + \left\langle {{g^j},x - {x^k}} \right\rangle \ge {\rm{ }}f\left( {{x^k}} \right) + \langle {g^j},x - \\ {x^k}\rangle + f_j^k - ({f_\varepsilon }({x^k}) + \varepsilon ){\rm{ }} = f({x^k}) + {\rm{ }}\left\langle {{g^j},x - {x^k}} \right\rangle - \alpha _j^k, \end{array}$

(1.11)

从而(1.10)式的第一个式子成立.类似地,根据(1.5)式知

$f\left( x \right) \ge f({x^k}) + \left\langle {{\rm{ }}{s^{k - 1}},x - {x^k}} \right\rangle - \alpha _s^k.$

(1.12)

在(1.11)式和(1.12)式两边分别乘以λ_j^k,j∈J^k和λ_s^k再进行求和,有

$f\left( x \right)\ge f({{x}^{k}})+\left\langle {{s}^{k}},x-{{x}^{k}} \right\rangle -\overset{\vee }{\mathop{\text{ }a}}\,_{s}^{k},$

(1.13)

故(1.10)式的第二个式子成立.

根据c_i的凸性,有

${c_i}\left( x \right) \ge {\rm{ }}{c_i}({x^k}) + \langle \nabla {\rm{ }}{c_i}({x^k}),x - {x^k}\rangle .$

因此,

$\begin{array}{l} \sum\limits_{i \in I} {\mu _i^k} {c_i}\left( x \right) \ge \sum\limits_{i \in I} {\mu _i^k} ({c_i}({x^k}) + \langle \nabla {\rm{ }}{c_i}({x^k}),x - \\ {x^k}\rangle ). \end{array}$

此式结合(1.6)式,(1.13)式,θ^k≤1及H(x^k;x^k)=0可得

$\begin{array}{*{35}{l}} H\left( x;{{x}^{k}} \right)=\max \left\{ f\left( x \right)-f\left( {{x}^{k}} \right)-{{\delta }^{k}};{{c}_{i}}\left( x \right),i\in \right. \\ I_{-}^{k};{{c}_{i}}\left( x \right)-{{\varphi }^{k}},i\in {{I}^{k}}_{+}\ge {{\theta }^{k}}\left( f\left( x \right)-f\left( {{x}^{k}} \right)-{{\delta }^{k}} \right)+ \\ \sum\limits_{i\in I}{\mu _{i}^{k}}{{c}_{i}}\left( x \right)-\sum\limits_{i\in I_{+}^{k}}{\mu _{i}^{k}}{{\varphi }^{k}}\ge {{\theta }^{k}}\left( \left\langle {{s}^{k}},x-{{x}^{k}} \right\rangle -\overset{\vee }{\mathop{\text{ }a}}\,_{s}^{k}-{{\delta }^{k}} \right)+ \\ \sum\limits_{i\in I}{\mu _{i}^{k}}{{c}_{i}}\left( {{x}^{k}} \right)+\sum\limits_{i\in I}{\mu _{i}^{k}}\left\langle \nabla {{c}_{i}}\left( {{x}^{k}} \right),x-{{x}^{k}} \right\rangle -\sum\limits_{i\in I_{+}^{k}}{\mu _{i}^{k}}{{\varphi }^{k}}= \\ H\left( {{x}^{k}};{{x}^{k}} \right)+\left\langle -{{\rho }^{k}}{{d}^{k}},x-{{x}^{k}} \right\rangle -\left( {{\theta }^{k}}\left( \overset{\vee }{\mathop{\text{ }a}}\,_{s}^{k}+{{\delta }^{k}} \right)- \right. \\ \left. \sum\limits_{i\in {{I}^{k}}_{-}}{\mu _{i}^{k}}{{c}_{i}}\left( {{x}^{k}} \right)-\sum\limits_{i\in I_{+}^{k}}{\mu _{i}^{k}}\left( {{c}_{i}}\left( {{x}^{k}} \right)-{{\varphi }^{k}} \right) \right)=H\left( {{x}^{k}};{{x}^{k}} \right)+ \\ \left\langle -{{\rho }^{k}}{{d}^{k}},x-{{x}^{k}} \right\rangle -{{\overset{\vee }{\mathop{\text{ }a}}\,}^{k}}. \\ \end{array}$

由此证明(1.10)式的第三个式子.

(iii) 由于${{\overset{\vee }{\mathop{\text{ }a}}\,}^{k}}$≥0,故由(1.8)式知,当z^k=0时有ρ^kd^k=0和${{\overset{\vee }{\mathop{\text{ }a}}\,}^{k}}$=0,从而$0 \in \partial H({x^k};{x^k})$;x^k).故根据引理1.1(iii) 知x^k是问题(0.1)的一个最优解.

算法1.1

步骤0(初始化) 选取初始点x¹∈R_n,初始误差限ε¹≥0,终止参数ε_TOL≥0,线搜索参数β∈(0,1),邻近参数ρ_min＞0,ρ¹＞ρ_min,步长下界t∈(0,0.1］.选择两个线搜索参数m_L和m_R满足0＜m_L＜m_R＜1.令y¹=x¹,s⁰=g¹∈$\partial $_ε¹ f(x¹),f_s¹=f₁¹=f_ε¹(x¹),J¹={1}.置k=1,l=0 及k(0)=1.

步骤1(寻找搜索方向) 令ε=ε^k,求解子问题(1.4)得到最优解(d^k,z^k)和乘子λ_j^k,j∈J^k,λ_s^k,μ_i^k,i∈I.根据(1.7)式计算s^k,$\mathop f\limits^ \vee $_s^k 和α_s^k.

步骤2(误差限更新) 如果ε^k＞-(m_R-m_L)tz^k/5,置ε^k=ε^k/2并返回步骤1; 否则,转步骤3.

步骤3(终止准则) 如果z^k≥-ε_TOL,算法终止;否则,转步骤4.

步骤4(线搜索) 计算试探步长t^k,它是序列{1,β,β²,…}中第一个满足下列不等式组的t值:

${c_i}({x^k} + t{\rm{ }}{d^k}) \le {\varphi ^k} + {m_L}t{\rm{ }}{z^k},i \in I_ + ^k,$

(1.14)

${c_i}({x^k} + t{\rm{ }}{d^k}) \le 0,i \in I_ - ^k.$

(1.15)

如果

${f_{{\varepsilon ^k}}}({x^k} + {t^k}{d^k}) \le {f_{{\varepsilon ^k}}}({x^k}) + {m_L}{t^k}{z^k} + {t^k}{\delta ^k} - 2{\varepsilon ^k},$

则令t_L^k=t^k(有效步)及辅助步长t_R^k=t^k,置k(l+1)=k+1,l:=l+1;否则令t_L^k=0(无效步)及t_R^k=max{t,t^k}.

步骤5(更新) 令${\varepsilon ^{k + 1}} = {\varepsilon ^k},{x^{k + 1}} = {x^k} + {t^k}_L{d^k},{y^{k + 1}} = {x^k} + {t^k}_R{d^k}$.选取${{\hat J}^k} \subseteq {J^k}$并令${J^{k + 1}} = {{\hat J}^k} \cup \left\{ {k + 1} \right\}$,计算${g^{k + 1}} \in {\partial _{{\varepsilon ^{k + 1}}}}f({y^{k + 1}})$及$f_{k + 1}^{^{k + 1}} = {f_{{\varepsilon ^{k + 1}}}}({y^{k + 1}}) + \left\langle {{\rm{ }}{g^{k + 1}},{x^{k + 1}} - {y^{k + 1}}} \right\rangle - 2{\varepsilon ^{k + 1}}$,

$\begin{align} & f_{j}^{k+1}=f_{j}^{k}+\left\langle {{g}^{j}},{{x}^{k+1}}-{{x}^{k}} \right\rangle ,j\in {{{\hat{J}}}^{k}}, \\ & f_{s}^{k+1}=\overset{\vee }{\mathop{\text{ }f}}\,_{s}^{k}+\left\langle {{s}^{k}},{{x}^{k+1}}-{{x}^{k}} \right\rangle . \\ \end{align}$

(1.16)

步骤6(邻近参数选择) 如果${x^{k + 1}} \ne {x^k}$,取${\rho ^{k + 1}} \in [{\rho _{\min }},{\rho ^k}]$; 否则,ρ^k+1=ρ^k.

步骤7 令k:=k+1,返回步骤1.

引理 1.3^[4] 算法1.1是适定的,即线搜索(1.14)和(1.15)能在有限次计算后终止.

引理 1.4 算法1.1必定出现以下两种情形之一.

(i) 存在一个指标k₀使得φ^k₀=0,从而φ^k≡0,δ^k≡0和f(x^k+1)≤f(x^k),对于所有的k≥ k₀成立;

(ii) 对任意的k,有${\varphi ^k} > 0,{\varphi ^{k + 1}} \le {\varphi ^k},{I^k}_ - \subseteq {I^{k + 1}}_ - $.

证明 (i) 由步骤4可知,φ^k≡0及δ^k≡0对k≥k₀成立.现证明f(x^k+1)≤f(x^k).根据步骤4,如果是一个有效步,由z^k＜0可得

$\begin{array}{l} f({x^{k + 1}}) \le {f_{{\varepsilon ^k}}}({x^{k + 1}}) + {\varepsilon ^k} \le {f_{{\varepsilon ^k}}}({x^k}) + {m_L}{t^k}_L{z^k} - \\ {\varepsilon ^k} \le f({x^k}) + {m_L}{t^k}_L{z^k} \le f({x^k}). \end{array}$

若是一个无效步,则有f(x^k+1)=f(x^k).

(ii) 根据线搜索(1.14)和(1.15)易证.

2 算法的收敛性

在以下收敛分析中取ε_TOL=0.若算法有限步终止于x^k点,则由步骤3可知z^k=0,因此由引理1.2(iii) 得x^k是问题(0.1)的一个最优解.假设算法产生一个无限迭代点列,以下将证明该序列的任一聚点都是问题(0.1)的一个最优解.根据引理1.4,在下面的分析中不妨假设${I^k}_ - \equiv {I_ - },{I^k}_ + \equiv {\rm{ }}{I_ + }$.

引理2.1 邻近参数序列{ρ^k}单调不增,且有正的下界.

证明 根据步骤6,显然{ρ^k} 单调不增,且ρ^k≥ρ_min＞0.

引理2.2 假设存在无限指标集$K \subseteq \left\{ {1,2, \ldots } \right\}$和一个点x∈R_n满足${x^k}{\rm{ }}\bar x$及${z^k}0$,则是问题(0.1)的一个最优解.

证明 由${z^k}0$和(1.8)式知ρ^kd^k→0,$\mathop a\limits^ \vee $^k→0,k∈K.故由${x^k}{\rm{ }}\bar x$及引理1.2知$0 \in \partial H\left( {\bar x;\bar x} \right)$,因此是问题(0.1)的一个最优解.

分两种情形证明.首先考虑有无限个有效步的情形.类似文献[7],有如下引理.

引理2.3 假设存在一个无限指标集$L \subseteq \left\{ {1,2, \ldots } \right\}$和一个点x∈R_n使得x^k(l)→x, l→∞,l∈ L,则是问题(0.1)的一个最优解.

接下来考虑有效步有限的情形,即存在一个指标使得x^k=x^k,k≥k.下面证明x^k是问题(0.1)的一个最优解.

引理2.4 令${{\omega }^{k}}=\frac{1}{2}{{\rho }^{k}}{{\left\| {{d}^{k}} \right\|}^{2}}+{{\rho }^{k}}{{\overset{\vee }{\mathop{\text{ }a}}\,}^{k}}$,则ω^k是以下问题的最优值

$\begin{array}{l} \min \frac{1}{2}\sum\limits_{j \in {\rm{ }}{J^k}} {{\lambda _j}} {g^j} + {\lambda _s}{s^{k - 1}} + \\ \sum\limits_{i \in {\rm{ }}I} {{\mu _i}} \nabla {c_i}({x^k}){^2} - {\rho ^k}[\sum\limits_{j \in {J^k}} {{\lambda _j}} ( - {\alpha ^k}_j - {\rm{ }}{\delta ^k}) - {\lambda _s}( - {\alpha ^k}_s - \\ {\delta ^k}) - \sum\limits_{i \in {I_ - }} {{\mu _i}{c_i}({x^k})} - \sum\limits_{i \in {I_ + }} {{\mu _i}({c_i}({x^k})} - {\varphi ^k}){\rm{ }}]\\ {\rm{s}}.{\rm{t}}.{\lambda _j} \ge 0,j \in {J^k},{\lambda _s} \ge 0,{\mu _i} \ge 0,i \in I,\\ \sum\limits_{j \in {J^k}} {{\lambda _j}} + {\lambda _s} + \sum\limits_{i \in I} {{\mu _i} = 1} . \end{array}$

(2.1)

证明 由于问题(2.1)是问题(1.4)的对偶问题,故问题(2.1)的最优解即为问题(1.4)的KKT乘子.因此,由(1.6)式,(1.9)式及ω^k的定义可得结论成立.

引理 2.5^[6] 设n维向量d,g及数η∈(0,1),ρ＞0,C,ω,z,$\mathop a\limits^ \vee $和α满足

$\omega = \frac{1}{2}\rho {\rm{ }}d{^2} + \rho \mathop \alpha \limits^ \vee ,z = - (\rho d{^2} + \mathop \alpha \limits^ \vee ),$

$ - \alpha + \left\langle {g,d} \right\rangle \ge {\rm{ }}\eta {\rm{ }}z,C \ge \max \left\{ {\rho {\rm{ }}d,g,\mathop \alpha \limits^ \vee ,1} \right\}.$令ω=min{Q(υ):υ∈0, 1]},其中$Q\left( \upsilon \right) = \frac{1}{2}\left( {1 - \upsilon } \right)\left( { - \rho {\rm{ }}d} \right) + \upsilon {\rm{ }}g{^2} + \rho \left[ {\left( {1 - \upsilon } \right)\mathop \alpha \limits^ \vee + \upsilon \alpha } \right]$,则$\bar \omega \le \omega - {\rho ^2}{\left( {1 - \eta } \right)^2}{\omega ^2}/8{C^2}$.

基于引理2.5,得到以下一个重要的结论.

引理 2.6 假设对于某个k＞1有t_L^k=0及ε^k-1=ε^k,则

$({\rm{i}}) - ({\alpha ^k}_k + {\delta ^{k - 1}}) + \left\langle {{g^k},{d^{k - 1}}} \right\rangle \ge {m_{_R}}{z^{k - 1}},$

(2.2)

其中$\varepsilon _k^k = {f_{{\varepsilon ^k}}}({x^k}) - {f^k}_k + {\varepsilon ^k}$;

$\begin{array}{l} ({\rm{ii}}){\omega ^k} \le {\omega ^{k - 1}} - {\left( {{\rho ^{k - 1}}} \right)^2}(1 - \\ {m_{_R}}{)^2}{({\omega ^{k - 1}})^2}/8{({C^k})^2}, \end{array}$

(2.3)

其中C^k满足C^k≥max{‖ρ^k-1 d^k-1‖,‖g^k‖,${{\overset{\vee }{\mathop{\alpha }}\,}^{k-1}}$,1}.

证明 (i) 由算法1.1中步骤4知当t_L^k-1=0,ε^k-1=ε^k时,x^k=x^k-1,y^k=x^k-1+t_R^k-1d^k-1,且有

${f_{{\varepsilon ^k}}}({y^k}) > {f_{{\varepsilon ^k}}}({x^{k - 1}}) + {m_L}t_R^{k - 1}{z^{k - 1}} + t_R^{k - 1}{\delta ^{k - 1}} - 2{\varepsilon ^k}.$

(2.4)

因此,由(1.1)式和(2.4)式有

$\begin{array}{l} - \left( {{\alpha ^k}_k + {\delta ^{k - 1}}} \right) = - \left( {{f_{{\varepsilon ^k}}}\left( {{x^k}} \right) - {f^k}_k + {\varepsilon ^k}} \right) - {\delta ^{k - 1}} = \\ - ({f_{{\varepsilon ^k}}}({x^k}) - {f_{{\varepsilon ^k}}}({y^k}) - \left\langle {{g^k},{x^k} - {y^k}} \right\rangle + 3{\varepsilon ^k}) - \\ {\delta ^{k - 1}} = - ({f_{{\varepsilon ^k}}}({x^{k - 1}}) - {f_{{\varepsilon ^k}}}({y^k}) - \left\langle {{\rm{ }}{g^k},{x^{k - 1}} - {y^k}} \right\rangle + \\ 3{\varepsilon ^k}) - {\delta ^{k - 1}} = {f_{{\varepsilon ^k}}}({y^k}) - {t^{k - 1}}_R\left\langle {{g^k},{d^{k - 1}}} \right\rangle - {f_{{\varepsilon ^k}}}({x^{k - 1}}) - \\ {\delta ^{k - 1}} - 3{\varepsilon ^k} \ge {m_{_L}}t_R^{k - 1}{z^{k - 1}} - t_R^{k - 1}\left\langle {{g^k},{d^{k - 1}}} \right\rangle + (1 - \\ {t^{k - 1}}_R){\delta ^{k - 1}} - 5{\varepsilon ^k}. \end{array}$

(2.5)

由${\varepsilon ^k}_k = {f_{{\varepsilon ^k}}}({x^k}) - {f^k}_k + {\varepsilon ^k} \ge {\rm{ }}f({x^k}) - {f^k}_k \ge 0$知${\varepsilon ^k}_k = {f_{{\varepsilon ^k}}}({x^{k - 1}}) - {f_{{\varepsilon ^k}}}({y^k}) + {t^{k - 1}}_R\left\langle {{g^k},{d^{k - 1}}} \right\rangle + 3{\varepsilon ^k} \ge 0$,

因此根据(2.4)式可得

$\left\langle {{g^k},{d^{k - 1}}} \right\rangle \ge {\rm{ }}{m_{_L}}{z^{k - 1}} + {\delta ^{k - 1}} - 5{\varepsilon ^k}/t_R^{k - 1}.$

(2.6)

结合(2.5)式,(2.6)式和$t_R^{k - 1} \in \left[ {t,1} \right]$得

$\begin{array}{l} - ({\alpha ^k}_k + {\delta ^{k - 1}}) + \left\langle {{g^k},{d^{k - 1}}} \right\rangle \ge {m_L}t_R^{k - 1}{z^{k - 1}} + (1 - \\ t_R^{k - 1})(\left\langle {{g^k},{d^{k - 1}}} \right\rangle - {\delta ^{k - 1}}) - 5{\varepsilon ^k} \ge {\rm{ }}{m_L}t_R^{k - 1}{z^{k - 1}} + (1 - \\ t_R^{k - 1})({m_{_L}}{z^{k - 1}} - 3{\varepsilon ^k}/t_R^{k - 1}) - 5{\varepsilon ^k} = {m_L}{z^{k - 1}} - 5{\varepsilon ^k}/{t^{k - 1}}_R \ge \\ {m_L}{z^{k - 1}} - 5{\varepsilon ^k}/t{\rm{ }} \end{array}$

由步骤2知$5{{\varepsilon }^{k}}/\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{t}=5{{\varepsilon }^{k-1}}/\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{t}>-({{m}_{R}}-{{m}_{L}}){{z}^{k-1}}$,从而得到

$ - ({\alpha ^k}_k + {\delta ^{k - 1}}) + \left\langle {{g^k},{d^{k - 1}}} \right\rangle \ge {m_R}{z^{k - 1}}.$

(ii) 对任意的υ∈>[0, 1],定义问题(2.1)的可行解

$\begin{array}{*{20}{l}} {{\lambda _k}\left( \upsilon \right) = \upsilon ,{\lambda _j}\left( \upsilon \right) = 0,j \in {J^k}\left\{ k \right\},}\\ {{\lambda _s}\left( \upsilon \right) = \left( {1 - \upsilon } \right){\theta ^{k - 1}},{\mu _i}\left( \upsilon \right) = \left( {1 - \upsilon } \right){\mu ^{k - 1}}_i,i \in I.} \end{array}$

由(1.16)式和x^k-1=x^k可得

$\begin{array}{*{35}{l}} {{\alpha }^{k}}_{s}={{f}_{{{\varepsilon }^{k}}}}({{x}^{k}})-{{f}^{k}}_{s}+{{\varepsilon }^{k}}={{f}_{{{\varepsilon }^{k}}}}({{x}^{k-1}})-\overset{\vee }{\mathop{\text{ }f}}\,_{s}^{k-1}+{{\varepsilon }^{k}}= \\ \overset{\vee }{\mathop{\alpha }}\,_{s}^{k-1}, \\ \end{array}$

(2.7)

因此

$\begin{array}{l} \sum\limits_{j \in {J^k}} {{\lambda _j}\left( \upsilon \right){\rm{ }}{g^j}} + {\lambda _s}\left( \upsilon \right){s^{k - 1}} + \sum\limits_{i \in I} {{\mu _i}\left( \upsilon \right)} \nabla {\rm{ }}{c_i}\left( {{x^k}} \right) = \\ \upsilon {g^k} + \left( {1 - \upsilon } \right){\theta ^{k - 1}}{s^{k - 1}} + \left( {1 - \upsilon } \right)\sum\limits_{i \in I} {\mu _i^{k - 1}} \nabla {\rm{ }}{c_i}\left( {{x^{k - 1}}} \right) = \\ \upsilon {g^k} + \left( {1 - \upsilon } \right)( - {\rho ^{k - 1}}{d^{k - 1}}). \end{array}$

此外,根据(2.7)式有

$\begin{align} & -\sum\limits_{j\in {{J}^{k}}}{{{\lambda }_{j}}}\left( -{{\alpha }^{k}}_{j}-{{\delta }^{k}} \right)-{{\lambda }_{s}}\left( -{{\alpha }^{k}}_{s}-{{\delta }^{k}} \right)- \\ & \sum\limits_{i\in {{I}_{-}}}{{{\mu }_{i}}{{c}_{i}}({{x}^{k}})}-\sum\limits_{i\in {{I}_{+}}}{{{\mu }_{i}}({{c}_{i}}({{x}^{k}})-{{\varphi }^{k}})}=-\upsilon (-\alpha _{k}^{k}-{{\delta }^{k}})- \\ & \left( 1-\upsilon \right){{\theta }^{k-1}}(-{{\alpha }^{k}}_{s}-{{\delta }^{k}})-\left( 1-\upsilon \right)\sum\limits_{i\in {{I}_{-}}}{{{\mu }_{i}}^{k-1}{{c}_{i}}({{x}^{k}})}-\left( 1- \right. \\ & \upsilon )\sum\limits_{i\in {{I}_{+}}}{{{\mu }_{i}}^{k-1}}({{c}_{i}}({{x}^{k}})-{{\varphi }^{k}})=\upsilon ({{\alpha }^{k}}_{k}+{{\delta }^{k-1}})+\left( 1- \right. \\ & \upsilon )({{\theta }^{k-1}}(\overset{\vee }{\mathop{\alpha }}\,_{s}^{k-1}+{{\delta }^{k-1}})-\sum\limits_{i\in {{I}_{-}}}{{{\mu }_{i}}^{k-1}}{{c}_{i}}({{x}^{k-1}})- \\ & \sum\limits_{i\in {{I}_{+}}}{{{\mu }_{i}}^{k-1}}({{c}_{i}}({{x}^{k-1}})-{{\varphi }^{k-1}}))=\upsilon ({{\alpha }^{k}}_{k}+{{\delta }^{k-1}})+\left( 1-\upsilon \right) \\ & {{\overset{\vee }{\mathop{\alpha }}\,}^{k-1}}. \\ \end{align}$

令ω是如下问题的最优值

$\begin{align} & \min \frac{1}{2}{{\left\| \left( 1-\upsilon \right)\left( -{{\rho }^{k-1}}{{d}^{k-1}} \right)+\upsilon {{g}^{k}} \right\|}^{2}}+ \\ & {{\rho }^{k-1}}[\left( 1-\upsilon \right){{\overset{\vee }{\mathop{\alpha }}\,}^{k-1}}+\upsilon ({{\alpha }^{k}}_{k}+{{\delta }^{k-1}})], \\ & \text{s}.\text{t}.\upsilon \in [0,1]. \\ \end{align}$

则由引理2.4知ω^k≤ω.在定理2.5中令d=d^k-1,g=g^k,η=m_R,ρ=ρ^k-1,ω=ω^k-1,z=z^k-1,$\overset{\vee }{\mathop{\alpha }}\,={{\overset{\vee }{\mathop{\alpha }}\,}^{k-1}}$,α=α_k^k+δ^k-1,并结合(2.2)式,我们有ω^k≤ω≤ ω^k-1-(ρ^k-1)²(1-m_R)²(ω^k-1)²/8(C^k)².

定理 2.1 (i) 如果算法1.1有限步终止于第k次迭代,则x^k是问题(0.1)的一个最优解;(ii) 如果算法1.1在第k次迭代时无限次在步骤1与步骤2之间循环,则x^k是问题(0.1)的一个最优解;(iii) 如果算法1.1产生一个无限迭代序列{x^k},则其任一聚点x^*都是问题(0.1)的一个最优解.

证明 (i) 如果算法1.1有限次终止于点x^k,则z^k=0.根据引理1.2知x^k是问题(0.1)的一个最优解.

(ii) 如果算法在第k次迭代时于步骤1 与步骤2 之间无限次循环,此时因为每次在步骤2 中ε^k 减半,$({{m}_{R}}-{{m}_{L}})>0,-{{z}^{k}}={{\rho }^{k}}{{\left\| {{d}^{k}} \right\|}^{2}}+{{\overset{\vee }{\mathop{\varepsilon }}\,}^{k}}\ge 0$,所以${\varepsilon ^k} \to 0,{z^k} \to 0$. 由引理2.2知x^k是问题(0.1)的一个最优解.

(iii) 现在假设算法1.1产生一个无限迭代序列{x^k},且x^*是其任一聚点.则分两种情况证明x^*是问题(0.1)的一个最优解.

情形 1 有无限多个有效步.此时,必然存在无限指标集$L \subseteq \left\{ {1,2, \ldots } \right\}$使得${x^{k(l)}} \to {\rm{ }}{x^*},l \to \infty ,l \in L$.因此,根据引理2.3知x^*是问题(0.1)的一个最优解.

情形 2 有效步有限.则存在一个指标使得${x^k} \equiv {x^{\bar k}} = {x^*}$且有ρ^k≡ρ.如果ε^k→0,类似与(ii) 的证明,知x^*是问题(0.1)的一个最优解.设对于任意的k≥k有ε^k≡ε＞0,此时存在一个常数C＞0使得$C \ge \max \{ \rho {\rm{ }}{d^{k - 1}},{g^k},\alpha {^{k - 1}},1\} ,\forall k \ge \bar k$.结合(2.3)式,有

${\omega ^k} \le {\omega ^{k - 1}} - {\rho ^2}{(1 - {m_{_R}})^2}{({\omega ^{k - 1}})^2}/8{C^2},$

由此可得ω^k→0,k→∞,从而z^k→0,k→∞.因此,由引理2.2可知x^*是问题(0.1)的一个最优解.