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

曾 榮

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

1 引 言

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

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

(1)

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

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

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連續(xù)且強半光滑，若μ>0，令則φτ，μ(x，s)連續(xù)可微，且對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連續(xù)且強半光滑，若μ>0，對任意z∶=(x，s)∈n×n，Hτ，μ(z)連續(xù)可微其雅可比為

(6)

(ii) 若F(x)連續(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(xiàn)′(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(非精確非內點連續(xù)化算法)

步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)是連續(xù)可微且單調的，則算法1適定.

證由算法1知μk>0，而F(x)連續(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處連續(xù)可微，故由(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)是連續(xù)可微且單調的，則

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

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

4 收斂性分析

本節(jié)給出算法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 數值實驗

本節(jié)給出一些數值實驗驗證算法1的有效性.所有測試用Matlab(2018a)編程在Intel(R) Core(TM) i5-7300U CPU @2.60GHz 2.71 GHz 8GB內存，Windows10專業(yè)版操作系統(tǒng)上實現(xiàn).測試中隨機生成向量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求解不同規(guī)模的wSOCCP的數值結果

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

6 結 論

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

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