最近, Potra^[1]提出$ {{\Bbb R}} ^{n} $上权互补问题(wCP)的概念, 并将线性规划和加权中心问题^[2]、二次规划和加权中心问题以及Fisher市场均衡问题转化为权互补问题求解. 特别地, Potra证明了Fisher市场均衡问题转化为权互补问题比转化为互补问题可以被更有效地求解. 这一优点使得权互补问题的相关理论与方法备受关注, 参见文献[3-5].

基于上述权互补问题的成果, 本文研究求解对称锥上权互补问题的算法. 令$ F(x):{\cal J} \rightarrow {\cal J} $为连续可微映射, $ {\cal J} $为$ n $-维欧氏空间, 找到$ (x, s)\in {\cal J}\times{\cal J} $使得

(1.1) $ \begin{equation} x\in {\cal K}, s\in {\cal K}, x\circ s = w, s = F(x), \end{equation} $

其中$ {\cal K}\subset{\cal J} $为对称锥, $ w\in{\cal K} $是给定的权向量.当$ w $为零向量时, 对称锥权互补问题(1.1)退化为对称锥互补问题.

目前, 许多方法被提出求解各类优化问题. 如光滑方法^[6-18], 内点算法^[19-20], 渐近逼近法^[21]等. 其中, 正则化牛顿法可有效处理一些不适定问题^{[8, 10, 13]}, 故与许多其他方法相比, 正则化牛顿法更容易实现.

为提高算法求得全局最优解的可能性以及加快其收敛速度, 许多非单调线搜索被提出^[23-25]. Grippo等^[24]首先提出非单调牛顿法, 这是对Armijo搜索的推广. 之后, Zhang和Hager^[25]提出了新的非单调算法求解无约束优化问题, 新提出的算法与单调方法或传统的非单调方法相比, 需要更少的函数值和梯度评估次数. 此外, Ahookhosh^[23]结合一些常用的非单调线搜索, 给出两类新的非单调线搜索方案.

受文献[23]的启发, 本文提出求解对称锥权互补问题的正则化非单调非精确光滑牛顿法. 算法求解以下对称锥权互补问题

(1.2) $ \begin{equation} x\in {\cal K}, s\in {\cal K}, x\circ s = w, s = F_{\mu}(x), \end{equation} $

其中$ \mu>0 $为正则参数, 函数$ F_{\mu}(x):{\cal J}\rightarrow {\cal J} $定义为

(1.3) $ \begin{equation} F_{\mu}(x) = F(x)+\mu x. \end{equation} $

当$ \mu\rightarrow 0 $时, 则问题(1.2)退化为对称锥权互补问题(1.1).

本节回顾欧几里德若当代数中的一些概念和结果^[26].

若$ ({\cal J}, \langle\cdot, \cdot\rangle) $为实数域上有限维内积空间, $ (x, s)\mapsto x\circ s:{\cal J}\times{\cal J}\rightarrow {\cal J} $为双线性映射, 满足

(i) $ x\circ s = s\circ x, $$ {\forall} $$ x, s\in{\cal J} $;

(ii) $ x\circ (x^{2}\circ s) = x^{2}\circ(x\circ s), $$ {\forall} $$ x, s\in{\cal J} $, 其中$ x^{2}: = x\circ x $;

(iii) $ \langle x\circ s, y\rangle = \langle s, x\circ y\rangle, $$ {\forall} $$ x, s, y\in{\cal J} $.

则称$ ({\cal J}, \circ, \langle\cdot, \cdot\rangle) $是欧几里德若当代数.

上述若当代数一般不满足结合律, 即$ x\circ(s\circ y)\neq(x\circ s)\circ y. $假设总存在元素$ e\in {\cal J} $, 对任意$ x\in {\cal J} $满足$ x\circ e = e\circ x = x $, 则$ e $为单位元.

欧几里德若当代数$ {\cal J} $中$ {\cal K}: = \{x^{2}|x\in{\cal J}\} $表示对称锥^[26], 也为自对偶闭凸锥, $ \rm{int} {\cal K} $表示其非空内部. 对任意$ x, s\in\rm{int} {\cal K} $, 存在可逆线性变换$ {\cal T}:{\cal J}\rightarrow {\cal J} $使得$ {\cal T}({\cal K}) = {\cal K} $, $ {\cal T}(x) = s $. 任意$ x\in {\cal J} $, 设$ m(x) $为使得$ \{e, x, \cdots, x^{m(x)}\} $线性无关的最小正整数, 则$ ({\cal J}, \circ, \langle\cdot, \cdot\rangle) $的秩表示为$ r: = \max \{m(x):x\in{\cal J}\} $. 若元素$ c\in{\cal J} $且$ c\circ c = c $, 则$ c $是幂等元.若对任意$ i, j\in\{1, \ldots, k\} $, $ i\neq j $有$ c_{i}\circ c_{j} = 0 $且$ \sum\limits_{i = 1}^{k}c_{i} = e $, 则$ \{c_{1}, \cdots, c_{k}\} $表示幂等元集.

定理2.1(谱分解定理)^[26]  设$ ({\cal J}, \circ, \langle\cdot, \cdot\rangle) $是秩为$ r $的欧几里德若当代数. 那么对任意$ x\in{\cal J} $, 必存在唯一的幂等元集$ \{c_{1}, \cdots, c_{r}\} $和实数$ \lambda_{1}(x), \cdots, \lambda_{r}(x) $使得

$ x = \sum\limits_{i = 1}^{r}\lambda_{i}(x)c_{i} = \lambda_{1}(x)c_{1}+\lambda_{2}(x)c_{2}+\cdots+\lambda_{r}(x)c_{r}, $

其中$ \lambda_{i}(x) \ (i = 1, \cdots, r) $为$ x $的特征值, $ {\rm{Tr}}(x): = \sum\limits_{i = 1}^{r}\lambda_{i}(x) $为$ x $的迹.

设$ x = \lambda_{1}(x)c_{1}+\lambda_{2}(x)c_{2}+\cdots+\lambda_{r}(x)c_{r} $为$ x $的谱分解, $ f:{{\Bbb R}} \rightarrow {{\Bbb R}} $为实值连续函数, 则与$ ({\cal J}, \circ, \langle\cdot, \cdot\rangle) $相关的向量值函数可以表示为

$ f(x): = \sum\limits_{i = 1}^{r}f(\lambda_{i}(x))c_{i} = f(\lambda_{1}(x))c_{1}+f(\lambda_{2}(x))c_{2}+\cdots+f(\lambda_{r}(x))c_{r}. $

对任意$ x\in{\cal J} $, Lyapunov算子$ L:{\cal J}\rightarrow {\cal J} $定义为: 对任意$ s\in{\cal J} $, $ L_{x}s: = x\circ s $.

引理2.1^[12]  若$ c\succ 0 $, 则线性映射$ L_{c} $的逆映射$ L^{-1}_{c} $存在, 且在$ (\overline{x}, \overline{c})\in{\cal J}\times\rm{int}{\cal K} $处连续.

定义2.1^[8]  令$ F:{{\Bbb R}} ^{n}\rightarrow {{\Bbb R}} ^{n} $,

(i) 若任意$ (x, s)\in{{\Bbb R}} ^{n}\times{{\Bbb R}} ^{n} $, 满足$ (x-s)^{T}(F(x)-F(s))\geq 0 $, 则$ F(x) $单调;

(ii) 若存在$ \varepsilon>0 $, 使得对任意$ (x, s)\in{{\Bbb R}} ^{n}\times{{\Bbb R}} ^{n} $, 满足$ (x-s)^{T}(F(x)-F(s))\geq\varepsilon\|x-s\|^{2} $, 则$ F(x) $强单调.

由定义2.1知若$ F $单调, 则对任意$ \mu>0 $, 函数$ F_{\mu}(x) $ (见(1.3)式)单调.

