考虑对称锥互补问题(SCCP),寻找$x,y \in J$,使得

$$\begin{equation} x \in K,y = F(x) \in K,〈 {x,y} 〉 = 0, \end{equation}$$

(1)

其中$J$是赋有内积 的有限维实向量空间,$K$是$J$上的对称锥, $F(x)$是$J \to J$的一个连续映射,问题(1)包含了半定锥互补问题(SDCP)、 二阶锥互补问题(SOCCP)和线性和非线性互补问题(LCP/NCP). 对称锥互补问题具有非常广的理论和实际应用,近年来逐渐引起人们的重视, 对称锥互补问题的算法成为优化领域研究的热点之一,学者们对如何求解对称 锥互补问题作了大量的工作,把线性互补问题(LCP)和非线性互补问题(NCP), 二阶锥互补问题和半定锥互补问题(SDCP)的算法,推广到对称锥互补问题, 光滑牛顿法已经成功地推广到对称锥互补问题^{[1, 2, 3, 4, 5, 6]}. 然而, 光滑牛顿法每次迭代都要求解一次线性方程组,对于规模较大的问题效率不高, 非精确光滑牛顿法是解决这一问题的一种好的选择^{[7, 8, 9]}.

本文考虑基于一个光滑函数,提出一个求解SCCP(1)的非精确光滑牛顿法, 数值实验表明,当维数变大非精确光滑牛顿法的效果好于光滑牛顿法.

简要介绍一下Euclidean-Jordan代数知识,详细的内容请参考文献^[10].

欧几里德若当代数$(J,\circ ,〈 \cdot ,\cdot 〉 )$是指: $(J,\circ ,〈 \cdot ,\cdot 〉 )$是一个定义在实数域上的有限维内积空间, $(J,\circ ,〈 \cdot ,\cdot 〉 )$是一个满足下述条件的双线性映射

(i) $x \circ y = y \circ x,x,y \in J$;

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

(iii) $〈 x \circ y,z 〉 = 〈 y,x \circ z〉 ,\forall x,y,z \in J$.

称$x \circ y$为元素$x$和$y$的若当积.假设$J$总存在一个元素$e$满足$\forall x \in J$, 有$x \circ e = e \circ x = x$,则将该元素称为单位元. 如果 $e \circ e = e \ne 0$, 称元素$e\in J$为幂等元.如果幂等元$e$和$e'$满足$e \circ e' = 0$,称$e$和$e'$是正交的. 如果非零幂等元$e$不能分解为两个非零幂等元之和,称幂等元$e$为基本幂等元. 定义$J$的秩$r: = \max \{ \deg (x):x \in J\}$,,其中$\deg (x)$为使得 $\{ e,x,\cdots ,{x^m}\}$为线性相关的最小正整数$m$.

如果${e_1},{e_2},\cdots ,{e_r}$相互正交且${e_1} + {e_2} + \cdots +{e_r} = e$,则幂等元集合$\{ {e_1},{e_2},\cdots ,{e_r}\}$ 称为幂等元正交完备系.如果幂等元正交完备系中的所有幂等元都是基本幂等元, 则称此基本幂等元正交完备系为欧几里德若当代数 的一个若当基底.

定理1 (谱分解类型I ^[10])设$J$是一个秩为$r$的欧几里得若当代数, 则对于每一个元素$X\in J$,必存在一个若当基底$\{ {c_1},{c_2},\cdots ,{c_r}\}$ 和一组实数${\lambda _1},{\lambda _2},\cdots ,{\lambda _r}$,使得

$$\begin{equation} x = {\lambda _1}{c_1} + \cdots + {\lambda _r}{c_r}. \end{equation}$$

(2)

式(2)称为元素$x$的一个谱分解,实数${\lambda _i} = {\lambda _i}(x) (i = 1,\cdots,r)$称为元素$x$的特征值,${c_i}(i = 1,\cdots ,r\}$ 称为元素$x$的相应于特征值${\lambda _i}$的特征向量.

平方集合$K: = \{ {x^2}:x \in J\}$称为对称锥,即$K$是一个自对偶的非空凸集. 对任意两元素$x,y \in K$,存在一个可逆的线性变换$\Gamma :J \to J$使得 ${L_x}\left( y \right) = x \circ y$和$\Gamma (x) \to y$.

定义 1 若当积是双线性的,对$\forall x \in J$, 存在线性映射${L_x} : J \to J$, 使得: 对$\forall y \in J$有 ${L_x}\left( y \right) = x \circ y$, 称该线性映射为Lyapunov变换,$\!\!\!{L_x}$的逆记为$L_x^{ - 1}$.

