趙花麗

(咸陽師范學院數(shù)學與統(tǒng)計學院，陜西 咸陽 712000)

0 引言

內(nèi)點算法是求解對稱錐互補問題的一類非常有效的方法，當今關于對稱錐非線性互補問題的研究還處于不成熟階段，相關的研究較少.2006年,Yoshise[1]擴展了Andersen等[2]提出的齊次模型,隨后基于該模型提出了單調(diào)對稱錐非線性互補問題的齊次算法[3].Zhao等[4]在新的SLC條件下估計了單調(diào)對稱錐非線性互補問題的齊次算法的理論復雜度.笛卡爾P*(κ)對稱錐非線性互補問題是一類非單調(diào)非線性互補問題，單調(diào)問題是該問題的特例，因此研究笛卡爾P*(κ)對稱錐非線性互補問題就成為研究的熱點，Zhao等[5-7]對不可行內(nèi)點算法做了相關的研究.

一直以來，學者們都在研究如何改進寬鄰域算法的理論復雜度.2005年，Ai等[8]定義了一個Frobenius范數(shù)寬鄰域,得到了和窄鄰域短步算法具有相同復雜性的寬鄰域算法.隨后該鄰域被推廣到半定規(guī)劃和對稱錐優(yōu)化問題中[9-10].然而上述研究都是基于可行算法的，Liu等[11]將Ai等的鄰域進行了簡化,給出了寬鄰域不可行內(nèi)點算法并獲得了較好的理論復雜度.隨后,Yang等[12]將不等式中的Frobenius范數(shù)換成1范數(shù),并且利用該鄰域得到了較好的算法.2018年，Asadi等[13]進一步得到無窮范數(shù)寬鄰域，分析了笛卡爾P*(κ)線性互補問題的內(nèi)點算法的復雜度.本文基于Asadi等提出的無窮范數(shù)寬鄰域,給出了笛卡爾P*(κ)對稱錐非線性互補問題一個無窮范數(shù)寬鄰域不可行內(nèi)點算法.

1 歐幾里得若當代數(shù)與對稱錐

ⅰ)x°y=y°x；

ⅱ)x°(x2°y)=x2°(y°x),其中x2=x°x；

ⅲ)〈x°y,z〉=〈x,y°z〉,其中x°y為x和y的若當積.

關于對稱錐更為詳細的介紹,請參考文獻[14].

2 算法及預備知識

其中

I+={v:〈x(v)-y(v),φ(x)(v)-φ(y)(v)〉≥0}，I-={v:〈x(v)-y(v),φ(x)(v)-φ(y)(v)〉<0}.

本文假定嚴格可行集非空.考慮迭代點在以下寬鄰域的情形：

(1)

(2)

給定步長α∈[0,1],則新的迭代為

(3)

(4)

這里α滿足:

(5)

(6)

(7)

算法1(不可行寬鄰域內(nèi)點算法)

[步驟1] 如果μk≤ε,則停止.

[步驟4] 令(xk+1,sk+1)=(x(αk),s(αk)),計算新的對偶間隙μk+1=〈xk+1,sk+1〉/n.令k:=k+1， 轉步驟1.

3 復雜度分析

證明ⅰ)由引理1有

ⅱ)利用引理2和引理3有

所以ⅱ)成立.

ⅲ)由于

故成立.

因此ⅳ)成立.

又由引理3,可知

令

所以有

所以

ⅰ)μ(α)≤(1+α(τ-1+τβ)+Cα2n3/2)μ；

ⅱ)μ(α)≥(1+α(τ-1)-Cα2n3/2)μ.

證明ⅰ)經(jīng)過簡單計算可知

因為

所以有μ(α)≤(1+α(τ-1+τβ)+Cα2n3/2)μ.

ⅱ)因為

tr(h(α))≥nμ+α(τ-1)nμ=(1+α(τ-1))nμ，

所以μ(α)≥(1+α(τ-1)-Cα2n3/2)μ.

因此由引理5、引理6和引理7有

‖(τμ(α)e-h(α))+‖∞+‖(T(α))-‖∞≤

‖(τμ(α)e-h(α))+‖∞+‖T(α)‖∞≤βτμ(α),

證明由引理8,可知

證明由引理8,有

μ(α)≤μ+α(τ-1+βτ)μ+Cα2μn3/2≤μ[1-(1-τ-βτ-Cαn3/2)α]≤

利用引理11,可獲得下面的復雜度.

推論1當使用NT方向時,算法1至多O((2+κ)3n9/4logε-1)步終止.當使用xs方向時,算法1至多O((2+κ)3n4logε-1)步終止.當使用sx方向時,算法1至多O((2+κ)3n5/2logε-1)步終止.

4 數(shù)值實驗

以下測試算法1的實際計算效果.在算法的執(zhí)行中,取參數(shù)γ=0.000 1.算法的終止條件為max{r,mu}≤1e-6.可行性殘差r=‖s-φ(x)‖F(xiàn),互補間隙mu=〈x,s〉/n，k表示算法的迭代步數(shù)，t表示算法的運行時間.

在這里，分別對n=500,n=1 000,n=1 500,n=2 000進行計算，結果列于表1.

表1 非線性互補問題的數(shù)值結果Tab.1 The numerical results for nonlinear complementarity problems

從表1數(shù)據(jù)結果來看，本文提出的算法1與文獻[7]中的算法1迭代步數(shù)基本相同，但是計算時間優(yōu)于文[7]中算法1.