對稱錐非線性互補(bǔ)問題的無窮范數(shù)寬鄰域算法

趙花麗

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

0 引言

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

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

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

ⅰ)x°y=y°x；

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

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

關(guān)于對稱錐更為詳細(xì)的介紹,請參考文獻(xiàn)[14].

2 算法及預(yù)備知識

其中

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

本文假定嚴(yán)格可行集非空.考慮迭代點(diǎn)在以下寬鄰域的情形：

(1)

(2)

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

(3)

(4)

這里α滿足:

(5)

(6)

(7)

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

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

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

3 復(fù)雜度分析

證明ⅰ)由引理1有

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

所以ⅱ)成立.

ⅲ)由于

故成立.

因此ⅳ)成立.

又由引理3,可知

令

所以有

所以

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

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

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

因?yàn)?/p>

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

ⅱ)因?yàn)?/p>

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,可獲得下面的復(fù)雜度.

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

4 數(shù)值實(shí)驗(yàn)

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

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

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

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