線性權互補問題的全牛頓步可行內(nèi)點算法

王博妲, 遲曉妮,2,3, 崔然然

(1.桂林電子科技大學 數(shù)學與計算科學學院,廣西 桂林 541004;2.桂林電子科技大學 廣西自動檢測技術與儀器重點實驗室,廣西 桂林 541004;3.桂林電子科技大學 廣西高校數(shù)據(jù)分析與計算重點實驗室,廣西 桂林 541004)

權互補問題的概念是Potra[1]在2012年最先引入,是互補問題的推廣,它主要解決的問題是找到一對屬于一個流形與一個錐的交集的向量,使得它們在某個代數(shù)中的乘積等于一個給定的權向量。當權向量為零向量時,權互補問題退化為互補問題。權互補問題的理論比互補問題理論復雜得多,而且經(jīng)濟領域的Fisher市場均衡問題可以轉化為線性權互補模型求解[1],比通過建立非線性互補模型求解更有效。Anstreicher[2]提出Fisher 問題的廣義Eisenberg-Gale[3],被稱為線性規(guī)劃與權中心問題。Potra在文獻[1]中提出二次規(guī)劃與權中心問題可以轉化為單調(diào)線性權互補問題。之后,Potra[4]給出充分線性權互補問題的一些結論。但目前關于求解權互補問題的理論和算法尚不多見。光滑方法[5-6]和內(nèi)點算法是求解優(yōu)化問題的有效算法。Zhang等[7]運用光滑牛頓算法求解線性權互補問題,并證明了在適當?shù)臈l件下此算法具有局部二次收斂性。Roos[8]提出了線性規(guī)劃問題的全牛頓步不可行內(nèi)點算法,并證明了其收斂性及復雜度。文獻[9]提出了一種線性權互補問題的新全牛頓步可行內(nèi)點算法。文獻[10]提出了一種求解Rn上線性權互補問題的全牛頓步可行內(nèi)點算法。文獻[11-14]也對線性權互補問題進行了相關研究?；诖?將Roos[8]的內(nèi)點算法改進并推廣到權互補問題上,提出求解線性權互補問題的全牛頓步內(nèi)點算法。通過定義中心路徑,設計全牛頓步可行內(nèi)點算法來求解線性權互補問題,并分析了算法的可行性,證明了算法的多項式時間迭代復雜度。數(shù)值實驗驗證了算法的有效性。

1 權互補問題

Fisher市場均衡問題可建模為如下線性權互補問題[1]:

其中:A∈Rm×n;b∈Rm;c∈Rn。因而,本研究要尋找一向量對(x,y,s),使得

成立,其中:A∈Rm×n;b∈Rm;c、ω∈Rn,且ω>0。不失一般性,假設rank(A)=m。

當權互補問題(1)中ω=0時,線性權互補問題退化為線性互補問題:

其中e=(1,1,…,1)T。 本研究將Roos的線性規(guī)劃內(nèi)點算法[8]推廣到線性權互補問題,并證明其多項式時間迭代復雜度。

1.1 中心路徑

擾動問題線性權互補問題(1)得

其中,ω(t)∶=(1-t)ω+tκ,0≤t≤1,κ=x0s0,x0>0,s0>0,y0,t0=1為可行初始點。

若式(3)存在可行解(x,y,s)>0,則稱式(3)滿足內(nèi)點條件(IPC),這里用(x(t),y(t),s(t))表示原問題(1)的t-中心解。所有t-中心解的集合稱為原問題的中心路徑。更新t+=(1-θ)t,當t→0時,(x(t),y(t),s(t))收斂到一個極限點(x*,y*,s*),從而得到線性權互補問題(1)的解。

1.2 搜索方向

設可行點(x,y,s)為當前迭代點,(Δx,Δy,Δs)為搜索方向,則新的迭代點為

可得牛頓搜索方向(Δx,Δy,Δs)。因為矩陣A行滿秩,且向量x和s是正向量,易證上述方程組中的系數(shù)矩陣非奇異。因此,方程組(6)定義了唯一的搜索方向(Δx,Δy,Δs)。

由式(6)的前2個式子知,Δx屬于矩陣A的零空間,且Δs屬于矩陣A的行空間,因此Δx和Δs正交,即

定義鄰近測度:

δ(x,s;t)∶=δ(v,t)∶=‖ω(t)v-1-v‖。

在本算法中,δ(x,s;t)是一個度量(x,y,s)與中心解(x(t),y(t),s(t))的距離的量。當t→0時,若δ(x,s;t)=0,則ωv-1-v=0,即xs=ω。又有x,s滿足Ax=b,ATy+s=c,則(x,y,s)是原問題的解。

2 全牛頓步內(nèi)點算法

設參數(shù)ε是給定的精度參數(shù),若‖x k s k-ω‖<ε,則算法終止;否則進行下一步迭代,令t∶=(1-θ)t更新t,其中0<θ<1是更新參數(shù)。由當前的t求解新的搜索方向,根據(jù)式(4)得出新的迭代點。隨著迭代次數(shù)的增加,t→0,找到滿足給定精度的迭代點,從而得到權互補問題(1)的近似解。

算法1 線性權互補問題的全牛頓步內(nèi)點算法

1)若‖x s-ω‖<ε,則算法停止;否則,轉步驟2)。

2)令t∶=(1-θ)t,解方程組(6),得到搜索方向(Δx,Δy,Δs)。

3)令(x,y,s)∶=(x,y,s)+(Δx,Δy,Δs),轉步驟1)。

3 可行性分析

引理1[15]若u與v正交,則

又由式(8)可知

下述引理將給出下一迭代點在t更新之后的鄰近測度的上界。

4 復雜度分析

定理1 若線性權互補問題(1)的可行點初始點為(x0,y0,s0),則算法至少經(jīng)過次迭代后可得到權互補問題(1)的近似最優(yōu)解。

5 數(shù)值算例

為了檢驗算法1 的有效性,運用MATLAB(R2016b)編程,在Intel(R)Core(TM)i5-8250U CPU@1.80 GHz 8 GiB 內(nèi)存,64 位操作系統(tǒng),Windows 10系統(tǒng)的計算機上進行數(shù)值實驗。

表1、表2和表3分別為用內(nèi)點算法求解β≥1,β≥5,β≥10情況下的權互補問題的迭代次數(shù)和運行時間。

表1 算法1求解β≥1線性權互補問題的數(shù)值結果

表2 算法1求解β≥5線性權互補問題的數(shù)值結果

表3 算法1求解β≥10線性權互補問題的數(shù)值結果

例1 考慮形如式(1)的線性權互補問題,其中

6 結束語

提出了一種求解線性權互補問題的全牛頓步內(nèi)點算法。給出其擾動問題,定義中心路徑設計內(nèi)點算法求解權互補問題(1),對算法進行可行性和復雜度分析,并給出線性權互補問題的數(shù)值算例。數(shù)值實驗結果表明,算法是有效的。