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

魏 潇

(西安电子科技大学数学与统计学院，陕西西安 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.