基于核函數(shù)求解單調(diào)線性互補(bǔ)問題的新full-Newton步內(nèi)點(diǎn)算法

吳　珊　張明望　黃正偉

(1. 三峽大學(xué) 理學(xué)院， 湖北 宜昌　443002； 2. 三峽大學(xué) 經(jīng)濟(jì)與管理學(xué)院， 湖北 宜昌　443002)

?

基于核函數(shù)求解單調(diào)線性互補(bǔ)問題的新full-Newton步內(nèi)點(diǎn)算法

吳珊1張明望1黃正偉2

(1. 三峽大學(xué) 理學(xué)院， 湖北 宜昌443002； 2. 三峽大學(xué) 經(jīng)濟(jì)與管理學(xué)院， 湖北 宜昌443002)

摘要：本文對單調(diào)線性互補(bǔ)問題設(shè)計(jì)了一種基于核函數(shù)的full-Newton步內(nèi)點(diǎn)算法．該核函數(shù)導(dǎo)出新的搜索方向并定義了迭代點(diǎn)到中心路徑的鄰近度量．通過應(yīng)用新的技術(shù)引理，證明了該算法的多項(xiàng)式復(fù)雜性階為L)，這與當(dāng)前求解單調(diào)線性互補(bǔ)問題內(nèi)點(diǎn)算法最好的迭代復(fù)雜性階一致．

關(guān)鍵詞：單調(diào)線性互補(bǔ)問題；full-Newton步；核函數(shù)；多項(xiàng)式復(fù)雜性

線性互補(bǔ)問題是運(yùn)籌學(xué)與計(jì)算數(shù)學(xué)相互交叉的一個(gè)研究領(lǐng)域，為線性規(guī)劃、二次規(guī)劃提供了一個(gè)統(tǒng)一的研究框架，在經(jīng)濟(jì)學(xué)和工程中有著廣泛的應(yīng)用[1]．求解線性互補(bǔ)問題的算法很多，其中原始-對偶內(nèi)點(diǎn)算法是一類非常重要而有效的算法[2-3]．

受文獻(xiàn)[6-12]的啟發(fā)，本文設(shè)計(jì)了一種基于具有線性增長項(xiàng)的核函數(shù)求解單調(diào)線性互補(bǔ)問題的新full-Newton步內(nèi)點(diǎn)算法，并應(yīng)用該核函數(shù)導(dǎo)出新的搜索方向且定義了迭代點(diǎn)到中心路徑的鄰近度量．同時(shí)，證明了該算法的多項(xiàng)式復(fù)雜性階與當(dāng)前求解線性互補(bǔ)問題內(nèi)點(diǎn)算法最好的迭代復(fù)雜性階一致．據(jù)我們所知，這是基于具有線性增長項(xiàng)核函數(shù)的第一個(gè)多項(xiàng)式full-Newton步內(nèi)點(diǎn)算法．

文中記法：Rn表示n維歐式空間；e表示分量全為1的n維列向量；‖·‖1，‖·‖2和‖·‖∞分別表示向量的1-范數(shù)、2-范數(shù)和無窮范數(shù)；對于x=(x1，x2，…，xn)∈Rn，X表示x的對應(yīng)分量構(gòu)成的對角矩陣，即X=diag(x)；對x，s∈Rn，xs表示對應(yīng)分量乘積所得向量，即xs=(x1s1，x2s2，…，xnsn)．

1算法

本文考慮如下標(biāo)準(zhǔn)形式的單調(diào)線性互補(bǔ)問題，即求(x，s)∈Rn×Rn(n≥2)，滿足

(1)

其中，q∈Rn，M∈Rn×n是半正定矩陣．

內(nèi)點(diǎn)算法的基本思想就是用參數(shù)方程xs=μe(μ>0)取代(1)中的互補(bǔ)條件xs=0，得到下列方程組：

(2)

假設(shè)問題(1)是嚴(yán)格可行的，即滿足內(nèi)點(diǎn)條件(IPC)，則對給定的μ>0，方程組(2)有唯一的解，記作(x(μ)，s(μ))，并稱之為問題(1)的μ-中心．所有μ-中心組成的集合{(x(μ)，s(μ))|μ>0}就稱為問題(1)的中心路徑．當(dāng)μ→0時(shí)，(x(μ)，s(μ))收斂于問題(1)的最優(yōu)解．

