数学物理学报, 2021, 41(2): 507-522 doi:

论文

对称锥权互补问题的正则化非单调非精确光滑牛顿法

迟晓妮,1,2, 曾荣1,3, 刘三阳4, 朱志斌1

A Regularized Nonmonotone Inexact Smoothing Newton Algorithm for Weighted Symmetric Cone Complementarity Problems

Chi Xiaoni,1,2, Zeng Rong1,3, Liu Sanyang4, Zhu Zhibin1

通讯作者: 迟晓妮, E-mail: chixiaoni@126.com

收稿日期: 2019-03-15  

基金资助: 国家自然科学基金.  11861026
国家自然科学基金.  61877046
国家自然科学基金.  61967004
广西自然科学基金.  2016GXNSFBA380102
广西密码学与信息安全重点实验室研究课题.  GCIS201819
广西自动检测技术与仪器重点实验室基金.  YQ18112

Received: 2019-03-15  

Fund supported: the NSFC.  11861026
the NSFC.  61877046
the NSFC.  61967004
the NSF of Guangxi.  2016GXNSFBA380102
the Guangxi Key Laboratory of Cryptography and Information Security.  GCIS201819
the Guangxi Key Laboratory of Automatic Detection Technology and Instrument.  YQ18112

Abstract

In this paper, we propose a regularized nonmonotone inexact smoothing Newton algorithm for solving the weighted symmetric cone complementarity problem(wSCCP). In the algorithm, we consider the regularized parameter as an independent variable. Therefore, it is simpler and easier to implement than many available algorithms. At each iteration, we only need to obtain an inexact solution of a system of equations. Moreover, the nonmonotone line search technique adopted in our algorithm includes two popular nonmonotone search schemes. We prove that the algorithm is globally and locally quadratically convergent under suitable assumptions. Finally, some preliminary numerical results indicate the effectiveness of our algorithm.

Keywords: Regularized inexact smoothing Newton algorithm ; Weighted symmetric cone complementarity problem ; Nonmonotone line search ; Global convergence ; Locally quadratic convergence

PDF (445KB) 元数据 多维度评价 相关文章 导出 EndNote| Ris| Bibtex  收藏本文

本文引用格式

迟晓妮, 曾荣, 刘三阳, 朱志斌. 对称锥权互补问题的正则化非单调非精确光滑牛顿法. 数学物理学报[J], 2021, 41(2): 507-522 doi:

Chi Xiaoni, Zeng Rong, Liu Sanyang, Zhu Zhibin. A Regularized Nonmonotone Inexact Smoothing Newton Algorithm for Weighted Symmetric Cone Complementarity Problems. Acta Mathematica Scientia[J], 2021, 41(2): 507-522 doi:

1 引言

最近, 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} $使得

$ \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]的启发, 本文提出求解对称锥权互补问题的正则化非单调非精确光滑牛顿法. 算法求解以下对称锥权互补问题

$ \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} $定义为

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

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

2 预备知识

本节回顾欧几里德若当代数中的一些概念和结果[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) $使得

其中$ \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) $相关的向量值函数可以表示为

对任意$ 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) $

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

则称$ \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 $.

3 wSCCP的光滑函数

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

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

$ \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} $

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

$ \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}} $, 令

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

因此

$ \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}) $.

$ 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)式)是强制的.

4 wSCCP的正则化非单调非精确光滑牛顿法

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

$ z: = (\mu, x, s)\in{{\Bbb R}} \times{\cal J}\times{\cal J} $, $ \phi $由(3.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} $处连续可微, 其雅可比为

$ \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 $可逆, 即证线性方程组

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

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

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

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

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

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

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

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

$ \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} $

$ \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知

$ \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有

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

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

$ \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)式知

$ \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}} _{+} $

$ \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 $, 停止. 否则, 令

$ \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} $使得

$ \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 \} $使得

$ \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} $,

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

$ \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} $

这里

$ \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} $

$ \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]提出的无约束优化问题的非单调形式

$ \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} $

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

$ k>N $

其中

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

$ \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)式知

证毕.

引理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_{0}\beta(z_{k})\leq\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适定. 令

$ \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} $处连续可微, 且

$ \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 $

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

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

$ \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适定.

5 收敛性分析

本节给出算法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有

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

$ \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 $连续可微且单调, 则

$ \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知

$ \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)式有

$ \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得

$ \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 $使得

$ \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)式有

$ \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)式知

$ \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)式有

$ \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 $

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

$ \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)式有

$ \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 $, 即

$ \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)式表明

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

$ \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)式知

$ \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有

$ \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)式得

$ \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} \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)式得

$ \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)式有

又因为$ \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^{*} $, 即

6 数值算例

由于二阶锥可视为对称锥的特例, 本节给出算法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时间.

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

$ \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列出了第一个数值试验结果.