定义 2 设变换$F:J \to J$,任取$x,y \in J$有 $〈 {x - y,F(x) - F(y)} 〉 \ge 0$,则称$F$在$J$上单调.

定义 3 对于非光滑函数$g:{R^n} \to {R^m}$,含有参数$\mu$的函数${g_\mu }: {R^n} \to {R^m}$有下列性质

(1) 对于任意的 $\mu > 0$,${g_\mu }$是可微的;

(2) 对于任意的$x \in {R^n}$,$\mathop {\lim }\limits_{\mu \to 0} {g_\mu } \left( x \right) = g\left( x \right)$,则称函数${g_\mu }$是$g$ 的光滑函数.

文献^[13]中证明了最小值函数${\phi _{\min }}: J \times J \to J$ $${\phi _{\min }}: (x,y) = x + y - \sqrt {{{(x - y)}^2}}$$ 满足${\phi _{\min }}(x,y) = 0 \Leftrightarrow x \in K,y \in K,x \circ y = 0$, 而最小值函数是非光滑函数. 文献^{[2, 14]}中光滑化极小值函数得到如下的光滑函数

$$\begin{equation} \phi \left( {\mu ,x,y} \right):= \left( {\cos \mu + \sin \mu } \right)\left( {x + y} \right) - \sqrt {{{\left( {\cos \mu - \sin \mu } \right)}^2}{{\left( {x{\rm{ - }}y} \right)}^2} + 2{\mu ^2}e} . \end{equation}$$

(3)

引理1^{[2, 14]} 设$\phi : {R_{ + + }} \times J \times J \to J$ 定义如式(3),则

(1) $x \in K,y \in K,x \circ y = 0 \Leftrightarrow x \in K,y \in K, 〈 {x,y} 〉 = 0$;

(2) $\phi {\rm{(0,}}x,y{\rm{) = }}{\phi _{\min }}{\rm{(}}x,y{\rm{) = 0}} \Leftrightarrow x \in K,y \in K,x \circ y = 0$.

定理2 设$\phi : {R_{ ++ }} \times J \times J \to J$定义如式(1)则

(1) $\phi$处处全局Lipschitz连续,强半光滑,并且$\phi$在任意$z = \left( {\mu ,x,y} \right) \in {R_{ ++ }} \times J \times J$ 处连续可微,且其雅克比矩阵为

