線性二階錐互補問題的非單調(diào)線搜索光滑算法

趙花麗

(咸陽師范學院數(shù)學與信息科學學院，陜西咸陽 712000)

線性二階錐互補問題:求解一向量x∈Rn，使其滿足

s=Mx+q，x ?s=0，且 x ∈ Kn，s∈ Kn。

這里M∈ Rn×n，q∈ Rn，n維二階錐定義為:Kn

二階錐互補問題是近十年來研究的新問題，目前利用光滑算法［1-4］來求解二階錐互補問題已成為一個研究熱點，本文在光滑算法的基礎上利用CM光滑函數(shù)提出了線性二階錐互補問題的非單調(diào)線搜索光滑算法。算法中利用非單調(diào)因子來控制搜索的非單調(diào)程度，對初始點的選取沒有任何限制，最后，給出算法的全局收斂性和局部超線性收斂性分析，并且給出數(shù)值實驗，就非單調(diào)因子對計算結(jié)果的影響進行了比較。

1 預備知識

對任意的向量x=(x1，x2)，y=(y1，y2)∈R ×Rn-1，定義二階錐Kn上的若當積:x?y=(x，[]y，y1x2+x1y2)。

設 λ1，λ2，u1，u2分別表示 x 的特征值和相應的特征向量，則向量x=(x1，x2)∈R×Rn-1可以表示為:x= λ1u1+ λ2u2，其中

2 基于非單調(diào)線搜索的光滑算法

本文中用CHKS函數(shù)

y=x-s=(y1，y2)∈ R × Rn-1，λ1，λ2分別表示 y的最大、最小特征值，則［2］

其中

將線性二階錐互補問題轉(zhuǎn)化為求解下面的光滑方程組

顯然，對任意光滑參數(shù) μ ＞ 0，H(x，s，μ)的雅可比矩陣 H'(x，s，μ)在任意點 (x，s，μ)都存在。

其中Dx=I-g'(y)，Ds=I+g'(y)，

Dμ=g'(y)。

算法步驟:

(1)令 ω =(x，s，μ)∈Rn× Rn× R+，給定初始值 ω0=(x0，s0，μ0)，取常數(shù) δ，σ ∈ (0，1)，W0=‖H(ω0)‖，Q0=1。

p=(0，0，1)∈ Rn× Rn× R，β ＞ 1 滿足‖H(ω0)‖ ≤ βμ0，令 k=0。

(2)如果H(ωk)=0，則算法停止。

(3)求解牛頓方向 (Δxk，Δsk，Δμk)，解線性方程組 H(ωk)+H'(ωk)Δωk=(1/β)Wkp。

(4)確定步長rk=δlk，lk是使得關(guān)于l的不等式成立的最小非負整數(shù)，

‖H(ωk+ δlΔωk)‖ ≤(1- σ(1-1/β)δl)Wk。

(5)令 ωk+1= ωk+rkΔωk，取參數(shù)

ηk∈［0，1］，Qk+1= ηkQk+1

