線性權互補問題基于核函數(shù)的全牛頓步可行內(nèi)點算法

張睿婕， 遲曉妮，2，3， 劉文麗

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

權互補問題最先由Potra[1]提出，是一類新的優(yōu)化問題，且互補問題[2]是該類問題的一種特殊形式?；パa問題與不動點問題、變分不等式及數(shù)學規(guī)劃等有著密切聯(lián)系[3]，在經(jīng)濟學和工程中有著廣泛應用。科學和工程領域一大類問題可以轉化為權互補問題[4]，甚至相比于建立互補模型求解問題，利用權互補模型求解在某些情況下會得到一個更高效的數(shù)值解。Roos等[5]首次提出求解線性規(guī)劃的對數(shù)障礙核函數(shù)內(nèi)點算法和全牛頓步內(nèi)點算法。隨后，Peng等[6]和Bai等[7]相繼設計了新的核函數(shù)，并基于新核函數(shù)提出求解線性規(guī)劃的內(nèi)點算法。Potra等[8]設計了一種預估-校正內(nèi)點算法用于求解充分權互補問題。寧小玲等[9]提出了求解線性權互補問題的一種改進全牛頓步可行內(nèi)點算法。

鑒于此，將線性互補問題的可行內(nèi)點算法推廣到權互補問題，運用文獻[10]中核函數(shù)，得到新的牛頓搜索方向，并基于全牛頓步給出求解非負象限上線性權互補問題的可行內(nèi)點算法。定義了迭代點到中心路徑的鄰近測度，證明了該算法的可行性及迭代復雜度。數(shù)值算例結果表明了算法的有效性。

1 算法

考慮Rn上的線性權互補問題(WCP)[1]：尋找向量對(x,y,s)∈Rn×Rm×Rn，使得

(1)

其中A∈Rm×n,b∈Rm,c∈Rn,ω≥0。定義方程組(1)的嚴格可行域：

F0=

(2)

其中，

ω(t)=tx0s0+(1-t)ω,t∈[0,1]。

初始點(x0,y0,s0)∈F0。假定A為行滿秩矩陣，即R(A)=m。若內(nèi)點條件(IPC)[5]成立，即(x,y,s)∈F0,則對任意參數(shù)00}稱為方程組(1)的中心路徑。當t→0時，ω(t)→ω,可得方程組(1)的最優(yōu)解。

求解如下方程組，得牛頓搜索方向(Δx,Δy,Δs)：

(3)

定義

(4)

由式(4)，方程組(3)可化為

(5)

方程組(5)中υ-1-υ為對數(shù)障礙函數(shù)

考慮Zhang等[10]提出的局部核函數(shù)φ(t)：=(1-t)2,用dx+ds=2(e-υ)替換方程組(5)中第3式，得

(6)

定義鄰近測度：

(7)

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

‖e-υ‖2=δ(υ)2。

(8)

同理，可得

(9)

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

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

選取適當參數(shù)θ及任意初始點x0,s0>0,y0=0。令ω(t0)=x0s0,其中t0=1。顯然δ(x0,s0,ω(t0))=0。求解方程組(6)，并結合式(4)可得牛頓搜索方向(Δx,Δy,Δs),其中t+=(1-θ)t,θ∈(0,1)。令新迭代點

x+：=x+Δx,y+：=y+Δy,s+：=s+Δs

(10)

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

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

算法1求解線性WCP基于核函數(shù)的全牛頓步可行內(nèi)點算法。

1)選擇參數(shù)t0=1,ε>0,初始點(x0,y0,s0)∈F0，y0=0，且ω(t0)=x0s0。置k：=0。

2)當‖xs-ω‖≤ε算法終止，否則轉步驟3)。

3)求解方程組(6)，并結合式(4)，得搜索方向(Δx,Δy,Δs)。令

x：=x+Δx，y:=y+Δy,s:=s+Δs，

t：=(1-θ)t，ω(t)=tx0s0+(1-t)ω，θ∈(0,1)。

置k：=k+1，轉步驟2)。

2 算法分析

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

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

由式(4)和方程組(6)得

x(α)s(α)=xs+α(sΔx+xΔs)+α2ΔxΔs=

ω(t)[υ2+2α(υ-υ2)+α2dxds]=

