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

遲曉妮， 劉三陽(yáng)， 王博妲

(1. 桂林電子科技大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院 廣西自動(dòng)檢測(cè)技術(shù)與儀器重點(diǎn)實(shí)驗(yàn)室，桂林 541004;2. 西安電子科技大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，西安 710071)

0 引言

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

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

1 線(xiàn)性權(quán)互補(bǔ)問(wèn)題

引理1 原問(wèn)題(1)可行當(dāng)且僅當(dāng)對(duì)任意0＜ν ≤1，其擾動(dòng)問(wèn)題(2)滿(mǎn)足IPC。

假設(shè)原問(wèn)題(1)存在可行點(diǎn)，由引理1 知，對(duì)任意0＜ν ≤1， 0＜t ≤1，擾動(dòng)問(wèn)題(2)存在嚴(yán)格可行點(diǎn)。把該點(diǎn)記作(x(ν，t)，y(ν，t)，s(ν，t))，定義為擾動(dòng)問(wèn)題(2)的t-中心，所有t-中心的集合稱(chēng)為擾動(dòng)問(wèn)題(2)的中心路徑。當(dāng)ν，t →0 時(shí)，(x(ν，t)，y(ν，t)，s(ν，t))收斂到線(xiàn)性權(quán)互補(bǔ)問(wèn)題(1)的解(x*，y*，s*)。

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

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

本節(jié)給出線(xiàn)性權(quán)互補(bǔ)問(wèn)題(1)的改進(jìn)不可行內(nèi)點(diǎn)算法的基本思想和具體步驟。本算法通過(guò)對(duì)參數(shù)τ、θ的選取，使得每步主迭代都滿(mǎn)足δ(x，s;t)≤τ，從而算法可行。算法的每步主迭代分為一個(gè)可行步和幾個(gè)中心步。可行步搜索方向可通過(guò)求解方程組(3)得到，中心步的搜索方向可通過(guò)求解以下方程組得出

則轉(zhuǎn)步驟6，否則轉(zhuǎn)步驟2；

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

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

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

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

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

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

3 收斂性分析

4 復(fù)雜度分析

5 數(shù)值算例

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

首先，考慮形如問(wèn)題(1)的線(xiàn)性權(quán)互補(bǔ)問(wèn)題算例如下

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

圖1 殘差一隨著t 的變化

圖2 殘差二隨著t 的變化

圖3 殘差三隨著t 的變化

圖4 鄰近測(cè)度隨著t 的變化

6 結(jié)論

本文給出了求解線(xiàn)性權(quán)互補(bǔ)問(wèn)題(1)的改進(jìn)全牛頓步不可行內(nèi)點(diǎn)算法。通過(guò)選取任意滿(mǎn)足x0s0＞w的初始點(diǎn)建立擾動(dòng)問(wèn)題，對(duì)原問(wèn)題進(jìn)行等價(jià)變換，定義中心路徑，選取適當(dāng)?shù)母聟?shù)θ保證算法的收斂性，對(duì)算法的復(fù)雜度進(jìn)行分析，并給出隨機(jī)生成的線(xiàn)性權(quán)互補(bǔ)問(wèn)題的數(shù)值算例。數(shù)值實(shí)驗(yàn)結(jié)果表明算法是有效的。