表 1   三种算法求解二阶锥权互补问题的数值结果

Algorithm 4.1Grippo's methodZhang-Hager's method
nACPUAIterACPUAIterACPUAIter
1000.00774.860.00974.960.00804.94
2000.03275.080.03405.160.03535.26
3000.09676.000.09976.000.09956.00
4000.26836.000.27636.000.28356.00
5000.45766.000.48106.020.47576.02
6000.77716.500.78246.580.95036.66
7001.21127.001.21787.001.50067.00
8001.60967.001.61627.001.76677.00

新窗口打开| 下载CSV


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

表 2   求解二阶锥互补问题与二阶锥权互补问题的数值结果

SOCCP(w =0)wSOCCP(w = e)wSOCCP(w = (1, 1, 0, …, 0)T)
nACPUAIterACPUAIterACPUAIter
1000.00925.540.00774.860.00815.00
2000.04046.000.03275.080.04036.00
3000.10846.520.09676.000.09996.00
4000.32247.000.26836.000.28856.10
5000.60377.000.45766.000.54767.00
6000.86667.120.77716.500.85257.00
7001.37987.821.21127.001.27007.00
8001.92438.001.60967.001.69157.00

新窗口打开| 下载CSV


第三个数值试验中, 考虑具有多个二阶锥约束的二阶锥互补问题和二阶锥权互补问题, 即$ {\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) $求解二阶锥互补问题和二阶锥权互补问题的数值结果.

表 3   求解具有多个二阶锥约束的二阶锥权互补问题的数值结果

SOCCP(w =0)wSOCCP(w = e)wSOCCP(w = (1, 1, 0, …, 0)T)
nACPUAIterACPUAIterACPUAIter
1000.01806.240.01455.020.01796.00
2000.06177.080.05126.000.06217.00
3000.13957.760.11456.540.12947.28
4000.33788.220.29167.000.34348.00
5000.60968.920.47447.000.56018.02
6000.95769.280.85057.240.93948.96
7001.40909.501.37118.001.35849.00
8002.20109.761.68038.001.76389.00

新窗口打开| 下载CSV


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

表 4   求解不同初始点的线性二阶锥权互补问题的数值结果

n(x0, s0)ACPUAIter
100(e, 0)0.00785.00
100(0, e)0.00694.38
100(1, 1)0.00925.46
100-(1, 1)0.00945.66
10010×(1, 1)0.01015.92
100-10×(1, 1)0.00985.88

新窗口打开| 下载CSV


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

$ \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} $定义为

$ \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给出了数值实验结果.

表 5   求解不同初始点的非线性二阶锥权互补问题的数值结果

SOCCP(w = 0)wSOCCP(w = (1, 0, 0, 1, 0)T)
(x0, s0)ACPUAIterACPUAIter
(1, 1)0.01498.000.00857.00
-(1, 1)0.01448.000.01509.00
10×(1, 1)0.025513.000.017412.00
-10×(1, 1)0.023113.000.019413.00

新窗口打开| 下载CSV


表 1-5的数值结果知

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

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

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

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

参考文献

Potra F A .

Weighted complementarity problems-a new paradigm for computing equilibria

SIAM J Optim, 2012, 22 (4): 1634- 1654

DOI:10.1137/110837310      [本文引用: 1]

Anstreicher K M .

Interior-point algorithms for a generalization of linear programming and weighted centring

Optim Methods Softw, 2012, 27 (4/5): 605- 612

URL     [本文引用: 1]

Potra F A .

Sufficient weighted complementarity problems

Comput Optim Appl, 2016, 64 (2): 467- 488

DOI:10.1007/s10589-015-9811-z      [本文引用: 1]

Jian Z .

A smoothing Newton algorithm for weighted linear complementarity problem

Optim Lett, 2016, 10 (3): 499- 509

DOI:10.1007/s11590-015-0877-4     

Chi X N , Gowda M S , Tao J Y .

The weighted horizontal linear complementarity problem on a Euclidean Jordan algebra

J Global Optim, 2019, 73 (1): 153- 169

DOI:10.1007/s10898-018-0689-z      [本文引用: 1]

Chen X J , Qi L Q , Sun D F .

Global and superlinear convergence of the smooothing Newton method and its application to general box constrained variational inequalities

Math Comput, 1998, 67 (222): 519- 540

DOI:10.1090/S0025-5718-98-00932-6      [本文引用: 1]

Chi X N , Liu S Y .

A one-step smoothing Newton method for second-order cone programming

J Comput Appl Math, 2009, 223 (1): 114- 123

DOI:10.1016/j.cam.2007.12.023     

Hayashi S , Yamashita N , Fukushima M .

A combined smoothing and regularization method for monotone second-order cone complementarity problems

SIAM J Optim, 2005, 15 (8): 593- 615