通常用Newton法求解方程組(1)．對于任意給定的可行解(x，s)>0，Newton方向(Δx，Δs)滿足下列方程組：

(3)

記

(4)

則方程組(3)可表示為下列尺度方程組：

(5)

(6)

考慮如下核函數(shù)

(7)

注：核函數(shù)p=0是文獻(xiàn)[14]中核函數(shù)

在p=0時(shí)的2倍．

(8)

通過求解方程組(8)得到尺度搜索方向(dx，ds)，再由式(4)計(jì)算得到新的搜索方向(Δx，Δs)．記新的迭代點(diǎn)

為分析算法，引入δ(x，s；μ)來度量迭代點(diǎn)(x，s)到單調(diào)線性互補(bǔ)問題μ-中心的鄰近程度，其定義如下：

若(x，s)=(x(μ)，s(μ))，則υ=e，從而δ(x，s；μ)=0；否則δ(x，s；μ)>0．

表1給出了本文算法的具體步驟．單調(diào)線性互補(bǔ)問題的full-Newton步內(nèi)點(diǎn)算法：

Input

閾值0<τ<1；

精度參數(shù)ε>0；

障礙校正參數(shù)θ，0<θ<1；

嚴(yán)格的初始可行點(diǎn)(x0，s0)>0使得x0s0=μ0e，δ(x0，s0；μ0)≤τ，

begin

x：=x0；s：=s0；μ：=μ0

whilexTs>ε

求解(7)再應(yīng)用(3)得到搜索方向(Δx，Δs)，令

x：=x+Δx

s：=s+Δs

μ-校正：μ：=(1-θ)μ

end

end

2算法分析

本節(jié)研究full-Newton步的可行性并證明full-Newton步對于中心路徑的二次收斂性，且得到該算法的多項(xiàng)式迭代復(fù)雜性．

2.1full-Newton步的可行性分析

由式(4)和方程組(8)的第二個(gè)方程，可得

(9)

引理2.1迭代點(diǎn)(x+，s+)嚴(yán)格可行當(dāng)且僅當(dāng)

證明充分性：如果x+和s+是嚴(yán)格可行的，由式(9)可知

必要性：令步長α∈[0，1]，則定義

從而x0=x，s0=s，x1=x+，s1=s+，有x0s0=xs>0．因此，

(10)

再由式(4)，可知

(11)

進(jìn)一步根據(jù)式(10)和(11)，有

由于(υ-e)2+e+dxds>0，則

因此

其中，(1-α)≤(1-α2)=(1-α)(1+α)，所以上式中的第二個(gè)不等式成立．對α∈[0，1]，由于(1-α)μ[(υ-αe)2+α(2-α)e]>0，則xαsα>0成立．因此，對α∈[0，1]，xα和sα分量乘積恒大于0．又因?yàn)閤0和s0是嚴(yán)格可行的初始點(diǎn)，且xα和sα關(guān)于α線性增長，所以對α∈[0，1]，xα>0，sα>0．由上可知，x1和s1嚴(yán)格可行，則可得迭代點(diǎn)x+和s+嚴(yán)格可行．

2.2full-Newton步的二次收斂性

引理2.2[8]令δ：=δ(x，s；μ)，從而可得

引理2.3令(dx，ds)是方程組(8)的唯一解，從而可知

所以

證畢．

證明

證畢．

證明根據(jù)引理2.4，可知

證畢．

下面引理描述了μ-校正和full-Newton步后對鄰近度量的影響．

由于

min(υ2-2υ+2e+dxds)≥

則

因此，

證畢．

2.3復(fù)雜性分析

為了得到算法的多項(xiàng)式復(fù)雜性，需找到閾值τ和障礙校正參數(shù)θ，使得迭代開始時(shí)迭代點(diǎn)滿足δ(x，s；μ)<τ．在full-Newton步和μ-校正后，仍有δ(x+，s+；μ+)<τ．由引理2.4可知

(12)

其中，式(12)左端關(guān)于δ單調(diào)遞增．因此，

若取

(13)

從而得到

為了使得(xk)Tsk≤ε，則

取對數(shù)，可得

(14)

再根據(jù)-log(1-θ)≥θ，則

得證．

注：由θ在式(13)的取值可知，該算法是小步校正內(nèi)點(diǎn)算法．隨著單調(diào)線性互補(bǔ)問題規(guī)模n的逐漸增加，不能期待在實(shí)際計(jì)算中取得太好的結(jié)果[4]．今后將進(jìn)一步研究大步校正內(nèi)點(diǎn)算法及一般推廣．

