線性權互補問題的一種改進全牛頓步可行內點算法

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

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

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

內點算法是求解線性優化問題的有效算法。2003年，Darvay[7]設計了線性規劃的一種全牛頓步原對偶路徑跟蹤內點算法。2006年，Roos[8]提出線性優化的原對偶不可行內點算法，并證明了算法的收斂性及多項式時間復雜度。2011年，Zhang等[9]提出一種修正牛頓步可行內點算法來求解線性優化問題。2015年，Achache等[10]給出了單調線性互補問題的全牛頓步加權原對偶內點算法。2015年，Mansouri等[11]提出求解線性優化的改進不可行內點算法。

基于線性優化的內點算法，給出求解線性權互補問題的改進全牛頓步可行內點算法。通過擾動線性權互補問題，構造新的等價變換，分析算法的可行性和復雜度，并給出數值算例驗證算法的有效性。

1 權互補問題

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

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

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

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

(1)

擾動線性權互補問題(1)得中心路徑

(2)

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

設(x,y,s)為當前可行點，則新的迭代點

(3)

滿足

(4)

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

(5)

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

(Δx)TΔs=0。

(6)

令

(7)

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

dxTds=0。

定義鄰近測度

2 改進全牛頓步可行內點算法

算法1線性權互補問題的全牛頓步可行內點算法。

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

3 可行性分析

引理1對任意k≥1，有

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

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

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

所以

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

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

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

證明令α∈[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。

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

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

(8)

故

根據引理1和引理2可得

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

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

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

只需證

4 復雜度分析

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

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

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

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

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

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

因為t0=1，所以在第k次迭代當

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

(k-1)log(1-θ)

次迭代后，可得到線性權互補問題(1)的ε-近似最優解。

5 數值算例

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

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

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

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

表1 β<20時算法求解不同規模線性權互補問題的數值結果

表2 β<2時算法求解不同規模線性權互補問題的數值結果

表3 算法1選取不同θ值求解m=n=300線性權互補問題和線性互補問題的數值結果

6 結束語

基于全牛頓步搜索方向，設計改進可行內點算法求解線性權互補問題(1)，在適當的條件下對算法的可行性進行分析，該算法只需多項式時間迭代復雜度即可得到原問題的近似最優解，并給出隨機生成的權互補問題的數值算例。數值實驗結果表明，算法是有效的。