Wk+1=(ηkQkWk+ ‖H(ωk+1)‖/Qk+1。令k=k+1，轉(zhuǎn)步驟(2)。

從算法很容易看出參數(shù)ηk的值控制著線搜索的非單調(diào)程度，當ηk為0時就是一般的單調(diào)Armijo線搜索。

3 收斂性分析

引理1 假定M是半正定矩陣，如果所有V∈?H(ω*)是非奇異的，則有:

(1)算法所產(chǎn)生的序列{Wk}是單調(diào)下降的。

(2)序列{μk}是單調(diào)下降的，并且對所有k有:μk＞ 0。

證明:(1)由算法可知:

(2)由算法可知

所以序列{μk}是單調(diào)下降的，并且對所有 k有:μk＞ 0。

引理2 假定M是半正定矩陣，如果所有V∈?H(ω*)是非奇異的，則算法產(chǎn)生的序列{ωk}都位于中心路徑的鄰域內(nèi)，即 ‖H(xk，sk，μk)‖ ≤ βμk。

證明:由算法知:

因此對所有 k 有:‖H(xk，sk，μk)‖ ≤ βμk。

引理3 假定M是半正定矩陣，如果所有V∈?H(ω*)是非奇異的，則由算法產(chǎn)生的序列{Wk}是收斂的且極限為W*=0。

證明:由引理1知

由Qk的定義有:

又因為0＜rk=δlk＜1，

定理1 假定M是半正定矩陣，如果所有V∈?H(ω*)是非奇異的，則由算法產(chǎn)生的序列{ωk}是有界的且序列 {(xk，sk)}的任意聚點是 SOCCP的解。

證明:首先證明序列{ωk}是有界的。

由引理1知:{μk}是有界的，使得 |μk|＜ ε。下證序列{(xk，sk)}是有界的。

假定{(xk，sk)}是無界的，則存在子序列{(xk，sk)}，使得 limk→∞‖(xk，sk)‖ = ∞。

因為M是半正定矩陣，函數(shù)φμ是連續(xù)可微的，所以函數(shù) H是連續(xù)可微的，所以對每個 μk有l(wèi)im‖(xk，sk)‖→∞‖H(xk，sk，μk)‖ = ∞ 。

又由引理 2 知:‖H(xk，sk，μk)‖ ≤ βμk。

即存在ε＞0，當k充分大時有:

‖H(xk，sk，μk)‖ ≤ βε。

這就產(chǎn)生了矛盾。所以{(xk，sk)}是有界的。因此序列{ωk}有界。

其次我們證明{(xk，sk)}的任意聚點是SOCCP的解。

由引理 1知序列 {Wk}是收斂的，序列{‖H(ωk)‖}是有界的。由于{ωk}是有界的，則序列{ωk}有收斂的子序列，記為{ωk}。令ω*表示子序列的極限，則

由引理3有‖H(ω*)‖ =0，所以得證。

定理3 (局部超線性收斂)假定M是半正定矩陣，如果所有V∈?H(ω*)是非奇異的，則{ωk}超線性收斂到ω*。即

其證明類似于文獻［5］中的定理5，在此省略證明。

4 數(shù)值實驗

隨機產(chǎn)生一個線性二階錐互補問題進行數(shù)據(jù)實驗。在整個實驗中，取參數(shù) σ =1.0e-4，δ=0.5，μ0=1.0e-4，初始點x0，s0的每個分量均為［-1，1］的隨機數(shù)，參數(shù)，算法的終止準則為 ‖H(x，s，μ)‖ ≤1.0e-7。在實驗中，對每組r，n分別用上述算法進行20次實驗，I表示平均迭代次數(shù)，T表示平均CPU時間，NH表示|xTs|的最大值。

我們做了3組實驗，第一組實驗:對算法的有效性進行測試。在整個實驗中固定ηk=0.1，見表1，從數(shù)據(jù)結(jié)果來看，該算法是有效的，并且所用的CPU時間較短，迭代次數(shù)也較少。

表1 算法的數(shù)值結(jié)果

第二組實驗:固定n=100，r=95對算法中ηk的不同取值進行結(jié)果比較，見表2。ηk值的變化對算法所用的CPU時間和迭代次數(shù)產(chǎn)生很大的影響。當ηk值為0時，即算法為一般的光滑算法，采用非單調(diào)因子之后，對結(jié)果的精確程度有明顯的改進，但對速度的改進程度還依賴ηk的取值。

表2 不同ηk的結(jié)果比較

第三組實驗:固定n=100，r=95，在實驗過程中取ηk為(0，1)區(qū)間上的隨機數(shù)，發(fā)現(xiàn)對同樣的問題，不同次的實驗，算法所需要的迭代次數(shù)與時間差別很大，也沒有一個規(guī)律可尋。

5 結(jié)語

本文給出了一個非單調(diào)線搜索光滑算法，從算法的3組實驗中可以看出，采用非單調(diào)線搜索的光滑算法，對于求解線性二階錐互補問題是有效的，并且精確度也很高。非單調(diào)因子ηk的值在算法中起著非常重要的作用，因子ηk取適當?shù)臄?shù)值，非單調(diào)線搜索算法比單調(diào)線搜索算法的效果要好，那么因子ηk的取值規(guī)則，對算法進一步優(yōu)化起關(guān)鍵性作用，這也是我們下一步要研究的問題。

［1］Fukushima M，Luo Z Q，Tseng P.Smoothing Functions for Second-order Cone Complementarity Problems［J］.SIAM Journal on Optimization，2002，12:436-460.

［2］Xiang Song Zhang，SanYang Liu，ZhenHua Liu.A Smoothing Method for Second Order Cone Complementarity Problem［J］.Jurnal of Computational and Applied Mathematical，2009，228:83-91.

［3］Huali Zhao，Hongwei Liu.Predictor Corrector Smoothing Newton Method for Solving the Second Order Cone Complementarity［J］.ICICTA，2010，3:927-930.

［4］Hua-li Zhao， Hong-wei Liu.A Predictor-corrector smoothing Newton Method for the Second-order Cone Complementarity［J］.CASON，2010，1:259-262.

［5］Qi L，Sun D，Zhou G.A New Look at Smoothing Newton Methods for Nonlinear Complementarity Problems and Box Constrained Variational Inequalities［J］.Mathematical Programming，2000，87:1-35.