一種求解線性圓錐互補問題的非精確光滑牛頓法

韋洪錦, 遲曉妮, 黃鴻柳, 李春紅

(1.廣西科技師范學(xué)院 數(shù)學(xué)與計算機科學(xué)學(xué)院,廣西 來賓 546100;2.桂林電子科技大學(xué) 數(shù)學(xué)與計算科學(xué)學(xué)院,廣西 桂林 541004)

一般線性圓錐互補問題(LCCCP)[1]是指求一向量x∈Rn,使得

其中:θ∈(0,π/2)為給定的旋轉(zhuǎn)角;‖·‖為歐幾里得范數(shù)。故當(dāng)θ≠π/4時,圓錐是非自對偶的,因此其是非對稱錐。而當(dāng)θ=π/4時,n-維圓錐化為n-維二階錐[6],即

則問題(1)轉(zhuǎn)化為線性二階錐互補問題(LSOCCP)[7]。

為方便起見,用x=(x1,x2:n)∈R×Rn-1表示x=(x1,x2:nT)T,用(x,s)表示(xT,sT)T。

LCCCP被廣泛應(yīng)用于工程問題,如四足機器人力優(yōu)化問題和多指手臂機器人的抓力操作問題等[8-9],同時其又是非對稱錐互補問題的特例,因此近年來備受關(guān)注[1]。目前有很多求解互補問題的算法,如內(nèi)點算法[10-11]、半光滑牛頓法、光滑牛頓法[12-13]等。因其具有較好的理論結(jié)果和數(shù)值效果,光滑牛頓法被推廣到很多領(lǐng)域,如二階錐優(yōu)化問題[14-15]和圓錐規(guī)劃問題[16-17]等。此外,光滑牛頓法不要求初始點和中間迭代點的嚴格可行性,且一般具有全局和局部二階收斂性,因此是求解LCCCP的一種好方法,其主要思想是將LCCCP轉(zhuǎn)化為與之等價的方程組,然后運用光滑技術(shù)求解該方程組,從而得到LCCCP 的解。但在求解規(guī)模較大的問題時,在每次迭代中精確地求解方程組往往效率不高。因此,考慮使用非精確牛頓法[12,18]近似地求解方程組,以提高算法的效率。

基于一個新的圓錐互補函數(shù)的光滑函數(shù),提出一種求解LCCCP的非精確光滑牛頓法。該算法在每次迭代中運用非精確牛頓法近似地求解方程組,以減少計算量。在較弱的條件下,證明了算法具有全局和局部二階收斂性。數(shù)值結(jié)果表明,該算法可求解LCCCP。

1 預(yù)備知識

以下給出與二階錐[6]相伴的歐幾里得Jordan代數(shù)的概念。

對任意x=(x1,x2:n)∈R×Rn-1和s=(s1,s2:n)∈R×Rn-1,定義Jordan內(nèi)積

2 算法及其收斂性

其中μ≥0是一個實參數(shù),θ∈(0,π/2)。當(dāng)θ=π/4時,?(μ,x,s)退化為一個二階錐互補函數(shù)的光滑函數(shù)[14]。以下定理給出該函數(shù)的性質(zhì)。

定理1 設(shè)函數(shù)?:R+×Rn×Rn→Rn由式(10)定義,則:

1)?(0,x,s)=0?x∈Cnθ,s∈(Cnθ)*,=0;

2) 對任意(μ,x,s)∈R++×Rn×Rn,?(μ,x,s)連續(xù)可微,且其雅可比為

由定理1得Φ(z)=0?μ=0和(x,s)是LCCCP的解。因此,基于函數(shù)?(μ,x,s),當(dāng)μ>0時,可在每步迭代中使用非精確光滑牛頓法求解方程組Φ(z)=0。令μ→0,得LCCCP的解(x*,s*)。

定理2 設(shè)M是半正定矩陣,且函數(shù)Φ(z)由(12)定義,則:

