曾 榮

(廣東東軟學(xué)院 基礎(chǔ)教學(xué)院， 廣東 佛山528000)

1 引 言

考慮二階錐權(quán)互補(bǔ)問(wèn)題(wSOCCP)：給定權(quán)向量w∈，求向量x∈n使得

x∈，s=F(x)∈，x°s=w，

(1)

近年來(lái)，權(quán)互補(bǔ)問(wèn)題的理論和算法研究已取得了一些成果[1-2].權(quán)互補(bǔ)問(wèn)題可以被應(yīng)用于經(jīng)濟(jì)學(xué)中，如Fisher市場(chǎng)均衡問(wèn)題，二次規(guī)劃和權(quán)中心問(wèn)題等都可以被轉(zhuǎn)化為權(quán)互補(bǔ)問(wèn)題進(jìn)行求解.基于這些研究工作，二階錐上的權(quán)互補(bǔ)問(wèn)題的求解方法也陸續(xù)受到關(guān)注[3-4].

目前，許多算法已被用于求解各類(lèi)優(yōu)化問(wèn)題，如：共軛梯度法[5]，內(nèi)點(diǎn)算法[1]，非內(nèi)點(diǎn)連續(xù)化算法[6-7]等.其中，內(nèi)點(diǎn)算法最早被用于權(quán)互補(bǔ)問(wèn)題的求解[1]，但該算法要求初始點(diǎn)嚴(yán)格可行，因此在求解問(wèn)題時(shí)要找到這樣的初始點(diǎn)較為困難.非內(nèi)點(diǎn)連續(xù)化算法由于具有較好的收斂性和數(shù)值結(jié)果，近年來(lái)發(fā)展迅速[6-7].非內(nèi)點(diǎn)連續(xù)化算法不同于內(nèi)點(diǎn)算法，它能選擇任意點(diǎn)為初始點(diǎn)，且迭代過(guò)程中不要求中間迭代點(diǎn)為可行內(nèi)點(diǎn)，這些特點(diǎn)使得非內(nèi)點(diǎn)連續(xù)化算法比內(nèi)點(diǎn)算法更加便于進(jìn)行數(shù)值計(jì)算.本文運(yùn)用非內(nèi)點(diǎn)連續(xù)化算法求解二階錐權(quán)互補(bǔ)問(wèn)題，并引入了非精確牛頓法.在適當(dāng)假設(shè)下，證明了該算法是全局收斂與局部二階收斂的.最后通過(guò)數(shù)值實(shí)驗(yàn)表明了算法的有效性.

2 預(yù)備知識(shí)

對(duì)任意x=(x0，x1)，s=(s0，s1)∈×n-1，與二階錐相伴的歐幾里得約當(dāng)代數(shù)定義為

x°s=(xTs，x0s1+s0x1)，

易知Lxs=x°s.若x∈int，則Lx可逆.

對(duì)任意x=(x0，x1)∈×n-1，令λi和u(i)(i=1，2)分別為x的譜值和對(duì)應(yīng)的譜向量，則稱(chēng)x=λ1u(1)+λ2u(2)為x的譜分解，其中

ω∈n-1是‖ω‖=1的任意非零向量.由譜分解定義易知

(ii)x∈? 0≤λ1≤λ2，x∈int? 0<λ1≤λ2；

3 算法設(shè)計(jì)

本文考慮含參數(shù)τ∈(0，4)的wSOCCP函數(shù)φτ，μ(x，s)∶n×n→n：

(2)

其中w∈為權(quán)向量.類(lèi)似文獻(xiàn)[2]中命題1易得φτ，0(x，s)=0?x∈，s∈，x°s=w.

定理1令φτ，μ(x，s)由(2)定義，則有

(i) 對(duì)任意μ∈，φτ，μ(x，s)在任意(x，s)∈n×n處全局Lipschitz連續(xù)且強(qiáng)半光滑，若μ>0，令則φτ，μ(x，s)連續(xù)可微，且對(duì)x和s的偏導(dǎo)數(shù)為

(3)

(ii)對(duì)任意(x，s)∈n×n有則φτ，μ(x，s)為φτ，0(x，s)的一個(gè)光滑函數(shù).

證因?yàn)?/p>

由(2)和文獻(xiàn)[8]中定理3.2易得到(i)和(ii)成立.

對(duì)任意x=(x0，x1)，s=(s0，s1)∈×n-1和w=(w0，w1)∈，由譜分解定義有

λ(x，s)=min(λ1，λ2).

(4)

引理2令φτ，μ(x，s)由(2)定義，則對(duì)任意μ1，μ2>0和(x，s)∈n×n，有

當(dāng)λ(x，s)>0時(shí)

‖φτ，μ1(x，s)-φτ，μ2(x，s)‖

令z∶=(x，s)∈n×n，結(jié)合(2)定義

(5)

易知Hτ，0(z)=0? (x，s)為(1)的解.

定理3令w∈，Hτ，μ(z)由(5)定義，則結(jié)合(3)有以下結(jié)論成立：

