求解球约束变分不等式问题的局部光滑化同伦方法

周正勇,代恩华

(1.山西师范大学数学与计算机科学学院，山西临汾 041004;2.聊城大学东昌学院数学与信息工程系，山东聊城 252000)

求解球约束变分不等式问题的局部光滑化同伦方法

周正勇1,代恩华2

(1.山西师范大学数学与计算机科学学院，山西临汾 041004;2.聊城大学东昌学院数学与信息工程系，山东聊城 252000)

给出了一类球型集合上的局部光滑化投影函数,其主要特点是具有较高的计算效率．基于该局部光滑化投影函数和Robinson法方程，给出了一种求解球约束变分不等式问题的局部光滑化同伦方法．当定义函数F在可行域上二阶连续可微时，对于Rn内几乎所有的初始点，证明了该同伦方法的全局收敛性．数值结果验明了该方法的有效性．

球约束变分不等式；投影函数；光滑化；同伦方法；全局收敛性

0 引言

(1)

变分不等式问题在科学及工程领域有着广泛的应用，相关理论、算法和应用可参考文献[1]．当X为某些简单的凸集时，如箱式集合、球型集合，变分不等式问题VIP(F,X)通常被等价地转化为Robinson法方程[2]：

(2)

其中，ΠX(x)为集合X上的投影函数．如果x*是方程(2)的根，那么ΠX(x*)是方程(1)的解；反之，如果p*是问题(1)的解，那么p*-F(p*)是方程(2)的根．

本文中，除非特殊说明，X定义为：

(3)

于是问题(1)退化为球约束变分不等式问题BVIP(F,X)．

为了求解BVIP(F,X)的等价非光滑方程(2)，文献[3]给出了一种光滑化牛顿法，并且在F在任意点x∈X的雅可比矩阵是半正定的条件下，证明了算法的全局收敛性．为了减弱光滑化牛顿方法的全局收敛性条件，文献[4]给出了一种光滑化同伦方法，在F在可行域上二阶连续可微的条件下，证明了算法的全局收敛性．

本文首先给出一种球型集合上的局部光滑化投影函数，它具有一般光滑化投影函数所具有的性质，同时还有更高的计算效率．基于该局部光滑化投影函数和Robinson法方程，给出了一种求解球约束变分不等式问题的光滑化同伦方法．当F在可行域X上二阶连续可微时，对于Rn内几乎所有的初始点，证明了算法的全局收敛性．初步的数值结果验明了该方法的有效性．

1 局部光滑化投影函数

由投影函数ΠX(x)非光滑可知法方程(2)也是非光滑的．因此，为了给出一种基于法方程(2)的光滑化方法，首先需要给出一种光滑化投影函数．在文献[3]中，利用正函数[5]的Chen-Harter-Kanzow-Smale光滑化函数

(4)

其中

给出了如下光滑化投影函数:

(5)

其中

文献[4]中的光滑化投影函数与(5)式类似．

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

(1)对任意给定的t>0,φ(·,t)连续可微.

(2)对任意给定的t>0,φ(x,t)∈intX.

(4)对任意给定的t>0,

(6)

(7)

(5)对任意给定的x∈Rn,t>0，有

(8)

(9)

(10)

首先，给出如下正函数的局部光滑化函数:

(11)

(12)

引理2ψL(s,t)有如下性质：

(1)ψL(s,t)在R×R++上二阶连续可微.

(3)对任意给定的t>0，

因此，(3)得证． 】

利用正函数的局部光滑化函数ψL(s,t)，构造如下局部光滑化投影函数:

(13)

其中

引理3φL(x,t)如下性质：

(1)φL(x,t)在Rn×R++上二阶连续可微.

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

(3)对任意给定的t>0,φL(x,t)∈X.

(4)对任意给定的t>0,

因此，(4)得证． 】

注1 由引理3可知，局部光滑化投影函数φL(x,t)是二阶连续可微且可行的，且一致逼近于投影函数ΠX(x)，因此具有一般光滑化投影函数的主要性质．并且对任意的(x,t)∈(RnXα)×R++,

