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

遲曉妮， 劉三陽， 王博妲

(1. 桂林電子科技大學數(shù)學與計算科學學院 廣西自動檢測技術與儀器重點實驗室，桂林 541004;2. 西安電子科技大學數(shù)學與統(tǒng)計學院，西安 710071)

0 引言

權互補問題的概念最早由Potra[1]在2012 年提出，是指找到一對屬于一個流形與一個錐的交集的向量，使得這對向量的某個代數(shù)積等于一個給定的權向量。當權向量為零時，權互補問題退化為互補問題[2]。非零權向量的存在，使得權互補問題的理論和算法都比互補問題復雜。權互補問題在科學、工程和經(jīng)濟等領域中有著廣泛的應用，可以建模比互補問題更廣泛的一大類均衡問題。Potra[1]指出經(jīng)濟領域的Fisher 市場均衡問題可建模為線性權互補問題，可以用內點方法更有效地求解。由Anstreicher[3]引入的線性規(guī)劃權中心問題同樣也可以轉化為斜對稱線性權互補問題。Potra[4]給出了充分線性權互補問題的概念，討論其性質，并提出求解該問題的一種預估校正內點算法。隨后，Zhang[5]提出用光滑牛頓算法來求解線性權互補問題，并證明了在適當?shù)臈l件下算法的局部二次收斂性。Chi 等[6]給出了歐幾里得約當代數(shù)上線性權互補問題一些解的存在性和唯一性結果。

內點算法是求解權互補問題的有效算法[7—8]之一。Roos[9]提出用全牛頓步不可行內點算法求解線性規(guī)劃，并證明了算法的收斂性及復雜度。Zhang 和Xu[10]提出了一個無需進行線搜索的可行內點算法來解決線性優(yōu)化問題，并重新構造了中心路徑，算法中采用了修正全牛頓步，且具有多項式復雜度。Mansouri 等人[11]設計了一種求解線性互補問題的改進不可行內點算法。內點算法不僅可以求解線性互補問題[12—13]和線性規(guī)劃問題[14—16]，還可應用于二階錐互補問題[17]和二階錐規(guī)劃問題[18—20]。Chi 和Liu[21]利用Alizadeh-Haeberly-Overton(AHO)搜索方向，給出了二階錐規(guī)劃全局收斂的預估-校正不可行內點算法，并給出了適當假設下的復雜度。Zangiabadi 等[22]提出了求解對稱錐線性互補問題的一種新的基于參數(shù)核函數(shù)的大步校正內點算法。Bai[23]給出求解錐優(yōu)化的基于核函數(shù)的內點算法。Liu 等人[24]提出了求解對稱錐規(guī)劃的一種基于寬鄰域的新不可行內點算法，并給出該寬鄰域不可行內點方法的迭代復雜度界，與現(xiàn)有的短步路徑跟蹤算法的最好復雜度界一致。隨后，基于核函數(shù)[25—28]或者寬鄰域[29—30]的相關內點算法被提出并應用于求解優(yōu)化問題。這些線性規(guī)劃和錐優(yōu)化的內點算法及相關理論[31]的研究成果，將有助于進一步研究權互補問題的內點算法。

1 線性權互補問題

引理1 原問題(1)可行當且僅當對任意0＜ν ≤1，其擾動問題(2)滿足IPC。

假設原問題(1)存在可行點，由引理1 知，對任意0＜ν ≤1， 0＜t ≤1，擾動問題(2)存在嚴格可行點。把該點記作(x(ν，t)，y(ν，t)，s(ν，t))，定義為擾動問題(2)的t-中心，所有t-中心的集合稱為擾動問題(2)的中心路徑。當ν，t →0 時，(x(ν，t)，y(ν，t)，s(ν，t))收斂到線性權互補問題(1)的解(x*，y*，s*)。

通過求解以下方程組可得牛頓搜索方向(Δfx，Δfy，Δfs)：

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

本節(jié)給出線性權互補問題(1)的改進不可行內點算法的基本思想和具體步驟。本算法通過對參數(shù)τ、θ的選取，使得每步主迭代都滿足δ(x，s;t)≤τ，從而算法可行。算法的每步主迭代分為一個可行步和幾個中心步?？尚胁剿阉鞣较蚩赏ㄟ^求解方程組(3)得到，中心步的搜索方向可通過求解以下方程組得出

則轉步驟6，否則轉步驟2；

步驟2 解方程組(3)得可行步之后迭代點(x，y，s):=(x，y，s)+(Δfx，Δfy，Δfs)；

步驟3 更新參數(shù)t:=(1－θ)t，ν:=(1－θ)ν；

步驟4 如果δ(x，s;t)＞τ，則轉到步驟5，否則轉步驟1；

步驟5 解方程組(4)，可得中心步之后迭代點(x，y，s):=(x，y，s)+(Δx，Δy，Δs)，轉步驟4；

步驟6 如果δ(x，s;t)≤ε，則算法停止，否則轉步驟7；

步驟7 解方程組(4)，可得中心步之后迭代點(x，y，s):=(x，y，s)+(Δx，Δy，Δs)，轉步驟6。

3 收斂性分析

4 復雜度分析

5 數(shù)值算例

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

首先，考慮形如問題(1)的線性權互補問題算例如下

為算法1 的終止條件。圖1 至圖4 分別表示m=n= 50，100，150，200 的‖rb‖(記為殘差一)，‖rc‖(記為殘差二)，‖xs－w‖(記為殘差三)和鄰近測度δ(v)隨著t →0 的變化，其中參數(shù)t ∈(0，1]。容易看出，‖rb‖、‖rc‖、‖w(t)－w‖和δ(v)的值都隨著t減小而有不同程度的減小，且最終都趨向于0。

圖1 殘差一隨著t 的變化

圖2 殘差二隨著t 的變化

圖3 殘差三隨著t 的變化

圖4 鄰近測度隨著t 的變化

6 結論

本文給出了求解線性權互補問題(1)的改進全牛頓步不可行內點算法。通過選取任意滿足x0s0＞w的初始點建立擾動問題，對原問題進行等價變換，定義中心路徑，選取適當?shù)母聟?shù)θ保證算法的收斂性，對算法的復雜度進行分析，并給出隨機生成的線性權互補問題的數(shù)值算例。數(shù)值實驗結果表明算法是有效的。