周正勇,代恩華

(1.山西師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，山西臨汾 041004;2.聊城大學(xué)東昌學(xué)院數(shù)學(xué)與信息工程系，山東聊城 252000)

求解球約束變分不等式問題的局部光滑化同倫方法

周正勇1,代恩華2

(1.山西師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，山西臨汾 041004;2.聊城大學(xué)東昌學(xué)院數(shù)學(xué)與信息工程系，山東聊城 252000)

給出了一類球型集合上的局部光滑化投影函數(shù),其主要特點(diǎn)是具有較高的計(jì)算效率．基于該局部光滑化投影函數(shù)和Robinson法方程，給出了一種求解球約束變分不等式問題的局部光滑化同倫方法．當(dāng)定義函數(shù)F在可行域上二階連續(xù)可微時(shí)，對(duì)于Rn內(nèi)幾乎所有的初始點(diǎn)，證明了該同倫方法的全局收斂性．?dāng)?shù)值結(jié)果驗(yàn)明了該方法的有效性．

球約束變分不等式；投影函數(shù)；光滑化；同倫方法；全局收斂性

0 引言

(1)

變分不等式問題在科學(xué)及工程領(lǐng)域有著廣泛的應(yīng)用，相關(guān)理論、算法和應(yīng)用可參考文獻(xiàn)[1]．當(dāng)X為某些簡(jiǎn)單的凸集時(shí)，如箱式集合、球型集合，變分不等式問題VIP(F,X)通常被等價(jià)地轉(zhuǎn)化為Robinson法方程[2]：

(2)

其中，ΠX(x)為集合X上的投影函數(shù)．如果x*是方程(2)的根，那么ΠX(x*)是方程(1)的解；反之，如果p*是問題(1)的解，那么p*-F(p*)是方程(2)的根．

本文中，除非特殊說明，X定義為：

(3)

于是問題(1)退化為球約束變分不等式問題BVIP(F,X)．

為了求解BVIP(F,X)的等價(jià)非光滑方程(2)，文獻(xiàn)[3]給出了一種光滑化牛頓法，并且在F在任意點(diǎn)x∈X的雅可比矩陣是半正定的條件下，證明了算法的全局收斂性．為了減弱光滑化牛頓方法的全局收斂性條件，文獻(xiàn)[4]給出了一種光滑化同倫方法，在F在可行域上二階連續(xù)可微的條件下，證明了算法的全局收斂性．

本文首先給出一種球型集合上的局部光滑化投影函數(shù)，它具有一般光滑化投影函數(shù)所具有的性質(zhì)，同時(shí)還有更高的計(jì)算效率．基于該局部光滑化投影函數(shù)和Robinson法方程，給出了一種求解球約束變分不等式問題的光滑化同倫方法．當(dāng)F在可行域X上二階連續(xù)可微時(shí)，對(duì)于Rn內(nèi)幾乎所有的初始點(diǎn)，證明了算法的全局收斂性．初步的數(shù)值結(jié)果驗(yàn)明了該方法的有效性．

1 局部光滑化投影函數(shù)

由投影函數(shù)ΠX(x)非光滑可知法方程(2)也是非光滑的．因此，為了給出一種基于法方程(2)的光滑化方法，首先需要給出一種光滑化投影函數(shù)．在文獻(xiàn)[3]中，利用正函數(shù)[5]的Chen-Harter-Kanzow-Smale光滑化函數(shù)

(4)

其中

給出了如下光滑化投影函數(shù):

(5)

其中

文獻(xiàn)[4]中的光滑化投影函數(shù)與(5)式類似．

引理1[3]φ(x,t)有如下性質(zhì)：

(1)對(duì)任意給定的t>0,φ(·,t)連續(xù)可微.

(2)對(duì)任意給定的t>0,φ(x,t)∈intX.

(4)對(duì)任意給定的t>0,

(6)

(7)

(5)對(duì)任意給定的x∈Rn,t>0，有

(8)

(9)

(10)

首先，給出如下正函數(shù)的局部光滑化函數(shù):

(11)

(12)

引理2ψL(s,t)有如下性質(zhì)：

(1)ψL(s,t)在R×R++上二階連續(xù)可微.

(3)對(duì)任意給定的t>0，

因此，(3)得證． 】

利用正函數(shù)的局部光滑化函數(shù)ψL(s,t)，構(gòu)造如下局部光滑化投影函數(shù):

(13)

其中

引理3φL(x,t)如下性質(zhì)：

(1)φL(x,t)在Rn×R++上二階連續(xù)可微.

(2)對(duì)任意的(x,t)∈(RnXα)×R++，

