線性二階錐互補(bǔ)問(wèn)題的光滑信賴域法

趙花麗

(咸陽(yáng)師范學(xué)院 數(shù)學(xué)與信息科學(xué)學(xué)院，陜西 咸陽(yáng)　712000)

線性二階錐互補(bǔ)問(wèn)題的光滑信賴域法

趙花麗

(咸陽(yáng)師范學(xué)院 數(shù)學(xué)與信息科學(xué)學(xué)院，陜西 咸陽(yáng)712000)

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

關(guān)鍵詞：二階錐互補(bǔ)問(wèn)題；信賴域；光滑算法；全局收斂

線性二階錐互補(bǔ)問(wèn)題：找到x∈Rn，使得：

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

(1)

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

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

1預(yù)備知識(shí)

對(duì)任意的向量x=(x1，x2)，y=(y1，y2)∈R×Rn-1，定義二階錐Kn上的若當(dāng)積：x°y=(〈x，y〉，y1x2+x1y2)。

設(shè)λ1，λ2，u1，u2分別表示x的特征值和相應(yīng)的特征向量，則向量x=(x1，x2)可以表示為：x=λ1u1+λ2u2，其中：

2光滑信賴域法

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

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

(2)

其中：

本文取信賴域的子問(wèn)題如下：

(3)

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

下面給出二階錐互補(bǔ)問(wèn)題的光滑信賴域法。

算法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=-▽?duì)?zk)，令m是滿足下式的最小整數(shù)：

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

(5)

步驟4令k=k+1 ，轉(zhuǎn)步驟1。

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

3收斂性分析

首先做一個(gè)假設(shè)：

假設(shè)1

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

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

引理1假設(shè)序列 {zk}是由算法1產(chǎn)生的序列，則序列{μk} 是單調(diào)下降的，且μk>0。

證明

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

又因?yàn)?<γ<1，所以有μk + 1> 0，μk + 1<μk。

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

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

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

證明

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

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

否則：

所以有

又因?yàn)?/p>

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

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

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

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

4數(shù)值試驗(yàn)

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

2) 步長(zhǎng)小于1.0e-15；

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

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

參考文獻(xià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]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]王亞，王希云.求非線性互補(bǔ)問(wèn)題的完全光滑信賴域算法[J].西南民族大學(xué)學(xué)報(bào):自然科學(xué)版，2010,36(5):735-739.

(責(zé)任編輯劉舸)

收稿日期：2014-11-27

基金項(xiàng)目：陜西省教育廳科學(xué)研究計(jì)劃項(xiàng)目(2013JK0602)；咸陽(yáng)師范學(xué)院科研基金項(xiàng)目(10XSYK108).

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

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

中圖分類號(hào)：O224

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

文章編號(hào)：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

引用格式：趙花麗.線性二階錐互補(bǔ)問(wèn)題的光滑信賴域法[J].重慶理工大學(xué)學(xué)報(bào)：自然科學(xué)版，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.