吳昕陽(yáng)， 張睿婕， 遲曉妮， 王博妲

(桂林電子科技大學(xué) 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,廣西 桂林 541004)

權(quán)互補(bǔ)問(wèn)題(weighted complementarity problem, 簡(jiǎn)稱WCP)是一類新的優(yōu)化問(wèn)題，目前關(guān)于權(quán)互補(bǔ)問(wèn)題的理論和算法研究較少。Potra[1]最先提出權(quán)互補(bǔ)的概念，即找到一對(duì)屬于一個(gè)流形與一個(gè)錐的交集的向量，使得它們?cè)谀硞€(gè)代數(shù)中的乘積等于一個(gè)給定的權(quán)向量。當(dāng)權(quán)向量為零向量時(shí)，權(quán)互補(bǔ)問(wèn)題退化為互補(bǔ)問(wèn)題。Potra[1]將Fisher市場(chǎng)均衡問(wèn)題、二次規(guī)劃與權(quán)中心問(wèn)題轉(zhuǎn)化為單調(diào)線性權(quán)互補(bǔ)問(wèn)題，并提出了求解單調(diào)線性權(quán)互補(bǔ)問(wèn)題的2種內(nèi)點(diǎn)算法。之后，Potra[2]又證明了充分線性權(quán)互補(bǔ)問(wèn)題的一些基本結(jié)論，設(shè)計(jì)了一種校正-預(yù)估內(nèi)點(diǎn)算法。目前,光滑牛頓法[3,9]和內(nèi)點(diǎn)算法[10]是求解線性優(yōu)化、互補(bǔ)問(wèn)題[11-12]和權(quán)互補(bǔ)問(wèn)題[13]等的有效算法，其中內(nèi)點(diǎn)算法由于具有多項(xiàng)式時(shí)間復(fù)雜度[14]而備受關(guān)注。Kojima等[4-5]給出了線性互補(bǔ)問(wèn)題的原對(duì)偶內(nèi)點(diǎn)算法及其復(fù)雜度。Roos等[6]首次提出了線性規(guī)劃的全牛頓步可行內(nèi)點(diǎn)算法。隨后，Zhang等[7]基于修正牛頓方向提出了新的全牛頓步可行內(nèi)點(diǎn)算法。Xu[8]給出了線性規(guī)劃的基于修正全牛頓方向的不可行內(nèi)點(diǎn)算法，并證明了該算法在適當(dāng)條件下具有良好的復(fù)雜度上界。Asadi 等[15]提出了求解單調(diào)線性權(quán)互補(bǔ)問(wèn)題的全牛頓步可行內(nèi)點(diǎn)算法。

鑒于此，基于Xu[8]提出的修正全牛頓步，提出一種求解非負(fù)象限上線性權(quán)互補(bǔ)問(wèn)題(LWCP)的可行內(nèi)點(diǎn)算法。本算法采用修正全牛頓步，避免了線性搜索，簡(jiǎn)化了算法分析，且保證了迭代點(diǎn)都位于中心路徑的窄鄰域內(nèi)，最后分析了算法的可行性、收斂性及復(fù)雜度。數(shù)值算例結(jié)果表明，本算法是有效的。

1 權(quán)互補(bǔ)問(wèn)題

考慮Rn上的LWCP[1]：找到一向量對(duì)(x,y,s)∈Rn×Rm×Rn使得

(1)

定義LWCP(1)的嚴(yán)格可行域?yàn)?/p>

1.1 中心路徑及搜索方向

由于直接求解LWCP(1)比較困難，用xs-ω=μe代替xs-ω=0,求解方程組

(2)

假定A是行滿秩矩陣，即R(A)=m。若內(nèi)點(diǎn)條件(IPC)[6]成立，即(x,y,s)∈F0,則對(duì)任意參數(shù)μ>0,方程組(2)有唯一解(x(μ),y(μ),s(μ)),稱之為L(zhǎng)WCP(1)的μ-中心。所有μ-中心的集合{(x(μ),y(μ),s(μ))|μ>0}稱為L(zhǎng)WCP(1)的中心路徑。當(dāng)μ→0時(shí)，中心路徑的極限點(diǎn)便是LWCP(1)的最優(yōu)解。當(dāng)xs-ω≥0時(shí)，定義

(3)

當(dāng)υ≥0時(shí)，易證

xs-ω=μe?υ2=e?υ=e?υ2=υ。

則方程組(2)可化為

(4)

其中，μ+=(1-θ)μ,θ∈(0,1)。因而，通過(guò)求解方程組

(5)

可得牛頓搜索方向(Δx,Δy,Δs)。

定義

(6)

由式(3)、(6)，方程組(5)可化為

(7)

定義鄰近測(cè)度

(8)

引理1[6]若u與v正交，則

因?yàn)閐x與ds正交，由引理1和式(8)可得

(9)

同理可得

引理2[7]對(duì)任意υ∈Rn,有