1) 對任意z=(μ,x,s)∈R++×Rn×Rn,Φ(z)連續(xù)可微,且其雅可比矩陣為

算法1 求解LCCCP的非精確光滑牛頓法

定理3 設(shè)M為半正定矩陣,且{z k=(μk,x k,s k)}是算法1生成的迭代序列, 則算法1適定,且對任意k≥0,有μk∈R++。

證明 由于μk>0,且M為半正定矩陣,故由定理1知,Φ'(z)可逆,從而步驟2)適定。下證存在λ-∈(0,1),使任意λ∈(0,λ-]滿足式(24)。令Δz k∶=(Δμk,Δx k,Δs k)是(23)的唯一解,則

又由引理1得

因此,對任意λ∈(0,1),有

對任意λ∈(0,1),定義

由β(z k)的定義,當(dāng)Ψ(z k)<1時,

定理4 若M是半正定矩陣,則算法1產(chǎn)生有界無窮序列,且任一聚點都是方程Ψ(z)=0的解。

證明 用數(shù)學(xué)歸納法證明。易見z0∈Ω。假設(shè)z k∈Ω,即μk≥β(z k)μ0。由式(25)和β(z k)的定義有

故z k∈Ω。

其中λ-∈(0,1],η-∈[0,1-2γμ0]。因此,對任一非負整數(shù)l滿足δl∈(0,λ-],

又因為對充分大的k有λk=δl k≥δl,故由式(24)和(30)得

對上式兩邊取極限有

從而Ψ(z*)≤0,這與假設(shè)矛盾,因而z*是方程Ψ(z)=0的解。

類似定理8[21]的證明,有以下定理。

定理5 若M是半正定矩陣,z*為算法1產(chǎn)生的迭代序列{z k}的一個聚點。 如果所有V∈Φ(z*)(?Φ(z*)為函數(shù)Φ(z)在z*處的Clarke[22]意義下的廣義雅可比)非奇異,那么{z k}局部二階收斂到z*,即

‖z k+1-z*‖=O(‖z k-z*‖2),且μk+1=O(μk2)。

3 數(shù)值結(jié)果

運用MATLAB (R2016a)在配置為2.11 GHz CPU 處理器、8.00 GiB內(nèi)存的個人計算機上進行數(shù)值實驗。

算法1中選擇以下參數(shù):μ0=0.1,δ=0.95,σ=0.2,γ=0.45,ηk=2-k。以Ψ(z k)<ε=10-8作為終止準則。Iter和CPU 分別表示迭代次數(shù)和計算時間,n是維數(shù)。隨機生成一個向量q=rand(n,1)和矩陣A=rand(n,n),M=ATA,其中A和q中的元素是[0,1]隨機產(chǎn)生的數(shù)。令x0=e,s0=0為初始點。針對不同旋轉(zhuǎn)角和不同規(guī)模LCCCP進行求解,結(jié)果如表1和表2。

表1 求解中小規(guī)模LCCCP的數(shù)值結(jié)果

表2 求解較大規(guī)模LCCCP的數(shù)值結(jié)果

表1為求解不同旋轉(zhuǎn)角的中小規(guī)模LCCCP的CPU 和Iter。選取與表1同樣的旋轉(zhuǎn)角,表2為求解較大規(guī)模LCCCP的數(shù)值結(jié)果。從表1和表2可看出,算法所需的CPU 和Iter較少,且性能穩(wěn)定。因此,算法1對求解LCCCP是有效的。

4 結(jié)束語

基于一個新的圓錐互補函數(shù)的光滑函數(shù),給出非精確光滑牛頓法求解線性圓錐互補問題,并對算法的適定性、全局和局部二階收斂性進行分析。 該算法在每次迭代中只執(zhí)行一次線搜索,且不要求初始點和中間迭代點是嚴格可行的。隨機生成的圓錐互補問題的算例的數(shù)值結(jié)果表明,算法的有效性。