1、系统科学与数学（）（，），求解随机混合变分不等式问题的方差约减随机算子外推算法杨静龙宪军（重庆工商大学数学与统计学院，重庆 ）摘 要利用方差约减策 略，提出了一种新的随机算子外推 算法求解随机混合 变 分不等 式问题所给算法每次迭代 仅需计 算一次 期望算子的随机近似和一次广义投影在 不需要连续的假设 下，得到了残差意义下的收敛率（），这里表示算法得迭代次数最后，文章 将所给算法应用于求解正则化回归问题、随机网络问题以及资 源调 度问题数值结果展 现了文章 所 提 算法相比已有算法的优越 性关键词随机混合 变 分不等 式，算子外推，距离，资 源调度问题（）主题分类号，），（），重庆 市自然科学
2、基金（），重庆 市 教育 委员会科学技术研究重点项目（），经济社 会应用统计重庆 市重点实验室开放课题（），重庆 市研究 生 导师团队建设项目（），重庆工商大学研究 生 铜新型科研 项目（）资助课题收稿日期：，收到修改稿日期：通信作者：龙 宪军，：编 委：杨新民 系统科学与数学卷 ，引言设？是一个非 空闭凸子 集，：？是正常下 半 连 续凸函数文章考虑 如下的随机混合变 分不等式问题：寻找向量，使之满足（），）（）（），（）这 里）：（：，），其中表示期望算 子，：是概 率空间（仏，）上的随机向量，（，：是一个连 续 可测函数记函数的有效 域：？（在后文中，我们假设，同时记问题（）的解集为近年
3、来，学 者们利用随机混合变分不等式模型求解随机网络问题、资源调度问题、随机复 合优化问题以及随机凸凹鞍点问题等，见文献当（）（）时，即集合的指 示函数时，问题（）退化为随机变 分不等式问题，即寻找向量，使之满足（），），（）许多学 者研究了求解问题（）的算法，见文献特别地，等人运用距离提出了随机镜像近似 算法 等人提出了下述随机算 子外推算法（），（），）（，），这 里是外推系数，是步长，（）是）的随机近似，）表示向量和之间的距离（见 定义）在 算 子是单调且连 续的假设 下，等人网证明了上述算法可以达到（）的收敛 率，这 里表示算法的迭 代 次数对于问题（），和提出了方差约减邻近点算法（）和
4、方差约减向前向后算法（），在 算 子是单调且连 续的假设 下，得到（）的收敛 率注 意到上述算法每 次 迭 代 都需要计算两次的随机近似，这会导致 高 额的计算成本为降低计算成本，和提出了方差约减邻近最优梯度 算法（）和方差约减黄金分割算法（）在同样的假设 下，等人得到了（）的收敛 率另一方面，由于投影可以充分利用可行域的几何结构，从而在求解某些高 维问题时 相 较于欧氏投影有显著优势见文献，基于上述优势，等人提出了一种 加速随机投影 梯度算法求解问题（），在 算 子是单调且连 续的假设 下，同样得到了（）的收敛率注 意到上述求解问题（）的算法都需要 假 设是连 续的但此 假 设对 某些实 际
5、问题可能 不 成立，如 资源 调度问题（见例）因此，在无法 保证连 续的假 设下，如何设计一种投影算法求解问题（）是 文章研究的重点杨静等：求解随机混合 变 分不等 式问题的方差约减随机算子外推 算法期受 到文献的启发，文章 给出一种新的随机投影方法，用于求解随机混合变分不等式问题（）利用间隙函数，在连 续（见 定义）的假 设 下，证明了新算法具有（）的收敛 率预备知识本节主要介绍一些定义和结论用表示 不超过的最大正整数对于一个随机变量和一个域八：，：，用旧表示的数学 期望，表示关于八的条件期望设是？中范数，表示 其对偶范数定义（见）若：？是映射，称（）是单调的，如果（），），（）是连 续的，
6、如果），其中定义（见）令：），即由向量：，张 成的子空间若连 续函数：十满足（）（，），）（，），：（）：（，）；（）（），等式 成立当且仅当別，则称：（：，）为向量在处的一个局部范数进一步，由对偶局部范数的定义可得，由局部范数诱导出来的对偶局部范数为，：，：，这 里表示的对偶空间注在后续的讨论中，为了简单起见，假设存在常数，使 得对任意的以及，都 有事实上，令：，则上述假设显然成立进一步，对任意的以及，有叫叫定理（见）设：为 任意函数，：是其对偶函数满足 尸（）：（），其中：（）则下述不等式恒成立，）（）（），在定理中令（）则有 下述推论成立推 论（不等式）设？是一个局部范数若：满足（）引则
7、有 下述不等式恒成立（？，），定义（见）设是一个局部范数函数称为函数当且仅当是一个下 半 连 续的凸函数；（）对任意的。：抓，都存在）抓（）；系统科学与数学卷（）相对于 局部范数是强凸的，即存在，对任意的和，有（）（）（），恒成立定义（见）设是一个局部范数，是函数对任意的，。，称（，）（）（）（），为 诱导的距离根据距离的定义可得，）（）定义（见）设是一个局部范数，是一个函数，？（：，）是由 诱导的距离若算 子：满足（）（）（，），则称算 子是连 续的，其中注当（）时，连 续 退化 成连 续因此，连 续比连 续更广泛下面的例子进一步说明存在一个函数 满足连 续，但不是连 续的例（见）设：，），
8、十）满足（）：占令：興，易证满足定义，从而是一个局部范数进一步，由局部范数诱导的对偶局部范数，（）取，联立局部范数的定义知是一个函数进一步，由诱导的距离为（，）（），（）其中，）下面验证是连 续的事实上，（）（），本（尸（）（）（，）不等式两边同时 开根号知，是连 续的但是，由于），故不是连 续的对任意的，以及向量，定义广义投影算 子为（：；）：；，（）（），其中：是一个正常下 半连 续的凸函数引理（见）对于 任意的，常数以及向量记：（，则（：）（：）（，）（）（）：），算法和主要结果本文假设（）解集是非 空的（）在 可行域上是单调且连 续的（）对任意的以及，都存在正数別和叱，使 得（：）：（
9、：；）（）以及（）（，）十（）注假设条件（）是研究隨机变分不等式问题和隨机优化问题时 常用的假设，它比文 献，中用到的标准方差一致有 界更弱因为它只要求方差 在解集上有 界，而不是在上有 界杨静等：求解随机混合 变 分不等 式问题的方差约减随机算子外推 算法 期文章提出下述算法算法设置算法的最大迭 代次数为选取初 始点，给定参数序列，汍以及样本量序 列馬根 据样本量。，产生的随机样本：同时计算（；）：益）令，转至步骤步骤产生的随机样本：，计算（）：），其中（；）：忐步骤更新 迭 代点：，）（），）（，）（）令：，转至步骤注若（：），则算法退化为文献中算法注注意到算法每次迭代只需要计算一次算 子
10、的随机近似和一次广义投影，这降低了计算成本其次，由于算法产生的 点列始终属 于可行集，故文章只需假设 算 子在 可行域上是连 续的，这比在？上的连 续性更弱最后，由注知，连 续性比连 续性 更广泛，故算法的适用范围更广注在 算法的迭 代 过 程中，每 次 迭 代 都需要求解一个强凸的子问题（）显然，对于不同的子问题的求解难易程 度不同幸运的是，对于大多数的（，），这个强凸的子问题都具有显示解，见文 献为了方便分析，令：（；）（），厶负：（；）（由于夺是的独立同分布样本，故 对任意的：，有引理假设条件（）成立，是由算法迭 代产生的序 列，则对任意，都 有？（）以证证明过 程与文 献 中命题的证明
11、相似，故这 里省略详细的证明由引理和的有 界性（即对任意的：，都存在常数，使 得）可 得如下推论推论假设条件（）成立，是由算法迭 代产生的序 列若是有 界 集，则对任意，都 有其中：？（）引理对任意的，：，设是一个非负序 列，是任意的一个点令：（）（，），（）则八，），系统科学与数学卷其中为函数 的强凸系数，常数满足 注证根据式（）和引理得，）（）（，），）由式（）和不等式知，）（，）（），）（，）（，）：（，）（，）？（，）（，），）上式对从到求和得，）证毕引理设，是算法产生的序 列假 设条 件（）和（）成立，且参数和？满足，则（，）（）（）￥（）这 里：，迅十，與，？（）：（），十（）（）
12、此外，为函数的强凸系数，常数满足 注证由引理和式（）得（，）（，）（），）（），）（；）（）；），）（）（，）（），），（）（）（）杨静等：求解随机混合 变 分不等 式问题的方差约减随机算子外推 算法期）（，）（，）（，）记私：上式对从到求和，并使用）的定义和（）得（：）（：）（？（）；，）：，（）下面估 计涵，事实上（，）（，）（）（），）：）（，）（）（十，）（：）（：（，）（，）由（），式（）以及不等式知）（），（）（）、：）进一步，联立式（）得）（）（），）（）、同理可 得（？系统科学与数学卷联立（）（）得（，）（，上式结 合（）知八（：（）（，）（？（）；，）（，）八）：）（事实上，
13、根 据假 设（），式（）以及不等式知；，十（，）（）（），）（，；（：）（），卿印，：十卿印，：）（，）；（）（），）（，）；，？）（，）（：，）；（？）（，）类 似 地，）（）：）：）（）（）（）：）（）（，）（，）：）？（）（）（）（）杨静等：求解隨机混合 变 分不等 式问题的方差约减隨机算子外推 算法 联立（）（）得（，（）（，）（）十“，）（，）（，），；）（）￥）（）重 新整理上式，并结 合式（）和的定义知（，）（），）证毕在后续的讨论中，假设是有 界 集定义间隙函数（）：（）（岣容易发现，当且仅当（）引理设是算法产生的序列假设条件（）成立，且参数？和满足（）以及（），则？！，），（
14、）这 里办，为函数的强凸系数，常数满足 注，由推论所定义证首先考虑迅：十，卜设是以铲为初 始点 的任意 隨机过 程，令参数：？，；？记：十卿印，；浐由不等式和引理得（）：）：）十；，）：）：）系统科学与数学卷）：）（，）：；（，？上式结 合（）得（，）（），）二（，）（，）联立（）和（），移项整理得、（）（，）（）（，由的单调 性和的定义知给（）（）？），（）（）（）？十（）（）上式结 合（），对得到的式子取 期望，并使用和推论得（）？十沒（）（）禁：響；出？（）杨静等：求解隨机混合 变 分不等 式问题的方差约减隨机算子外推 算法上式两边同时 除运用不等式，并使用（办）的定义可 得（）证毕下面
15、证明算法的收敛 率定理设是算法产生的序 列假设条件抑）成立，且参数他是一个小 于兹的常数，则（）这 里是一个常数使 得馬满足。表义证由于参数？和汍满足（）以及（），故由引理知（）成立，从而有（）十十 证毕若（），我们有如下推论推 论设（），是算法产生的序 列假 设条 件（）成立，且参数？是一个小 于益的常数，汍，则（）这 里是一个常数使 得馬满足是义注推论从以下两方面改进了文献中命题：（）将连 续性弱化为连 续性；（）通过考虑动 态样本，推论将文 献中命题所得（）收敛 率提升至（）注文 献，考虑了求解随机混合变 分不等式问题（）的邻近点算法在连 续的假设 下，文献，得到了（）的收敛 率文章考虑
16、了求解随机混合变分不等式问题（）的邻近点算法，它包含文献，考虑的邻近点算法作为特例值得注 意的是，文章在不 需要连 续的假 设 下，同样得到了（）的收敛 率数值结果本节通过数值算例将算法与文献中算法和算法，文献中算法和算法进行比较文章的代码都是基于和系统编 系统科学与数学写的，计羿根的基本参数是獅（，为减小 随机因素对实验结果的影响文章展示的数 值实验均为箅法执行次后的平均结果此外，用表示算法的运行时间例考虑如下正则化回归问题跸：其中纪？）（；，）是智量这是一个经典的机器学习问题因为是可微的，所以上述题可转化为下述随机馄合变分不等式问题：寻 找满足），：（），其中（）去，：（）在本例中，我们将算法，与算法和算法进行比较设恤：，三种算法的步长埤：其 他参 数为勒），乳此外，取算 法的距离 生成函数为）？设置最大 迭代次数为 ，用残差丨去 度敖算法的效果在上述参数 假设下，我 们在 表所示的个测试数据集上比较了彐种算法当样本量呈多项式增长，即】（）时，数值结果如图所当样本量几何增长，即踢誠（取傭）时，数值结果如图所示例，滅试菌數据集（）名称数据量变量稀疏度 （）（）（）杨静等：求解随机 混