2012年, Florian A. Potra提出了加权线性互补问题(weighted Linear Complementarity Problem)^[1], 其数学模型定义如下: 求$ (x, s, y)\in{\mathbb{R}}^n\times{\mathbb{R}}^n\times{\mathbb{R}}^m $, 使得

$ \begin{equation} x\geq0, \; s\geq0, \; Px+Qs+Ry=a, \; x s=w, \end{equation} $

(1.1)

这里$ P\in{\mathbb{R}}^{(n+m)\times n}, Q\in{\mathbb{R}}^{(n+m)\times n}, R\in{\mathbb{R}}^{(n+m)\times m} $为给定矩阵, $ a\in {\mathbb{R}}^{n+m} $是给定向量, $ w\geq0 $为权重向量. $ xs $表示向量$ x $和$ s $对应分量相乘组成的向量, 即$ {xs}:=(x_1s_1, ..., x_ns_n)^T $. 我们称加权线性互补问题是单调的, 如果其满足对任意的$ (\Delta x, \Delta s, \Delta y)\in\mathbb{R}^{n}\times\mathbb{R}^{n}\times\mathbb{R}^{m} $,

$ P\Delta x+Q\Delta s+R\Delta y=0\Longrightarrow\langle\Delta x, \Delta s\rangle\geq0. $

经济、管理等领域中的许多均衡问题都可以转化成加权线性互补问题模型进行求解, 比如Fisher竞争市场均衡问题可以转化为单调加权线性互补问题, Arrow-Debreue竞争市场均衡问题可以转化成自对偶加权线性互补问题等等^[2]. 有些市场均衡问题既可以转化成标准的互补问题, 也可以转化成加权线性互补问题, 但后者往往可以更有效地进行求解. 比如Fisher竞争市场均衡问题既可以转化为非线性互补问题, 也可以转化为单调加权线性互补问题, 而后者可以被内点法有效地求解^[1]. 2018年, Potra在其综述性论文[2]中详细介绍了加权线性互补问题的应用. 自从Potra提出了加权线性互补问题的数学模型后, 许多学者对该问题的求解方法展开了深入研究, 取得了很好的结果. 比如, Potra在文献[1, 2, 3]中给出了求解加权线性互补问题的内点算法, Dong等人^[4]给出了一个求解加权线性互补问题的非内部连续化算法, Asadi等人^[5]给出了一个求解加权线性互补问题的完全牛顿步内点法, Tang和Zhou在文献^{[6, 7]}中给出了求解加权线性互补问题的阻尼高斯牛顿法和非单调Levenberg-Marquardt型法, He和Tang^[8]给出了一个求解加权线性互补问题的光滑Levenberg-Marquardt法.

光滑牛顿法是求解加权线性互补问题十分有效的算法, 其基本思想是利用某个光滑函数将加权线性互补问题等价转化成一个光滑方程组, 然后利用牛顿法求解该方程组. 2016年, Zhang^[9]给出了一个求解单调加权线性互补问题的光滑牛顿法, 证明了算法具有全局和局部二次收敛性质. 2018年, Tang^[10]给出了一个适合求解大规模单调加权线性互补问题的光滑非精确牛顿法, 分析了算法的全局和局部收敛性质. 2020年, Liu和Tang^[11]给出了一个求解加权线性互补问题的光滑牛顿法, 在非奇异条件下证明了算法具有局部二次收敛速度. 2021年, Tang和Zhang^[12]给出了一个求解对称锥加权互补问题的非单调光滑牛顿法, 当问题的解集非空时, 证明了算法在弱于非奇异条件下具有局部二次收敛速度.

本文首先给出一类光滑函数, 分析了函数的性质. 基于此函数, 我们给出了一个新的求解加权线性互补问题的非单调光滑牛顿法, 在适当条件下证明了算法具有全局和局部二次收敛性质. 与文献[9-12]中的光滑牛顿法不同, 我们的算法采用一个非单调无导数线搜索技术去产生步长, 从而具有更好的收敛性质和实际计算效果.

在本文中, $ \mathbb{R}^{n} $定义为$ n $维实列向量空间, $ \mathbb{R}^{n}_{+} $和$ \mathbb{R}^{n}_{++} $分别表示$ \mathbb{R}^{n} $中的非负和正象限. $ \|\cdot\| $表示2-范数. 定义$ \mathbb{N}:=\{1, 2, ..., n\} $. 对于任意$ x\in {\mathbb{R}}^n $, 用$ \mbox{vec}\{x_i: i\in \mathbb{N}\} $表示向量$ x $, 用$ \mbox{diag}\{x_i: i\in \mathbb{N}\} $表示第$ i $个对角元素为$ x_i $的对角矩阵.

光滑函数在光滑牛顿法的设计中起着至关重要的作用. 在本文中, 我们考虑如下单参数光滑函数:

$ \begin{equation} \phi^c_\theta(\mu, a, b)=a+b-\sqrt{\theta(a-b)^2+(1-\theta)(a^2+b^2)+2(1+\theta)c+\mu^2}, \; \forall(\mu, a, b)\in\mathbb{R}^3, \end{equation} $

(2.1)

其中$ c\geq0 $为固定的常数, $ \theta\in(-1, 1] $为给定的参数.

引理2.1  设$ \phi^c_\theta $由(2.1)定义, 则

$ \begin{equation} \phi^c_\theta(\mu, a, b)=0\Longleftrightarrow a\geq0, \; b\geq0, \; ab=c+\frac{\mu^{2}}{2(1+\theta)}. \end{equation} $

(2.2)

证  首先证明"$ \Longrightarrow $". 由$ \phi^c_\theta(\mu, a, b)=0 $可得

$ \begin{equation} a+b=\sqrt{\theta(a-b)^2+(1-\theta)(a^2+b^2)+2(1+\theta)c+\mu^2}. \end{equation} $

(2.3)

将上式两边同时平方, 可得$ 2(1+\theta)ab=2(1+\theta)c+\mu^{2}, $ 即

$ \begin{equation} ab=c+\frac{\mu^{2}}{2(1+\theta)}. \end{equation} $

