考虑如下的非线性二阶锥规划问题 (NSOCP)

$\min f(x)\quad {\hbox{s.t.}} Ax=b, x\in K, $

(1.1)

其中$f:R^n\rightarrow R$是二阶连续可微函数, $A\in R^{m\times n}$, $b\in R^m$.将向量$x$可分成$r$块

$x=(x_1,\cdots,x_r), x_i\in R^{n_i}, i=1,\cdots, r.$

同理矩阵$A$也可分为$r$块

$A=(A_1,\cdots,A_r), A_i\in R^{m\times n_i}, i=1,\cdots, r, n_1+\cdots n_r=n.$

那么二阶锥$K = \left\{ {({x_0};\bar x) \in R \times {R^{n - 1}}|{x_0} \ge \left\| {\bar x} \right\|} \right\}$可表示成$K=K_1\times\cdots\times K_r$的笛卡尔乘积的形式, 其中${K_i} = \left\{ {({x_{i0}};{{\bar x}_i}) \in R \times {R^{{n_i} - 1}}|{x_{i0}} \ge \left\| {{{\bar x}_i}} \right\|} \right\}$, $\left\| \cdot \right\|$是欧式范数.进行这样的分块之后, 使得每个$x_i$都属于一个单块的二阶锥.

定义二阶锥$K$的内部、边界以及非零边界分别为

$ {\hbox{int}}K=\{x\in K|x_0>\|\bar x\|\}, bdK=\{x\in K|x_0=\|\bar x\|\},\\ bd^+K=\{x\in K|x_0=\|\bar x\| \hbox{和} x\neq 0\}. $

关于单块的二阶锥$K_i (i=1, \cdots, r)$的内部、边界以及非零边界可类似定义.

本文还需运用$B$-次微分和半光滑的知识, 下面仅作简单介绍.

定义1.1 映射$T:R^n\rightarrow R^m$局部Lipschitz连续.记$\mathcal {D}_T$为$T$的Frèchet方向可微点集合, $T$在$z$点处的Jacobian为$T^\prime (z)$. $T$在$z$处的$B$-次微分记为

$\partial_BT(z)={\mathop {\lim }\limits_{k \to \infty}T^\prime (z^k)|z^k\in \mathcal {D}_T, z^k\rightarrow z}.$

定义1.2 假设$T:R^n\rightarrow R^m$局部Lipschitz连续.称$T$在$z$处是半光滑的, 如果

(i) $T$在$z$处是方向可微的;

(ii) 对任何$h\in R^n$, $h\rightarrow0$, 任何$V\in \partial T(z+h)$满足

$T(z+h)-T(z)-Vh=o(\|h\|).$

进一步, 若$T$在$z$处是半光滑的, 且对任意$h\in R^n$, $h\rightarrow0$, 任何$V\in \partial T(z+h)$满足

$T(z+h)-T(z)-Vh=O(\|h\|^2), $

则称$T$在$z$处是强半光滑的.

二阶锥规划的发展历程较短, 所以可参看的文献很有限, 有兴趣的读者可参看文献[1, 2].研究者们的成果主要在线性二阶锥规划方面, 且通常选用内点法求解.但最近也有光滑和半光滑法求解二阶锥规划, 见文献[3, 4].在非线性二阶锥规划方面的成果比较有限.

因为二阶锥规划在其它的数学领域和学科中有广泛的应用, 所以它在较短的时间内成为较热门的研究课题.二阶锥规划, 半定规划以及线性规划统称为对称锥规划.二阶锥规划在组合优化, 金融优化, 图像恢复, 信号处理, 传感网络定位等方面有广泛的应用.

本文研究的问题是目标函数为二阶连续可微函数, 含有线性约束和锥约束的非线性二阶锥规划问题.给出原问题的KKT条件, 利用一个投影映射将互补性条件转化成非光滑函数. KKT条件即可转化成非光滑方程组.分析方程组的半光滑性质, 求出不可微点处的$B$-次微分.给出适当的条件保证方程组的$B$-次微分在任意点处可逆.运用中心路径非光滑牛顿法解非线性方程组, 在适当的条件下证明算法的全局收敛性.

众所周知, 解问题 (1.1) 等价于解最优性条件:

$\label{KKT} \nabla f(x)-A^T\nu-y=0, Ax=b,\\ x_i\in K_i, y_i\in K_i, x_i^Ty_i=0, i=1,\cdots,r. $

(2.1)

