線性二階錐互補問題的光滑信賴域法

趙花麗

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

線性二階錐互補問題的光滑信賴域法

趙花麗

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

摘要：基于CHKS光滑函數(shù)給出了二階錐互補問題的一個新的光滑信賴域法。該算法與其他的信賴域算法的不同之處在于將參量μ看作與未知量x同等重要的變量加以迭代，并構造了新的參數(shù)λk。該參數(shù)λk與當前迭代點有關，其功能類似于信賴域半徑的自適應調節(jié)。最后證明了該算法的在某種假設下是全局收斂的。 數(shù)值試驗結果表明該算法是有效的。

關鍵詞：二階錐互補問題；信賴域；光滑算法；全局收斂

線性二階錐互補問題：找到x∈Rn，使得：

s=Mx+q，x°s=0，且x∈Kn，s∈Kn

(1)

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

二階錐互補問題算法的研究已取得了一些成果，包括光滑牛頓法[1-4]、半光滑牛頓法[5-6]、內點算法[6-10]及價值函數(shù)法[4，11]，但是目前對二階錐互補問題的光滑信賴域算法的研究成果還不多。本文將非線性互補問題的完全光滑信賴域算法[12]擴展到二階錐互補問題中，基于CHKS函數(shù)給出了一個求解二階錐互補問題的光滑信賴域算法。該算法與其他的信賴域算法的不同之處在于將參量μ看作與未知量x同等重要的變量加以迭代，并構造了新的參數(shù)λk。該參數(shù)λk與當前迭代點有關，功能類似于信賴域半徑的自適應調節(jié)。由此提出了一種新的光滑信賴域算法，研究了算法的全局收斂性，并通過數(shù)值實驗證明了該算法是有效的。

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)可以表示為：x=λ1u1+λ2u2，其中：

2光滑信賴域法

本文使用CHKS函數(shù)：

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

(2)

其中：

本文取信賴域的子問題如下：

(3)

這里Gk=▽H(zk)T▽H(zk)。

下面給出二階錐互補問題的光滑信賴域法。

算法1(光滑信賴域法)

步驟0(初始化)任給向量z0= (x0，s0，μ0)，選擇常數(shù)δ，σ∈(0，1)，0<ρ0<1，λ0>0，c>0，ε>0，令k=0。

步驟2解線性方程組

(4)

得pk=(Δxk，Δsk，Δμk)，令

步驟3 若ρk<ρ0，則pk=-▽Ψ(zk)，令m是滿足下式的最小整數(shù)：

令γ=δm，zk+1=zk+γpk，否則，令

(5)

步驟4令k=k+1 ，轉步驟1。

注意到，當?shù)痪芙^時，算法1使用線搜索代替了求解子問題，同時該算法在迭代被拒絕時是一個下降算法，這時該算法有很好的定義。

3收斂性分析

首先做一個假設：

假設1

1) 水平集L(z0)={z∈R++×Rn|Ψ(z)≤Ψ(z0)} 是有界的。

本文所給出的算法的收斂性分析都是在假定1滿足的條件下進行的。

引理1假設序列 {zk}是由算法1產生的序列，則序列{μk} 是單調下降的，且μk>0。

證明

1) 若ρk<ρ0，由步驟2、3有

又因為0<γ<1，所以有μk + 1> 0，μk + 1<μk。

2) 若ρk≥ρ0，由式 (4) 有

因此：μk + 1> 0，μk + 1<μk，則序列{μk} 是單調下降的且μk> 0。

引理2如果單調映射f是連續(xù)可微的，假設序列{zk}是由算法1產生的序列， 則序列{Ψ(zk)} 收斂且{zk} 位于水平集L(z0)={z∈R++×Rn|Ψ(z)≤Ψ(z0)}內。

證明

1) 若ρk<ρ0，由步驟2、3有pk=-▽Ψ(zk)，則Ψ(zk)-Ψ(zk+1)≥σγ▽Ψ(zk)T·▽Ψ(zk)，即Ψ(zk+1)≤Ψ(zk)。

2) 若ρk≥ρ0，由步驟2、3有

否則：

所以有

又因為

若ρki≥ρ0>0，由引理2有

若ρk<ρ0，由引理2有

定理2如果單調映射f是連續(xù)可微的，假設序列{zk}是由算法1產生的序列，z*是{zk}的一個聚點，則μ*=0， 所以z*是H(z)=0的解。

