劉文麗， 遲曉妮,2,3， 張 璐， 李紹剛

(1.桂林電子科技大學 數(shù)學與計算科學學院，廣西 桂林 541004;2.桂林電子科技大學 廣西自動檢測技術(shù)與儀器重點實驗室，廣西 桂林 541004;3.桂林電子科技大學 廣西密碼學與信息安全重點實驗室，廣西 桂林 541004)

非負象限權(quán)互補問題(wCP)定義為尋找一組向量(x,s)∈Rn×Rn，使得

(1)

其中xs=(x1s1,x2s2,…,xnsn)T∈Rn,ω≥0為給定權(quán)向量,f(x):Rn→Rn是連續(xù)可微函數(shù)。若f(x)為線性函數(shù),則對應的權(quán)互補問題是非負象限線性權(quán)互補問題,否則為非負象限非線性權(quán)互補問題。由式(1)知,當權(quán)向量ω=0時,wCP退化為互補問題(CP)。

wCP最早由Potra[1]提出。該問題在金融、大氣、化學等領(lǐng)域有著重要應用,如Fisher市場均衡問題[1]及線性規(guī)劃與加權(quán)中心問題[2]等皆可通過建立權(quán)互補問題來求解。雖然帶有非零權(quán)向量的wCP比一般的CP理論更加復雜,但wCP模型在某些情況下會提供一個更有效的數(shù)值解法。目前關(guān)于wCP理論和算法研究已取得了一定的成果。Potra[1]提出了求解非負象限上單調(diào)線性wCP的2種內(nèi)點算法,并建立了算法的計算復雜度。2019年,Gowda[3]研究了歐幾里得約當代數(shù)上線性wCP和內(nèi)點系統(tǒng)的共正線性變換。張睿婕等[4]給出一種求解線性wCP的全牛頓步可行內(nèi)點算法,定義了迭代點到中心路徑的鄰近測度,并證明了算法具有多項式時間迭代復雜度。

光滑牛頓法因其理論上良好的收斂性,被廣泛用于CP的求解[5-8],因此利用光滑牛頓法求解wCP引起了眾多學者關(guān)注。Zhang[9]運用光滑牛頓法求解單調(diào)線性wCP,證明了在適當假設(shè)下算法是局部二次收斂的。Tang[10]給出求解線性wCP的光滑方法,并在非嚴格互補條件下分析了算法的全局和局部二次收斂性。遲曉妮等[11]研究了求解二階錐wCP的光滑牛頓法,證明了算法的全局和局部超線性收斂性質(zhì)。

針對非線性方程組問題,Griewank[12]最先提出免導數(shù)搜索技術(shù),該搜索技術(shù)使得算法不依賴于目標函數(shù)的雅可比矩陣，但當目標函數(shù)的范數(shù)和目標函數(shù)正交時,該搜索技術(shù)可能會搜索失敗,因此Li等[13]給出了新的免導數(shù)搜索技術(shù)。免導數(shù)搜索技術(shù)被用于各類優(yōu)化問題的求解[14-16]。最近，Tang等[17]研究了求解圓錐非線性互補問題的光滑牛頓法,采用新的免導數(shù)非單調(diào)線搜索技術(shù)，確保了其全局和局部超線性收斂性和二次收斂性。

基于此，構(gòu)造一個新的權(quán)互補光滑函數(shù),并分析其性質(zhì),然后基于該函數(shù)將式(1)轉(zhuǎn)化為光滑方程組。結(jié)合文獻[13,17-18]的算法思想,提出求解該方程新的免導數(shù)非單調(diào)光滑牛頓法，在一定條件下證明算法的全局收斂性,并通過數(shù)值算例驗證算法的有效性。

1 光滑函數(shù)及其性質(zhì)

給定權(quán)向量ω≥0,構(gòu)造式(1)的一個新光滑函數(shù)Φ(μ,a,b):R×R×R→R:

(2)

其中α≥0為實參數(shù)。若ω=0,易證Φ(μ,a,b)退化為CP的光滑函數(shù)

若α=0,則Φ(μ,a,b)退化為Chen-Harker-Kanzow-Smale權(quán)互補光滑函數(shù)[10]

命題1對任意ω,α≥0,函數(shù)Φ(μ,a,b)滿足如下性質(zhì)。

1)Φ(0,a,b)是權(quán)互補函數(shù),即

Φ(0,a,b)=0?a、b≥0,ab=ω,

(3)

2)Φ(μ,a,b)處處連續(xù)可微,強半光滑,且若(a,b)≠(0,0),

否則

aΦ(μ,a,b)=bΦ(μ,a,b)=0,

證明由函數(shù)Φ(μ,a,b)的定義和引理5.1[19]知，Φ(μ,a,b)連續(xù)可微且強半光滑,結(jié)合導數(shù)鏈式法則可得2)成立。以下證明1)成立。

1)必要性顯然成立。設(shè)Φ(0,a,b)=0,根據(jù)a不同取值分情況討論。

即ab=ω,這與假設(shè)ab-ω<0矛盾,因而該種情況不存在；若ab-ω>0,有

即

4(ab-ω)。

因ab-ω>0，則

(4)

由α的任意性知式(4)不成立,故該種情況不存在.

綜上所述,Φ(0,a,b)=0，當且僅當a,b≥0且ab=ω成立。證畢。

(5)

由式(1)～(3)式知，z*=(μ*,x*,s*)是G(z)=0的解當且僅當(0,x*,s*)是非負象限上wCP(1)的解。

定義1[20]P0矩陣和P0函數(shù)定義如下：

1)若矩陣N∈Rn×n的所有主子式非負,則N為P0矩陣。

2)設(shè)函數(shù)F∶Rn→Rn,對任意x,y∈Rn且x≠y,存在指標i0∈{1,2,…,n}，使得