(2.4)

将(2.4)代入(2.3)可得

$ \begin{equation*} \begin{split} a=\sqrt{a^2+b^2+2c+\frac{\mu^2}{1+\theta}}-b\geq0, \quad b=\sqrt{a^2+b^2+2c+\frac{\mu^2}{1+\theta}}-a\geq0. \end{split} \end{equation*} $

接下来证明"$ \Longleftarrow $". 因为$ ab=c+\frac{\mu^{2}}{2(1+\theta)} $, 故可知$ 2(1+\theta)c=2(1+\theta)ab-\mu^2 $. 再结合$ a\ge0, b\ge0 $, 可得

$ \begin{equation*} \begin{split} \phi^c_\theta(\mu, a, b)&=a+b-\sqrt{a^2+b^2-2\theta ab+2(1+\theta)ab}\\ &=a+b-\sqrt{(a+b)^2}\\ &=0. \end{split} \end{equation*} $

因此, 引理成立. 证毕.

由(2.2)可知, 函数$ \phi^c_\theta $满足如下性质:

$ \begin{equation} \phi^c_\theta(0, a, b)=0\Longleftrightarrow a\geq0, \; b\geq0, \; ab=c. \end{equation} $

(2.5)

引理2.2 设$ \phi^c_\theta $由(2.1)定义, 则$ \phi^c_\theta $在任意点$ (\mu, a, b)\in\mathbb{R}_{++}\times\mathbb{R}\times\mathbb{R} $处是连续可微的, 并且

$ \begin{equation*} \label{phi-gre} \nabla\phi^c_\theta(\mu, a, b)=\left[ \begin{array}{c} \frac{\partial\phi^c_\theta}{\partial \mu}(\mu, a, b)\\ \frac{\partial\phi^c_\theta}{\partial a}(\mu, a, b)\\ \frac{\partial\phi^c_\theta}{\partial b}(\mu, a, b)\end{array} \right], \end{equation*} $

其中

$ \begin{eqnarray*} \frac{\partial\phi^c_\theta}{\partial\mu}(\mu, a, b)&=& -\frac{\mu}{\sqrt{\theta(a-b)^2+(1-\theta)(a^2+b^2)+2(1+\theta)c+\mu^2}}, \label{phi-mu}\\ \frac{\partial\phi^c_\theta}{\partial a}(\mu, a, b)&=& 1-\frac{a-\theta b}{\sqrt{\theta(a-b)^2+(1-\theta)(a^2+b^2)+2(1+\theta)c+\mu^2}}, \label{phi-a}\\ \frac{\partial\phi^c_\theta}{\partial b}(\mu, a, b)&=& 1-\frac{b-\theta a}{\sqrt{\theta(a-b)^2+(1-\theta)(a^2+b^2)+2(1+\theta)c+\mu^2}} \label{phi-b}. \end{eqnarray*} $

证  因为对任意的$ (\mu, a, b)\in\mathbb{R}_{++}\times\mathbb{R}\times\mathbb{R} $, 有$ {\theta(a-b)^2+(1-\theta)(a^2+b^2)+2(1+\theta)c+\mu^2}>0, $ 所以由导数的定义可知结论成立. 证毕.

引理2.3  设$ \phi^c_\theta $由(2.1)定义, 则在任意点$ (\mu, a, b)\in\mathbb{R}_{++}\times\mathbb{R}\times\mathbb{R} $处满足

$ 0<\frac{\partial\phi^c_\theta}{\partial a}(\mu, a, b)<2, \; \; 0<\frac{\partial\phi^c_\theta}{\partial b}(\mu, a, b)<2. $

证  对任意的$ (\mu, a, b)\in\mathbb{R}_{++}\times\mathbb{R}\times\mathbb{R} $, 因为$ \mu>0 $, 故

$ \begin{eqnarray*} (a-\theta b)^2&\le& a^2+b^2-2\theta ab\\ &=&\theta(a-b)^2+(1-\theta)(a^2+b^2)\\ &<& \theta(a-b)^2+(1-\theta)(a^2+b^2)+2(1+\theta)c+\mu^2, \end{eqnarray*} $

进而可得

$ -1<\frac{a-\theta b}{\sqrt{\theta(a-b)^2+(1-\theta)(a^2+b^2)+2(1+\theta)c+\mu^2}}<1. $

这表明$ 0<\frac{\partial\phi^c_\theta}{\partial a}(\mu, a, b)<2 $. 同理可证$ 0<\frac{\partial\phi^c_\theta}{\partial b}(\mu, a, b)<2 $. 证毕.

引理2.4  设$ \phi^c_\theta $由(2.1)定义, 则对任意的$ (\mu, a, b), (\bar{\mu}, \bar{a}, \bar{b})\in \mathbb{R}^3 $, 有

$ \begin{eqnarray*} |\phi^c_\theta(\mu, a, b)-\phi^c_\theta(\bar{\mu}, \bar{a}, \bar{b})| &\le&2\sqrt{2}\|(\mu, a, b)-(\bar{\mu}, \bar{a}, \bar{b})\|. \end{eqnarray*} $

证  我们定义$ g^c_\theta(\mu, a, b):=\sqrt{\theta(a-b)^2+(1-\theta)(a^2+b^2)+2(1+\theta)c+\mu^2}. $ 注意到$ g^c_\theta $等价于

$ \begin{eqnarray*} g^c_\theta(\mu, a, b)&=&\sqrt{(a-\theta b)^2+(1-\theta^2)b^2+2(1+\theta)c+\mu^2}\\ &=&\|(a-\theta b, \sqrt{1-\theta^2}b, \sqrt{2(1+\theta)c}, \mu)\|. \end{eqnarray*} $

因此, 对任意的$ (\mu, a, b), (\bar{\mu}, \bar{a}, \bar{b})\in \mathbb{R}^3 $, 有