ω(t)[(1-α)υ2+α(2υ-υ2)+α2dxds]。

(11)

又由式(8)和引理2得,

min{2υ-υ2+αdxds}≥min(2υ-υ2)-

‖dxds‖∞≥2(1+δ(υ))-

(1+δ(υ))2-‖dxds‖∞≥1-2δ(υ)2。

(12)

因為ω(t)>0,(1-α)υ2>0,所以由式(11)、(12)知,若

(13)

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

由于x(0)=x>0,s(0)=s>0,且x(α),s(α)與α呈線性關系，對α∈[0,1]，有x(α)>0，s(α)>0，相應地，x(1)>0，s(1)>0。證畢。

引理4令

證明由式(7)、(9)、(11)得,

‖e-(2υ-υ2)-dxds‖≤

(14)

引理5令

證明由式(9)，(11)和引理2得

‖(υ+)2‖=‖2υ-υ2+dxds‖≤‖e‖+

引理6令

則

‖e-(υ+)2‖≤‖e-(υ+)2‖+

證明因為ω(t+)=ω(t)+θt(ω-x0s0)，所以

(15)

由式(15)和引理5得,

‖e-(υ+)2‖≤‖e-(υ+)2‖+

引理7令δ(υ+)：=‖e-υ+‖，則

證明由引理4、6得,

(16)

引理8令

證明由引理7得

(17)

(18)

設

(19)

其中t+=(1-θ)t,θ∈(0,1)?；喪?19)得

因此，令

3 復雜度分析

由于初始迭代點滿足

選取

(20)

‖x+s+-ω‖≤

證明由式(11)和引理4得，

‖x+s+-ω‖≤‖x+s+-ω(t)‖+‖ω(t)-ω‖≤

‖ω(t)((υ+)2-e)‖+t‖x0s0-ω‖≤

‖x+s+-ω‖≤

引理10若線性WCP(1)存在最優(yōu)解，則算法1至多經(jīng)過

次迭代得到WCP(1)的ε近似解。

證明因為

‖ω(t)‖∞≤max{max(x0s0),max(ω)},

所以由引理9可得,

由式(20)可知，

故迭代次數(shù)的上界為

4 數(shù)值算例

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

首先選取任意初始點(x0,y0,s0),權向量ω>0,按照式(20)選擇參數(shù)θ，K。在算法1中令t0=1,ε=10-5。隨機生成行滿秩矩陣A∈Rm×n。令b=Ax0,c=ATy0+s0,即初始點滿足內(nèi)點條件。算法的終止條件為‖xs-ω‖≤ε,記Gap=‖xs-ω‖。表1～3為K值上界的選取影響算法1求解不同規(guī)模WCP的數(shù)值結果，表中數(shù)據(jù)均為求解不同規(guī)模的WCP10次結果的平均值，其中Iter為平均迭代次數(shù)，Time為平均運行時間。從表1～3可看出，在K值上界確定的情況下，運行時間和迭代次數(shù)受m和n的影響。

表1 K≤4時求解不同規(guī)模WCP的數(shù)值結果

表2 K≤2時求解不同規(guī)模WCP的數(shù)值結果

表3 K≤0.5時求解不同規(guī)模WCP的數(shù)值結果

例1考慮R4上的線性WCP方程組(1)，其中：

取初始點

x0=(1,1,3,2)T,y0=(0,0,0)T,

s0=(2,1,2,1)T,t0=1。

用算法1進行求解該問題，迭代95次后得到最優(yōu)解

x*=(1.063,0.619,2.619,1.873)T,
y*=(0.242,-0.855,-0.894)T,
s*=(2.821,1.613,1.145,2.135)T。

圖1為迭代過程中鄰近測度及Gap的值。由圖1可知，隨著t從1減小至0，Gap逐漸減小并趨于0，且每步迭代鄰近測度都小于2t/5，保障了每一步迭代點的可行性。

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

5 結束語

基于核函數(shù)，將線性優(yōu)化的全牛頓步可行內(nèi)點算法推廣至線性權互補問題。分析了算法的可行性，并證明了該算法具有目前線性優(yōu)化最好的多項式時間迭代復雜度。數(shù)值實驗表明了該算法的有效性。設計基于核函數(shù)的全牛頓不可行內(nèi)點算法求解線性權互補問題是進一步的研究方向。