半光滑概念在光滑牛顿法的局部收敛性分析中起着重要作用, 最初由Mifflin^[27]提出, 后来Qi和Sun^[28]将其进行了推广.

定义2.2  设函数$ \Phi:{{\Bbb R}} ^{m}\rightarrow {{\Bbb R}} ^{n} $在$ x \in{{\Bbb R}} ^{m} $处局部Lipschitz连续.若$ \Phi $在$ x $处方向可微, 且对任意$ V\in\partial \Phi(x+\triangle x) $有

$ \Phi(x+\triangle x)-\Phi(x)-V(\triangle x) = o(\|\triangle x\|), $

其中$ \partial \Phi $表示$ \Phi $在Clarke^[29]意义下的广义Jacobian矩阵, 则称$ \Phi $在$ x $处半光滑.若$ \Phi $在$ x $处半光滑且

$ \Phi(x+\triangle x)-\Phi(x)-V(\triangle x) = O(\|\triangle x\|^{1+p}), $

则称$ \Phi $在$ x $处$ p $ -阶半光滑. 特别地, 若$ \Phi $在$ x $处$ 1- $阶半光滑, 则称$ \Phi $在$ x $处强半光滑.

引理2.2^[30]  在欧几里德若当代数$ {\cal J} $上, 若对任意$ u\succeq 0, v\succeq0 $满足$ u^{2}-v^{2}\succ0 $, 则有$ u-v\succ0 $.

引理2.3^[20]  设$ x, y, u, v\in{\cal J} $且$ x, y\succ 0 $, $ x\circ y\succ 0 $. 若$ \langle u, v\rangle\geq 0 $且$ x\circ u+y\circ v = 0 $, 则$ u = v = 0 $.

本节引入对称锥权互补问题的一个光滑函数, 并研究该函数的一些性质. 这将在后续的正则化非单调非精确光滑牛顿法中起着重要作用.

设函数$ \phi(\mu, x, s):{{\Bbb R}} _{+}\times{\cal J}\times{\cal J}\rightarrow {\cal J} $:

(3.1) $ \begin{eqnarray} \phi(\mu, x, s): = x+s-\sqrt{[x-\mu(x-s)]^{2}+[s+\mu(x-s)]^{2}+2w+2\mu^{2}e}, \end{eqnarray} $

其中$ w\in{\cal K}. $当$ w $为零向量且$ {\cal K} $为二阶锥时, (3.1)式退化为二阶锥互补问题的光滑函数^[25].

下面证明函数$ \phi(\mu, x, s) $在$ {{\Bbb R}} _{++}\times{\cal J}\times{\cal J} $上连续可微.

引理3.1  对任意$ x, s\in{\cal J} $, $ \mu>0 $和$ w\in{\cal K} $, 设函数$ \phi $由(3.1)式定义,

(i) 令$ w_{1}: = x-\mu(x-s), w_{2}: = s+\mu(x-s), c: = \sqrt{w_{1}^{2}+w_{2}^{2}+2w+2\mu^{2}e} $和

$ \begin{eqnarray*} \widehat{g}:& = &w_{1}\circ[u-h(u-v)]+w_{2}\circ[v+h(u-v)]-\mu(w_{1}-w_{2})\circ(u-v)\\ &&-h[w_{1}-w_{2}+u-v-2\mu(u-v)]\circ(x-s)+2\mu he, \end{eqnarray*} $

其中$ u, v\in{\cal J} $和$ h\in{{\Bbb R}} . $那么$ L_{c} $存在逆算子$ L_{c}^{-1} $且

(3.2) $ \begin{equation} D\phi(\mu, x, s)(h, u, v) = u+v-L^{-1}_{c}(\widehat{g}). \end{equation} $

(ii) $ D\phi(\cdot, \cdot, \cdot) $在$ {{\Bbb R}} _{++}\times{\cal J}\times{\cal J} $上连续可微.

证  (i) 因为$ c\succ0 $, 由引理2.1知$ L_{c} $存在逆算子$ L^{-1}_{c} $. 对任意$ x, s, u, v\in{\cal J}, \mu>0 $和$ h\in {{\Bbb R}} $, 令

$ \begin{eqnarray*} d^{2}:& = &[x+u-(\mu+h)(x+u-s-v)]^{2}+[s+v+(\mu+h)(x+u-s-v)]^{2}\\ &&+2w+2(\mu+h)^{2}e, \\ \widetilde{g}:& = &[u-h(u-v)]^{2}+[v+h(u-v)]^{2}-2\mu[u-v-2h(u-v)]\circ(u-v)\\ && +4h^{2}(u-v)\circ(x-s)+2\mu^{2}(u-v)^{2}+2h^{2}(x-s)^{2}+2h^{2}e, \end{eqnarray*} $

则有$ d^{2}-c^{2} = 2(d-c)\circ c+(d-c)^{2} $和

$ \begin{eqnarray*} d^{2}-c^{2}& = &[x+u-(\mu+h)(x+u-s-v)]^{2}+[s+v+(\mu+h)(x+u-s-v)]^{2}+2w\\ &&+2(\mu+h)^{2}e-[x-\mu(x-s)]^{2}-[s+\mu(x-s)]^{2}-2w-2\mu^{2}e\\ & = &2[x-\mu(x-s)]\circ[u-h(u-v)-h(x-s)-\mu(u-v)]+[u-h(u-v)\\ &&-h(x-s)-\mu(u-v)]^{2}+2[s+\mu(x-s)]\circ[v+h(u-v)+h(x-s)\\ &&+\mu(u-v)]+[v+h(u-v)+h(x-s)+\mu(u-v)]^{2}+4\mu he+2h^{2}e\\ & = &2[x-\mu(x-s)]\circ[u-h(u-v)]-2[x-\mu(x-s)]\circ[h(x-s)+\mu(u-v)]\\ &&+[u-h(u-v)]^{2}-2[u-h(u-v)]\circ[h(x-s)+\mu(u-v)]\\ & &+2[h(x-s)+\mu(u-v)]^{2}+2[s+\mu(x-s)]\circ[v+h(u-v)]+2[s\\ &&+\mu(x-s)]\circ[h(x-s)+\mu(u-v)]+[v+h(u-v)]^{2}+2[v+h(u\\ &&-v)]\circ[h(x-s)+\mu(u-v)]+4\mu he+2h^{2}e\\ & = &2[x-\mu(x-s)]\circ[u-h(u-v)]+2[s+\mu(x-s)]\circ[v+h(u-v)]\\ &&-2h[x-\mu(x-s)]\circ(x-s)-2\mu[x-\mu(x-s)]\circ(u-v)+[u-h(u-v)]^{2}\\ &&-2h[u-h(u-v)]\circ(x-s)-2\mu[u-h(u-v)]\circ(u-v)+2h^{2}(x-s)^{2}\\ &&+4h\mu(x-s)\circ(u-v)+2\mu^{2}(u-v)^{2}+2h[s+\mu(x-s)]\circ(x-s)\\ &&+2\mu[s+\mu(x-s)]\circ(u-v)+[v+h(u-v)]^{2}+2h[v+h(u-v)]\circ(x-s)\\ &&+2\mu[v+h(u-v)]\circ(u-v)+4\mu he+2h^{2}e\\ & = &2[x-\mu(x-s)]\circ[u-h(u-v)]+2[s+\mu(x-s)]\circ[v+h(u-v)]\\ & &-2h[x-\mu(x-s)-s-\mu(x-s)+u-v-2\mu(u-v)]\circ(x-s)\\ &&-2\mu[x-\mu(x-s)-s-\mu(x-s)]\circ(u-v)+4\mu he+[u-h(u-v)]^{2}\\ &&+[v+h(u-v)]^{2}+4h^{2}(x-s)\circ(u-v)-2\mu[u-v-2h(u-v)]\circ(u-v)\\ & &+2h^{2}(x-s)^{2}+2\mu^{2}(u-v)^{2}+2h^{2}e\\ & = &2w_{1}\circ[u-h(u-v)]+2w_{2}\circ[v+h(u-v)]-2h[w_{1}-w_{2}+u-v\\ & &-2\mu(u-v)]\circ(x-s)-2\mu(w_{1}-w_{2})\circ(u-v)+4\mu he+[u-h(u-v)]^{2}\\ &&+[v+h(u-v)]^{2}+4h^{2}(x-s)\circ(u-v)-2\mu[u-v-2h(u-v)]\circ(u-v)\\ &&+2h^{2}(x-s)^{2}+2\mu^{2}(u-v)^{2}+2h^{2}e = 2\widehat{g}+\widetilde{g}. \end{eqnarray*} $