(3)對(duì)任意給定的t>0,φL(x,t)∈X.

(4)對(duì)任意給定的t>0,

因此，(4)得證． 】

注1 由引理3可知，局部光滑化投影函數(shù)φL(x,t)是二階連續(xù)可微且可行的，且一致逼近于投影函數(shù)ΠX(x)，因此具有一般光滑化投影函數(shù)的主要性質(zhì)．并且對(duì)任意的(x,t)∈(RnXα)×R++,

通過適當(dāng)選取參數(shù)α可以使Xα?Rn為較小的集合．同時(shí)φL(x,t)和φ(x,t)在Xα×R++上的計(jì)算量相差不大．因此，相對(duì)于φ(x,t),φL(x,t)有相似的性質(zhì)且有更高的計(jì)算效率．

2 求解球約束變分不等式問題的局部光滑化同倫方法

為了求解球約束變分不等式問題，基于局部光滑化投影函數(shù)φL(x,t)和Robinson法方程，構(gòu)造如下的局部光滑化同倫(LSH)方程

(14)

其中x0∈Rn為初始點(diǎn)．

則稱y∈Rp為f的是一個(gè)正則值．

證明 將H(x,t)看作是關(guān)于變量(x0,x,t)∈Rn×Rn×R++的映射，直接計(jì)算可得

(15)

非奇異，因此H(x0,x,t)的雅可比矩陣行滿秩，從而0是H(x0,x,t)的一個(gè)正則值．根據(jù)參數(shù)化Sard定理及引理4可知，對(duì)幾乎所有的x0∈Rn，0是H(x,t)的一個(gè)正則值．由

H(x,1)=x-x0

可知，x0是方程H(x,1)=0的唯一的且單的根．根據(jù)隱函數(shù)定理，局部光滑化同倫方程(14)定義了一條在點(diǎn)(x0,1)處穿過超平面t=1的光滑曲線，即存在一條始于(x0,1)的光滑同倫路徑Γx0?Rn×(0,1]． 】

證明 假設(shè)Γx0無界，則必存在一個(gè)無界序列{(xk,tk)}?Rn×(0,1)．由局部光滑化同倫方程(14)可知，

(16)

證明 由引理5，Γx0可以一直延拓直至收斂到Rn×(0,1)的邊界．由引理6，Γx0有界，因此Γx0的任意極限點(diǎn)(x*,t*)都有界．因此，對(duì)于任意極限點(diǎn)(x*,t*)，只有下列兩種可能的情況：

(i)(x*,t*)∈Rn×{1};

( ii )(x*,t*)∈Rn×{0}.

因?yàn)镠(x,1)=x-x0=0僅有唯一的單根x0，所以情形(i)不可能發(fā)生．因此，只有(ii)是可能的情形，即x*是方程(2)的解，ΠX(x*)是BVIP(F,X)的解． 】

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

基于Robinson法方程和箱式集合上的光滑化投影函數(shù)，文獻(xiàn)[7]給出了一種求解混合互補(bǔ)問題的光滑化同倫方法，并給出了一種預(yù)估-校正路徑跟蹤算法．該算法包括三個(gè)主要步驟：預(yù)估步，利用預(yù)估方向和步長(zhǎng)計(jì)算預(yù)估點(diǎn)；校正步，以預(yù)估點(diǎn)為初始點(diǎn)，利用一個(gè)或多個(gè)Newton迭代步計(jì)算校正點(diǎn)；終結(jié)策略，一個(gè)當(dāng)同倫參數(shù)接近0時(shí)比預(yù)估-校正法更有效的策略．關(guān)于預(yù)估-校正算法及其收斂性的更多討論可參考文獻(xiàn)[8-11]．

本文利用球型集合上的局部光滑化投影函數(shù)代替文獻(xiàn)[7]中的箱式集合上的光滑化投影函數(shù)，然后利用文獻(xiàn)[7]的預(yù)估-校正算法對(duì)LSH的同倫路徑進(jìn)行數(shù)值跟蹤．同時(shí)，為了體現(xiàn)該方法的高效性，同樣利用該預(yù)估-校正算法實(shí)現(xiàn)了光滑化同倫(簡(jiǎn)稱為SH)方法，其同倫方程由Robinson法方程和光滑化投影函數(shù)(5)定義．

