二階錐權互補問題的非精確非內點連續化算法

曾 榮

(廣東東軟學院 基礎教學院， 廣東 佛山528000)

1 引 言

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

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

(1)

近年來，權互補問題的理論和算法研究已取得了一些成果[1-2].權互補問題可以被應用于經濟學中，如Fisher市場均衡問題，二次規劃和權中心問題等都可以被轉化為權互補問題進行求解.基于這些研究工作，二階錐上的權互補問題的求解方法也陸續受到關注[3-4].

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

2 預備知識

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

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

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

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

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

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

3 算法設計

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

(2)

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

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

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

(3)

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

證因為

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

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

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

(4)

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

當λ(x，s)>0時

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

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

(5)

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

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

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

(6)

(ii) 若F(x)連續可微且單調，則當μ>0時，H′τ，μ(z)可逆.

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

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

(7)

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

(8)

因為F(x)單調，結合(7)知

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

(9)

將(8)兩邊同時乘Lc有

(10)

而由c定義知

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

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

結合(9)得到

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

(11)

又因為

算法1(非精確非內點連續化算法)

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

步1 若μk=0，停止.

步2 若‖Hτ，μk(zk)‖=0，則zk+1∶=zk且θk∶=1，轉步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為初始點，且

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

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

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

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

(16)

因為μk>0，由定理3(i)知Hτ，μk(zk)在zk處連續可微，故由(16)有‖g(θ)‖=o(θ).結合(12)，(16)和

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

對任意θ∈(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適定.當Hτ，μk(zk)≠0時，由(13)-(15)和引理2知

(17)

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

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

引理5設函數F(x)是連續可微且單調的，則

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

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

4 收斂性分析

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

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

又根據(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)

另一方面，根據步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，當k→∞則有‖Hτ，0(z*)‖=‖Hτ，μ*(z*)‖≤βμ*，而μ*=0，故Hτ，0(z*)=0.定理得證.

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

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

結合步4知

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

(22)

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

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

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

(23)

另外，根據定理3(i)得到Hτ，μk(·)在點zk+Δzk處強半光滑，即對充分大的k，

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

(24)

故由(12)，(23)和(24)，對充分大的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 數值實驗

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

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

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

另外，當μ≤10-6時算法1停止迭代.表1給出了取不同參數τ時，算法1求解線性wSOCCP所需的迭代次數和所占的CPU時間.其中Iter和cpu分別表示針對每個n運行10次的平均迭代次數和平均CPU時間.

表1 運用算法1求解不同規模的wSOCCP的數值結果

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

6 結 論

運用非精確非內點連續化算法求解二階錐權互補問題.算法在每次迭代過程中最多求解一個方程組.基于單調假設，證明了算法是全局與局部二階收斂的.從數值實驗結果可知，算法求解不同規模的二階錐權互補問題時，只需要較少的迭代次數，這表明了算法的良好性能.

致謝作者非常感謝相關文獻對本文的啟發以及審稿專家提出的寶貴意見.