通过适当选取参数α可以使Xα⊂Rn为较小的集合．同时φL(x,t)和φ(x,t)在Xα×R++上的计算量相差不大．因此，相对于φ(x,t),φL(x,t)有相似的性质且有更高的计算效率．

2 求解球约束变分不等式问题的局部光滑化同伦方法

为了求解球约束变分不等式问题，基于局部光滑化投影函数φL(x,t)和Robinson法方程，构造如下的局部光滑化同伦(LSH)方程

(14)

其中x0∈Rn为初始点．

则称y∈Rp为f的是一个正则值．

证明 将H(x,t)看作是关于变量(x0,x,t)∈Rn×Rn×R++的映射，直接计算可得

(15)

非奇异，因此H(x0,x,t)的雅可比矩阵行满秩，从而0是H(x0,x,t)的一个正则值．根据参数化Sard定理及引理4可知，对几乎所有的x0∈Rn，0是H(x,t)的一个正则值．由

H(x,1)=x-x0

可知，x0是方程H(x,1)=0的唯一的且单的根．根据隐函数定理，局部光滑化同伦方程(14)定义了一条在点(x0,1)处穿过超平面t=1的光滑曲线，即存在一条始于(x0,1)的光滑同伦路径Γx0⊂Rn×(0,1]． 】

证明 假设Γx0无界，则必存在一个无界序列{(xk,tk)}⊂Rn×(0,1)．由局部光滑化同伦方程(14)可知，

(16)

证明 由引理5，Γx0可以一直延拓直至收敛到Rn×(0,1)的边界．由引理6，Γx0有界，因此Γx0的任意极限点(x*,t*)都有界．因此，对于任意极限点(x*,t*)，只有下列两种可能的情况：

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

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

因为H(x,1)=x-x0=0仅有唯一的单根x0，所以情形(i)不可能发生．因此，只有(ii)是可能的情形，即x*是方程(2)的解，ΠX(x*)是BVIP(F,X)的解． 】

3 数值试验

基于Robinson法方程和箱式集合上的光滑化投影函数，文献[7]给出了一种求解混合互补问题的光滑化同伦方法，并给出了一种预估-校正路径跟踪算法．该算法包括三个主要步骤：预估步，利用预估方向和步长计算预估点；校正步，以预估点为初始点，利用一个或多个Newton迭代步计算校正点；终结策略，一个当同伦参数接近0时比预估-校正法更有效的策略．关于预估-校正算法及其收敛性的更多讨论可参考文献[8-11]．

本文利用球型集合上的局部光滑化投影函数代替文献[7]中的箱式集合上的光滑化投影函数，然后利用文献[7]的预估-校正算法对LSH的同伦路径进行数值跟踪．同时，为了体现该方法的高效性，同样利用该预估-校正算法实现了光滑化同伦(简称为SH)方法，其同伦方程由Robinson法方程和光滑化投影函数(5)定义．

采用三个测试问题对算法进行测试,第一个和第三个测试问题选自文献[4]，第二个测试问题选自文献[3]，其变量的维数可变．对每个测试问题，选取两个初始点x0，其中，第一个是(0,…,0)T∈Rn；第二个是(1 000,…,1 000)T∈Rn，其距离问题的解相对较远，因此可以用来检验算法的全局收敛性；x*表示算法最后得到的Robinson法方程(2)的近似解；IT表示在校正步和终结策略的迭代次数；Time表示算法的运行时间．选取(11)式中的参数c=0.01,α=0.1．预估-校正算法中使用的参数与文献[7]一致．

例1[4]

例2[3]

例3[4]

表1 例1的计算结果

表2 例2的计算结果

表3 例3的计算结果

4 结论

本文首先给出了一类球型集合上的局部光滑化投影函数，它具有一般光滑化投影函数所具有的性质以及更高的计算效率．基于该光滑化投影函数以及Robinson法方程，给出了一种求解球约束变分不等式问题的局部光滑化同伦方法及其全局收敛性分析．初步的数值实验表明这种方法具有很好的稳定性以及较高的计算效率．

[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.

(责任编辑 马宇鸿)

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

山西师范大学自然科学基金资助项目(ZR1303)

周正勇(1982—)，男，山东聊城人，讲师，博士.主要研究方向为数值优化. E-mail:zzy198300@163.com

O 221.2

A

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