求解随机线性互补问题的Barzilai-Borwein算法

2015-12-20 01:09
电子科技 2015年2期
关键词:投影梯度数值

魏 潇

(西安电子科技大学数学与统计学院,陕西西安 710126)

考虑概率空间(Ω,F,P),其中,Ω∈Rm是相应的样本空间,P是已知的概率分布。随机线性互补问题[1-7](SLCP)定义为,求 x∈Rn满足

其中,ω∈Ω 是随机变量;M(ω)∈Rn×n和q(ω)∈Rn分别是关于ω的随机矩阵和随机向量;a.s.表示几乎必然成立。

通常,不存在x使得对所有的ω∈Ω,式(1)均有解。解决式(1)常用的方法是寻求适当的再定形式,将其转化为约束优化问题。Gürkan等[1]提出了期望值(EV)模型Rn满足

此外,Chen和Fukushima[2]提出了求解SLCP的期望残差(ERM)模型:求极小化问题

的最优解。其中

这里 Ψ∶R2→R 是一个 NCP 函数,Ψ(a,b)=0 ⇐⇒a≥0,b≥0,ab=0。

常用的NCP函数有min函数Ψmin(a,b)=min(a,b)和 Fischer-Burmeister(FB)[8]函数 ΨFB(a,b)=a+

Chen和Zhang等[6]指出,由 ERM 模型所得到的数值解具有鲁棒性。本文考虑随机线性互补问题的ERM模型

其中,ΨFB(x,ω)是由函数 ΨFB(·)对应形如式(4)的向量。

Zhang和Chen[3]提出了求解 ERM 模型的光滑投影梯度(SPG)算法。该算法借助经典的求解约束极小化问题的投影梯度法[9]对ERM模型进行求解。通过数值实验可发现,算法中求解投影梯度方向时耗时较大。因此,需研究求解该模型更有效的算法。

文中假设M(ω)和q(ω)是ω的可测函数,且

定理 1[4,10-11]f(x)在 Rn上是连续可微的。

定义1[7]称 M(·)是随机 R矩阵,若 x≥0,0M(ω)x≥0,xTM(ω)x=0,a.e.⇒x=0。

引理 2[6]若是R矩阵,则M(·)是随机R00矩阵。

定理 2[6]对任意的q(·),ERM(M(·),q(·))的解集非空有界,当且仅当M(·)是随机R0矩阵。

1 Barzilai-Borwein算法

借鉴 Liu 等[12-13]提出的求解 SLCP 的 Barzilai-Borwein(BB)算法,借助有效集策略,文中给出了求解SLCP的ERM模型BB算法。算法旨在求模型(5)的极小点,由引理1可知,在极小点处必有xki和▽f(xk)i(i=1~n)至少其中之一为0。据此可定义有效集

其中,N={1,2,L,n}。显然,集合 U(xk)和 S(xk)所对应的元素不满足局部极小点条件,因此可对该部分元素进行迭代更新。定义搜索方向

在此,γk即 Barzilai-Borwein步

其中,sk-1=xk-xk-1,yk-1=▽f(xk)- ▽f(xk-1),γmax>γmin>0。

算法1

步骤1 选择参数 ρ,σ∈(0,1),令 x0≥0,k:=0。

步骤2 (非单调线搜索)记mk为满足下式的最小非负整数。

令λk= ρmdk,xk+1=xk+ λkdk。

步骤3 令k:=k+1,转步骤2。

2 数值结果

其中,Nl表示所选取的样本数,ω1,ω2,L,ωNl是由Monte Carlo法得到的独立同分布样本。进一步可计算其梯度的近似值

其中,VΨ(x,ωi)为 Ψ(x,ωi)在 x处的广义雅克比矩阵,其计算方法如文献[4]所示。

生成测试问题的步骤如文献[6]。对每个测试问题,向量x%∈Rn+均是随机生成的,其中,有n0(<n)个元素在区间(0,c1)上,c1>0,且期望矩阵正定。若c3=0,则x%是式(5)的一个解;若c3>0,则x%不一定是式(5)的解,且测试问题本身可能无解。由于是正定矩阵,故其是一个R0矩阵[8],根据引理2及定理2,式(5)的解集为非空有界。