參考文獻(xiàn)：

[1]韓繼業(yè)，修乃華，戚厚鐸．非線性互補(bǔ)理論與算法[M]．上海：上海科學(xué)出版社，2006．

[2]雍龍泉，鄧方安，陳濤．單調(diào)線性互補(bǔ)問題的一種內(nèi)點(diǎn)算法[J]．?dāng)?shù)學(xué)雜志，2009，29(5)：681-686．

[3]KarmarkarNK．ANewPolynomial-TimeAlgorithmforLinearProgramming[J]．Combinatorialoptimization, 1984, 4 (4)：373-395．

[4]RoosC,TerlakyT,VialJP．TheoryandAlgorithmsforLinearOptimization：anInteriorPointApproach[M]．Chichester：Wiley,1997．

[5]RoosC．AFull-NewtonStepO(n)InfeasibleInterior-pointAlgorithmforLinearOptimization[J]．SIAMJournalonOptimization,2006,16(4)：1110-1136．

[6]WangGQ,YuCJ,TeoKL．AFull-NewtonStepFeasibleInterior-pointAlgorithmforP*(κ)-LinearComplementarityProblems[J]．JournalofGlobalOptimization,2014,59(1)：81-99．

[7]PengJ,RoosC,TerlakyT．Self-regularFunctionsandNewSearchDirectionsforLinearandSemidefiniteOptimization[J]．MathematicalProgramming,2002,93(1)：129-171．

[8]BaiYQ,ElGhamiM,RoosC．AComparativeStudyofKernelFunctionsforPrimal-dualInterior-pointAlgorithmsinLinearOptimization[J]．SIAMJournalonOptimization,2004,15(1)：101-128．

[9]ZhangL,XuY．AFull-NewtonStepInterior-pointAlgorithmBasedonModifiedNewtonDirection[J]．OperationsResearchLetters,2011,39(5)：318-322．

[10]LesajaG,WangGQ,ZhuDT．Interior-pointMethodsforCartesianP*(κ)-LinearComplementarityProblemsOverSymmetricConesBasedontheEligibleKernelFunctions[J]．OptimizationMethodsandSoftware,2012,27(4-5)：827-843．

[11]LiuZ,SunW,TianF．AFull-NewtonStepInfeasibleInterior-pointAlgorithmforLinearProgrammingBasedonaKernelFunction[J]．AppliedMathematicsandOptimization, 2009,60(2)：237-251．

[12]KheirfamB．AFull-NewtonStepInfeasibleInterior-pointAlgorithmforLinearComplementarityProblemsBasedonaKernelFunction[J]．AlgorithmicOperationsResearch,2013,7(2)：103-110．

[13]KheirfamB．AFullNesterov-ToddStepInfeasibleInterior-pointAlgorithmforSymmetricOptimizationBasedonaSpecificKernelFunction[J]．NumericalAlgebraControlandOptimization,2013,3(4)：601-614．

[責(zé)任編輯王康平]

收稿日期：2015-11-04

基金項(xiàng)目：國家自然科學(xué)基金項(xiàng)目(71471102)

通信作者：張明望(1959-)，男，教授，主要研究方向?yàn)樽顑?yōu)化理論與應(yīng)用．E-mail：zmwang@ctgu.edu.cn

DOI：10.13393/j.cnki.issn.1672-948X.2016.02.024

中圖分類號：O221.2

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號：1672-948X(2016)02-0108-05

A Interior-point Algorithm with Full-Newton Steps for Monotone Linear Complementarity Problem Based on a Kernel Function

Wu Shan1Zhang Mingwang1Huang Zhenghai2

(1. College of Science, China Three Gorges Univ., Yichang 443002, China; 2. College of Economics & Management, China Three Gorges Univ., Yichang 443002, China)

AbstractIn this paper, a new full-Newton step interior-point algorithm is proposed based on a kernel function with linear growth term for monotone linear complementarity problem. This kernel function determines searching directions and the proximity measure between the iterates and the center path. By developing some new technical results, an iteration bound L) that coincides with the currently best known iteration bound is derived for monotone linear complementarity problem.

Keywordsmonotone linear complementarity problem；full-Newton step；kernel function；iteration bound