URL     [本文引用: 2]

Huang Z H , Ni T .

Smoothing algorithms for complementarity problems over symmetric cones

Comput Optim Appl, 2010, 45 (3): 557- 579

DOI:10.1007/s10589-008-9180-y      [本文引用: 1]

Kong L C , Sun J , Xiu N H .

A regularized smoothing Newton method for symmetric cone complementarity problems

SIAM J Optim, 2008, 19 (3): 1028- 1047

DOI:10.1137/060676775      [本文引用: 1]

Fang L , He G P .

Some modifications of Newton's method with higher-order convergence for solving nonlinear equations

J Comput Appl Math, 2009, 228 (1): 296- 303

DOI:10.1016/j.cam.2008.09.023     

Liu Y J , Zhang L W , Wang Y H .

Analysis of a smoothing method for symmetric conic linear programming

J Appl Math Comput, 2006, 22 (1/2): 133- 148

DOI:10.1007/BF02896466      [本文引用: 1]

Pan S H , Chen J S .

A regularization method for the second-order cone complementarity problem with the Cartesian P0-property

Nonlinear Anal, 2009, 70 (4): 1475- 1491

DOI:10.1016/j.na.2008.02.028      [本文引用: 1]

Qi L Q , Sun D F , Zhou G L .

A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities

Math Program, 2000, 87 (1): 1- 35

DOI:10.1007/s101079900127      [本文引用: 1]

Tang J Y , Dong L , Zhou J C , et al.

A smoothing-type algorithm for the second-order cone complementarity problem with a new nonmonotone line search

Optim, 2015, 64 (9): 1935- 1955

DOI:10.1080/02331934.2014.906595     

Wu J , Zhang L W , Zhang Y .

A smoothing Newton method for mathematical programs governed by second-order cone constrained generalized equations

J Glob Optim, 2013, 55 (2): 359- 385

DOI:10.1007/s10898-012-9880-9     

Yu G L , Liu S Y .

Optimality conditions of globally proper efficient solutions for set-valued optimization problems

Acta Math Appl Sin, 2010, 33 (1): 150- 160

URL    

Zhang Y S , Gao L F .

A smoothing inexact Newton method for symmetric cone complementarity problems

Acta Math Sci, 2015, 35A (4): 824- 832

URL     [本文引用: 1]

Chi X N , Liu S Y .

An infeasible-interior-point predictor-corrector algorithm for the second-order cone program

Acta Math Sci, 2008, 28B (3): 551- 559

URL     [本文引用: 1]

Yoshise A .

Interior point trajectories and a homogeneous model for nonlinear complementarity problems over symmetric cones

SIAM J Optim, 2006, 17 (4): 1129- 1153

[本文引用: 2]

Wan Z P , Wang X J , He J L , et al.

Asymptotic approximation method and its convegence on semi-infinite programming

Acta Math Sci, 2006, 26B (1): 17- 24

[本文引用: 1]

Xu Y H , Liu S Y .

The (h, φ)-Lipschitz function, its generalized directional derivative and generalized gradient

Acta Math Sci, 2006, 26A (2): 212- 222

URL    

Ahookhosh M , Ghaderi S .

On efficiency of nonmonotone Armijo-type line searches

Appl Math Model, 2017, 43, 170- 190

DOI:10.1016/j.apm.2016.10.055      [本文引用: 4]

Grippo L , Lampariello F , Lucidi S .

A nonmonotone line search technique for Newton's Method

SIAM J Numer Anal, 1986, 23 (4): 707- 716

DOI:10.1137/0723046      [本文引用: 4]

Zhang H , Hager W W .

A nonmonotone line search technique and its application to unconstrained optimization

SIAM J Optim, 2004, 14 (4): 1043- 1056

DOI:10.1137/S1052623403428208      [本文引用: 7]

Faraut J , Korányi A . Analysis on Symmetric Cones. New York: Oxford University Press, 1994

[本文引用: 3]

Mifflin R .

Semismooth and semiconvex functions in constrained optimization

SIAM J Control Optim, 1977, 15 (6): 957- 972

URL     [本文引用: 1]

Qi L , Sun J .

A nonsmooth version of Newton's method

Math Program, 1993, 58 (1/3): 353- 367

URL     [本文引用: 2]

Clarke F H . Optimization and Nonsmooth Analysis. New York: Wiley, 1983

[本文引用: 1]

Gowda M S , Sznajder R , Tao J .

Some P-properties for linear transformations on Euclidean algebras

Linear Algebra Appl, 2004, 393 (1): 203- 232

[本文引用: 2]

Sun D , Sun J .

Strong semismoothness of the Fischer-Burmeister SDC and SOC complementarity functions

Math Program, 2005, 103 (3): 575- 581

DOI:10.1007/s10107-005-0577-4      [本文引用: 1]

/