$$\begin{equation} \nabla \phi \left( {u,x,y} \right) = \left( \begin{array}{c} \phi _\mu ' \\ \phi _x' \\ \phi _y' \\ \end{array} \right) = \left( \begin{array}{c} \left( {\cos \mu - \sin \mu } \right)\left( {x + y} \right) + L_w^{ - 1}\left[{\cos 2\mu {{\left( {x - y} \right)}^2} - 2\mu e} \right] \\ \left( {\cos \mu + \sin \mu } \right)I - {\left( {\cos \mu - \sin \mu } \right)^2}L_w^{ - 1}{L_{\left( {x - y} \right)}} \\ \left( {\cos \mu + \sin \mu } \right)I + {\left( {\cos \mu - \sin \mu } \right)^2}L_w^{ - 1}{L_{\left( {x - y} \right)}} \\ \end{array} \right), \end{equation}$$

(4)

其中

$$\begin{equation} w:= w\left( {\mu ,x,y} \right) = \sqrt {{{\left( {\cos \mu - \sin \mu } \right)}^{\rm{2}}}{{\left( {x{\rm{ - }}y} \right)}^2}{\rm{ + 2}}{\mu ^2}e}. \end{equation}$$

(5)

(2) 对于任意$\left( {x,y} \right) \in J \times J$, 有$\mathop {\lim }\limits_{\mu \to 0} \phi \left( {\mu ,x,y} \right) = {\phi _{\min }}\left( {x,y} \right)$成立,因此,${\phi _{\min }} \left( {x,y} \right)$ 是$\phi \left( {\mu ,x,y} \right)$ 的光滑逼近函数.

证 (1) 根据文献[11,定理3.2]的推论,可知$\phi$处处全局Lipschitz连续,强半光滑, 且在任意$z = \left( {\mu ,x,y} \right) \in {R_{ ++ }} \times J \times J$处连续可微.下证式(4)成立,对于任意$z = \left( {\mu ,x,y} \right) \in {R_{ ++ }} \times J \times J$, 通过式(5)有 $w \in {\mathop{\rm int}} K$,因此${L_w}$可逆,由$w$的定义可以得到

$$\begin{equation} {w^2} = {\left( {\cos \mu - \sin \mu } \right)^2}{\left( {x - y} \right)^2} + 2{\mu ^2}e, \end{equation}$$

(6)

对式(6)两边同时求导,通过求微分的链式法则得出

$$\begin{equation} \nabla w\left( {\mu ,x,y} \right) = \left( \begin{array}{c} - L_w^{ - 1}\left[{\cos 2\mu {{\left( {x - y} \right)}^2} - 2\mu e} \right] \\ {\left( {\cos \mu - \sin \mu } \right)^2}L_w^{ - 1}{L_{\left( {x - y} \right)}} \\ - \left( {\cos \mu - \sin \mu } \right)L_w^{ - 1}{L_{\left( {x - y} \right)}} \\ \end{array} \right), \end{equation}$$

(7)

因此得到$\phi$的雅克比矩阵.

(2) 由定理1,设$x + y = \sum\limits_{i = 1}^r {{a_i}{u_i}}$和${\left( {x - y} \right)^2} = \sum\limits_{i = 1}^r {{\beta _i}{v_i}}$因此得到$\psi \left( {{\rm{0,}}x,y} \right) = \sum\limits_{i = 1}^r {{a_i}{u_i}} - \sum\limits_{i = 1}^r {\sqrt {{\beta _i}} {v_i}}$ 所以 $$\begin{eqnarray*} \phi \left( {\mu ,x,y} \right) &=& \sum\limits_{i = 1}^r {\left( {\left( {\cos \mu + \sin \mu } \right){\alpha _i}} \right){u_i}} - \sum\limits_{i = 1}^r {\sqrt {\left( {{\beta _i}{{\left( {\cos \mu - \sin \mu } \right)}^2} + 2{\mu ^2}} \right)} } {v_i} \\ &= & \sum\limits_{i = 1}^r {{a_i}\left( \mu \right){u_i}} - \sum\limits_{i = 1}^r {\sqrt {{\beta _i}\left( \mu \right)} {v_i}} . \end{eqnarray*}$$ 由$\mathop {\lim }\limits_{\mu \to 0} {\alpha _i}\left( \mu \right) = {\alpha _i}$和$\mathop {\lim }\limits_{\mu \to 0} {\beta _i}\left( \mu \right) = {\beta _i}$得到 $\mathop {\lim }\limits_{\mu \to 0} \phi \left( {\mu ,x,y} \right) = \psi \left( {{\rm{0,}}x,y} \right)$成立,因此, $\psi \left( {{\rm{0,}}x,y} \right)$是$\phi \left( {\mu ,x,y} \right)$的光滑逼近函数.

基于光滑函数(3),给出求解对称锥互补问题的非精确光滑牛顿法. 记$z = \left( {\mu ,x,y} \right) \in {R_{ ++ }} \times J \times J$,将对称锥互补问题的非光滑等价方程组光滑为如下光滑方程组

$$\begin{equation} H\left( z \right):= \left( \begin{array}{c} \mu \\ F\left( x \right) - y \\ \phi \left( z \right) \end{array} \right) = 0. \end{equation}$$

(8)

由互补函数的定义知道对称锥互补问题(1)的解和方程$\left\| {H\left( z \right)} \right\| = 0$的解是一致的.

算法 3.1 (非精确光滑牛顿法)

初始步:任取${z^0} = \left( {{\mu ^0},{x^0},{y^0}} \right) \in {R_{ + + }} \times J \times J$,选取常数$\delta \in \left( {0,1} \right),\sigma \in \left( {0,1} \right)$选取常数$\gamma \in \left( {0,1} \right)$使得$\gamma {\mu ^0} ＜ 1$,另取序列 $\left\{ {{\eta _k}} \right\}$满足${\eta _k} \in \left[{0,\eta } \right]$, 这里$\eta \in \left[{0{\rm{,1 - }}\gamma {\mu ^0}} \right]$为一个常数, $k: = 0$.

步骤1\quad 若$\left\| {H\left( {{z^k}} \right)} \right\| = 0$,则终止.

步骤2\quad 由下列式子计算$\Delta {z^k} = \left( {\Delta {\mu ^k},\Delta {x^k},\Delta {y^k}} \right)$

$$\begin{equation} H\left( {{z^k}} \right) + \nabla H\left( {{z^k}} \right)\Delta {z^k} = \left( \begin{array}{c} {\beta _k}{\mu _0} \\ 0 \\ {r^k} \end{array} \right), \end{equation}$$

(9)

这里${\beta _k} = \beta \left( {{z^k}} \right) : = \gamma \left\| {H\left( {{z^k}} \right)} \right\|\min \left\{ {1,\left\| {H\left( {{z^k}} \right)} \right\|} \right\}$,${r^k} \in {R^n}$满足$\left\| {{r^k}} \right\| \le {\eta _k}\left\| {H\left( {{z^k}} \right)} \right\|$.

步骤3\quad 让${\lambda _k}$为$1,\delta ,{\delta ^2},\cdots$ 中使得下式成立的最大值. $$\|H(z^k+\lambda_k\Delta {z^k})\|\leq [1-\sigma (1-\gamma \mu_0 -\eta_k)\lambda_k]\|H(z^k)\|.$$

步骤4\quad 置${z^{k + 1}}:= {z^k} + {\lambda _k}\Delta {z^k}$, $k=k+1$,返回步骤1.

注 当${r^k} = 0$时就成为精确的牛顿算法.

引理2^[3] 对于任意的$a \in K,b \in K,u \in {R^n},v \in {R^n}$, 如果$a \succ 0,b \succ 0,a \circ b \succ 0,〈 {u,v} 〉 \ge 0$且$a \circ u + b \circ v = 0$成立,则$u = v = 0$.

定理3 令$z = \left( {\mu ,x,y} \right) \in {R_{ ++ }} \times J \times J$,由式(8)定义,则得到如下结果

(1) $H$在任意$z = \left( {\mu ,x,y} \right) \in {R_{ ++ }} \times J \times J$处连续可微,其雅克比矩阵为

$$\begin{equation} \nabla {H_\tau }\left( z \right):= \left( {\begin{array}{*{20}{c}} 1 & 0 & 0 \\ 0 & {\nabla F\left( x \right)} & { - I} \\ {\left( {{{\phi '}_\mu }} \right)} & {\left( {{{\phi '}_x}} \right)} & {\left( {{{\phi '}_y}} \right)} \\ \end{array}} \right), \end{equation}$$

(10)

其中${\left( {{{\phi '}_\mu }} \right)}$,${\left( {{{\phi '}_x }} \right)}$, ${\left( {{{\phi '}_y }} \right)}$的表达式见式(4).

(2) 如果函数$F$连续可微且单调,则$\nabla H\left( z \right)$在$z = \left( {\mu ,x,y} \right) \in {R_{ ++ }} \times J \times J$处可逆.

证 由定理2可以得到结论(1),下面证明结论(2),任取$\mu>0$,令$\Delta z = \left( {\Delta \mu ,\Delta x,\Delta y} \right) \in R \times J \times J$.

假设

$$\begin{equation} \nabla H\left( z \right)\Delta z = 0. \end{equation}$$

(11)

则只需要证明$\Delta z = 0$,由式(10)(11)得到

$$\begin{equation} \begin{array}{l} \Delta \mu = 0 ,\\ \nabla F\left( x \right)\Delta x - \Delta y = 0,\\ \left( {\cos \mu + \sin \mu } \right)\left( {\Delta x + \Delta y} \right) - L_w^{ - 1}\left[{{{\left( {\cos \mu - \sin \mu } \right)}^2}\left( {x - y} \right)\left( {\Delta x - \Delta y} \right)} \right] + {{\phi '}_\mu }\Delta \mu = 0 . \end{array} \end{equation}$$

(12)

由函数$F$的单调性和式(12)中第2式可以得到

$$\begin{equation} 〈 {\Delta x,\Delta y} 〉 = 〈 {x,\nabla F\left( x \right)\Delta x} 〉 \ge 0. \end{equation}$$

(13)

由式(12)其余2式得到 $${L_w}\left[{\left( {\cos \mu + \sin \mu } \right) \left( {\Delta x + \Delta y} \right)} \right] - {\left( {\cos \mu - \sin \mu } \right)^2}\left( {x - y} \right)\left( {\Delta x - \Delta y} \right) = 0,$$ 即 $$\begin{array}{l} \left[{w - \left( {\cos \mu - \sin \mu } \right)\left( {x - y} \right)} \right]\left( {\Delta x\cos \mu + \Delta y\sin \mu } \right) \\ + \left[{w + \left( {\cos \mu - \sin \mu } \right)\left( {x - y} \right)} \right]\left( {\Delta x\sin \mu + \Delta y\cos \mu } \right) = 0 . \end{array}$$ 有

$$\begin{equation} \left( {\Delta x\sin \mu + \Delta y\cos \mu } \right) = - {\rm{L}}_{w + \left( {\cos \mu - \sin \mu } \right)\left( {x - y} \right)}^{ - 1}{{\rm{L}}_{w - \left( {\cos \mu - \sin \mu } \right)\left( {x - y} \right)}}\left( {\Delta x\cos \mu + \Delta y\sin \mu } \right) \end{equation}$$

(14)

和

$$\begin{eqnarray} && 〈 {{\rm{L}}_{w + \left( {\cos \mu - \sin \mu } \right)\left( {x - y} \right)}^{ - 1}{{\rm{L}}_{w - \left( {\cos \mu - \sin \mu } \right)\left( {x - y} \right)}}\left( {\Delta x\cos \mu + \Delta y\sin \mu } \right),\Delta x\cos \mu + \Delta y\sin \mu } 〉 \nonumber\\ & =& - 〈 {\Delta x\sin \mu + \Delta y\cos \mu , \Delta x\cos \mu + \Delta y\sin \mu } 〉 \nonumber\\ &=& - \sin \mu \cos \mu \left( {{{\left\| {\Delta x} \right\|}^2} + {{\left\| {\Delta y} \right\|}^2}} \right) - \left( {{{\sin }^{\rm{2}}}\mu + {{\cos }^{\rm{2}}}\mu } \right)〈 {\Delta x\Delta y} 〉 \le {\rm{0}} . \end{eqnarray}$$

(15)

通过$w - \left( {\cos \mu - \sin \mu } \right)\left( {x - y} \right) \in K$, $w + \left( {\cos \mu - \sin \mu } \right)\left( {x - y} \right) \in K$和

$$\begin{equation} \left[{w - \left( {\cos \mu - \sin \mu } \right)\left( {x - y} \right)} \right] \circ \left[{w + \left( {\cos \mu - \sin \mu } \right)\left( {x - y} \right)} \right] \ge 0, \end{equation}$$

(16)

由引理2可得到: $\Delta x\cos \mu + \Delta y\sin \mu = 0$, 由式(14)可以得到$\Delta x\sin \mu + \Delta y\cos \mu = 0$ 得到$〈 {\Delta x,\Delta y} 〉 = 0$, 所以$\nabla H\left( z \right)$可逆. 定理得证.

由式(9)可以得到${\mu _{k + 1}} = \left( {1 - {\lambda _k}} \right) {\mu _k} + {\lambda _k}{\beta _k}{\mu _0} > 0$,${\mu _0} > 0$, 在由定理3知$\nabla H\left( z \right)$可逆,因此步骤2是适定的. 对于任意$\alpha \in \left[{0,1} \right]$,令

$$\begin{equation} R\left( \alpha \right) = H\left( {{z^k} + \alpha \Delta {z^k}} \right) - H\left( {{z^k}} \right) - \alpha {\left( {\nabla H\left( {{z^k}} \right)} \right)^T}\Delta {z^k}, \end{equation}$$

(17)

$\left( {{\mu ^k} + \alpha \Delta {\mu ^k}} \right) > 0$. 由定理3知$H$在任意$z = \left( {\mu ,x,y} \right) \in {R_{ ++ }} \times J \times J$处连续可微,故 $$\left\| {R\left( \alpha \right)} \right\| = o\left( \alpha \right).$$ 又${\beta _k} = \beta \left( {{z^k}} \right):= \gamma \left\| {H\left( {{z^k}} \right)} \right\|\min \left\{ {1,\left\| {H\left( {{z^k}} \right)} \right\|} \right\},$ 得到当$\left\| {H\left( {{z^k}} \right)} \right\| > 1$时, ${\beta _k} = \gamma \left\| {H\left( {{z^k}} \right)} \right\|$ $\left\| {H\left( {{z^k}} \right)} \right\|\leq 1$时,${\beta _k} \leq \gamma \left\| {H\left( {{z^k}} \right)} \right\|$,故有

$$\begin{equation} {\beta _k} \le \gamma \left\| {H\left( {{z^k}} \right)} \right\|. \end{equation}$$

(18)

由式(9),(14),(18)知,对于$\alpha \in \left[{0,1} \right]$, ${\eta _k} \in \left[{0{\rm{,1 - }}\gamma {\mu ^0}} \right]$容易得出

$$\begin{eqnarray} \left\| {H\left( {{z^k} + \alpha \Delta {z^k}} \right)} \right\| &=& \left\| {H\left( {{z^k}} \right) + \alpha {{\left( {\nabla H\left( {{z^k}} \right)} \right)}^T}\Delta {z^k} + R\left( \alpha \right)} \right\| \nonumber\\ & =& \left\| {H\left( {{z^k}} \right) - \alpha H\left( {{z^k}} \right) + \alpha \left( {{\beta _k}{\mu ^0},0,{r^k}} \right) + R\left( \alpha \right)} \right\| \nonumber\\ & \le& \left( {1 - \alpha } \right)\left\| {H\left( {{z^k}} \right)} \right\| + \alpha \left( {{\beta _k}{\mu ^0}} \right) + \alpha \left\| {{r^k}} \right\| + \left\| {R\left( \alpha \right)} \right\| \nonumber\\ &\le& \left( {1 - \alpha } \right)\left\| {H\left( {{z^k}} \right)} \right\| + \alpha \left( {\gamma \left\| {{H_\tau }\left( {{z^k}} \right)} \right\|{\mu ^0}} \right) + \alpha {\eta _k}\left\| {H\left( {{z^k}} \right)} \right\| + o\left( \alpha \right) \nonumber\\ &\le& \left[{\left( {1 - \alpha } \right) + \alpha \gamma {\mu ^0} + \alpha {\eta _k}} \right]\left\| {H\left( {{z^k}} \right)} \right\| + o\left( \alpha \right) . \end{eqnarray}$$

(19)

因此由式(19)知,存在数$\bar \alpha \in \left( {0,1} \right]$, 对所有的$\alpha \in \left[{0,\bar \alpha } \right]$, ${\eta _k} \in \left[{0{\rm{,1 - }}\gamma {\mu ^0}} \right]$有 $$\left\| {H\left( {{z^k} + \alpha \Delta {z^k}} \right)} \right\| \le \left[{1 - \sigma \left( {1 - \gamma {\mu _0} - {\eta _k}} \right)\alpha } \right]\left\| {H\left( {{z^k}} \right)} \right\|.$$ 这样,步骤3也是适定的.

引理3 设函数$F$ 连续可微且单调,函数$H$如(10)式定义,则函数$H$在 $z = \left( {\mu ,x,y} \right) \in {R_{ ++ }} \times J \times J$处是强制的,即 $$\mathop {\lim }\limits_{\left\| {\left( {\mu ,x,y} \right)} \right\| \to \infty } \left\| {H\left( {\mu ,x,y} \right)} \right\|{\rm{ = + }}\infty .$$ 其证明可参见文献^[3].

算法3.1中,当迭代序列的的聚点满足一个非奇异假设时, 迭代序列全局线性收敛且局部二次收敛于该聚点. 由函数$F$单调连续可微, 则算法3.1生成的迭代点列满足

$$\begin{equation} \left\{ {{z^k}} \right\} \subset \Omega := \left\{ {z = \left( {\mu ,x,y} \right) \in {R_{ ++ }} \times {R^n} \times {R^n}{\rm{|}}\mu \ge \beta \left( z \right){\mu _0}} \right\}. \end{equation}$$

(20)

事实上${z^0} \in \Omega$ ,假设${z^k} \in \Omega$,则有 $${\mu _{k + 1}} = {\lambda _k}{\beta _k}{\mu _0} + \left( {1 - {\lambda _k}} \right){\mu _k} \ge \left( {1 - {\lambda _k}} \right){\beta _k}{\mu _0} + {\lambda _k}{\beta _k}{\mu _0} = {\beta _k}{\mu _0}.$$ 又由$\left\| {H\left( {{z^{k + 1}}} \right)} \right\| \le \left\| {H\left( {{z^k}} \right)} \right\|$,有${\beta _k} \ge {\beta _{k + 1}}$,所以有 ${\mu _{k + 1}} \ge {\beta _{k + 1}}{\mu ^0}$.

定理4 设函数$F$单调连续可微,且${z^ * } = \left( {{\mu ^ * },{x^ * },{y^ * }} \right)$是算法3.1所生成的迭代点列 $[\left\{ {{z^k}} \right\}$的一个聚点,则

(1) ${z^ * } = \left( {{\mu ^ * },{x^ * },{y^ * }} \right)$是 $H\left( {{z^k}} \right) = 0$的一个解;

(2) 如果所有的$V\in \partial H\left( {{z^ * }} \right)$可逆,且$\nabla F$ Lipchitz 连续,则$\left\{ {{z^k}} \right\}$局部二阶收敛于${z^ * }$, 即$\left\| {{z^{k + 1}} - {z^ * }} \right\| = O\left( {{{\left\| {{z^{k + 1}} - {z^ * }} \right\|}^2}} \right)$且${\mu _{k + 1}} = O\left( {\mu _k^2} \right)$.

证 (1) 由定理3.1和算法3.1知${z^k} \in \Omega$, $\left\| {H\left( {{z^{k + 1}}} \right)} \right\| \le \left\| {H\left( {{z^k}} \right)} \right\|$ ,因此$\left\| {H\left( {{z^k}} \right)} \right\|$和 ${\beta _k} = \beta \left( {{z^k}} \right)$是单调递减的, 由于$\left\| {{H_\tau }\left( {{z^k}} \right)} \right\| \ge 0$, $\beta \left( {{z^k}} \right) \ge 0$,则当$k \to \infty$时, 由连续性知$\left\| {H\left( {{z^k}} \right)} \right\| \to \left\| {H\left( {{z^ * }} \right)} \right\| \ge 0$,$\beta \left( {{z^k}} \right) \to \beta \left( {{z^ * }} \right) \ge 0$.

用反正法证明${H_\tau }\left( {{z^k}} \right) = 0$,假设$\left\| {H\left( {{z^ * }} \right)} \right\| > 0$,且${z^ * } = \left( {{\mu ^ * },{x^ * },{y^ * }} \right)$ 是算法3.1所生成的迭代点列$\left\{ {{z^k}} \right\}$的聚点,由定理3,存在${z^ * }$的一个闭邻域$N\left( {{z^ * }} \right)$,和一个正数$\bar \alpha \in \left( {0,1} \right]$,使得$z \in N\left( {{z^ * }} \right)$和$\alpha \in \left[{0,\bar \alpha } \right]$,有$\left\| {H\left( {z + \alpha \Delta {z^k}} \right)} \right\| \le \left[{1 - \sigma \left( {1 - \gamma {\mu _0} - {\eta _k}} \right)\alpha } \right]\left\| {H\left( z \right)} \right\|$成立. 对任意非负整数$l$满足${\delta ^l} \in \left( {0,\bar \alpha } \right]$, $\left\| {H\left( {{z^k} + {\delta ^l}\Delta {z^k}} \right)} \right\| \le \left[{1 - \sigma \left( {1 - \gamma {\mu _0} - {\eta _k}} \right){\delta ^l}} \right]\left\| {H\left( {{z^k}} \right)} \right\|$,对于充分大的$k$, 有${\delta ^l} \le {\lambda _k}$,从而对于充分大的$k$有

$$\begin{equation} \left\| {H\left( {{z^{k + 1}}} \right)} \right\| \le \left[{1 - \sigma \left( {1 - \gamma {\mu _0} - {\eta _k}} \right){\lambda _k}} \right]\left\| {H\left( {{z^k}} \right)} \right\| \le \left[{1 - \sigma \left( {1 - \gamma {\mu _0} - {\eta _k}} \right){\delta ^l}} \right]\left\| {H\left( {{z^k}} \right)} \right\|. \end{equation}$$

(21)

对(21)式两边取极限与$\left\| {H\left( {{z^ * }} \right)} \right\| > 0$矛盾, 因此结论(1)得证.

(2) 因为所有$V \in \partial H\left( {{z^ * }} \right)$可逆, ${z^ * } = \left( {{\mu ^ * },{x^ * },{y^ * }} \right)$是算法3.1所生成的迭代点列 $\left\{ {{z^k}} \right\}$的一个聚点,根据文献[12,定理3]可知, 对于充分靠近${z^ * } = \left( {{\mu ^ * },{x^ * },{y^ * }} \right)$的${z^k}$, 存在常数$C > 0$使得$\left\| {\nabla H{{\left( {{z^k}} \right)}^{{\rm{ - }}1}}} \right\| ＜ C$,对于任意$k \ge 0$ 成立. 由定理3 和$\nabla F$ Lipchitz 连续知${H_\tau }\left( \cdot \right)$在${z^ * } = \left( {{\mu ^ * }, {x^ * },{y^ * }} \right)$处是强半光滑的,因此,在 ${z^*}$ 的一个很小的邻域内存在${z^k}$,有

$$\begin{equation} \left\| {H\left( {{z^k}} \right) - H\left( {{z^ * }} \right)} \right\| = O\left( {\left\| {{z^k} - {z^ * }} \right\|} \right) \end{equation}$$

(22)

和

$$\begin{equation} \left\| {H\left( {{z^k}} \right) - H\left( {{z^ * }} \right) - \nabla H\left( {{z^k}} \right)\left( {{z^k} - {z^ * }} \right)} \right\| = O\left( {{{\left\| {{z^k} - {z^ * }} \right\|}^2}} \right). \end{equation}$$

(23)

得到

$$\begin{eqnarray} && \left\| {{z^k} + \Delta {z^k} - {z^ * }} \right\| \nonumber\\ &=& \left\| {{z^k} + \nabla H{{\left( {{z^k}} \right)}^{ - 1}}\left[{ - H\left( {{z^k}} \right) + {{\left( {{\beta _k}{\mu ^0},0,{r^k}} \right)}^T}} \right] - {z^ * }} \right\| \nonumber\\ & = &\left\| {\nabla H{{\left( {{z^k}} \right)}^{ - 1}}} \right\|\left( {\left\| {H\left( {{z^k}} \right) - H\left( {{z^ * }} \right) - \nabla H\left( {{z^k}} \right)\left( {{z^k} - {z^ * }} \right) + {{\left( {{\beta _k}{\mu ^0},0,{r^k}} \right)}^T}} \right\|} \right) \nonumber\\ & \le& \left\| {\nabla H{{\left( {{z^k}} \right)}^{ - 1}}} \right\|\left( {\left\| {H\left( {{z^k}} \right) - H\left( {{z^ * }} \right) - \nabla H\left( {{z^k}} \right)\left( {{z^k} - {z^ * }} \right)} \right\| + {\beta _k}{\mu ^0} + \left\| {{r^k}} \right\|} \right) \nonumber\\ & =& O\left( {{{\left\| {{z^k} - {z^ * }} \right\|}^2}} \right) . \end{eqnarray}$$

(24)

第一步等式根据式(9)而得,最后一步不等式由式(23)和${\beta _k}$ 的定义及${r^k} \in {R^n}$满足$\left\| {{r^k}} \right\| \le {\eta _k}\left\| {H\left( {{z^k}} \right)} \right\|$而得. 由式(22)(24)得到

$$\begin{equation} \left\| {H\left( {{z^k} + \Delta {z^k}} \right)} \right\| = O\left( {{{\left\| {H\left( {{z^k}} \right)} \right\|}^2}} \right). \end{equation}$$

(25)

由式(25)知当$k$ 充分大时${\lambda _k} = 1$,因此 在${z^ * }$的一个很小的邻域内存在${z^k}$,有${z^{k + 1}} = {z^k} + \Delta {z^k}$ 得到$\left\| {{z^{k + 1}} - {z^ * }} \right\| = O\left( {{{\left\| {{z^{k + 1}} - {z^ * }} \right\|}^2}} \right)$ 此外 $${\mu _{k + 1}} = {\mu _k} + \Delta {\mu _k} = {\beta _k}{\mu _0} = O\left( {{{\left\| {H\left( {{z^k}} \right)} \right\|}^2}} \right) = O\left( {{{\left\| {{z^{k + 1}} - {z^ * }} \right\|}^2}} \right) = O\left( {{{\left( {{\mu _k}} \right)}^2}} \right).$$ 所以则$\left\{ {{z^k}} \right\}$局部二阶收敛于${z^ * }$.

为了验证算法3.1的可行性和有效性,我们进行了对比实验,利用Matlab7.0编程, 在Intel(R),Pentium(R) Dual 1.73GHz,0.99GB的内存, Windows XP操作系统的hp笔记本上进行数学实验. 在测试中使用如下参数:

$\gamma {\rm{ = 0}}.{\rm{01}}\min \left\{ {1,1 / \left\| {H\left( {{z^0}} \right)} \right\|} \right\},\eta = {{\rm{2}}^{ - k - 1}},\sigma = 0.001,\delta = 0$, ${r^k}$取$\left[{0,1} \right)$的随机$n$维向量,停机标准是$\left\| {H\left( {{z^k}} \right)} \right\| \le {10^{ - 6}}$,CPU时间单位为秒. 初始点${z^0} = \left( {{\mu ^0},{x^0},{y^0}} \right)$ 随机选取.

当$r=0$其他的参数不变,算法变为精确光滑牛顿法(记为: PSN),${r^k}$取 $\left[{0,1} \right)$的随机$n$维向量,即不精确的光滑牛顿法 (记为:$\!\!\!$ISN),Iter,cpu分别表示500次数值实验平均的迭代次数和平均的cpu时间.

算例1 $F(x) = Mx + q$,其中 $M \in {R^n} \times {R^n}$为对称稀疏矩阵, 由库函数sprandsym(n,den,rc)随机生成,den表示矩阵的稀疏度, 条件数rc是由库函数unifrnd 随机生成的一个[0,1]中的数,它保证了矩阵$M$的半正定性. $q \in {R^n}$的每个元素从区间[-1,1]中Matlab的库函数rand随机生成.

算例2 $F(x) = {(0.02x_1^3,0.05x_2^3,0.09x_3^3, 0.01x_4^3,\cdots,0.01x_n^3)^T}$, 其中$K = {K^n}$且$F:{R^n} \to {R^n}$.由于 $$\nabla F(x) = \left( {\begin{array}{*{20}{c}} {0.06x_1^2} & {} & {} & {} & {} & {} \\ {} & {0.15x_2^2} & {} & {} & {} & {} \\ {} & {} & {0.27x_3^2} & {} & {} & {} \\ {} & {} & {} & {0.03x_4^2} & {} & {} \\ {} & {} & {} & {} & \cdots & {} \\ {} & {} & {} & {} & {} & {0.03x_n^2} \\ \end{array}} \right)$$ 是半正定矩阵,因此$F(x)$单调.

从表 1与表 2的对比实验可以看出算法3.1是有效的, 在维数较大的情况下非精确光滑算法cpu时间相对较小. 非精确光滑牛顿法对处理对称锥上复杂大规模问题是一种较好的算法.