$ \begin{eqnarray*} |g^c_\theta(\mu, a, b)-g^c_\theta(\bar{\mu}, \bar{a}, \bar{b})|&=&|\|(a-\theta b, \sqrt{1-\theta^2}b, \sqrt{2(1+\theta)c}, \mu)\|\\ &&-\|(\bar{a}-\theta \bar{b}, \sqrt{1-\theta^2}\bar{b}, \sqrt{2(1+\theta)c}, \bar{\mu})\||\\ &\leq&\|(a-\theta b, \sqrt{1-\theta^2}b, \sqrt{2(1+\theta)c}, \mu)\\ &&-(\bar{a}-\theta \bar{b}, \sqrt{1-\theta^2}\bar{b}, \sqrt{2(1+\theta)c}, \bar{\mu})\|\\ &=&\|(a-\bar{a}+\theta(\bar{b}-b), \sqrt{1-\theta^2}(b-\bar{b}), \mu-\bar{\mu}\|\\ &=&\sqrt{[a-\bar{a}+\theta(\bar{b}-b)]^2+(1-\theta^2)(b-\bar{b})^2+(\mu-\bar{\mu})^2}\\ &\leq&\sqrt{2(a-\bar{a})^2+2\theta^2(b-\bar{b})^2+(1-\theta^2)(b-\bar{b})^2+(\mu-\bar{\mu})^2}\\ &=&\sqrt{2(a-\bar{a})^2+(1+\theta^2)(b-\bar{b})^2+(\mu-\bar{\mu})^2}\\ &\le&\sqrt{2}\|(\mu, a, b)-(\bar{\mu}, \bar{a}, \bar{b})\|, \end{eqnarray*} $

这里最后一个不等式成立是因为$ \theta\in(-1, 1] $. 此外, 对任意的$ (\mu, a, b), (\bar{\mu}, \bar{a}, \bar{b})\in \mathbb{R}^3 $, 我们有

$ \begin{eqnarray*} |a+b-(\bar{a}+\bar{b})|&\le&|a-\bar{a}|+|b-\bar{b}| \\ &\leq&\sqrt{2[(a-\bar{a})^2+(b-\bar{b})^2]}\\ &\leq&\sqrt{2[(a-\bar{a})^2+(b-\bar{b})^2+(\mu-\bar{\mu})^2]}\\ &=&\sqrt{2}\|(\mu, a, b)-(\bar{\mu}, \bar{a}, \bar{b})\|. \end{eqnarray*} $

因此, 对任意的$ (\mu, a, b), (\bar{\mu}, \bar{a}, \bar{b})\in \mathbb{R}^3 $, 有

$ \begin{eqnarray*} |\phi^c_\theta(\mu, a, b)-\phi^c_\theta(\bar{\mu}, \bar{a}, \bar{b})|&=&|a+b-(\bar{a}+\bar{b})-(g^c_\theta(\mu, a, b)-g^c_\theta(\bar{\mu}, \bar{a}, \bar{b}))|\\ &\le&|a+b-(\bar{a}+\bar{b})|+|g^c_\theta(\mu, a, b)-g^c_\theta(\bar{\mu}, \bar{a}, \bar{b})|\\ &\le&2\sqrt{2}\|(\mu, a, b)-(\bar{\mu}, \bar{a}, \bar{b})\|. \end{eqnarray*} $

这表明$ \phi^c_\theta $在$ \mathbb{R}^3 $上全局Lipschitz连续. 证毕.

函数的强半光滑性质在光滑牛顿型算法局部收敛速度的分析中起着重要作用. 关于函数强半光滑的具体定义, 可参见文献[13].

引理2.5  设$ \phi^c_\theta $由(2.1)定义, 则$ \phi^c_\theta $在任意点$ (\mu, a, b)\in\mathbb{R}^3 $处是强半光滑的.

证  如果$ c>0 $, 则易知$ \phi^c_\theta $在任意点$ (\mu, a, b)\in\mathbb{R}^3 $处二次连续可微. 这表明梯度$ \nabla\phi^c_\theta $在$ (\mu, a, b)\in\mathbb{R}^3 $处局部Lipschitz连续. 因此, $ \phi^c_\theta $在点$ (\mu, a, b)\in\mathbb{R}^3 $处强半光滑. 如果$ c=0, $ 则由(2.1)可知$ \phi^c_\theta(\mu, a, b)=a+b-\sqrt{(a-\theta b)^2+(1-\theta^2)b^2+\mu^2}. $ 由文献[14]中的引理2.1可知函数$ \sqrt{\alpha^2+\beta^2+\gamma^2} $在任意点$ (\alpha, \beta, \gamma)\in\mathbb{R}^3 $处局部Lipschitz连续、方向可微并且强半光滑. 此外, 函数$ a-\theta b $和$ \sqrt{(1-\theta^2)}b $显然处处强半光滑. 因为强半光滑函数的复合函数仍然是强半光滑的, 所以函数$ \sqrt{(a-\theta b)^2+(1-\theta^2)b^2+\mu^2} $在任意点$ (\mu, a, b)\in\mathbb{R}^3 $处是强半光滑的. 显然, 函数$ a+b $处处强半光滑. 因此, $ \phi^c_\theta $在任意点$ (\mu, a, b)\in\mathbb{R}^3 $处是强半光滑的. 证毕.

记$ z:=(\mu, x, s, y)\in\mathbb{R}\times\mathbb{R}^{n}\times\mathbb{R}^{n}\times\mathbb{R}^{m} $. 我们定义函数

$ \begin{equation} H_\theta(z):=\left( \begin{array}{cccc} \mu\\ \; Px+Qs+Ry-a\\ \phi_\theta^{w_{1}}(\mu, x_1, s_1)\\ \vdots\\ \phi_\theta^{w_{n}}(\mu, x_{n}, s_{n}) \end{array} \right), \end{equation} $

(3.1)

其中$ w=(w_1, ..., w_n)^T $为权重向量, 则由(2.5)可知$ H_\theta(z)=0\Longleftrightarrow \mu=0\; \mbox{且}\; (x, s, y)\; $是加权线性互补问题(1.1)的解.

引理3.1  (ⅰ) $ H_\theta(z) $在任意点$ z\in\mathbb{R}_{++}\times\mathbb{R}^{n}\times\mathbb{R}^{n}\times\mathbb{R}^{m} $处连续可微, 其雅克比矩阵为

$ H'_\theta(z)=\left( \begin{array}{cccc} 1&0&0&0\\ 0&P&Q&R\\ d_\mu&D_x&D_s&0 \end{array} \right), $

其中

$ d_\mu:={{\text{vec}}}\bigg\{-\frac{\mu}{\sqrt{\theta(x_i-s_i)^2+(1-\theta)(x_i^2+s_i^2)+2(1+\theta)w_i+\mu^2}}:i\in \mathbb{N}\bigg\}, \; \; \; $

$ D_x:={{\text{diag}}}\bigg\{1-\frac{x_i-\theta s_i}{\sqrt{\theta(x_i-s_i)^2+(1-\theta)(x_i^2+s_i^2)+2(1+\theta)w_i+\mu^2}}:i\in \mathbb{N}\bigg\}, \; $

$ D_s:={{\text{diag}}}\bigg\{1-\frac{s_i-\theta x_i}{\sqrt{\theta(x_i-s_i)^2+(1-\theta)(x_i^2+s_i^2)+2(1+\theta)w_i+\mu^2}}:i\in \mathbb{N}\bigg\}.\; $

(ⅱ) $ H_\theta(z) $在$ \mathbb{R}^{1+2n+m} $上全局Lipschitz连续, 即存在常数$ L>0 $使得

$ \|H_\theta(z_1)-H_\theta(z_2)\|\le L\|z_1-z_2\|, \; \; \forall\; z_1, z_2\in\mathbb{R}^{1+2n+m}. $

(ⅲ) $ H_\theta(z) $在$ \mathbb{R}^{1+2n+m} $上是强半光滑的.

(ⅳ) 如果加权线性互补问题是单调的, 则$ H'_\theta(z) $在任意点$ z\in\mathbb{R}_{++}\times\mathbb{R}^{n}\times\mathbb{R}^{n}\times\mathbb{R}^{m} $处可逆.

证  由引理2.2和引理2.4可知结论(ⅰ)和(ⅱ)成立. 因为一个向量值函数强半光滑当且仅当它所有的组成函数强半光滑, 故由引理2.5可知结论(ⅲ)成立. 由引理2.3可知$ D_x $和$ D_s $是正的对角矩阵. 利用这个性质, 类似于文献[9]中引理1的证明, 我们可以证明结论(ⅳ)成立. 证毕.

下面, 我们给出具体的算法.

算法3.1  (非单调光滑牛顿法)

步骤0  选取参数$ \lambda_1, \lambda_2, \delta\in(0, 1) $和$ \mu_0>0 $. 选取$ \gamma\in(0, 1) $使得$ \mu_0\geq\gamma $. 选取$ x^0, s^0\in \mathbb{R}^n, y^0\in\mathbb{R}^m $并令$ z^0:=(\mu_0, x^0, s^0, y^0) $. 令$ {C}_0:=\|H_\theta(z^0)\| $, $ \beta_{0}:=\gamma\min\{1, \|H_\theta(z^{0})\|^2\}. $ 选取常数$ \eta_{\min} $和$ \eta_{\max} $满足$ 0\leq\eta_{\min}<\eta_{\max}<1. $ 选取点列$ \{\eta_k\} $满足$ \eta_k\in[\eta_{\min}, \eta_{\max}] $. 选取$ Q_0:=1. $ 令$ h:=(1, 0, 0, 0)\in\mathbb{R}^{1+2n+m} $. 令$ k:=0. $

步骤1  如果$ \|H_\theta(z^k)\|=0 $, 则算法停止迭代.

步骤2  解下面方程得$ \Delta z^k:=(\Delta \mu_k, \Delta x^k, \Delta s^k, \Delta y^k)\in\mathbb{R}\times\mathbb{R}^n \times\mathbb{R}^n\times \mathbb{R}^m $,

$ \begin{equation} H_\theta(z^k)+H'_\theta(z^k)\Delta z^k=\beta_k h. \end{equation} $

(3.2)

步骤3  令$ \alpha_k:=\delta^{l_k} $, 其中$ l_k $是满足下式的最小非负整数$ l, $

$ \begin{equation} \|H_\theta(z^k+\delta^l\Delta z^k)\|\leq {C}_k-\lambda_1\|\delta^l\Delta z^k\|^2-\lambda_2\|\delta^lH_\theta(z^k)\|^2. \end{equation} $

(3.3)

步骤4  令$ z^{k+1}:=z^k+\alpha_k\Delta z^k $. 令

$ \begin{equation} Q_{k+1}:=\eta_{k}Q_{k}+1, \; C_{k+1}:=\frac{\eta_{k} Q_{k} C_{k}+ \|H_\theta(z^{k+1})\|}{Q_{k+1}}. \end{equation} $

(3.4)

$ \begin{equation} \beta_{k+1}:=\gamma\min\{1, \|H_\theta(z^{k+1})\|^2, \beta_k\}. \end{equation} $

(3.5)

令$ k:=k+1. $ 转步骤1.

注: 与文献[9-12]中的光滑牛顿法不同, 算法3.1在步骤3采用一个非单调无导数线搜索技术去产生步长$ \alpha_k $, 该技术是基于著名的Zhang-Hager^[15]非单调线搜索技术设计的.

定理3.1  如果加权线性互补问题是单调的, 那么算法3.1有好的定义.

证  假设对于某个$ k $有$ z^k=(\mu_k, x^k, s^k, y^k)\in\mathbb{R}_{++}\times\mathbb{R}^{n}\times\mathbb{R}^{n}\times\mathbb{R}^{m} $和$ \|H_\theta(z^{k})\|\leq{C}_k $. 由引理3.1(ⅳ) 可知$ H'_\theta(z^k) $可逆, 故方程(3.2)是可解的. 这表明步骤2是可行的. 记$ f_\theta(z):=\|H_\theta(z)\|^2, $ 则$ f_\theta(z) $在任意点$ z\in\mathbb{R}_{++}\times\mathbb{R}^{n}\times\mathbb{R}^{n}\times\mathbb{R}^{m} $处连续可微, 并且$ f_\theta'(z)=2H_\theta(z)^{T}H'_\theta(z) $. 因为

$ \mu_k<\|H_\theta(z^k)\|=\sqrt{f_\theta(z^k)}, \; \beta_{k}\le\gamma\min\{1, \|H_\theta(z^{k})\|^2\}\le \gamma\|H_\theta(z^k)\|=\gamma\sqrt{f_\theta(z^k)}, $

故$ \mu_k\beta_{k}\le\gamma f_\theta(z^k) $, 再结合(3.2)可得

$ \begin{equation} \begin{split} f'(z^k)\Delta z^k&=2H_\theta(z^k)^{T}H'_\theta(z^k)\Delta z^k\\ &=-2f_\theta(z^k)+2\mu_k \beta_k\\ &\leq-2f_\theta(z^k)+ 2\gamma f_\theta(z^k)\\ &=-2(1-\gamma)f_\theta(z^k)\\ &<0, \end{split} \end{equation} $

(3.6)

这里最后一个不等式成立是因为$ f_\theta(z^k)\ge\mu_k^2>0 $和$ \gamma\in(0, 1). $ 现在我们证明步骤3是可行的. 采用反证法, 假设对所有的非负整数$ l $, 都有$ \|H_\theta(z^k+\delta^l\Delta z^k)\|>{C}_k-\lambda_1\|\delta^l\Delta z^k\|^2-\lambda_2\|\delta^lH_\theta(z^k)\|^2. $ 因为$ {C}_k\geq\|H_\theta(z^{k})\|, $ 故可知

$ \begin{equation} \frac{\|H_\theta(z^k+\delta^l\Delta z^k)\|-\|H_\theta(z^{k})\|}{\delta^{l}}>-\lambda_1\delta^l\|\Delta z^k\|^2-\lambda_2\delta^l\|H_\theta(z^k)\|^2. \end{equation} $

(3.7)

在不等式(3.7)两端同时乘以$ \|H_\theta(z^k+\delta^l\Delta z^k)\|+\|H_\theta(z^{k})\| $可得

$ \begin{equation} \frac{f_\theta(z^k+\delta^l\Delta z^k)-f_\theta(z^{k})}{\delta^{l}}>[-\lambda_1\delta^l\|\Delta z^k\|^2-\lambda_2\delta^l\|H_\theta(z^k)\|^2][\|H_\theta(z^k+\delta^l\Delta z^k)\|+\|H_\theta(z^{k})\|]. \end{equation} $

(3.8)

因为$ f_\theta(z) $在$ z^k $点连续可微, 故在(3.8) 两边令$ l\rightarrow \infty $, 则可得$ f'(z^k)\Delta z^k\geq0 $, 这与(3.6)矛盾, 故至少存在一个非负整数$ l $使得(3.3) 成立, 即步骤3是可行的. 因此, 我们可以在步骤4得到新的迭代点$ z^{k+1}=z^k+\alpha_{k}\Delta z^k $.

下面我们证明$ z^{k+1}\in \mathbb{R}_{++}\times \mathbb{R}^n\times\mathbb{R}^n\times\mathbb{R}^m $并且$ \|H_\theta(z^{k+1})\|\leq{C}_{k+1} $. 事实上, 由(3.2)的第一个方程, 我们有$ \Delta\mu_k=-\mu_k+\beta_k $, 再结合$ \alpha_k\in(0, 1] $和$ \beta_k>0 $可得

$ \begin{equation} \mu_{k+1}=\mu_k+\alpha_k\Delta\mu_k=(1-\alpha_k)\mu_k+\alpha_k\beta_k>0. \end{equation} $

(3.9)

这表明$ z^{k+1}=(\mu_{k+1}, x^{k+1}, s^{k+1}, y^{k+1})\in \mathbb{R}_{++}\times\mathbb{R}^n\times \mathbb{R}^n\times \mathbb{R}^m $. 此外, 由步骤3和步骤4, 我们有$ \|H_\theta(z^{k+1})\|\leq {C}_{k} $, 结合(3.4)可得

$ {C}_{k+1}\geq \frac{\eta_{k} Q_{k} \|H_\theta(z^{k+1})\| + \|H_\theta(z^{k+1})\| }{Q_{k+1}}= \|H_\theta(z^{k+1})\|. $

因此, 我们可以得出结论: 如果$ z^k\in\mathbb{R}_{++}\times\mathbb{R}^n\times\mathbb{R}^n\times\mathbb{R}^m $并且$ \|H_\theta(z^{k})\|\leq{C}_k $对于某个$ k $成立, 那么$ z^{k+1} $可以由算法3.1生成, 其满足$ z^{k+1}\in \mathbb{R}_{++}\times \mathbb{R}^n\times\mathbb{R}^n\times\mathbb{R}^m $并且$ \|H_\theta(z^{k+1})\|\leq{C}_{k+1} $. 因为$ z^{0}\in\mathbb{R}_{++}\times\mathbb{R}^n\times\mathbb{R}^n\times\mathbb{R}^m $并且$ \|H_\theta(z^0)\|={C}_0 $, 所以由数学归纳法可知定理成立. 证毕.

本节给出算法3.1的全局收敛性. 为此, 我们需要以下引理.

引理4.1  设$ \{z^k=(\mu_k, x^k, s^k, y^k)\} $是由算法3.1生成的迭代点列, 则对所有的$ k\geq0 $有

(ⅰ) $ z^k\in\mathbb{R}_{++}\times\mathbb{R}^{n}\times\mathbb{R}^{n}\times\mathbb{R}^{m} $; (ⅱ) $ \|H_\theta(z^{k})\|\leq{C}_k $; (ⅲ)$ \mu_k\geq\beta_k $.

证  由定理3.1的证明过程可知(ⅰ)和(ⅱ)成立. 由步骤0可知$ \mu_0\geq\gamma\geq\beta_0. $ 假设对某个$ k $有$ \mu_k\geq\beta_k $, 则由(3.9)可知$ \mu_{k+1}\geq(1-\alpha_k)\beta_k+\alpha_k\beta_k=\beta_k\geq\beta_{k+1}, $ 其中最后一个不等式成立是因为$ \{\beta_k\} $是单调递减的. 因此, 由数学归纳法可知(ⅲ)成立.

引理4.2  设$ \{z^k\} $是由算法3.1生成的迭代点列, 则存在常数$ {C}^*\geq0 $使得

$ \lim\limits_{k\rightarrow \infty}\|H_\theta(z^k)\|= \lim\limits_{k\rightarrow \infty}{C}_k={C}^*. $

证  定理的具体证明可参见文献[7]中的引理7.

引理4.3  设$ \{z^k\} $是由算法3.1生成的迭代点列, 则

$ \lim\limits_{k\rightarrow \infty}\|\alpha_k\Delta z^k\|=0, \; \; \lim\limits_{k\rightarrow \infty}\|\alpha_kH_\theta(z^k)\|=0. $

证  对所有的$ k\geq0, $ 由步骤3可知

$ \begin{equation*} \label{qq} \lambda_1\|\alpha_k\Delta z^k\|^2+\lambda_2\|\alpha_kH_\theta(z^k)\|^2\leq {C}_k -\|H_\theta(z^{k+1})\|, \end{equation*} $

进而由引理4.2可知结论成立.

由引理4.3, 我们可以直接得到如下结论.

定理4.1  设$ \{z^k\} $是由算法3.1生成的迭代点列. 如果存在常数$ c>0 $使得对所有的$ k\ge0 $满足$ \alpha_k>c $, 则有$ \lim\limits_{k\rightarrow \infty}\|H_\theta(z^k)\|=0. $

定理4.2  设$ \{z^k=(\mu_k, x^k, s^k, y^k)\} $是由算法3.1生成的迭代点列, 则$ \{z^k\} $的任意聚点都是$ H_\theta(z)=0 $的解.

证  设$ z^*:=(\mu^*, x^*, s^*, y^*) $为$ \{z^k=(\mu_k, x^k, s^k, y^k)\} $的任意聚点, 则存在一个收敛子列$ \{z^k\}_{k\in K} $使得$ \lim\limits_{k\in K, \; k\rightarrow \infty}z^k=z^* $, 其中$ K\subset\{0, 1, ...\} $. 因为$ \{\beta_k\} $单调递减, 故存在$ \beta^*\geq0 $使得$ \lim\limits_{k\rightarrow \infty}\beta_k=\beta^* $. 此外, 由引理4.2可知存在$ {C}^*\geq0 $使得

$ \begin{equation} \lim\limits_{k\rightarrow \infty}\|H_\theta(z^k)\|= \lim\limits_{k\rightarrow \infty}{C}_k={C}^*. \end{equation} $

(4.1)

由$ H $的连续性可知

$ \begin{equation} \lim\limits_{k\in K, \; k\rightarrow \infty}\|H_\theta(z^k)\|=\|H_\theta(z^*)\|={C}^*. \end{equation} $

(4.2)

我们现在假设$ C^*> 0 $, 然后推出一个矛盾. 因为$ C^*> 0 $, 故由(3.5)和(4.1)可知$ \beta^*>0, $ 进而由引理4.1(ⅲ)可得

$ \mu^*=\lim\limits_{k\in K, \; k\rightarrow \infty}\mu_k\geq\lim\limits_{k\in K, \; k\rightarrow \infty}\beta_k=\beta^*>0. $

这表明$ z^*\in\mathbb{R}_{++}\times\mathbb{R}^n\times \mathbb{R}^n\times \mathbb{R}^m $, 从而可知$ H_\theta(z) $在$ z^* $点可微并且$ H'_\theta(z^*) $是非奇异的. 因此, 存在一个常数$ M>0 $使得$ \|H'_\theta(z^k)^{-1}\|\leq M $对所有充分大的$ k\in K $都成立. 由(3.2)可知对所有充分大的$ k\in K $,

$ \|\Delta z^k\|\leq\|H'_\theta(z^k)^{-1}\|(\|H_\theta(z^k)\|+\beta_k)\leq M(\|H_\theta(z^k)\|+\gamma). $

由(4.1)可知$ \{\|H_\theta(z^k)\|\} $有界. 因此, $ \{\|\Delta z^k\|\}_{k\in K} $有界, 从而可知$ \{\|\Delta z^k\|\}_{k\in K} $有一个收敛子列. 我们不妨假设$ \lim\limits_{k\in K_1, \; k\rightarrow \infty}\Delta z^k=\Delta z^* $, 其中$ K_1\subset K $. 在等式(3.2)的两端我们令$ k(\in K_1)\rightarrow \infty $, 则有

$ \begin{equation} H_\theta(z^*)+H'_\theta(z^*)\Delta z^*=\beta^* h. \end{equation} $

(4.3)

由引理4.3可知$ \lim\limits_{k\in K_1, k\rightarrow \infty}\|\alpha_kH_\theta(z^k)\|=0 $. 因为$ \lim\limits_{k\in K, \; k\rightarrow \infty}\|H_\theta(z^k)\|=C^*>0 $, 故有$ \lim\limits_{k\in K, \; k\rightarrow \infty } \alpha_{k}=0. $ 由步骤3和引理4.1(ⅱ), 对所有的$ k\in K_1 $, 我们有

$ \begin{eqnarray*} \|H_\theta(z^k+\delta^{-1}\alpha_{k}\Delta z^k)\|&>& {C}_k-\lambda_1\|\delta^{-1}\alpha_{k}\Delta z^k\|^2-\lambda_2\|\delta^{-1}\alpha_{k}H_\theta(z^k)\|^2\\ &\geq&\|H_\theta(z^k)\|-\lambda_1\|\delta^{-1}\alpha_{k}\Delta z^k\|^2-\lambda_2\|\delta^{-1}\alpha_{k}H_\theta(z^k)\|^2. \end{eqnarray*} $

因此

$ \frac{\|H_\theta(z^k+\delta^{-1}\alpha_{k}\Delta z^k)\|-\|H_\theta(z^k)\|}{\delta^{-1}\alpha_{k}}>-\lambda_1\delta^{-1}\alpha_{k}\|\Delta z^k\|^2-\lambda_2\delta^{-1}\alpha_{k}\|H_\theta(z^k)\|^2, $

即

$ \begin{array}{l} \; \; \; \; \; \; \frac{\|H_\theta(z^k+\delta^{-1}\alpha_{k}\Delta z^k)\|^2-\|H_\theta(z^k)\|^2}{\delta^{-1}\alpha_{k}}>\\ [-\lambda_1\delta^{-1}\alpha_{k}\|\Delta z^k\|^2-\lambda_2\delta^{-1}\alpha_{k}\|H_\theta(z^k)\|^2][\|H_\theta(z^k+\delta^{-1}\alpha_{k}\Delta z^k)\|+\|H_\theta(z^k)\|]. \end{array} $

(4.4)

因为$ \|H_\theta(z)\|^2 $在$ z^*\in\mathbb{R}_{++}\times\mathbb{R}^n\times \mathbb{R}^n\times \mathbb{R}^m $点处连续可微, 故在不等式(4.4)两端令$ k(\in K_1)\rightarrow \infty $, 我们有

$ \begin{equation} H_\theta(z^*)^TH'_\theta(z^*)\Delta z^*\geq0. \end{equation} $

(4.5)

另一方面, 因为$ \mu^*\leq\|H_\theta(z^*)\|={C}^* $, 故由(4.3)和$ \beta^*\le\gamma\min\{1, (C^*)^2\}\le \gamma{C}^* $可得

$ \begin{equation} H_\theta(z^*)^TH'_\theta(z^*)\Delta z^*=-\|H_\theta(z^*)\|^2+\mu^*\beta^*\leq-(1-\gamma)({C}^*)^2. \end{equation} $

(4.6)

由(4.5)和(4.6)可知$ (1-\gamma)({C}^*)^2\leq0 $. 因为$ \gamma\in(0, 1) $, 我们有$ {C}^*=0 $, 这与假设$ {C}^*>0 $矛盾. 因此, 我们有$ {C}^*=0 $, 进而由(4.2)可知$ H_\theta(z^*)=0, $ 即定理成立. 证毕.

由定理4.2的证明过程, 我们可以直接得到如下结论.

定理4.3  如果算法3.1生成的迭代点列$ \{z^k\} $有一个聚点, 那么$ \lim\limits_{k\rightarrow \infty}\|H_\theta(z^k)\|=0. $

定理4.4  如果算法3.1生成的迭代点列$ \{z^k\} $有一个孤立的聚点$ z^* $, 那么$ \lim\limits_{k\rightarrow \infty}z^k=z^* $.

证  由引理4.3可知$ \lim\limits_{k\rightarrow \infty}\|z^{k+1}-z^k\|=\lim\limits_{k\rightarrow \infty}\|\alpha_k\Delta z^k\|=0. $ 因此, 由文献[16]中的推论8.3.10可知定理成立. 证毕.

定理4.5  如果水平集$ L(C):=\{z\in\mathbb{R}^{1+2n+m}|\|H_\theta(z)\|\le C\} $对任意的$ C>0 $都有界, 那么算法3.1生成的迭代点列$ \{z^k\} $至少有一个聚点.

证  对所有的$ k\geq0 $, 由步骤3和步骤4可得$ \|H_\theta(z^{k+1})\|\leq {C}_{k} $, 进而由(3.4)可知,

$ {C}_{k+1}=\frac{\eta_{k} Q_{k} C_{k}+ \|H_\theta(z^{k+1})\|}{Q_{k+1}}\leq \frac{\eta_{k} Q_{k} C_{k}+C_k}{Q_{k+1}}=C_k. $

因此, 由引理4.1(ⅱ)可得$ \|H_\theta(z^{k})\|\le C_k\le C_0=\|H_\theta(z^0)\| $. 这表明$ \{z^k\}\subset L(\|H_\theta(z^0)\|) $, 故$ \{z^k\} $有界, 从而至少有一个聚点. 证毕.

本节给出算法3.1的局部二次收敛性质. 利用函数$ H_\theta(z) $的强半光滑性质, 类似于文献[17]中定理8的证明, 我们可以得到如下结论.

引理5.1  设$ z^* $是由算法3.1生成的迭代点列$ \{z^k\} $的任意聚点. 如果所有的$ V\in \partial H_\theta(z^*) $是非奇异的, 那么对所有充分接近于$ z^* $的$ z^k $, 有

$ \begin{equation} \|z^k+\Delta z^k-z^*\|=O(\|z^k-z^*\|^2), \end{equation} $

(5.1)

$ \begin{equation} \|H_\theta(z^k+\Delta z^k)\|=O(\|H_\theta(z^k)\|^2). \end{equation} $

(5.2)

定理5.1  设$ z^* $是由算法3.1生成的迭代点列$ \{z^k\} $的任意聚点. 如果所有的$ V\in \partial H_\theta(z^*) $是非奇异的, 则$ \{z^k\} $收敛到$ z^* $并且

$ \|z^{k+1}-z^*\|=O(\|z^k-z^*\|^2), \; \; \|H_\theta(z^{k+1})\|=O(\|H_\theta(z^k)\|^2). $

证  因为所有的$ V\in \partial H_\theta(z^*) $是非奇异的, 故由文献[13]中的推论3.1可知对所有充分接近于$ z^* $的$ z^k $, 有

$ \begin{equation} \|H'_\theta(z^k)^{-1}\|=O(1). \end{equation} $

(5.3)

由(3.5)可知对所有充分接近于$ z^* $的$ z^k $, 有

$ \begin{equation} \beta_k\leq\gamma\min\{1, \|H_\theta(z^k)\|^2\}\leq\gamma \|H_\theta(z^k)\|. \end{equation} $

(5.4)

由(3.2), (5.3)和(5.4)可知对所有充分接近于$ z^* $的$ z^k $, 有

$ \|\Delta z^k\|\leq\|H'_\theta(z^k)^{-1}\|(\|H_\theta(z^k)\|+\beta_k)=O(\|H_\theta(z^k)\|), $

进而可知

$ \begin{equation} \|\Delta z^k\|^{2}=O(\|H_\theta(z^k)\|^{2}). \end{equation} $

(5.5)

因此, 由(5.2)和(5.5)可知

$ \lim\limits_{k\rightarrow \infty}\frac{\|H_\theta(z^k+\Delta z^k)\|+\lambda_1\|\Delta z^k\|^2+\lambda_2\|H_\theta(z^k)\|^2}{\|H_\theta(z^k)\|}=0. $

因此, 对所有充分接近于$ z^* $的$ z^k $, 有

$ \|H_\theta(z^k+\Delta z^k)\|+\lambda_1\|\Delta z^k\|^2+\lambda_2\|H_\theta(z^k)\|^2\leq \|H_\theta(z^k)\|\le C_k. $

这说明对所有充分接近于$ z^* $的$ z^k $, 有$ \alpha_k=1 $, 即$ z^{k+1}=z^k+\Delta z^k $. 再结合(5.1)和(5.2)可知定理成立. 证毕.

本节我们对算法3.1进行数值实验. 参数取值为$ \mu_0=10^{-2}, \; \delta=0.5, \; \sigma=0.2, \; \gamma=10^{-3}, \; \lambda_1=10^{-3}, \; \lambda_2=10^{-3}, \; \eta_k=0.85. $ Potra教授在文献[1]中证明了二次规划和加权中心问题(Quadratic Programming and Weighted Centering Problem)的最优性条件为如下单调加权线性互补问题:

$ \begin{equation} x\geq0, \; s\geq0, \; Px+Qs+Ry=a, \; x s=w, \end{equation} $

(6.1)

其中矩阵$ P, Q, R $和向量$ a $定义如下:

$ \begin{equation*} P=\left( \begin{array}{cc} A\\ M \end{array} \right), \; Q=\left( \begin{array}{cc} 0\\ -I \end{array} \right), \; R=\left( \begin{array}{cc} 0\\ -A^{T} \end{array} \right), \; a=\left( \begin{array}{cc} b\\ -f \end{array} \right), \end{equation*} $

这里$ A\in\mathbb{R}^{m\times n} $是一个$ m<n $的满秩矩阵, $ I $为$ n\times n $单位矩阵, $ b, f\in \mathbb{R}^n $. 我们应用算法3.1去求解这个问题. 在实验中, 我们产生一个行满秩的矩阵$ A\in\mathbb{R}^{m\times n} $, 选择$ M=BB^{T}/\|BB^{T}\| $, 其中$ B={\bf{rand}}(n, n) $, 然后令$ \hat{x}={\bf{rand}}(n, 1) $, $ f={\bf{rand}}(n, 1) $, 再定义$ b:=A\hat x $, $ \hat s:=M\hat x+f $和$ w:=\hat x\hat s $.

首先, 我们生成一个$ n=1000, m=500 $的测试问题, 然后应用算法3.1去求解此问题. 我们使用$ x^{0}=s^0=(1, 0, ..., 0)^T, y^{0}=(0, ..., 0)^T $作为初始点进行测试. 表 1给出了迭代过程中$ \|H_\theta(z^k)\| $的值. 从表 1可以看出, 算法3.1的收敛速度至少是超线性.

接下来, 对于每个测试问题, 我们生成10个算例, 然后应用算法3.1去求解这些算例. 对于每个问题, 我们仍然使用$ x^{0}=s^0=(1, 0, ..., 0)^T, y^{0}=(0, ..., 0)^T $作为初始点进行测试. 在实验中, 我们采用$ \|H_\theta(z^{k})\|\leq10^{-12} $作为终止准则. 数值实验的结果列于表 2, 其中AIT和ACPU分别表示算法3.1求解问题所需的迭代次数和CPU时间的平均值, AHK表示算法终止时$ \|H_\theta(z^k)\| $的平均值. 从表 2可以看出, 算法3.1对于求解加权线性互补问题是非常有效的, 它只需很少的迭代次数和CPU时间就可以找到满足终止条件的解.

最后, 我们将算法3.1与文献[18]中的非单调光滑牛顿法进行比较. 需要说明的是, 文献[18]中的非单调光滑牛顿法也是基于Zhang-Hager^[15]非单调线搜索技术设计的, 该算法在步骤3采用如下形式的线搜索准则：

令$ \alpha_k:=\delta^{l_k} $, 其中$ l_k $是满足下式的最小非负整数$ l, $

$ \begin{equation} \|H_\theta(z^k+\delta^l\Delta z^k)\|\leq [1-2\sigma(1-\tau\beta)\delta^l]C_k, \end{equation} $

(6.2)

这里$ \sigma\in(0, 1/2) $, $ 0<\tau\beta<1 $. 然后令$ C_{k+1} $按照(3.4)迭代更新. 注意到, 除了文献[18], 文献[19, 20]也研究了基于(6.2)这种线性搜索准则的非单调光滑牛顿法.

在实验中, 对于每个测试问题, 我们仍然生成10个算例, 然后分别应用算法3.1和文献[18]中的非单调光滑牛顿法去求解这些算例. 对于每个问题, 我们选取初始点$ x^{0}={\bf rand}(n, 1), s^0={\bf rand}(n, 1), y^{0}={\bf rand}(m, 1) $. 我们采用$ \|H_\theta(z^{k})\|\leq10^{-6} $作为终止准则. 数值实验结果列于表 3, 其中算法3.1和算法^[18]分别表示本文给出的算法3.1和文献[18]中的非单调光滑牛顿法. 由表 3可以看出, 当求解相同规模的测试问题时, 我们的算法比文献[18]中的非单调光滑牛顿法需要更少的迭代次数和CPU时间. 这表明, 相比于文献[18-20]所采用的非单调线搜索技术(6.2), 本文所给出的非单调无导数线搜索技术(3.3)更有效. 此外, 由表 1, 表 2和表 3中的数据, 我们发现随着参数$ \theta $的增大, 算法求解相同规模的问题所需的迭代次数和CPU时间都减少. 当参数$ \theta=1 $时, 算法的计算效果最好. 这是一个新的发现, 值得进一步研究.