因此

(3.3) $ \begin{equation} 2(d-c)+L^{-1}_{c}((d-c)^{2}) = L^{-1}_{c}(d^{2}-c^{2}) = L^{-1}_{c}(2\widehat{g})+L^{-1}_{c}(\widetilde{g}). \end{equation} $

由引理2.1知$ L^{-1}_{c} $连续, 则(3.3)式表明$ d-c = O(\|(h, u, v)\|) $, 从而$ \widetilde{g} = O(\|(h, u, v)\|^{2}) $. 则

$ \begin{eqnarray*} \phi(\mu+h, x+u, s+v)-\phi(\mu, x, s)& = &x+u+s+v-x-s-(d-c)\\ & = &u+v-L^{-1}_{c}(\widehat{g})+O(\|(h, u, v)\|^{2}), \end{eqnarray*} $

故$ D\phi(\mu, x, s)(h, u, v) = u+v-L^{-1}_{c}(\widehat{g}). $

(ii) 因为$ c = \sqrt{w_{1}^{2}+w_{2}^{2}+2w+2\mu^{2}e}\succ 0 $, 所以$ L^{-1}_{c}(\widehat{g}) $在任意$ (\widehat{g}, c)\in{\cal J}\times{\cal J} $处连续. 由(3.2)式得$ D\phi(h, u, v) $在$ {{\Bbb R}} _{++}\times{\cal J}\times{\cal J} $上连续可微.

根据文献[30]中命题6和命题7, 可类似得到$ \phi $ (见(3.1)式)的如下结论, 此处省略不证.

引理3.2  对任意$ x, s\in{\cal J}, w\in{\cal K} $和$ \mu\in {{\Bbb R}} _{+} $, 令$ \phi $由(3.1)式给出. 则

(i) $ \phi(0, x, s) = 0\Leftrightarrow x\succeq0, s\succeq0, x\circ s = w; $

(ii) $ \phi(\mu, x, s) = 0\Leftrightarrow x-\mu(x-s)\succeq0, s+\mu(x-s)\succeq0, [x-\mu(x-s)]\circ [s+\mu(x-s)] = \mu^{2}e+w. $

引理3.3  令$ \phi $由(2.1)式定义, $ \mu_{1}, \mu_{2}\in{{\Bbb R}} _{++} $且$ \mu_{1}<\mu_{2} $. 设序列$ \{(\mu_{k}, x_{k}, s_{k})\}\subset{{\Bbb R}} _{++}\times{\cal J}\times{\cal J} $满足

(i) $ \mu_{k}\in[\mu_{1}, \mu_{2}] $且$ \{(x_{k}, s_{k})\} $无界;

(ii) 存在一有界序列$ \{(u_{k}, v_{k})\} $使得$ \{\langle x_{k}-u_{k}, s_{k}-v_{k}\rangle\} $有下界.

则序列$ \{\phi(\mu_{k}, x_{k}, s_{k})\} $无界.

证  由文献[9, 定理4.1]的证明可类似证得.

引理3.3表明$ \phi $ (见(3.1)式)是强制的.

本节基于(3.1)式中的光滑函数, 给出求解wSCCP的正则化非单调非精确光滑牛顿法.

令$ z: = (\mu, x, s)\in{{\Bbb R}} \times{\cal J}\times{\cal J} $, $ \phi $由(3.1)式给出, 定义

(4.1) $ \begin{eqnarray} H(z) = \left( \begin{array}{c} \mu\\ F(x)+\mu x-s\\ \phi(\mu, x, s) \end{array} \right). \end{eqnarray} $

由(1.1)-(3.1)式和(4.1)式易得$ H(z) = 0\Leftrightarrow \mu = 0 $且$ (x, s) $为wSCCP(1.1)的解.

定理4.1  设$ F $连续可微且单调, $ H(z) $由(4.1)式给出, 则$ H(z) $在$ {{\Bbb R}} \times{\cal J}\times{\cal J} $上$ \rm{Lipschitz} $连续且处处强半光滑, 在任意$ z = (\mu, x, s)\in{{\Bbb R}} _{++}\times{\cal J}\times{\cal J} $处连续可微, 其雅可比为

(4.2) $ \begin{eqnarray} DH(\mu, x, s)(h, u, v) = \left( \begin{array}{c} h\\ hx+(DF(x)+\mu I)u-v\\ D\phi(\mu, x, s)(h, u, v) \end{array} \right). \end{eqnarray} $

且对任意$ 0<\mu<1 $, $ DH $可逆.

证  由文献[31, 定理3.2]易知$ H(z) $在$ {{\Bbb R}} \times{\cal J}\times{\cal J} $上$ \rm{Lipschitz} $连续且处处强半光滑.又由引理3.1知$ H(z) $在任意$ z = (\mu, x, s)\in{{\Bbb R}} _{++}\times{\cal J}\times{\cal J} $处连续可微.下证对任意$ 0<\mu<1 $, $ DH $可逆, 即证线性方程组

(4.3) $ \begin{equation} DH(\mu, x, s)(h, u, v) = 0 \end{equation} $

只有零解. 由(4.2)和(4.3)式知

(4.4) $ \begin{eqnarray} & h = 0, \end{eqnarray} $

(4.5) $ \begin{eqnarray} &hx+(DF(x)+\mu I)u-v = 0, \end{eqnarray} $

(4.6) $ \begin{eqnarray} & D\phi(\mu, x, s)(h, u, v) = 0. \end{eqnarray} $

而$ F $是单调的, 故由(4.4)和(4.5)式有

(4.7) $ \begin{equation} \langle u, v\rangle = \langle u, (DF(x)+\mu I)u\rangle\geq 0. \end{equation} $

另外, 根据(4.4)式, (4.6)式和引理3.1有

(4.8) $ \begin{eqnarray} D\phi(\mu, x, s)(h, u, v)& = &u-\mu(u-v)+v+\mu(u-v){}\\ &&-L^{-1}_{c}[w_{1}\circ u+w_{2}\circ v -\mu(w_{1}-w_{2})\circ(u-v)] = 0. \end{eqnarray} $

将(4.8)式两侧同时乘$ L_{c} $得

(4.9) $ \begin{equation} (c-w_{1})\circ[(1-\mu)u+\mu v]+(c-w_{2})\circ[(1-\mu)v+\mu u] = 0. \end{equation} $

由引理3.1知

(4.10) $ \begin{equation} c^{2}-w_{1}^{2} = w_{2}^{2}+2w+2\mu^{2} e\succ0, \quad c^{2}-w_{2}^{2} = w_{1}^{2}+2w+2\mu^{2} e\succ0. \end{equation} $

则由引理2.2有

(4.11) $ \begin{equation} c-w_{1} \succ 0, \quad c-w_{2} \succ 0. \end{equation} $

注意到对任意$ 0<\mu<1 $有

