線性權(quán)互補(bǔ)問題的一種改進(jìn)全牛頓步可行內(nèi)點(diǎn)算法

寧小玲， 王博妲， 遲曉妮,2,3

(1.桂林電子科技大學(xué) 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院，廣西 桂林 541004；2. 桂林電子科技大學(xué) 廣西自動(dòng)檢測技術(shù)與儀器重點(diǎn)實(shí)驗(yàn)室,廣西 桂林 541004；3. 桂林電子科技大學(xué) 廣西密碼學(xué)與信息安全重點(diǎn)實(shí)驗(yàn)室, 廣西 桂林 541004)

權(quán)互補(bǔ)問題是一類相對較新的優(yōu)化問題，它是標(biāo)準(zhǔn)互補(bǔ)問題的推廣。2012年，Potra[1]提出權(quán)互補(bǔ)模型可以更高效求解經(jīng)濟(jì)學(xué)中的一些均衡問題。例如，經(jīng)濟(jì)領(lǐng)域的Fisher市場均衡問題可以轉(zhuǎn)化為線性權(quán)互補(bǔ)模型求解，比通過建立非線性互補(bǔ)模型求解更有效。2008年，Ye[2]提出了一種求解線性權(quán)互補(bǔ)問題特定實(shí)例的數(shù)值方法。隨后，Anstreicher[3]改進(jìn)了Ye求解Fisher問題的計(jì)算復(fù)雜度。Potra[1]提出的二次規(guī)劃與權(quán)中心問題可以退化為單調(diào)線性權(quán)互補(bǔ)問題。2016年，Potra[4]又給出了充分線性權(quán)互補(bǔ)問題的一些基本理論。Zhang[5]運(yùn)用光滑牛頓算法求解了線性權(quán)互補(bǔ)問題。2019年，Chi等[6]給出了歐幾里德約當(dāng)代數(shù)上線性權(quán)互補(bǔ)問題的一些解的存在性和唯一性結(jié)果。由于非零權(quán)向量的存在，使得權(quán)互補(bǔ)問題的理論和算法都比互補(bǔ)問題復(fù)雜，因而目前關(guān)于權(quán)互補(bǔ)問題的研究尚不多見。

內(nèi)點(diǎn)算法是求解線性優(yōu)化問題的有效算法。2003年，Darvay[7]設(shè)計(jì)了線性規(guī)劃的一種全牛頓步原對偶路徑跟蹤內(nèi)點(diǎn)算法。2006年，Roos[8]提出線性優(yōu)化的原對偶不可行內(nèi)點(diǎn)算法，并證明了算法的收斂性及多項(xiàng)式時(shí)間復(fù)雜度。2011年，Zhang等[9]提出一種修正牛頓步可行內(nèi)點(diǎn)算法來求解線性優(yōu)化問題。2015年，Achache等[10]給出了單調(diào)線性互補(bǔ)問題的全牛頓步加權(quán)原對偶內(nèi)點(diǎn)算法。2015年，Mansouri等[11]提出求解線性優(yōu)化的改進(jìn)不可行內(nèi)點(diǎn)算法。

基于線性優(yōu)化的內(nèi)點(diǎn)算法，給出求解線性權(quán)互補(bǔ)問題的改進(jìn)全牛頓步可行內(nèi)點(diǎn)算法。通過擾動(dòng)線性權(quán)互補(bǔ)問題，構(gòu)造新的等價(jià)變換，分析算法的可行性和復(fù)雜度，并給出數(shù)值算例驗(yàn)證算法的有效性。

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

權(quán)互補(bǔ)問題是找到一向量對(x,y,s)∈Rn×Rm×Rn，滿足

f(x,y,s)=0，x≥0，s≥0，xs=ω,

其中：f:Rn×Rm×Rn→Rn×Rm為連續(xù)可微函數(shù)；xs為向量x和s的Hadamard積(即對應(yīng)分量乘積)；ω≥0為給定的非負(fù)權(quán)向量。

考慮如下線性權(quán)互補(bǔ)問題，找到一向量對(x,y,s)∈Rn×Rm×Rn，使得

(1)

擾動(dòng)線性權(quán)互補(bǔ)問題(1)得中心路徑

(2)

若式(1)有可行解(x,y,s)，且x>0，s>0，則稱式(1)滿足內(nèi)點(diǎn)條件(IPC)[13]，?t∈[0,1],記式(2)的解為(x(t),y(t),s(t))，稱為原問題(1)的t-中心解。這些解的集合稱為原問題(1)的中心路徑。當(dāng)t→0時(shí)，(x(t),y(t),s(t))收斂到一個(gè)極限點(diǎn)(x*,y*,s*)，即線性權(quán)互補(bǔ)問題(1)的解。

設(shè)(x,y,s)為當(dāng)前可行點(diǎn)，則新的迭代點(diǎn)

(3)

滿足

(4)