1-δ(υ)≤υi≤1+δ(υ),i=1,2,…,n。

1.2 修正全牛頓步可行內(nèi)點(diǎn)算法

設(shè)μ0>0,(x0,y0,s0)∈F0,選擇適當(dāng)參數(shù)θ,ε,τ,使得

δ(x0,s0,μ0)≤τ。

在修正全牛頓步中，求解方程組(5)得牛頓搜索方向(Δx,Δy,Δs),其中μ+=(1-θ)μ,θ∈(0,1)。令新迭代點(diǎn)

(10)

滿足內(nèi)點(diǎn)條件，且

δ(x+,s+;μ+)≤τ，

當(dāng)‖xs-ω‖≤ε時(shí)，算法迭代終止。

算法1求解LWCP的修正全牛頓步可行內(nèi)點(diǎn)算法

2)當(dāng)‖xs-ω‖≤ε時(shí)，算法終止，否則，轉(zhuǎn)步驟3)。

3)求解方程組(5)，得搜索方向(Δx,Δy,Δs)。令

2 算法分析

2.1 可行性和收斂性分析

引理3若‖dxds‖∞<(1-θ)(1-δ(υ)),則(x+,y+,s+)∈F0。

證明令α∈[0,1],記

x(α)=x+αΔx,y(α)=y+αΔy,s(α)=s+αΔs。

則由式(3)、(6)和方程組(7)中第3式得

(11)

(12)

又因?yàn)?1-α)υ2>0,所以由式(12)、(13)知，若

‖dxds‖∞<(1-θ)(1-δ(υ)),

(13)

則x(α)s(α)-ω>0。

由于x(0)=x>0,s(0)=s>0,且x(α),s(α)與α呈線性關(guān)系，對(duì)α∈[0,1]，有x(α)，s(α)>0。相應(yīng)地，x(1)，s(1)>0。證畢。

證明由式(9)和引理3知，若

(14)

(15)

證明由式(11)得

引理6若(x+,y+,s+)∈F0,則

證明由引理5知，

因此，

由引理2可得

引理7若(x+,y+,s+)∈F0,則

證明由引理5得

證明由δ(υ+)的定義式(8)得

因此，由引理6得

由式(9)、(*)可知，

(16)

(17)

(18)

2.2 復(fù)雜度分析

(19)

又由引理5得

(1-θ)nμ‖υ‖∞+nμ‖dxds‖∞。

(20)

則根據(jù)式(12)、(21)和引理2 可知，

[2(1-θ)nμ]2。

次迭代，才能得到LWCP(1)的ε-近似解。

因此要使‖xksk-ω‖≤ε,只需

[2(1-θ)nμk-1]2=[2(1-θ)knμ0]2。

3 數(shù)值算例

為檢驗(yàn)算法1的有效性，運(yùn)用MATLAB R2016b編程，在Intel?Core i5 CPU 2.3 GHz，8.0 GiB內(nèi)存，IOS操作系統(tǒng)的計(jì)算機(jī)上進(jìn)行數(shù)值實(shí)驗(yàn)。隨機(jī)生成5個(gè)不同規(guī)模的LWCP(1)，對(duì)每種規(guī)模產(chǎn)生10個(gè)問(wèn)題進(jìn)行求解。

任意選取參數(shù)μ0>0,起始點(diǎn)(x0,y0,s0)及權(quán)向量ω≥0，使得δ(x0,s0;μ0)≤τ。隨機(jī)生成行滿秩矩陣A∈Rm×n。令b=Ax0,c=ATy0+s0,即初始點(diǎn)滿足內(nèi)點(diǎn)條件。算法的終止條件為‖xs-ω‖≤ε，記Gap=‖xs-ω‖。在算法1中取參數(shù)

表1為算法1求解不同規(guī)模的LWCP(1)的數(shù)值結(jié)果，其中數(shù)據(jù)為10次結(jié)果的平均值。

表1 求解不同規(guī)模線性權(quán)互補(bǔ)問(wèn)題的數(shù)值結(jié)果

例1考慮R3上的LWCP(1)，其中

x*=(2.477,1.477,2.000)T,y*=(0.385,0.499)T,s*=(1.615,3.385,1.500)T。圖1為迭代過(guò)程中鄰近測(cè)度及Gap的值。從圖1可看出，隨著μ的減小，鄰近測(cè)度和Gap逐漸減小，并趨于0。

圖1 迭代過(guò)程中鄰近測(cè)度及Gap的值

4 結(jié)束語(yǔ)

提出了求解一類線性權(quán)互補(bǔ)問(wèn)題的一種修正全牛頓步內(nèi)點(diǎn)算法。該算法基于中心路徑的等價(jià)變換，得到搜索方向。證明了算法經(jīng)過(guò)修正全牛頓步后生成的迭代點(diǎn)仍嚴(yán)格可行，且具有多項(xiàng)式時(shí)間復(fù)雜度。數(shù)值算例表明了算法的可行性。