基于核函數求解單調線性互補問題的新full-Newton步內點算法

吳　珊　張明望　黃正偉

(1. 三峽大學 理學院， 湖北 宜昌　443002； 2. 三峽大學 經濟與管理學院， 湖北 宜昌　443002)

?

基于核函數求解單調線性互補問題的新full-Newton步內點算法

吳珊1張明望1黃正偉2

(1. 三峽大學 理學院， 湖北 宜昌443002； 2. 三峽大學 經濟與管理學院， 湖北 宜昌443002)

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

關鍵詞：單調線性互補問題；full-Newton步；核函數；多項式復雜性

線性互補問題是運籌學與計算數學相互交叉的一個研究領域，為線性規劃、二次規劃提供了一個統一的研究框架，在經濟學和工程中有著廣泛的應用[1]．求解線性互補問題的算法很多，其中原始-對偶內點算法是一類非常重要而有效的算法[2-3]．

受文獻[6-12]的啟發，本文設計了一種基于具有線性增長項的核函數求解單調線性互補問題的新full-Newton步內點算法，并應用該核函數導出新的搜索方向且定義了迭代點到中心路徑的鄰近度量．同時，證明了該算法的多項式復雜性階與當前求解線性互補問題內點算法最好的迭代復雜性階一致．據我們所知，這是基于具有線性增長項核函數的第一個多項式full-Newton步內點算法．

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

1算法

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

(1)

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

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

(2)

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

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

(3)

記

(4)

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

(5)

(6)

考慮如下核函數

(7)

注：核函數p=0是文獻[14]中核函數

在p=0時的2倍．

(8)

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

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

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

表1給出了本文算法的具體步驟．單調線性互補問題的full-Newton步內點算法：

Input

閾值0<τ<1；

精度參數ε>0；

障礙校正參數θ，0<θ<1；

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

begin

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

whilexTs>ε

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

x：=x+Δx

s：=s+Δs

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

end

end

2算法分析

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

2.1full-Newton步的可行性分析

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

(9)

引理2.1迭代點(x+，s+)嚴格可行當且僅當

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

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

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

(10)

再由式(4)，可知

(11)

進一步根據式(10)和(11)，有

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

因此

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

2.2full-Newton步的二次收斂性

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

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

所以

證畢．

證明

證畢．

證明根據引理2.4，可知

證畢．

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

由于

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

則

因此，

證畢．

2.3復雜性分析

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

(12)

其中，式(12)左端關于δ單調遞增．因此，

若取

(13)

從而得到

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

取對數，可得

(14)

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

得證．

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

參考文獻：

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

[2]雍龍泉，鄧方安，陳濤．單調線性互補問題的一種內點算法[J]．數學雜志，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．

[責任編輯王康平]

收稿日期：2015-11-04

基金項目：國家自然科學基金項目(71471102)

通信作者：張明望(1959-)，男，教授，主要研究方向為最優化理論與應用．E-mail：zmwang@ctgu.edu.cn

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

中圖分類號：O221.2

文獻標識碼：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