(4.12) $ \begin{equation} (c-w_{1})\circ (c-w_{2}) = \frac{1}{2}(c-w_{1}-w_{2})^{2}+w+\mu^{2} e \succ 0, \end{equation} $

且由(4.7)式知

(4.13) $ \begin{equation} \langle (1-\mu)u+\mu v, (1-\mu)v+\mu u\rangle\geq 0. \end{equation} $

故当$ 0<\mu<1 $时, 由引理2.3, (4.9)和(4.11)-(4.13)式得$ (1-\mu)u+\mu v = 0 $, $ (1-\mu)v+\mu u = 0 $, 从而$ u = v = 0 $. 所以线性方程组(4.3)仅有零解.

定义函数$ \psi:{{\Bbb R}} _{+}\times{\cal J}\times{\cal J}\rightarrow {{\Bbb R}} _{+} $为

(4.14) $ \begin{equation} \psi(z): = \|H(z)\|^{2}, \end{equation} $

其中$ H(z) $由(4.1)式定义.

算法4.1  (wSCCP的正则化非单调非精确光滑牛顿法)

步骤0  选择$ \delta\in(0, 1), $$ \sigma\in(0, 1/2) $和任意整数$ N\in {\cal N} $. 取$ \gamma, \mu_0 \in (0, 1) $使得$ \gamma\mu_0<1 $. 令$ \kappa\in(0, 1-\gamma\mu_{0}), $$ 0\leq\eta_{\rm min}\leq\eta_{\rm max}<1 $和$ \eta_{k}\in[\eta_{\rm min}, \eta_{\rm max}] $. 取任意初始点$ z_{0}: = (\mu_{0}, x_{0}, s_{0})\in{{\Bbb R}} _{++}\times{\cal J}\times{\cal J} $和$ \overline{z}: = (\mu_{0}, 0, 0)\in {{\Bbb R}} _{++}\times{\cal J}\times{\cal J} $. 令$ T_{0}: = \psi(z_{0}), $$ Q_{0}: = 1 $和$ m(0): = 0 $. 置$ k: = 0 $.

步骤1  若$ \|H(z_{k})\| = 0 $, 停止. 否则, 令

(4.15) $ \begin{eqnarray} \beta(z_{k}): = \gamma{\rm min}\{1, \psi(z_{0}), \ldots, \psi(z_{k})\}. \end{eqnarray} $

步骤2  求搜索方向$ \Delta z_{k}: = (\Delta \mu_{k}, \Delta x_{k}, \Delta s_{k})\in{{\Bbb R}} \times{\cal J}\times{\cal J} $使得

(4.16) $ \begin{eqnarray} H(z_{k})+ DH(z_{k})\Delta z_{k} = \beta(z_{k})\overline{z}+\varrho_{k}, \end{eqnarray} $

其中$ \varrho_{k}: = (0, \overline{\varrho}_{k})\in{{\Bbb R}} \times{\cal J}^{2} $, $ \|\overline{\varrho}_{k}\|\leq\kappa\|H(z_{k})\| $.

步骤3  令$ \lambda_{k} = \max\{\delta^{l}|l = 0, 1, \ldots \} $使得

(4.17) $ \begin{eqnarray} \psi(z_{k}+\lambda_{k}\Delta z_{k}) \leq [1-2\sigma(1-\gamma\mu_{0}-\kappa)\lambda_{k}]T_{k}. \end{eqnarray} $

步骤4  置$ z_{k+1}: = z_{k}+\lambda_{k}\Delta z_{k} $,

(4.18) $ \begin{equation} Q_{k+1} = \eta_{k}Q_{k}+1, \end{equation} $