对算法1与文献[3]中的SPG算法分别在c3=0和c3>0时进行比较。算法1和SPG算法的终止条件为。当终止条件满足或迭代次数超过100时,终止计算。

通过实验,算法1中所用到的参数取值为ρ=0.25,σ =10-4,C=5,γmax=106,γmin=10-6。测试问题的参数选取 c1=20,μ =10,c4=15。

对所有的测试问题,初始迭代点均选为

对每个初始迭代点,随机生成10个问题,表1和表 2 中,测试问题记为(Nl,n,n0,c2,c3),Itr表示平均迭代次数,Time表示平均CPU运行时间,x1和x2分别表示SPG算法和算法1的数值解,f(·)代表对应的函数值。通过计算迭代点处r(·)的值来检验其最优性。对于c3=0的情况,计算所得数值解x的相对误差图1和图2中分别记录了c=03和c3>0时一定规模问题的迭代时间Time与迭代点处最优性度量r(·)的变化情况。

表1 算法SPG和算法1的比较(c3=0)

表2 算法SPG和算法1的比较(c3>0)

图1 c3=0,规模为Nl=1 000,n=50的数值结果

图2 c3>0,规模为Nl=1 000,n=100的数值结果

通过表1与表2及图1与图2的对比可发现,两算法所求得的最优值相差较小。算法1虽在一些问题上比SPG算法的迭代次数略多,但却能在更短的时间内达到与SPG算法相近的效果,因此表明算法1的单步迭代耗时更少,并能更快地收敛到极小点。而导致这一结果的原因是SPG算法在计算投影梯度时耗费较大,而算法1借助有效集策略,使用BB步进行迭代,缩短了计算时间。

[1]Gürkan G,Özge A Y,Robinson SM.Sample- path solution of stochastic variational inequalities[J].Mathematical Programming,1999,84(6):313 -333.

[2]Chen Xiaojun,Fukushima M.Expected residual minimization method for stochastic linear complementarity problems[J].Math Operation Result,2005,30(6):1022 -1038.

[3]Zhang Chao,Chen Xiaojun.Smoothing projected gradient method and its application to stochastic linear complementarity problems[J].SIAM Journal Optimization,2009,20(3):627 -649.

[4]Zhou Guanglu,Caccetta L.Feasible semismooth newton method for a class of stochastic linear complementarity problems[J].Journal Optimization Throry Application,2008,13(9):379-392.

[5]Lin Guihua,Fukushima M.Stochastic equilibrium problem and stochastic mathematical programs with equilibrium constrains:A survey[R].Kyoto:Department of Applied Mathematics and Physics,Kyoto University,2009.

[6]Chen Xiaojun,Zhang Chao,Fukushima M.Robust solution of monotone stochastic linear complementarity problems [J].Math Program,2009,117(3):51 -80.

[7]Fang Haitao,Chen Xiaojun,Fukushima M.Stochastic R_0 matrix linear complementarity problems[J].SIAM Journal Optimization,2007(18):482 -506.

[8]韩继业,修乃华,戚厚铎.非线性互补理论与算法[M].上海:上海科技出版社,2006.

[9]袁亚湘,孙文瑜.最优化理论与方法[M].北京:科学出版社,1997.

[10]Sun Defeng,Qi Liqun.On NCP functions[J].Computational Optimization Application,1999(13):201 -220.

[11]Chen Bintong,Chen Xiaojun,Christian Kanzow,et al.On NCP functions[J].Computational Optimization Application,2000,88,(3):211 -216.

[12]Li Xiangli,Liu Hongwei,Sun Xiaojun.Feasible smooth method based on Barzilai-Borwein method for stochastic linear complementarity problem [J].Numerical Algorithms,2011,57(6):207-215.

[13]Huang Yakui,Liu Hongwei,Zhou Sha.A barzilai- borwein type method for stochastic linear complementarity problems[J].Complementarity Problem Numerical Algorithms,2011,57(2):207-215.

猜你喜欢
投影梯度数值
一个带重启步的改进PRP型谱共轭梯度法
一个改进的WYL型三项共轭梯度法
数值大小比较“招招鲜”
解变分不等式的一种二次投影算法
基于最大相关熵的簇稀疏仿射投影算法
一种自适应Dai-Liao共轭梯度法
一个具梯度项的p-Laplace 方程弱解的存在性
找投影
找投影
基于Fluent的GTAW数值模拟