一類線性權(quán)互補問題的修正全牛頓步可行內(nèi)點算法

吳昕陽， 張睿婕， 遲曉妮， 王博妲

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

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

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

1 權(quán)互補問題

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

(1)

定義LWCP(1)的嚴格可行域為

1.1 中心路徑及搜索方向

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

(2)

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

(3)

當υ≥0時，易證

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

則方程組(2)可化為

(4)

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

(5)

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

定義

(6)

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

(7)

定義鄰近測度

(8)

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

因為dx與ds正交，由引理1和式(8)可得

(9)

同理可得

引理2[7]對任意υ∈Rn,有

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

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

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

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

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

(10)

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

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

當‖xs-ω‖≤ε時，算法迭代終止。

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

2)當‖xs-ω‖≤ε時，算法終止，否則，轉(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)

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

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

(13)

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

由于x(0)=x>0,s(0)=s>0,且x(α),s(α)與α呈線性關(guān)系，對α∈[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ù)值算例

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

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

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

表1 求解不同規(guī)模線性權(quá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為迭代過程中鄰近測度及Gap的值。從圖1可看出，隨著μ的減小，鄰近測度和Gap逐漸減小，并趨于0。

圖1 迭代過程中鄰近測度及Gap的值

4 結(jié)束語

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