xi0≠yi0,(xi0-yi0)(Fi0(x)-Fi0(y))≥0

成立,則稱F為P0函數(shù)。

引理1[20]設(shè)F:Rn→Rn是連續(xù)可微函數(shù),則對任意x∈Rn,F(x)是P0矩陣當且僅當F是P0函數(shù)。

定理1若G(z)如式(5)定義,則以下結(jié)論成立。

(6)

其中：

(7)

(8)

i=1,2,…,n。

2)設(shè)函數(shù)f連續(xù)可微且單調(diào),則G(z)在任意點z(μ,x,s)∈R++×Rn×Rn處非奇異。

證明由命題1式(2)得式(1)成立。由于f為單調(diào)函數(shù),由定義1式(2)和引理1知，f(x)為P0矩陣,又因D2和D3為負對角矩陣,則對任意μ>0,

是非奇異的。證畢。

2 免導數(shù)非單調(diào)光滑牛頓法

定義

算法1非負象限wCP的免導數(shù)非單調(diào)光滑牛頓法

3)解以下方程組，得搜索方向

G(zk)+G(zk)Δzk=0。

(9)

4)令λk=δmk,mk為滿足

(10)

的最小非負整數(shù)，其中：

Qk+1=ηkQk+1；

(11)

(12)

成立。

引理3[21]對任意μ>0,有

引理4設(shè){μk}為算法1生成的迭代序列，則對任意k,有μk≥0,且{μk}為遞減序列。

證明由式(9)知，

(13)

假設(shè)μk>0,由引理1和式(13)，對任意λk∈(0,1]有

μk+1=μk+λkΔμk≥(1-λk)μk≥0。

又因μ0>0,故μk≥0。再由式(13)得Δμk=e-μk-1≤0,從而

μk+1=μk+λkΔμk≤μk+λk(e-μk-1)≤μk。

證畢。

引理5若函數(shù)f連續(xù)可微且單調(diào),則算法1適定，且對任意k≥0有H(zk)≤Ck成立。

證明由定理1和引理4知，G(z)非奇異,故步2)適定。假設(shè)對任意k有H(zk)≤Ck成立,將式(11)、(12)代入式(10)得

(14)

則步3適定。由步3)得

(15)

根據(jù)式(12)、(15)有

(16)

從而結(jié)合式(16)和H(z0)=C0得H(zk)≤Ck。證畢。

引理6設(shè){zk}是算法1生成的迭代數(shù)列,則{zk}包含于如下水平集中：

證明由式(10)、(16)知，

(17)

由引理2[13]可得

(18)

從而結(jié)合式(17)、(18)得H(zk+1)≤eξH(z0),且顯然H(z0)≤eξH(z0)。證畢。

3 收斂性分析

G(z*)+G(z*)Δz*=0。

(19)

因?qū)θ我鈑≥0有λk≥0,故考慮以下2種情況：

G(z*)=0。

根據(jù)引理5得

即

(20)

對式(20)兩邊取極限得

2G(z*)TG(z*)Δz*≥0。

結(jié)合式(19)有

0≤G(z*)TG(z*)Δz*=-‖G(z*)‖2≤0,

即G(z*)=0。證畢。

4 數(shù)值算例

運用MATLAB R2014在Intel(R) core(TM) i5-5200 CPU 2.7 GHz 4.0 GiB內(nèi)存,Windows 7操作系統(tǒng)的計算機上編程。每個算例均以G(z)≤10-8為算法終止條件,且σ=0.05,μ0=0.01,δ=0.5,ξk=2-k。

例1對于wCP式(1),令f(x)=Mx+q,即考慮如下線性非負象限權(quán)互補問題：

其中M為P0矩陣,向量q∈Rn。

隨機生成向量q∈Rn和矩陣N∈Rn×n,定義M=NTN，x*=5×rand(n,1),s*=Mx*+q，ω*=x*s*。選取初始點x0=rand(n,1),設(shè)s0=Mx0+q。問題規(guī)模n為100～600,取參數(shù)ηk=1/2k+1,且隨機生成10個問題進行求解。算法1求解不同規(guī)模的線性wCP的數(shù)值結(jié)果如表1所示，其中AIT為平均迭代次數(shù),ACPU為平均CPU時間，AOBJ為算法終止時的平均值。

表1 算法1求解不同規(guī)模的線性wCP的數(shù)值結(jié)果

由表1可知,算法1可有效求解非負象限線性wCP,且所需的迭代次數(shù)較少,時間較短,因而算法性能高效穩(wěn)定。

例2考慮非負象限非線性權(quán)互補問題：

其中f∶R4→R4為連續(xù)可微單調(diào)函數(shù),定義

實驗所需數(shù)據(jù)按以下方式生成：生成向量x*=rand(n,1),令s*=f(x*)和ω*=x*s*。選取初始點x0=rand(n,1)，s0=f(x0),令控制非單調(diào)搜索程度的參數(shù)ηk分別取1/2k+1,1/3k+1,1/4k+1,1/5k+1,數(shù)值結(jié)果如表2所示，其中AOBJ為算法終止時的值。

表2 算法1求解不同ηk的非線性wCP的數(shù)值結(jié)果

由表2可知,算法1能夠有效求解非負象限非線性wCP問題,收斂速度快，且迭代次數(shù)少。

5 結(jié)束語

針對非負象限權(quán)互補問題,提出一種免導數(shù)的非單調(diào)光滑牛頓法，并證明了算法的適定性及收斂性,數(shù)值算例表明了算法的可行性和有效性。如何證明本算法的局部收斂性和利用算法解決Fisher市場均衡問題等實際問題，可作為進一步研究的內(nèi)容。