(4.19) $ \begin{equation} T_{k+1} = \left\{\begin{array} {ll} \psi(z_{l(k+1)}), &\ k\leq N, \\ {\rm max}\{ \overline{C}_{k+1}, \psi(z_{k+1})\}, &\ k > N, \end{array} \right. \end{equation} $

这里

(4.20) $ \begin{equation} \psi(z_{l(k+1)}) = \max \limits_{0\leq j \leq m(k+1)}\{\psi(z_{k+1-j})\}, \quad m(k+1) = \min\{m(k)+1, N\}, \end{equation} $

(4.21) $ \begin{equation} \overline{C}_{k+1} = \frac{\eta_{k}Q_{k}}{Q_{k+1}}\overline{C}_{k}+\frac{1}{Q_{k+1}}\psi(z_{k+1})+\frac{\xi_{k+1}Q_{k-N}}{Q_{k+1}}(\psi(z_{k-N+1})-\psi(z_{k-N})), \end{equation} $

其中$ \xi_{k+1} = \frac{\eta_{k}}{\eta_{k-N-1}}\xi_{k} $. 置$ k: = k+1 $. 转步骤1.

注4.1  (i) 受文献[23]的启发, 算法4.1采用非单调线搜索(4.17)求解对称锥权互补问题(1.2). 该非单调线搜索中的非单调形式(4.19)结合了Grippo's method^[24]和Zhang-Hager's method^[25]的非单调形式.

(ii) 当迭代点接近最优解时, 非单调线搜索(4.17)运用一个较弱的非单调形式, 即当迭代次数$ k\geq N $时, 采用文献[25]提出的无约束优化问题的非单调形式

(4.22) $ \begin{eqnarray} C_{k} = \left\{\begin{array} {ll} \psi(z_{k}), & \ k = 0, \\ { } \frac{\eta_{k-1}Q_{k-1}C_{k-1}+\psi(z_{k})}{Q_{k}}, & \ k\geq 1, \end{array} \right. \end{eqnarray} $

$ Q_{k} = \left\{\begin{array} {ll} 1, & \ k = 0, \\ \eta_{k-1}Q_{k-1}+1, &\ k\geq1. \end{array} \right. $

取(4.22)式中最后$ N+1 $个函数值的凸组合定义为

$ \begin{eqnarray*} \overline{C}_{k} = \left\{\begin{array}{ll} \overline{C}_{0} = \psi(z_{0}) & \ k = 0, \\ { } \overline{C}_{1} = (1-\frac{\eta_{0}Q_{0}}{Q_{1}})\psi(z_{1})+\frac{\eta_{0}Q_{0}}{Q_{1}}\psi(z_{0})& \ k = 1, \\ \vdots \ \ \ \ \ \ \ \vdots &\vdots \\ \begin{array}{rl} \overline{C}_{N} = &{ } (1-\frac{\eta_{N-1}Q_{N-1}}{Q_{N}})\psi(z_{N})+\frac{\eta_{N-1}Q_{N-1}}{Q_{N}}(1-\frac{\eta_{N-2}Q_{N-2}}{Q_{N-1}})\psi(z_{N-1})\\ &{ } +\cdots+\frac{\eta_{N-1}\cdots\eta_{0}Q_{0}}{Q_{N}}\psi(z_{0}) \end{array} & \ k = N, \\ \vdots \ \ \ \ \ \ \ \vdots &\vdots\\ \begin{array}{rl} \overline{C}_{k} = &{ } (1-\frac{\eta_{k-1}Q_{k-1}}{Q_{k}})\psi(z_{k})+\frac{\eta_{k-1}Q_{k-1}}{Q_{k}}(1-\frac{\eta_{k-2}Q_{k-2}}{Q_{k-1}})\psi(z_{k-1}) \\ &{ } +\cdots+\frac{\eta_{k-1}\cdots\eta_{k-N}Q_{k-N}}{Q_{k}}\psi(z_{k-N}) \end{array} & \ k>N. \end{array}\right. \end{eqnarray*} $

当$ k>N $时

$ \begin{eqnarray*} \overline{C}_{k}& = &(1-\frac{\eta_{k-1}Q_{k-1}}{Q_{k}})\psi(z_{k})+\frac{\eta_{k-1}Q_{k-1}}{Q_{k}}(1-\frac{\eta_{k-2}Q_{k-2}}{Q_{k-1}})\psi(z_{k-1})+\cdots\\ &&+\frac{\eta_{k-1}\cdots\eta_{k-N}Q_{k-N}}{Q_{k}}\psi(z_{k-N}), \end{eqnarray*} $

其中

$ (1-\frac{\eta_{k-1}Q_{k-1}}{Q_{k}})+\frac{\eta_{k-1}Q_{k-1}}{Q_{k}}(1-\frac{\eta_{k-2}Q_{k-2}}{Q_{k-1}})+\cdots+\frac{\eta_{k-1}\cdots\eta_{k-N}Q_{k-N}}{Q_{k}} = 1. $

令$ \xi_{k} = \frac{\eta_{k-1}}{\eta_{k-N-2}}\xi_{k-1} $, 则

(4.23) $ \begin{equation} \overline{C}_{k} = \frac{\eta_{k-1}Q_{k-1}}{Q_{k}}\overline{C}_{k-1}+\frac{1}{Q_{k}}\psi(z_{k})+\frac{\xi_{k}Q_{k-N-1}}{Q_{k}}(\psi(z_{k-N})-\psi(z_{k-N-1})). \end{equation} $

当(4.23)式中$ \eta_{k-1} = 0 $时, 对任意$ k>N $有$ \xi_{k} = 0, Q_{k} = 1 $和$ \overline{C}_{k} = \psi(z_{k}) $. 故当$ k>N $时, $ \eta_{k} $在控制非单调性方面起着重要作用.

引理4.1  设$ F $连续可微且单调, $ \{z_{k}: = (\mu_{k}, x_{k}, s_{k})\} $为算法4.1生成的迭代序列, 则$ \psi(z_{k})\leq T_{k}\leq \psi(z_{l(k)}) $.

证  由(4.20)式知对任意非负整数$ k $有$ \psi(z_{k})\leq\psi(z_{l(k)}) $. 考虑以下两种情形.

(i) 当$ k\leq N $, 由(4.19)式有$ T_k = \psi(z_{l(k)}) $, 故$ \psi(z_{k})\leq T_k\leq\psi(z_{l(k)}) $.

(ii) 设$ k>N $, 若$ T_k = \psi(z_{k}) $, 显然结论成立.若$ T_k>\psi(z_{k}) $, 则由(4.20)式有$ m(k) = N $和$ \psi(z_{l(k)}) = \max \{\psi(z_{k}), \ldots, \psi(z_{k-N}) \}. $故对任意$ j = k-N, \ldots, k $有$ \psi(z_{j})\leq\psi(z_{l(k)}) $. 又由(4.19)式知

$ \begin{eqnarray*} \psi(z_{k})< T_{k} = \overline{C}_{k}& = &(1-\frac{\eta_{k-1}Q_{k-1}}{Q_{k}})\psi(z_{k})+\cdots+\frac{\eta_{k-1}\cdots\eta_{k-N}Q_{k-N}}{Q_{k}}\psi(z_{k-N})\\ &\leq&(1-\frac{\eta_{k-1}Q_{k-1}}{Q_{k}})\psi(z_{l(k)})+\cdots+\frac{\eta_{k-1}\cdots\eta_{k-N}Q_{k-N}}{Q_{k}}\psi(z_{l(k)})\\ & = &\psi(z_{l(k)}). \end{eqnarray*} $

证毕.

引理4.2  设序列$ \{z_{k}: = (\mu_{k}, x_{k}, s_{k})\} $由算法4.1迭代生成, 则

(i) 序列$ \{\beta(z_{k})\} $单调递减；

(ii) 对任意非负整数$ k $有$ \mu_{k}\geq \mu_{0}\beta(z_{k}) $且序列$ \{\mu_{k}\} $单调递减；

(iii) 设$ F $连续可微且单调, 则算法4.1适定.

证  (i) 由(4.15)知$ \{\beta(z_k)\} $是单调递减的.

(ii) 由(4.15)式易得$ \beta(z_{0})\leq\gamma $, 因此$ \mu_{0}\beta(z_{0})\leq\mu_{0}\gamma\leq\mu_{0} $. 假设存在$ k $使得$ \mu_{k}\geq\mu_{0}\beta(z_{k}) $. 由(4.16)式得

$ \mu_{k+1} = \mu_{k}+\lambda_{k}\Delta \mu_{k} = (1-\lambda_{k})\mu_{k}+\lambda_{k}\mu_{0}\beta(z_{k}), $

结合$ \mu_{0}\beta(z_{k})\leq\mu_{k} $有

$ \mu_{k+1}\geq (1-\lambda_{k})\mu_{0}\beta(z_{k})+\lambda_{k}\mu_{0}\beta(z_{k}) = \mu_{0}\beta(z_{k})\geq \mu_{0}\beta(z_{k+1}), $

$ \mu_{k+1}\leq (1-\lambda_{k})\mu_{k}+\lambda_{k}\mu_{k} = \mu_{k}. $

故对任意非负整数$ k $有$ \mu_{k}\geq \mu_{0}\beta(z_{k}) $, 且$ \{\mu_{k}\} $单调递减.

(iii) 由(4.14)和(4.15)式知$ \beta(z_{k})\geq0 $. 又因$ \{\mu_{k}\} $单调递减且$ \mu_{0}\in(0, 1) $, 则根据(ii)有$ 0<\mu_{0}\beta(z_{k})\leq\mu_{k}\leq\mu_{0}<1 $. 故对任意非负整数$ k $得$ 0<\mu_{k}<1 $. 由定理4.1知$ DH(z_{k}) $可逆, 从而步2适定. 令

(4.24) $ \begin{eqnarray} r_{k}(\lambda): = \psi(z_{k}+\lambda\Delta z_{k})-\psi(z_{k})-\lambda D\psi(z_{k})\Delta z_{k}. \end{eqnarray} $

根据定理4.1知$ \psi(z_{k}) $在$ z_{k} = (\mu_{k}, x_{k}, s_{k})\in{{\Bbb R}} _{++}\times{\cal J}\times{\cal J} $处连续可微, 且

(4.25) $ \begin{eqnarray} |r_{k}(\lambda)| = o(\lambda). \end{eqnarray} $

由(4.15)式有$ \beta(z_{k})\leq\gamma{\rm min}\{1, \psi(z_{k})\}. $当$ \|\psi(z_{k})\|\leq1 $, 即$ \|H(z_{k})\|\leq1 $, 则$ \beta(z_{k})\leq\gamma{\rm}\|H(z_{k})\| $; 当$ \|\psi(z_{k})\|>1 $时, 即$ \|H(z_{k})\|>1 $, 则$ \beta(z_{k})\leq\gamma{\rm}<\gamma{\rm}\|H(z_{k})\| $. 故对任意非负整数$ k $有

(4.26) $ \begin{equation} \beta(z_{k})\leq\gamma{\rm}\|H(z_{k})\|. \end{equation} $

由(4.14), (4.16), (4.24)-(4.26)式和引理4.1得

(4.27) $ \begin{eqnarray} \psi(z_{k}+\lambda\Delta z_{k})& = &\psi(z_{k})+\lambda D\psi(z_{k})\Delta z_{k}+r_{k}(\lambda){}\\ & = &\psi(z_{k})+2\lambda H^{T}(z_{k})DH(z_{k})\Delta z_{k}+r_{k}(\lambda){}\\ & = &\psi(z_{k})+2\lambda H^{T}(z_{k})(-H(z_{k})+\beta(z_k)\overline{z}+\varrho_{k})+r_{k}(\lambda){}\\ &\leq&(1-2\lambda)\psi(z_{k})+2\lambda\gamma\mu_{0}\|H(z_{k})\|^{2}+2\lambda\|\varrho_{k}\|\|H(z_{k})\|+o(\lambda){}\\ &\leq&(1-2\lambda)\psi(z_{k})+2\lambda\gamma\mu_{0}\|H(z_{k})\|^{2}+2\lambda\kappa\|H(z_{k})\|^{2}+o(\lambda){}\\ &\leq&[1-2(1-\gamma\mu_{0}-\kappa)\lambda]T_{k}+o(\lambda). \end{eqnarray} $

因为$ \gamma\mu_{0}<1 $, 则(3.27)式表明存在$ \overline{\lambda}\in(0, 1] $对任意$ \lambda\in(0, \overline{\lambda}] $和$ \sigma\in(0, \frac{1}{2}) $使得$ \psi(z_{k}+\lambda\Delta z_{k})\leq[1-2\sigma(1-\gamma\mu_{0}-\kappa)\lambda]T_{k} $. 从而步3适定. 综上算法4.1适定.

本节给出算法4.1的全局与局部二阶收敛性分析.

引理5.1  设$ F $连续可微且单调, 序列$ \{z_{{k}}\} $由算法4.1生成, 则$ \{\psi(z_{{l(k)}})\} $收敛.

证  因为$ \gamma\mu_{0}<1 $, $ \sigma\in(0, \frac{1}{2}) $, 由(4.17)式和引理4.1有

$ \begin{eqnarray*} \psi(z_{{k+1}})\leq[1-2\sigma(1-\gamma\mu_{0}-\kappa)\lambda_{k}]T_{k}&\leq[1-2\sigma(1-\gamma\mu_{0}-\kappa)\lambda_{k}]\psi(z_{l(k)})\leq\psi(z_{l(k)}). \end{eqnarray*} $

对任意$ k\geq0 $, 由(4.20)式知

$ \begin{eqnarray*} \psi(z_{{l(k+1)}}) = \max\limits_{0\leq j\leq m(k+1)}\{\psi(z_{{k+1-j}})\}&\leq\max\limits_{0\leq j\leq m(k)+1}\{\psi(z_{{k+1-j}})\} = \max\{\psi(z_{{l(k)}}), \psi(z_{{k+1}})\}. \end{eqnarray*} $

故$ \psi(z_{{l(k+1)}})\leq\psi(z_{{l(k)}}) $, 即$ \{\psi(z_{{l(k)}})\} $单调递减. 另外由(4.1)式, (4.14)式和引理4.1有$ 0\leq\mu_{k}^{2}\leq\psi(z_{k})\leq\psi(z_{{l(k)}}). $从而$ \{\psi(z_{{l(k)}})\} $收敛.

定理5.1  设$ \{z_{{k}}\} $由算法4.1迭代生成. 若$ F $连续可微且单调, 则

(5.1) $ \begin{eqnarray} \lim\limits_{k \rightarrow \infty}\psi(z_{k}) = \lim\limits_{k \rightarrow \infty}T_{k} = \lim\limits_{k \rightarrow \infty}\psi(z_{{l(k)}}). \end{eqnarray} $

证  若$ k>N $, 由(4.14), (4.24), (4.25)式和引理4.1知

(5.2) $ \begin{eqnarray} \psi(z_{l(k)})& = &\psi(z_{l(k)-1})+\lambda_{{l(k)-1}}D\psi(z_{l(k)-1})\Delta z_{l(k)-1}+r_{l(k)-1}(\lambda_{{l(k)-1}}){}\\ &\leq &T_{l(k)-1}+2\lambda_{{l(k)-1}}H^{T}(z_{l(k)-1})DH(z_{l(k)-1})\Delta z_{l(k)-1}+o(\lambda_{{l(k)-1}}){}\\ &\leq&\psi(z_{l(l(k)-1)})+2\lambda_{{l(k)-1}}H^{T}(z_{l(k)-1})DH(z_{l(k)-1})\Delta z_{l(k)-1}+o(\lambda_{{l(k)-1}}). \end{eqnarray} $

因为$ \gamma\mu_0<1 $, 则由(4.16)和(4.26)式有

(5.3) $ \begin{eqnarray} H^{T}(z_{l(k)-1})DH(z_{l(k)-1})\Delta z_{l(k)-1} & = &H^{T}(z_{l(k)-1})[-H(z_{l(k)-1})+\beta(z_{l(k)-1})\overline{z}+\varrho_{{l(k)-1}}]{}\\ &\leq&-\|H(z_{l(k)-1})\|^{2}+[\mu_0\beta(z_{l(k)-1})+\|\varrho_{l(k)-1}\|]\|H(z_{l(k)-1})\|{}\\ &\leq&-\|H(z_{l(k)-1})\|^{2}+\gamma\mu_0\|H(z_{l(k)-1})\|^{2}+\kappa\|H(z_{l(k)-1})\|^{2}{}\\ & = &-(1-\gamma\mu_0-\kappa)\|H(z_{l(k)-1})\|^{2}<0. \end{eqnarray} $

故由(5.2), (5.3)式和引理5.1得

(5.4) $ \begin{eqnarray} \lim\limits_{k\rightarrow \infty}\lambda_{{l(k)-1}}H^{T}(z_{l(k)-1})DH(z_{l(k)-1})\Delta z_{l(k)-1} = 0. \end{eqnarray} $

另外, 根据定理4.1知对任意$ 0<\mu_{l(k)-1}<1 $, $ DH(z_{l(k)-1}) $可逆. 从而由文献[28]命题3.1得$ \|[DH(z_{l(k)-1})]^{-1}\| = O(1) $. 故对任意非负整数$ k $, 存在$ \varsigma>0 $使得

(5.5) $ \begin{eqnarray} \|\Delta z_{l(k)-1}\|& = &\|[DH(z_{l(k)-1})]^{-1}(-H(z_{l(k)-1})+\beta(z_{l(k)-1})\overline{z}+\varrho_{{l(k)-1}})\|{}\\ &\leq&\|[DH(z_{l(k)-1})]^{-1}\|(\|H(z_{l(k)-1})\|+\gamma\mu_{0}\|H(z_{l(k)-1})\|+\|\varrho_{l(k)-1}\|){}\\ &\leq&\varsigma(\|H(z_{l(k)-1})\|+\gamma\mu_0\|H(z_{l(k)-1})\|+\kappa\|H(z_{l(k)-1})\|){}\\ & = &\varsigma(1+\gamma\mu_0+\kappa)\|H(z_{l(k)-1})\|. \end{eqnarray} $

由(5.3)和(5.5)式有

(5.6) $ \begin{eqnarray} \lambda_{{l(k)-1}}H^{T}(z_{l(k)-1})DH(z_{l(k)-1})\Delta z_{l(k)-1}&\leq&-(1-\gamma\mu_0-\kappa)\lambda_{{l(k)-1}}\|H(z_{l(k)-1})\|^{2}{}\\ &\leq&-\frac{1-\gamma\mu_0-\kappa}{\varsigma^{2}(1+\gamma\mu_0+\kappa)^{2}}\lambda_{{l(k)-1}}\|\Delta z_{l(k)-1}\|^{2}. \end{eqnarray} $

因为$ 1-\gamma\mu_0-\kappa>0 $, 故由(5.6)式知

(5.7) $ \begin{eqnarray} \lim\limits_{k\rightarrow \infty}\lambda_{{l(k)-1}}\|\Delta z_{l(k)-1}\| = 0. \end{eqnarray} $

下证$ \lim\limits_{k\rightarrow \infty}\lambda_{k}\|\Delta z_{k}\| = 0 $. 设$ \widehat{l}(k) = l(k+N+2) $, 由(4.20)式有

(5.8) $ \begin{eqnarray} k+N+2-m(k+N+2)\leq \widehat{l}(k) = l(k+N+2)\leq k+N+2. \end{eqnarray} $

运用归纳法, 先证对任意$ j\geq1 $有

(5.9) $ \begin{equation} \lim\limits_{k\rightarrow \infty}\lambda_{{\widehat{l}(k)-j}}\|\Delta z_{\widehat{l}(k)-j}\| = 0 \end{equation} $

且

(5.10) $ \begin{equation} \lim\limits_{k \rightarrow \infty}\psi(z_{{\widehat{l}(k)-j}}) = \lim\limits_{k \rightarrow \infty}\psi(z_{l(k)}). \end{equation} $

当$ j = 1 $时, 因为$ \{\widehat{l}(k)\}\subseteq\{l(k)\} $, 由(5.7)知(5.9)式成立. 又根据定理4.1和(4.14)式知当$ j = 1 $时(5.10)式成立. 假设(5.9)和(5.10)式对某个$ j $成立. 类似(5.2)式有

(5.11) $ \begin{eqnarray} \psi(z_{{\widehat{l}(k)-j}})&\leq&\psi(z_{\widehat{l}({\widehat{l}(k)-j-1})})+2\lambda_{\widehat{l}(k)-j-1}H^{T}(z_{\widehat{l}(k)-j-1})DH(z_{\widehat{l}(k)-j-1})\Delta z_{\widehat{l}(k)-j-1}{}\\ & &+o(\lambda_{\widehat{l}(k)-j-1}). \end{eqnarray} $

由(5.7)式的证明, 类似可得$ \lim\limits_{k\rightarrow \infty}\lambda_{{\widehat{l}(k)-j-1}}\|\Delta z_{\widehat{l}(k)-j-1}\| = 0 $, 即

(5.12) $ \begin{eqnarray} \lim\limits_{k\rightarrow \infty}\|z_{\widehat{l}(k)-j}-z_{\widehat{l}(k)-j-1}\| = 0. \end{eqnarray} $

另外, 由定理4.1知$ \psi(\cdot) $连续可微, 则(5.10)和(5.12)式表明

$ \begin{eqnarray*} \lim\limits_{k\rightarrow \infty}\psi(z_{{\widehat{l}(k)-j-1}}) = \lim\limits_{k\rightarrow \infty}\psi(z_{{\widehat{l}(k)-j}}) = \lim\limits_{k\rightarrow \infty}\psi(z_{{l(k)}}). \end{eqnarray*} $

故(5.9)和(5.10)式对任意$ j\geq1 $成立. 又

(5.13) $ \begin{eqnarray} z_{k+1} = z_{{\widehat{l}(k)}}-\sum^{\widehat{l}(k)-k-1}_{j = 1}\lambda_{{\widehat{l}(k)-j}}\Delta z_{{\widehat{l}(k)-j}}, \end{eqnarray} $

则由(5.8)式有$ \widehat{l}(k)-k-1\leq N+1 $. 结合(5.9)和(5.13)式知

(5.14) $ \begin{eqnarray} \lim\limits_{k\rightarrow \infty}\|z_{k+1}-z_{\widehat{l}(k)}\| = 0. \end{eqnarray} $

从而由定理4.1, 引理5.1和(5.14)式得到$ \lim\limits_{k\rightarrow \infty}\psi(z_{k}) = \lim\limits_{k\rightarrow \infty}\psi(z_{{\widehat{l}(k)}}) = \lim\limits_{k\rightarrow \infty}\psi(z_{l(k)}). $又由引理4.1知$ \psi(z_{k})\leq T_k\leq\psi(z_{l(k)}) $, 故$ \lim\limits_{k\rightarrow \infty}\psi(z_{k}) = \lim\limits_{k\rightarrow \infty}T_{k} = \lim\limits_{k\rightarrow \infty}\psi(z_{l(k)}). $

定理5.2  设$ F $连续可微且单调, $ \{z_{k}\} $由算法4.1迭代生成, 则$ \{z_{k}\} $的任一聚点$ z^{*}: = (\mu^{*}, x^{*}, s^{*}) $为$ H(z) = 0 $的解.

证  根据引理5.1的证明得$ \{\psi(z_{l(k)})\} $单调递减. 则由(4.1)式, (4.14)式和引理4.1有

(5.15) $ \begin{eqnarray} 0\leq\mu_{k}^{2}\leq\psi(z_{k})\leq T_k\leq\psi(z_{l(k)})\leq\psi(z_{0}), \end{eqnarray} $

结合引理3.3知$ \{z_{k}\} $有界. 故存在$ z^{*}: = (\mu^{*}, x^{*}, s^{*}) $使得$ {\lim\limits_{k \to \infty}}z_{k}: = z^{*} $. 由(5.15)式知$ \{\psi(z_{k})\} $有界. 因此$ \{\psi(z_{k})\} $存在收敛子列$ \{\psi(z_{k})\}_{k\in \overline{J}} $, $ \overline{J} $为非负整数子集. 根据(5.15)式, 定理4.1和引理4.2(i)知当$ \overline{J}\ni k\rightarrow \infty $时, $ \{\psi(z_{k})\} $和$ \{\beta(z_k)\} $分别收敛于$ \psi(z^{*}) $和$ \beta(z^{*}) $. 又由(4.14)和(4.15)式得$ \psi(z^{*}) = \| H(z^{*})\|^{2} $和$ \beta(z^{*}) = \gamma{\rm min}\{1, \psi(z^{*})\} $. 若$ \psi(z^{*}) = 0 $, 则结论成立. 设$ \psi(z^{*})>0 $, 考虑

(i) 设存在常数$ \epsilon>0 $, 使得对任意$ k\in\overline{J} $有$ \lambda_{k}\geq\epsilon>0 $. 由(3.17)式得

(5.16) $ \begin{eqnarray} \psi(z_{k}+\lambda_{k}\Delta z_{k})\leq[1-2\sigma(1-\gamma\mu_{0}-\kappa)\lambda_{k}]T_{k} \leq[1-2\sigma(1-\gamma\mu_{0}-\kappa)\epsilon]T_{k}. \end{eqnarray} $

对(5.16)式两边取极限, 结合(5.1)式得到$ \lim \limits_{\overline{J}\ni k\rightarrow \infty}\psi(z_{k}) = \lim \limits_{\overline{J}\ni k\rightarrow \infty}T_{k} = \psi(z^{*}) = 0 $, 这与$ \psi(z^{*})>0 $矛盾.

(ii) 设$ \lim \limits_{\overline{J}\ni k\rightarrow \infty}\lambda_{k} = 0 $. 根据算法4.1对充分大的$ k\in\overline{J} $, 步长$ \widehat{\lambda_{k}}: = \frac{\lambda_{k}}{\delta} $不满足(4.17)式. 则由引理4.1有

$ \begin{eqnarray*} \psi(z_{k}+\widehat{\lambda}_{k}\Delta z_{k})&>[1-2\sigma(1-\gamma\mu_{0}-\kappa)\widehat{\lambda_{k}}]T_{k}\geq[1-2\sigma(1-\gamma\mu_{0}-\kappa)\widehat{\lambda_{k}}]\psi(z_{k}), \end{eqnarray*} $

即

(5.17) $ \begin{eqnarray} \frac{\psi(z_{k}+\widehat{\lambda}_{k}\Delta z_{k})-\psi(z_{k})}{\widehat{\lambda_{k}}}\geq -2\sigma(1-\gamma\mu_{0}-\kappa)\psi(z_{k}). \end{eqnarray} $

因为$ 0<\mu_{k}<1 $, 则由引理4.2(ii)知$ 0<\mu_{0}\beta(z^{*})\leq\lim \limits_{\overline{J}\ni k\rightarrow \infty}\mu_{k} = \mu^{*}\leq1 $. 根据定理4.1知$ DH(z^{*}) $存在且可逆.故由(4.16)和(4.26)式得

(5.18) $ \begin{eqnarray} H^{T}(z^{*})DH(z^{*})\Delta z^{*}& = &\lim \limits_{\overline{J}\ni k\rightarrow \infty} H^{T}(z_{k})DH(z_{k})\Delta z_{k}{}\\ & = &\lim \limits_{\overline{J}\ni k\rightarrow \infty} H^{T}(z_{k})(-H(z_{k})+\beta(z_{k})\overline{z}+\varrho_{k}){}\\ &\leq&\lim \limits_{\overline{J}\ni k\rightarrow \infty}[-\psi(z_{k})+\gamma\mu_{0}\|H(z_{k})\|^{2}+\|\varrho_{k}\|\|H(z_{k})\|]{}\\ &\leq&\lim \limits_{\overline{J}\ni k\rightarrow \infty}[-\psi(z_{k})+\gamma\mu_{0}\|H(z_{k})\|^{2}+\kappa\|H(z_{k})\|^{2}]{}\\ & = &-(1-\gamma\mu_{0}-\kappa)\psi(z^{*}). \end{eqnarray} $

将(5.17)式两侧取极限, 结合(5.18)式有

$ \begin{eqnarray*} -2\sigma(1-\gamma\mu_{0}-\kappa)\psi(z^{*})\leq 2H^{T}(z^{*})DH(z^{*})\Delta z^{*}\leq-2(1-\gamma\mu_{0}-\kappa)\psi(z^{*}). \end{eqnarray*} $

又因为$ \gamma\mu_{0}+\kappa<1 $, 则上式表明$ \sigma\geq1 $, 这与$ 0<\sigma<\frac{1}{2} $矛盾. 故$ \psi(z^{*}) = 0 $和$ \beta(z^{*}) = 0 $.

由文献[14]中定理8的证明类似可得, 算法4.1具有如下局部二阶收敛性. 此处省略不证.

定理5.3  设$ F $连续可微且单调, $ z^{*} $是算法4.1迭代生成的序列$ \{z_{k}\} $的任意聚点. 若$ DF(x) $在$ {\cal J} $上Lipschitz连续且任意$ V\in\partial H(z^{*}) $非奇异, 则$ \{z_{k}\} $局部二阶收敛于$ z^{*} $, 即

$ \|z_{k+1}-z^{*}\| = O(\|z_{k}-z^{*}\|^{2}) \ {\rm{and}} \ \mu_{k+1} = O((\mu_{k})^{2}). $

由于二阶锥可视为对称锥的特例, 本节给出算法4.1求解二阶锥权互补问题的一些数值结果. 数值试验在Intel(R) Core(TM) i5-6500 CPU 3.20 GHz, 8.0GB内存, Windows 7操作系统的计算机上, 运用Matlab(R2015a)编程实现.

算法4.1中参数取值: $ \mu_{0} = 0.1, \sigma = 0.45, \delta = 0.75, \gamma = 0.225, \kappa = 0.1, \eta_{k} = 0.85 $和$ N = 3. $当$ \psi(z)\leq 10^{-6} $时迭代终止. 表中$ {\bf 0}: = (0, 0, \cdots, 0)^{T}\in {{\Bbb R}} ^{n}, {\bf 1}: = (1, 1, \cdots, 1)^{T}\in {{\Bbb R}} ^{n} $和$ e = (1, 0, \cdots, 0)^{T}\in {{\Bbb R}} ^{n} $. $ n $表示二阶锥权互补问题的规模, AIter和ACPU分别代表平均迭代次数和平均CPU时间.

第一个数值试验考虑二阶锥权互补问题

(6.4) $ \begin{eqnarray} x\in {\cal K}, s\in {\cal K}, x\circ s = w, s = Mx+q, \end{eqnarray} $

其中$ {\cal K} = {\cal K}^{n} $且$ w\in{\cal K} $. 令$ q\in{{\Bbb R}} ^{n} $为随机向量, $ B\in {{\Bbb R}} ^{n\times n} $为随机矩阵, 则$ M = B^{T}B $为半正定矩阵. 随机生成规模$ n $从100到800的二阶锥权互补问题, 每个问题随机生成50次. 为进行比较, 分别将求解无约束优化问题的非单调线搜索形式Grippo's method^[24]和Zhang-Hager's method^[25]用于求解二阶锥权互补问题. 选取权向量$ w = e $和初始点$ (x_{0}, s_{0}) = (e, e) $. 表 1列出了第一个数值试验结果.

第二个数值试验中选择权向量$ w = {\bf 0} $, 则(6.1)式退化为二阶锥互补问题.分别使用权向量$ w = {\bf 0} $, $ w = e $和$ w = (1, 1, 0, \cdots, 0)^{T} $进行测试.每个随机问题生成50次.表 2列出了第二个数值实验结果.

第三个数值试验中, 考虑具有多个二阶锥约束的二阶锥互补问题和二阶锥权互补问题, 即$ {\cal K} = {\cal K}^{10}\times\cdots\times{\cal K}^{10}\subseteq {{\Bbb R}} ^{n} $. 每个二阶锥约束中令权向量分别为$ w = {\bf 0} $, $ w = e $和$ w = (1, 1, 0, \cdots, 0)^{T} $. 表 3给出了算法4.1运用初始点$ (x_{0}, s_{0}) = (e, e) $求解二阶锥互补问题和二阶锥权互补问题的数值结果.

第四个数值试验中选取权向量$ w = e $. 考虑求解不同初始点的线性二阶锥权互补问题, 数值结果见表 4.

最后考虑非线性二阶锥权互补问题

(6.2) $ \begin{eqnarray} x\in {\cal K}, s\in {\cal K}, x\circ s = w, s = F(x), \end{eqnarray} $

其中$ {\cal K} = {\cal K}^{3}\times{\cal K}^{2} $且$ F:{{\Bbb R}} ^{5}\rightarrow {{\Bbb R}} ^{5} $定义为

(6.3) $ \begin{eqnarray} F(x) = \left( \begin{array}{c} 24(2x_{1}-x_{2})^{3}+{\rm{exp}}(x_{1}-x_{3})-4x_{4}+x_{5} \\ -12(2x_{1}-x_{2})^{3}+3(3x_{2}+x_{5})/\sqrt{1+(3x_{2}+x_{5})^{2}}-6x_{4}-7x_{5}\\ -{\rm{exp}}(x_{1}-x_{3})+5(3x_{2}+x_{5})/\sqrt{1+(3x_{2}+x_{5})^{2}}-3x_{4}+5x_{5}\\ 4x_{1}+6x_{2}+3x_{3}-1\\ -x_{1}+7x_{2}-5x_{3}+2 \end{array}\right). \end{eqnarray} $

选择权向量$ w = (1, 0, 0, 1, 0)^{T} $, 运用算法4.1求解二阶锥权互补问题(6.2)和(6.3)得到解$ x^{*}\approx(0.461951, 0.260760, 0.249817, 0.572061, -0.382505)^{T} $. 取$ w = {\bf 0} $, 则问题()退化为二阶锥互补问题, 得到解$ x^{*}\approx(0.241812, 0.067254, 0.232274, 0.147882, -0.147877)^{T} $. 表 5给出了数值实验结果.

从表 1-5的数值结果知

(i) 算法4.1可以有效地求解线性和非线性二阶锥权互补问题.

(ii) 表 1表明运用算法4.1中的非单调形式求解二阶锥权互补问题比运用文献[24]和^[25]中的非单调方案求解需要更少的迭代次数和CPU时间.

(iii) 表 2和表 3表明算法4.1求解具有单个二阶锥约束的二阶锥权互补问题通常比求解具有多个二阶锥约束的二阶锥权互补问题需要更少的迭代次数和更少的CPU时间.

(iv) 表 4和表 5表明算法4.1求解二阶锥权互补问题所需的迭代次数受初始点的影响不大, 因而算法性能比较稳定.