(i)Hτ，μ(z)全局Lipschitz連續(xù)且強(qiáng)半光滑，若μ>0，對(duì)任意z∶=(x，s)∈n×n，Hτ，μ(z)連續(xù)可微其雅可比為

(6)

(ii) 若F(x)連續(xù)可微且單調(diào)，則當(dāng)μ>0時(shí)，H′τ，μ(z)可逆.

證由定理1易知(i)成立.下面證明(ii)成立.對(duì)任意μ>0，令Δz=(Δx，Δs)∈n×n為H′τ，μ(z)零空間中任意向量，則只需證明Δz=0.由(6)有

F′(x)Δx-Δs=0，

(7)

Bτ，μΔx+Dτ，μΔs=0.

(8)

因?yàn)镕(x)單調(diào)，結(jié)合(7)知

〈Δx，Δs〉=〈Δx，F(xiàn)′(x)Δx〉≥0.

(9)

將(8)兩邊同時(shí)乘Lc有

(10)

而由c定義知

則根據(jù)文獻(xiàn)[9]中命題3.4知LcBτ，μ和LcDτ，μ可逆，將(10)兩側(cè)同乘ΔxT[LcDτ，μ]-1有

ΔxT[LcDτ，μ]-1[LcBτ，μ]Δx+ΔxTΔs=0.

結(jié)合(9)得到

ΔxT[LcDτ，μ]-1[LcBτ，μ]Δx≤0.

(11)

又因?yàn)?/p>

算法1(非精確非內(nèi)點(diǎn)連續(xù)化算法)

步0 選取δ，σ，η∈(0，1)，γ∈(0.5，1)和μ0>0，令z0=(x0，s0)∈n×n為任意初始點(diǎn)，選取β使得且‖Hτ，μ0(z0)‖≤βμ0.置k∶=0.

步1 若μk=0，停止.

步2 若‖Hτ，μk(zk)‖=0，則zk+1∶=zk且θk∶=1，轉(zhuǎn)步4；否則，令Δzk∶=(Δxk，Δsk)∈n×n為下列方程的解

H′τ，μk(zk)Δzk=-Hτ，μk(zk)+rk，

(12)

其中‖rk‖≤η‖Hτ，μk(zk)‖min{1，‖Hτ，μk(zk)‖}.

步3 令θk=max{1，δ，δ2，…}使得

‖Hτ，μk(zk+θkΔzk)‖≤[1-σ(1-η)θk]‖Hτ，μk(zk)‖.

(13)

置zk+1∶=zk+θkΔzk.

步4 置

(14)

令tk=min{1，γ，γ2，…}使得

(15)

注 算法可以取任意(μ0，x0，s0)∈++×n×n為初始點(diǎn)，且

定理4若函數(shù)F(x)是連續(xù)可微且單調(diào)的，則算法1適定.

證由算法1知μk>0，而F(x)連續(xù)可微且單調(diào)，則由定理3(ii)知H′τ，μk(zk)可逆.故步2適定.

接著證步3適定.對(duì)任意θ∈(0，1]，令

g(θ)∶=Hτ，μk(zk+θΔzk)-Hτ，μk(zk)-θH′τ，μk(zk)Δzk.

(16)

因?yàn)棣蘫>0，由定理3(i)知Hτ，μk(zk)在zk處連續(xù)可微，故由(16)有‖g(θ)‖=o(θ).結(jié)合(12)，(16)和

‖rk‖≤η‖Hτ，μk(zk)‖min{1，‖Hτ，μk(zk)‖}≤η‖Hτ，μk(zk)‖，

對(duì)任意θ∈(0，1]有

‖Hτ，μk(zk+θΔzk)‖≤‖Hτ，μk(zk)+θH′τ，μk(zk)Δzk‖+‖g(θ)‖

≤‖(1-θ)Hτ，μk(zk)+θrk‖+‖g(θ)‖

≤(1-θ)‖Hτ，μk(zk)‖+θη‖Hτ，μk(zk)‖+o(θ)

=[1-(1-η)θ]‖Hτ，μk(zk)‖+o(θ).

最后證步4適定.當(dāng)Hτ，μk(zk)≠0時(shí)，由(13)-(15)和引理2知

(17)

當(dāng)Hτ，μk(zk)=0時(shí)，zk+1=zk，故Hτ，μk(zk+1)=Hτ，μk(zk)=0.由(17)和[1-σ(1-η)θk]βμk≥0知

由算法1易得到下面的引理成立.此處省略不證.

引理5設(shè)函數(shù)F(x)是連續(xù)可微且單調(diào)的，則

(i) 對(duì)任意k≥0，序列{μk}單調(diào)遞減且μk>0；

(ii) 對(duì)任意k≥0有‖Hτ，μk(zk)‖≤βμk.

4 收斂性分析

本節(jié)給出算法1的全局收斂性和局部二階收斂性分析.

‖Hτ，μk(zk+kΔzk)‖>[1-σ(1-η)k]‖Hτ，μk(zk)‖.

又根據(jù)(12)可得

‖Hτ，μk(zk+kΔzk)‖=‖Hτ，μk(zk)+kH′τ，μk(zk)Δzk+g(k)‖=‖(1-k)Hτ，μk(zk)+krk+g(k)‖