在系统 (2.1) 中, 锥约束条件不易求解, 所以可将它转化成易计算的非线性半光滑的方程组.文献[5]中已经提出了一种投影映射, 可求解此问题.

定义2.1 (投影到二阶锥的映射) 任取$s\in R^n$, 定义映射

$\label{TYdef} G(s)=[s]_+$

(2.2)

表示对任意的$s\in R^n$, $[s]_+$为$s$到$K$内的投影.

由文献[5]知, 以下结论成立.

引理2.1 对任意$s=(s_0;\bar s)\in R\times R^{n-1}$, 有

$\label{slamc} [s]_+=|\lambda_1|c_1+|\lambda_2|c_2, $

(2.3)

其中$\lambda_1,\lambda_2$和$c_1,c_2$分别是$s$的谱值和谱向量, 且分别表示为

$\label{spedec} \lambda_1=s_0-\|\bar{s}\|, \lambda_2=s_0+\|\bar{s}\|,\\ {c_1}= \left\{ \begin{array}{l} \frac{1}{2}(1;- \frac{\bar{s}}{{\left\|\bar{s} \right\|}}), {\hbox{如果}} \bar s\neq0, \\ \frac{1}{2}(1;-\bar w), {\hbox{如果}} \bar s=0,\end{array} \right. {c_2}= \left\{ \begin{array}{l} \frac{1}{2}(1;\frac{\bar{s}}{{\left\|\bar{s} \right\|}}), {\hbox{如果}} \bar s\neq0, \\ \frac{1}{2}(1;\bar w), {\hbox{如果}} \bar s=0, \end{array} \right. $

(2.4)

其中$\bar w$是$R^{n-1}$中满足$\|w\|=1$的任意向量.

引理2.2 投影映射$G$强半光滑.

下述结论将互补性条件转化成容易处理的非线性方程组.证明参见文献[5].

命题2.1 任取$x,y\in R^n$, $x+y-G(x-y)=0$当且仅当$x, y\in K$, $x^Ty=0$.

令$s=(x,\nu,y)\in R^n\times R^m\times R^n$.由命题 知KKT条件 (2.1) 等价于方程组$F(s)=0$, 其中$F:R^n\times R^m\times R^n\rightarrow R^n\times R^m\times R^n$,

$F(s) = F(x,\nu ,y) = \left( {\begin{array}{*{20}{l}} {\nabla f(x) - {A^T}\nu - y} \\ {\;\;\;\;\;\;Ax - b} \\ {{x_1} + {y_1} - G({x_1} - {y_1})} \\ {\;\;\;\;\;\;\;\;\;\;\; \vdots } \\ {{x_r} + {y_r} - G({x_r} - {y_r})} \end{array}} \right). $

(2.5)

采用中心路径牛顿法求解方程组 (2.5), 需求出$F(s)$的$B$-次微分以求牛顿方向. $F(s)=0$由$r+2$个方程组组成, 且第一个方程组是二阶连续可微函数, 第二个方程组是线性方程组, 所以重点来考虑后$r$个方程组.因为后$r$个方程组强半光滑, 如果$f$的Hessian矩阵局部Lipschitz连续, 则$F$是强半光滑的.

由文献[6]的命题2知, $\forall s\in R^n$, $s$的谱值和谱向量由式 (2.4) 给出, $G$在$s$处可微当且仅当$|\cdot|$在$\lambda_1$, $\lambda_2$处可微.而映射$|\alpha|$在$\alpha\neq0$处可微, 只有当$\alpha=0$, 即$s_0=\pm\|\bar s\|$时, $|\cdot|$不可微.

引理2.3 任取$s=(s_0;\bar s)\in R\times R^{n-1}$, $H\in \partial_BG(s)$, 则$H$的表述如下:

(a) 若$s_0\neq\pm\|\bar s\|$, 则$G$在$s$处连续可微且$H=G^\prime(s)$,

$\label{GJac} G^\prime(s)= \left\{ \begin{array}{l}-I_n,  {\hbox{如果}} s_0<-\|\bar{s}\|, \\ I_n,  {\hbox{如果}} s_0>\|\bar{s}\|,\\ \left( {\begin{array}{*{20}{c}} {0\;\;\;{{\bar w}^T}} \\ {\bar w\;\;\;J} \end{array}} \right),{\hbox{如果}} -\|\bar{s}\|<s_0<\|\bar{s}\|, \end{array} \right. $

(2.6)

其中$\bar{w}={\bar{s}\over\|\bar{s}\|}$, $J={s_0\over\|\bar{s}\|}(I_{n-1}-\bar{w}\bar{w}^T).$

(b) 若$\bar s\neq0$且$s_0=\|\bar s\|$, 则

$H\in\Bigg\{I_n,\left( {\begin{array}{*{20}{c}} {0\;\;\;{{\bar w}^T}} \\ {\bar w\;\;\;J} \end{array}} \right)\Bigg\},$

其中$\bar{w}={\bar{s}\over\|\bar{s}\|}$, $J=I_{n-1}-\bar{w}\bar{w}^T$.

(c) 若$\bar{s}\neq0$且$s_0=-\|\bar s\|$, 则

$H\in\Bigg\{-I_n,\left( {\begin{array}{*{20}{c}} {0\;\;\;{{\bar w}^T}} \\ {\bar w\;\;\;J} \end{array}} \right)\Bigg\},$

其中$\bar{w}={\bar{s}\over\|\bar{s}\|}$, $J=\bar{w}\bar{w}^T-I_{n-1}.$

(d) 若$s=0$, 则$H=-I_n$或者$H=I_n$或者

$H\in\Bigg\{\left( {\begin{array}{*{20}{c}} {0\;\;\;{{\bar w}^T}} \\ {\bar w\;\;\;J} \end{array}} \right)|J=\varrho(I_{n-1}-\bar{w}\bar{w}^T), |\varrho|\leq1,\|\bar{w}\|=1\Bigg\}.$

由引理2.3知, 任取$H\in\partial_BG(s)$有如下三种形式

$\label{3Bcwf} H=-I_n,H=I_n,H=\left( {\begin{array}{*{20}{c}} {0\;\;\;{{\bar w}^T}} \\ {\bar w\;\;\;J} \end{array}} \right), $

(2.7)

其中$J=\varrho(I_{n-1}-\bar{w}\bar{w}^T), |\varrho|\leq1,\|\bar{w}\|=1$.在 (a)-(c) 中, $\bar w=\bar{s}/\|\bar{s}\|$, 而在 (d) 中$\bar w$只需满足模为$1$.在 (a) 中$\varrho=s_0/\|\bar s\|$, 且$-1<\varrho<1$; 在 (b) 中$\varrho=1$; 在 (c) 中$\varrho=-1$; 在 (d) 中是满足$|\varrho|\leq1$的实数.

为了运用中心路径牛顿法来求解需要引入参数$\theta$, 对方程组 (2.5) 作如下扰动

${F_\theta }(x,\nu ,y) = \left( {\begin{array}{*{20}{l}} {\;\;\;\nabla f(x) - {A^T}\nu - y} \\ {\;\;\;\;\;\;\;\;\;Ax - b} \\ {{x_1} + {y_1} - G({x_1} - {y_1}) - \theta e} \\ {\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \vdots } \\ {{x_r} + {y_r} - G({x_r} - {y_r}) - \theta e} \end{array}} \right). $

(2.8)

算法的中心思想是利用牛顿法求解非线性方程组 (2.8), 且迭代的每一步都要在中心邻域内.

函数$F_\theta(x,\nu,y)$在任意点$(x,\nu,y)$处的$B$-次微分为

$ W = \left( {\begin{array}{*{20}{c}} {U\;\;\;\;\;\;\;\; - {A^T}\;\;\;\;\;\;\; - {I_n}} \\ {A\;\;\;\;\;\;\;\;\;\;\;0\;\;\;\;\;\;\;\;\;\;0} \\ {{I_n} - H\;\;\;\;\;\;0\;\;\;\;\;{I_n} + H} \end{array}} \right), $

(2.9)

其中$U=\nabla^2 f(x), I_n-H$, $I_n+H$分别是函数$\phi_\theta(x,y)=x+y-G(x-y)-\theta e$在$x,y$处的$B-$次微分, 且矩阵$I_n-H$, $I_n+H$都有一重特征值$\eta_0=0$和$\eta_2=2$及$n-2$重特征值$\eta_n=\varrho$, $\varrho\in(0,2)$.

下面给出合适的条件, 使得函数$F_\theta$在任意点处的$B$-次微分可逆.

令$H^a, H^b\in R^{n\times n}$是两个正半定矩阵使得$H^a+H^b\succ0$, 且$H^a$和$H^b$有相同的特征向量基底, 所以存在正交矩阵$Q\in R^{n\times n}$和对角矩阵$P^a={\hbox{diag}}(a_1,a_2,\cdots,a_n)$, $P^b={\hbox{diag}}(b_1,b_2,\cdots,b_n)$满足$H^a=QP^aQ^T$, $H^b=QP^bQ^T$对所有的$j=1,2,\cdots,n$, 有$a_j\geq0$, $b_j\geq0$, $a_j+b_j>0$.将指标集${1,2,\cdots,n}$分割成$\alpha \cup \beta \cup \gamma ,$

$\alpha ={j|a_j>0,b_j=0},\beta={a_j>0,b_j>0},\gamma={j|a_j=0,b_j>0}. $

(2.10)

令$Q_\alpha, Q_\beta, Q_\gamma$表示$Q$的子阵, 且它们由矩阵$Q$对应的指标集$\alpha \cup\beta\cup\gamma$对应的列组成.同理将对角矩阵分割为$P^a={\hbox{diag}}(P^a_\alpha,P^a_\beta,P^a_\gamma),P^b={\hbox{diag}}(P^b_\alpha,P^b_\beta,P^b_\gamma)$.

令

$\label{Pbeta}P_\beta=(P^b_\beta)^{-1}P^a_\beta.$

(2.11)

参见文献[8], 有以下结论成立.

引理2.4 令$U\in R^{n\times n}$是对称矩阵, $A\in R^{m\times n}$.对于上述各量, 假设下面两个条件成立:

(a) 矩阵$(AQ_\beta,AQ_\gamma)\in R^{m\times(|\beta|+|\gamma|)}$行满秩;

(b) 在子空间

${\cal L} = \left\{ {\left( {\begin{array}{*{20}{c}} {{d_\beta }}\\ {{d_\gamma }} \end{array}} \right){\rm{ }} \in {R^{|\beta | + |\gamma |}}|(A{Q_\beta },A{Q_\gamma })\left( {\begin{array}{*{20}{c}} {{d_\beta }}\\ {{d_\gamma }} \end{array}} \right) = 0} \right\} $

上, 矩阵

$\left( {\begin{array}{*{20}{c}} {Q_\beta ^TU{Q_\beta } + {P_\beta }\;\;\;\;Q_\beta ^TU{Q_\gamma }} \\ {Q_\gamma ^TU{Q_\beta }\;\;\;\;\;\;\;\;\;\;Q_\gamma ^TU{Q_\gamma }} \end{array}} \right) \in {R^{(|\beta | + |\gamma |) \times (|\beta | + |\gamma |)}}$

正定.则矩阵

$M = \left( {\begin{array}{*{20}{c}} {U\;\;\;\; - {A^T}\;\;\;\; - {I_n}} \\ {A\;\;\;\;\;\;\;\;0\;\;\;\;\;\;\;\;\;0} \\ {{H^a}\;\;\;\;\;\;\;0\;\;\;\;\;\;\;{H^b}} \end{array}} \right)$

(2.12)

非奇异.

尤其, 当$U=0$时, 如果矩阵$AQ_\gamma$列满秩, 则当条件$(a)$成立时, 矩阵$M$非奇异.

由引理2.3与引理2.4, 可得到以下结论.

定理2.1 函数$F_\theta(x,\nu,y)$在任意点$(x,\nu,y)$处的$B$-次微分如 (2.9) 式所示.令$I_n-H=H^a$, $I_n+H=H^b$, 当引理2.3中的条件满足时 (2.9) 式中的$W$可逆.

首先, 作如下记号, $\forall s\in R^{2n+m}$, $F$在$s$点处的$B$-次微分为$W(s)$.中心邻域为

$\label{cen} N(\delta)={(x,\nu,y)|\nabla f(x)-A^T\nu-y=0,Ax=b,\|F_\theta(x,\nu,y)\|\leq\delta\theta}. $

(3.1)

下面给出算法的具体步骤.

算法A:

步骤0初始步 任意选取$s^0=(x^0,\nu^0,y^0)\in R^n\times R^m\times R^n$为初始点.给定常数$\sigma,\alpha_1\in(0,1)$.选取常数$\delta>0$, $\theta_0>0$, 使得$\|F_{\theta_0}(s^0)\|\leq\delta\theta_0$.令$k=0$.

步骤1终止条件 若$\|F_0(s^k)\|=0$, 停止.

步骤2预估步 解方程组

$\label{predictor} W(s^k)d^k=-F_{\theta_k}(s^k), $

(3.2)

得$d^k=(\Delta x^k,\Delta\nu^k,\Delta\mu y^k)\in R^n\times R^m\times R^n$.若$\|F_0(s^k+d^k)\|=0$, 停止; 否则, 若$\|F_{\theta_k}(s^k+d^k)\|>\delta\theta_k$, 令$\tilde{s}^k=s^k$, $\tilde{\theta}^k=\theta^k$, $\vartheta_k=1$; 若$\|F_{\theta_k}(s^k+d^k)\|\leq\delta\theta_k$, 令$\vartheta_k=\alpha_1^p$, $p$是使得下面不等式成立的正整数

$\label{alphatheta} \|F_{\alpha_1^q\theta_k}(s^k+d^k)\|\leq\delta\alpha_1^q\theta_k, q=0,1,\cdots,p,\\ \|F_{\alpha_1^{p+1}\theta_k}(s^k+d^k)\|>\delta\alpha_1^{p+1}\theta_k. $

(3.3)

令

${\tilde \theta _k} = {\vartheta _k}{\theta _k},{\tilde s^k} = \left\{ \begin{array}{l} {s^k} p = 0,\\ {s^k} + {d^k}p \ne 0. \end{array} \right.$

步骤3校正步 解方程组

$\label{correction} W(\tilde{s}^k)\tilde{d}^k=-F_{\tilde{\theta}_k}(\tilde{s}^k), $

(3.4)

得$\tilde{d}^k=(\Delta \tilde{x}^k,\Delta \tilde{\nu}^k,\Delta \tilde{y}^k) \in R^n\times R^m\times R^n$.设$\tilde{\vartheta}_k$是$\{1,\alpha_1,\alpha_1^2,\cdots\}$中使得下式成立的最大值

$\label{aemijo} \|F_{\tilde{\theta}_k}(\tilde{s}^k+\tilde{\vartheta}_k\tilde{d}^k)\|^2\leq \|F_{\tilde{\theta}_k}(\tilde{s}^k)\|^2+\tilde{\vartheta}_k\sigma (\nabla\|F_{\tilde{\theta}_k}(\tilde{s}^k)\|^2)^T\tilde{d}^k. $

(3.5)

令$s^{k+1}=\tilde{s}^k+\tilde{\vartheta}_k\tilde{d}^k$.

步骤4修正 设$\gamma_k$是$\{1,\alpha_1,\alpha_1^2,\cdots\}$中使得下式成立的最大值

$\label{update} \|F_{(1-\gamma_k)\tilde{\theta}_k}(s^{k+1})\|\leq\delta(1-\gamma_k)\tilde{\theta}_k. $

(3.6)

令$\theta_{k+1}=(1-\gamma_k)\tilde{\theta}_k$, $k=k+1$, 转步1.

对于上述算法, 易知有以下良定性结论成立.

定理3.1 在引理2.4的条件下, 对任意$k\geq 0, \forall\theta_k>0$, 方程组 (3.2) 和 (3.4) 都存在唯一解.从而步骤$2,3,4$是良定的.

引理3.1 在引理2.4的条件下, 则当$k\geq0$时, 有$\theta_k=\theta_0(1-\gamma_0)\vartheta_0\cdots(1-\gamma_{k-1})\vartheta_{k-1}>0$.而且对任意$k\geq0$, 有$\|F_{\theta_k}(s^k)\|\leq\delta\theta_k$.此时, 当$k\to \infty$时, $\nabla f(x^k)-A^T\nu^k-y^k\to 0$, $Ax^k-b\to 0$.

本节证明算法A的全局收敛性.

定理4.1 矩阵$W(s)$可逆, 序列${(s^k,\theta_k)}$由算法A产生.设$(s^*,\theta_*)=(x^*,\nu^*,y^*,\theta_*)$是它的一个聚点, 则$\theta_*=0$, $s^*$是$F_0(s)=0$的解.

证 不失一般性, 假设$\lim\limits_{k\to\infty}(s_k,\theta_k)=(s^\ast,\theta_\ast)$. ${\theta_k}$由算法A产生, 由引理3.1知, 序列${\theta_k}$单调下降, 且有下界, 即$\theta_*\geq0$.利用反证法证明$\theta_*=0$.假设$\theta_*>0$, 则由算法A步骤2知, 当$k$充分大时有

$\label{ta*>0} \tilde{s}^k=s^k, \tilde{\theta}_k=\theta_k, \vartheta _k=1. $

(4.1)

因为$\theta_k$的迭代公式为$\theta_k=\theta_0(1-\gamma_0)\vartheta_0\cdots(1-\gamma_{k-1})\vartheta_{k-1}$, 而且$\theta_k\to\theta_*>0$, 所以当$k$充分大时$\lim\limits_{k\to\infty}\gamma_k=0$.对任意的$k$, 有$\vartheta_k\geq0$, 不妨设$\lim\limits_{k\to\infty}\inf\tilde{\vartheta_k}>0$和$\lim\limits_{k\to\infty}\inf\tilde{\vartheta_k}=0$.

(i) 若$\lim\limits_{k\to\infty}\inf\tilde{\vartheta_k}>0$, 则存在常数$\tilde{\vartheta}>0$, 使得当$k$充分大时有$\tilde{\vartheta}_k>\tilde{\vartheta}$.由 (3.4) 和 (3.5) 式得

$\label{3.3d3.4} \|F_{\theta _k}(\tilde{s}^k+\tilde{\vartheta}_k\tilde{d}^k)\|^2\leq (1-2\sigma\tilde{\vartheta}_k)\|F_{\theta _k}(\tilde{s}^k)\|^2, $

(4.2)

即

$\label{equal4.2} \|F_{\theta _k}(s^{k+1})\|\leq\sqrt{1-2\sigma\tilde{\vartheta}_k}\|F_{\theta _k}(\tilde{s}^k)\| \leq\sqrt{1-2\sigma\tilde{\vartheta}_k}\theta _k\delta. $

(4.3)

由步骤4知, ${\gamma_k\over\alpha_1}$不满足 (3.6) 式, 由文献[5]和 (4.3) 知,

$\delta(1-{\gamma_k\over\alpha_1})\theta _k \leq \|F_{\theta _k}(s^{k+1})\|+ \|F_{(1-{\gamma_k\over\alpha_1})\theta _k}(s^{k+1})-F_{\theta _k}(s^{k+1})\|\\ \leq \sqrt{1-2\sigma\tilde{\vartheta}_k}\theta _k\delta+{\sqrt{2}\gamma_k\over\alpha_1}\theta _k. $

因此, $\gamma_k\geq{\alpha _1\delta\over\delta+\sqrt{2}}(1-\sqrt{1-2\sigma\tilde{\vartheta}_k})>0$, 这与$\lim\limits_{k\to\infty}\gamma_k=0$矛盾.

(ii) 若$\lim\limits_{k\to\infty}\inf\tilde{\vartheta}_k=0$, 不妨设$\lim\limits_{k\to\infty}\tilde{\vartheta}_k=0$. $F$是关于$s$和$\theta$的连续可微函数.由步骤3的线搜索知$\bar{\vartheta}=\frac{\tilde{\vartheta}_k}{\alpha_1}$不满足 (3.5) 式, 即

$\frac{\|F_{\theta _k}(\tilde{s}^k+\bar{\vartheta}_k\tilde{d}^k)\|^2-\|F_{\theta _k}(\tilde{s}^k)\|^2} {\bar{\vartheta}_k}>\sigma(\nabla\|F_{\theta _k}(\tilde{s}^k)\|^2)^T\tilde{d}^k.$

令$k\to\infty$, 两边求极限得

$(\nabla\|F_{\theta_*}(s^*)\|^2)^Td^*\geq\sigma(\nabla\|F_{\theta_*}(s^*)\|^2)^Td^*,$

则

$\label{FTd>=0} (\nabla\|F_{\theta_*}(s^*)\|^2)^Td^*\geq0. $

(4.4)

由式 (3.4) 和 (3.5) 知

$W(s^*)d^*=-F_{\theta_*}(s^*),$

因此

$\label{FFF} (\nabla\|F_{\theta_*}(s^*)\|^2)^Td^*=F_{\theta_*}(s^*)W(s^*)d^*=-\|F_{\theta_*}(s^*)\|^2\leq0. $

(4.5)

由式 (4.4) 和 (4.5) 知

$\label{Ftas=0} F_{\theta_*}(s^*)=0. $

(4.6)

又由算法A步骤4知, ${\gamma_k\over\alpha _1}$不满足 (3.6) 式, 即

$\|F_{(1-{\gamma_k\over\alpha_1})\theta _k}(s^{k+1})\|>\delta{(1-{\gamma_k\over\alpha_1})\theta _k}.$

令$k\to\infty$, 上式两边取极限得

$\|F_{\theta_*}(s^*)\|\geq\delta\theta_*>0. $

这与 (4.6) 式矛盾, 因此假设不成立, 即$\theta_*=0$.由引理3.1的 (iii) 知, $s^*$是$F_0(s)=0$的唯一解.定理证明完毕.