采用三個(gè)測(cè)試問題對(duì)算法進(jìn)行測(cè)試,第一個(gè)和第三個(gè)測(cè)試問題選自文獻(xiàn)[4]，第二個(gè)測(cè)試問題選自文獻(xiàn)[3]，其變量的維數(shù)可變．對(duì)每個(gè)測(cè)試問題，選取兩個(gè)初始點(diǎn)x0，其中，第一個(gè)是(0,…,0)T∈Rn；第二個(gè)是(1 000,…,1 000)T∈Rn，其距離問題的解相對(duì)較遠(yuǎn)，因此可以用來檢驗(yàn)算法的全局收斂性；x*表示算法最后得到的Robinson法方程(2)的近似解；IT表示在校正步和終結(jié)策略的迭代次數(shù)；Time表示算法的運(yùn)行時(shí)間．選取(11)式中的參數(shù)c=0.01,α=0.1．預(yù)估-校正算法中使用的參數(shù)與文獻(xiàn)[7]一致．

例1[4]

例2[3]

例3[4]

表1 例1的計(jì)算結(jié)果

表2 例2的計(jì)算結(jié)果

表3 例3的計(jì)算結(jié)果

4 結(jié)論

本文首先給出了一類球型集合上的局部光滑化投影函數(shù)，它具有一般光滑化投影函數(shù)所具有的性質(zhì)以及更高的計(jì)算效率．基于該光滑化投影函數(shù)以及Robinson法方程，給出了一種求解球約束變分不等式問題的局部光滑化同倫方法及其全局收斂性分析．初步的數(shù)值實(shí)驗(yàn)表明這種方法具有很好的穩(wěn)定性以及較高的計(jì)算效率．

[1] HARKER P T,PANG J S.Finite-dimensional variational inequality and nonlinear complementarity problems:a survey of theory,algorithms and applications[J].MathematicalProgramming,1990,48:161-220.

[2] ROBINSON S M.Normal maps induced by linear transformations[J].MathematicsofOperationsResearch,1992,17:691-714.

[3] QI Li-qun,ZHOU Guang-lu.A smoothing Newton method for ball constrained variational inequalities with applications[J].Computing,2001,15(Suppl):211-225.

[4] FAN Xiao-na,YAN Qing-lun.Homotopy method for solving ball-constrained variational inequalities[J].NonlinearAnalysis,2011,74:1539-1544.

[5] CHEN Chun-hui,MANGASARIAN O L.A class of smoothing functions for nonlinear and mixed complementarity problems[J].ComputationalOptimizationandApplications,1996,5:97-138.

[6] ALLGOWER E L,GEORG K.NumericalContinuationMethods:AnIntroduction[M].Berlin:Springer,1990.

[7] ZHOU Zheng-yong,YU Bo.A smoothing homotopy method based on Robinson’s normal equation for mixed complementarity problems[J].JournalofIndustrialandManagementOptimization,2011,7(4):977-989.

[8] ALLGOWER E L,GEORG K.NumericalPathFollowing[M]//CIARLET P G,LIONS J L.Handbook of Numerical Analysis Vol 5.Amsterdam:North-Holland,1997.

[9] ALLGOWER E L,GEORG K.IntroductiontoNumericalContinuationMethods[M].Philadelphia:Society for Industrial and Applied Mathematics,2003.

[11] WATSON L T,BILLUPUS S C,MORGAN A P.Algorithm 652.HOMPACK:A suite of codes for globally convergent homotopy algorithms[J].ACMTransactionsonMathematicalSoftware,1987,13:281-310.

(責(zé)任編輯 馬宇鴻)

A locally smoothing homotopy method for solving ball constrained variational inequality problems

ZHOU Zheng-yong1,DAI En-hua2

(1.School of Mathematics and Computer Sciences,Shanxi Normal University,Linfen 041004,Shanxi,China; 2.Department of Mathematics and Information Engineering of Dongchang School,Liaocheng University, Liaocheng 252000,Shandong,China)

In this paper,a locally smoothing projection function onto the ball set is provided.The primary feature of this smoothing projection function is its high computational efficiency.By using this locally smoothing projection function and the Robinson’s normal equation,a locally smoothing homotopy method is proposed for solving ball constrained variational inequality problems.Under the condition that the defining function is twice continuously differentiable on the feasible region,for almost all starting point in Rn,the global convergence of the proposed homotopy method is proved.Preliminary numerical results indicate that the proposed homotopy method is effective.

ball constrained variational inequalities;projection function;smoothing;homotopy method;global convergence

2014-11-26;修改稿收到日期:2015-04-27

山西師范大學(xué)自然科學(xué)基金資助項(xiàng)目(ZR1303)

周正勇(1982—)，男，山東聊城人，講師，博士.主要研究方向?yàn)閿?shù)值優(yōu)化. E-mail:zzy198300@163.com

O 221.2

A

1001-988Ⅹ(2015)04-0001-05