證明由引理2 和定理1即可知定理2成立。

4數(shù)值試驗

隨機產生一個線性二階錐互補問題進行數(shù)據(jù)實驗。在整個實驗中，取參數(shù)σ=0.5，λ0=0.1，ρ0=0.1，δ=0.75，c=0.5，初始點x0，s0的每個分量均為[-1，1]的隨機數(shù)。算法的終止準則：

2) 步長小于1.0e-15；

3) 迭代次數(shù)超過300。

表1　光滑信賴域法數(shù)據(jù)結果

參考文獻：

[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]Hayashi S，Yamashita N，F(xiàn)ukushima M.A combined smoothing and regularization method for monotone second-order cone complementarity problems[J].SIAM Journal of optimization，2005，15:593-615，.

[3]CHEN X D，SUN D.Complementarity Functions and Numerical Experiments on Some Smoothing Newton Methods For Second Order Cone Complementarity Problems[J].Computational Optimization and Applications，2000，25：362-366.

[4]Chen J S， Tseng P.An unconstrained smooth minimization reformulation of the second order cone complementarity problem[J].Mathematical Programming,2005，104:293-327.

[5]Pan S H，Chen J S.A damped Gauss Newton method for the second-order cone complementarity problem[J].Applied Mathematics and Optimization，2009，59:293-318.

[6]Pang J S，Sun D，Sun J.Semismooth homeomorphisms and strong stability of semidefinite and lorentz cone complementarity problems[J].Mathematics of Operations Research，2003，28:39-63.

[7]Tsuchiya T.A convergence analysis of the scaling-invariant primal-dual path-following algorithms for second-order cone programming[J].optimization methods and software， 1999，11:141-182.

[8]Bai Y Q，Wang G Q.Primal-dual interior-point algorithms for second-order cone optimization based on a new parametric kernel function[J].Acta Mathematica Sinica，English SeriesNov， 2007，23(11):2027-2042.

[9]Pan S H，Chen J S.A class of interior proximal-like algorithms for convex second order cone programming[J].SIAM Journal on Optimization， 2008，19:883-910.

[10]Chi xiaoni，Liu sanyang，Hou duo Qi.An infeasible interior point predictor corrector algorithm for the second-order cone program[J].Acta Mathematica Scientia，2008，28B(3):551-559.

[11]Jein-Shan Chen，Shaohua Pan.A descent method for a reformulation of the second-order cone complementarity problem[J].Journal of Computational and Applied Mathematics， 2008，213:547-558.

[12]王亞，王希云.求非線性互補問題的完全光滑信賴域算法[J].西南民族大學學報:自然科學版，2010,36(5):735-739.

(責任編輯劉舸)

收稿日期：2014-11-27

基金項目：陜西省教育廳科學研究計劃項目(2013JK0602)；咸陽師范學院科研基金項目(10XSYK108).

作者簡介：趙花麗(1979—)，女，博士研究生，講師，主要從事最優(yōu)化理論的研究。

doi:10.3969/j.issn.1674-8425(z).2015.07.022

中圖分類號：O224

文獻標識碼：A

文章編號：1674-8425(2015)07-0120-04

Smoothing Trust Region Algorithm for Linear Second
Order Cone Complementarities Problem

ZHAO Hua-li

(School of Mathematics and Information Science,

Xianyang Normal University, Xianyang 712000, China)

Abstract:Based on the CHKS smoothing function, we presented a new smoothing trust region algorithm for second order cone complementarity problem (SOCCP for short). The method is different from the other trust region method in that the parameters μ and the unknown quantity x, as equally important, were iterated, and we constructed a new parameter λk, and the parameter λkdepended on the current iteration point and its action was similar to the adaptive trust region radius. Under some conditions, we proved the global convergence of the algorithm. The numerical results show the efficiency of the algorithm.

Key words：second order cone complementarily problem; trust region; smoothing method; global convergence

引用格式：趙花麗.線性二階錐互補問題的光滑信賴域法[J].重慶理工大學學報：自然科學版，2015(7):120-123.

Citation format：ZHAO Hua-li.Smoothing Trust Region Algorithm for Linear Second Order Cone Complementarities Problem[J].Journal of Chongqing University of Technology:Natural Science，2015(7):120-123.