改進步長下的高斯牛頓算法的收斂性分析

作者簡介：

程秀蘭(1973)，女(漢)， 山東省濰坊市人，濰坊醫學院教師，碩士，運籌學方向．

魏軍（1969），男(漢)，山東省濰坊市人，濰坊學院教師，碩士，計算機軟件方向．

摘 要：本文將廣義互補問題轉化為一個非線性方程問題， 然后建立了GCP問題的無約束優化問題的轉化形式，對該優化問題，用改進步長下的高斯牛頓算法來求解，并對算法的收斂性作了分析.

關鍵詞：廣義互補問題 非線性方程組 新步長下的算法 收斂性

中圖分類號：G642文獻標識碼：A 文章編號：1673-9795(2012)01(a)-0000-00

1 引言

廣義互補問題，簡記為GCP，是求一向量x*∈Rn，使得:

F(x*)≥0， G(x*)≥0， F(x*)TG(x*)=0，

其中F，G:Rn→Rn的連續可微函數.特別的，當G(x)，GCP問題就退化為通常意義下的非線性互補問題(NCP).近年來， 互補問題成為運籌學研究的一個熱門課題， 并產生了各式各樣的有效算法[1，2]，本文用改進步長下的高斯牛頓算法求解，并分析了算法的收斂性.

2 非線性方程組

為得到GCP問題的轉化形式，首先建立以下非線性方程組.

基于[3]中定理2.1，可得下述定理，

定理2.1 設F，G:Rn→Rn，θ:R→R是一個嚴格遞增的函數且θ(0)=0，則x*是GCP的解當且僅當x*是非線性方程組(i=1，2，…，n)的解，其中Hi(x)=θ(│Fi(x)- Gi(x)│)-θ(Fi(x))-θ(Gi(x))， Fi(x)，Gi(x)是分量 此定理借助Mangasarian提出的互補函數將求解GCP問題轉化為求一非線性方程組H(x)=0的問題，其中H(x)= (H1(x)，H2(x)，···，Hn(x))T

令h(x)=1/2‖H(x)‖2， 由上述定理2.1知，求GCP的解等價于求H(x)=0的解，又x*是H(x)=0的解當且僅當x*是h(x)的全局最小點，因此，若GCP的解集非空，則求GCP的解可轉化為求下面的無約束優化問題

Min h(x) (2.1)

因為▽h(x*)=▽H(x*)T H(x*)，(▽h(x*)表示實值函數h(x)在點x* 的梯度向量)若▽H(x*)非奇異，且▽h(x*)=0，則H(x*)=0，因此h(x)的目標函數值為零的全局最小點可通過求h(x)的穩定點（使得▽h(x)=0的點）得到.

3 新步長下的算法和算法的收斂性

本文在DGN算法的基礎上采用了一種新的步長，對此種情況下算法的收斂性作了分析.

記Ax=▽H(x)T▽H(x)，則Ax為對稱半正定矩陣.

為討論問題的方便，作如下假設：

（H1）;

（H2）▽h(x)在Rn上是模為kg Lipschitz連續的，即對于任意x，y∈Rn，，有：.

新步長下的算法我們記為M-DGN算法，現表述如下：

M-DGN算法：

步1.給定x0和δ∈(0，1)，若有xk，按如下方法確定xk+1. 步2.如果▽h(xk)=0，則停.

步3.如果▽h(xk)≠0，定義Ak=▽H(xk)T▽H(xk). 步4.令λk=h(xk).

步5.令pk=(Ak+λkI)-1▽h(xk).

步6.設ωk = (3.1)

步7.令xk+1=xk-ωkpk

下面建立一個M-DGN算法的全局收斂性定理，不失一般性，不妨假設算法不在有限步內停止，即假設對于任意的k，.由上述的M-DGN算法，我們可得述引理：

引理3.1：令Ak=▽H(xk)T▽H(xk)，設{ xk }由M-DGN算法產生的序列，則對任意的k，下式成立：

(3.2)

引理3.2：假設成立，{ xk }由M-DGN算法產生，則：

(3.3)

由上述引理，可得算法的收斂性定理，以下定理給出了在一定條件下，算法產生的序列收斂到h(x)的穩定點。

以下是M-DGN算法的全局收斂定理：

定理3.2：假設（H1）和（H2）成立，x0是任意給定的初始點，{ xk }由M-DGN算法產生，則下述兩種情況必居其一：

證明：由中值定理， (3.1) (3.2)式和假設（H2）得：

（其中zk∈[xk，xk+1]）

由以上證明可知，序列{h(xk)}是單調下降的，又因為h(xk)是非負的，故一定存在， 不妨設，一定有.下面分兩種情況討論(1)若，則定理得證. (2)若，則由(3.4)式得:

參考文獻

[1] B.S.He.A modifeed projection and contraction method for a class of linear complementarity problem and its application in conves quadratic programming[J]. Appl.Math.and Optim，1992，25;247-262.

[2] B.S. He. A modifeed projection and contraction method for a class of linear complementarity problem[J].JCM，1996，14:54-63.

[3] Mangasarian O.L.， Equivalence of the Complementarity Problem to a System of Nonlinear Equations[J]， SIAM Journal on Applied Mathematics， 31：89-92，1976.

[4] H.Jiang，M.Fukushima，L.Qi and D.Sun. A trust region method for solving generalized complementarity problems[J].SIAM J.Optim.，8:140-157，1998.

[5] Subramanian P K， Xiu N H， Convergence Analysis of Gauss-Newton Methods for the Complementarity Problem[J]， Journal of Optimization Theory and Applications， 94：727-738，1997.

[6] Subramanian P K， Gauss-Newton Methods for the Complementarity Problem [J]，Journal of Optimization Theory and Applications，77:467-482，1993.