由式(2)、(4)知，可求解如下方程組得搜索方向(Δx,Δy,Δs)，

(5)

因?yàn)榫仃嘇行滿秩，且x>0，s>0，易證上述方程組中的系數(shù)矩陣非奇異。因此，式(5)可定義唯一的搜索方向(Δx,Δy,Δs)，且

(Δx)TΔs=0。

(6)

令

(7)

由式(6)和dx、ds的定義得

dxTds=0。

定義鄰近測度

2 改進(jìn)全牛頓步可行內(nèi)點(diǎn)算法

算法1線性權(quán)互補(bǔ)問題的全牛頓步可行內(nèi)點(diǎn)算法。

1)若‖xs-ω‖<ε，則算法終止；否則，轉(zhuǎn)步驟2。

3 可行性分析

引理1對任意k≥1，有

其中e=(1，1，…，1)。

ω(tk)=(1-(1-θ)kt0)ω+

(1-θ)kt0κ≥min(ω,κ)e,

所以

引理2[13]若(x,y,s)是可行點(diǎn)，則

引理3若(x,y,s)是可行點(diǎn)，x>0,s>0，且

則新迭代點(diǎn)(x+,y+,s+)嚴(yán)格可行。

證明令α∈[0,1]，定義

xα=x+αΔx，sα=s+αΔs。

由dx,ds的定義和式(7)得

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

t[v2+αv(dx+ds)+α2dxds]=

α2[min(ω,κ)-‖dxds‖∞]≥

α2[min(ω,κ)-δ(v,t)2]>0。

此時(shí)，則對任意α∈[0,1]有xαsα>0。

由于xα,sα是關(guān)于α的線性函數(shù)，?α∈[0,1]有xαsα>0，且x>0，s>0，則xα>0，sα>0。因此x+=x1>0，s+=s1>0。

(8)

故

根據(jù)引理1和引理2可得

下述引理將給出t更新之后迭代點(diǎn)的鄰近測度的上界。

證明由δ(v+,t+)的定義及式(8)得

則由引理1、引理2和引理4得

只需證

4 復(fù)雜度分析

定理1若線性權(quán)互補(bǔ)問題(1)的可行初始點(diǎn)為(x0,y0,s0)，θ≤(1-3η/2)/(1-η)，其中η∈(0,2/3)，則算法至少經(jīng)過

次迭代后生成的點(diǎn)(x,y,s)滿足‖xs-ω‖<ε，其中κ=x0s0。

證明根據(jù)式(5)、引理2和引理5得

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

‖ω(t+)-ω‖+‖ΔxΔs‖=

t+‖ω-κ‖+t‖dxds‖≤

因?yàn)閠0=1，所以在第k次迭代當(dāng)

時(shí)，有‖xksk-ω‖<ε。即需滿足不等式

(k-1)log(1-θ)

次迭代后，可得到線性權(quán)互補(bǔ)問題(1)的ε-近似最優(yōu)解。

5 數(shù)值算例

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

首先，生成行滿秩矩陣A∈Rm×n和向量b、c、ω以及可行初始點(diǎn)x0、y0、s0，記β=maxω/minω，取

其中η∈(0,2/3)。因此，θ可取(0,1)區(qū)間任意實(shí)數(shù)，算例中精度參數(shù)取ε=10-5，算法的迭代次數(shù)(Iter)和運(yùn)行時(shí)間(time)均選取200個(gè)同規(guī)模不同問題運(yùn)行結(jié)果的平均值。

表1、表2表明算法1所需要的迭代次數(shù)基本不受問題規(guī)模的影響，但運(yùn)行時(shí)間隨著問題規(guī)模的增大而增大。對比表2和表3可知，β值對算法運(yùn)行的時(shí)間和迭代次數(shù)影響都不大，且隨著θ的增大，β值對算法運(yùn)行的時(shí)間和迭代次數(shù)影響越來越小。

表1 β<20時(shí)算法求解不同規(guī)模線性權(quán)互補(bǔ)問題的數(shù)值結(jié)果

表2 β<2時(shí)算法求解不同規(guī)模線性權(quán)互補(bǔ)問題的數(shù)值結(jié)果

表3 算法1選取不同θ值求解m=n=300線性權(quán)互補(bǔ)問題和線性互補(bǔ)問題的數(shù)值結(jié)果

6 結(jié)束語

基于全牛頓步搜索方向，設(shè)計(jì)改進(jìn)可行內(nèi)點(diǎn)算法求解線性權(quán)互補(bǔ)問題(1)，在適當(dāng)?shù)臈l件下對算法的可行性進(jìn)行分析，該算法只需多項(xiàng)式時(shí)間迭代復(fù)雜度即可得到原問題的近似最優(yōu)解，并給出隨機(jī)生成的權(quán)互補(bǔ)問題的數(shù)值算例。數(shù)值實(shí)驗(yàn)結(jié)果表明，算法是有效的。