≤(1-k)‖Hτ，μk(zk)‖+kη‖Hτ，μk(zk)‖+o(k)

=[1-(1-η)k]‖Hτ，μk(zk)‖+o(k).

(18)

因此

[1-σ(1-η)k]‖Hτ，μk(zk)‖≤[1-(1-η)k]‖Hτ，μk(zk)‖+o(k).

(19)

‖Hτ，μ*(z*)‖=0.

(20)

另一方面，根據(jù)步4知‖Hτ，γμk+1(zk+1)‖>βγμk+1.令k→∞有

‖Hτ，γμ*(z*)‖≥βγμ*.

(21)

這與(20)矛盾.因此得到μ*=0.

最后證z*為Hτ，0(z)=0的解.由引理5(ii)知‖Hτ，μk(zk)‖≤βμk，當(dāng)k→∞則有‖Hτ，0(z*)‖=‖Hτ，μ*(z*)‖≤βμ*，而μ*=0，故Hτ，0(z*)=0.定理得證.

證對(duì)充分大的k，考慮下面兩種情形：

故存在一個(gè)較小的ε>0，使得對(duì)充分大的k有λ(xk+1，sk+1)≥λ(x*，s*)-ε>0.由引理2得

結(jié)合步4知

(ii) 若Hτ，μk(zk)≠0，類(lèi)似(i)可以得到

(22)

下面證明對(duì)充分大的k有zk+1=zk+Δzk成立.由于對(duì)任意V∈?Hτ，μ*(z*)非奇異，則由文獻(xiàn)[10]中命題3.1，對(duì)充分大的k有‖H′τ，μk(zk)-1‖=O(1).因此結(jié)合步2易知

‖Δzk‖=‖H′τ，μk(zk)-1(-Hτ，μk(zk)+rk)‖≤(1+η)‖H′τ，μk(zk)-1‖‖Hτ，μk(zk)‖

=O(‖Hτ，μk(zk)‖).

(23)

另外，根據(jù)定理3(i)得到Hτ，μk(·)在點(diǎn)zk+Δzk處強(qiáng)半光滑，即對(duì)充分大的k，

‖Hτ，μk(zk+Δzk)-Hτ，μk(zk)-H′τ，μk(zk)Δzk‖=O(‖Δzk‖2).

(24)

故由(12)，(23)和(24)，對(duì)充分大的k有

‖Hτ，μk(zk+Δzk)‖≤‖Hτ，μk(zk+Δzk)-Hτ，μk(zk)-H′τ，μk(zk)Δzk‖+‖rk‖

≤O(‖Δzk‖2)+η‖Hτ，μk(zk)‖min{1，‖Hτ，μk(zk)‖}

≤O(‖Hτ，μk(zk)‖2)+η‖Hτ，μk(zk)‖2=O(‖Hτ，μk(zk)‖2).

(25)

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

本節(jié)給出一些數(shù)值實(shí)驗(yàn)驗(yàn)證算法1的有效性.所有測(cè)試用Matlab(2018a)編程在Intel(R) Core(TM) i5-7300U CPU @2.60GHz 2.71 GHz 8GB內(nèi)存，Windows10專(zhuān)業(yè)版操作系統(tǒng)上實(shí)現(xiàn).測(cè)試中隨機(jī)生成向量q∈n和矩陣D∈n×n，令M=DTD.給定權(quán)向量w=(1，0，…，0)T∈，求解線(xiàn)性wSOCCP：

x∈，s=Mx+q∈，x°s=w.

選擇x0=s0=(1，1，…，1)T∈n作為初始點(diǎn).算法1中參數(shù)取值為

另外，當(dāng)μ≤10-6時(shí)算法1停止迭代.表1給出了取不同參數(shù)τ時(shí)，算法1求解線(xiàn)性wSOCCP所需的迭代次數(shù)和所占的CPU時(shí)間.其中Iter和cpu分別表示針對(duì)每個(gè)n運(yùn)行10次的平均迭代次數(shù)和平均CPU時(shí)間.

表1 運(yùn)用算法1求解不同規(guī)模的wSOCCP的數(shù)值結(jié)果

表1表明算法1求解規(guī)模較大的wSOCCP只需較少的迭代次數(shù)和CPU時(shí)間.取不同參數(shù)τ=3.8，τ=3.3和τ=2.6時(shí)，對(duì)迭代次數(shù)的影響較小.

6 結(jié) 論

運(yùn)用非精確非內(nèi)點(diǎn)連續(xù)化算法求解二階錐權(quán)互補(bǔ)問(wèn)題.算法在每次迭代過(guò)程中最多求解一個(gè)方程組.基于單調(diào)假設(shè)，證明了算法是全局與局部二階收斂的.從數(shù)值實(shí)驗(yàn)結(jié)果可知，算法求解不同規(guī)模的二階錐權(quán)互補(bǔ)問(wèn)題時(shí)，只需要較少的迭代次數(shù)，這表明了算法的良好性能.

致謝作者非常感謝相關(guān)文獻(xiàn)對(duì)本文的啟發(fā)以及審稿專(zhuān)家提出的寶貴意見(jiàn).