次梯度外梯度方法求解隨機(jī)變分不等式

張小娟

?

次梯度外梯度方法求解隨機(jī)變分不等式

張小娟

（重慶師范大學(xué)數(shù)學(xué)與科學(xué)學(xué)院，重慶 401331）

隨機(jī)變分不等式在供應(yīng)鏈網(wǎng)絡(luò)、交通運輸和博弈論中具有廣泛的應(yīng)用。提出基于次梯度外梯度的隨機(jī)逼近方法求解隨機(jī)變分不等式，將矯正步的投影改投在半空間，以此來減少計算投影的代價。在適當(dāng)?shù)募僭O(shè)下，證明了所提出的算法具有全局收斂性。

隨機(jī)變分不等式；隨機(jī)逼近；投影算法；次梯度外梯度；全局收斂性

0　引言

目前求解問題(1)最常用的方法主要有兩類，其一是樣本均值逼近(SAA)方法，其二是隨機(jī)逼近(SA)方法。SA方法每次取樣本的個數(shù)少，數(shù)值表現(xiàn)好于SAA。因此，本文主要考慮SA方法解問題(1)。最近Xu等人[3]提出基于基本投影的SA方法求解問題(1)，在強(qiáng)單調(diào)并且Lipschitz連續(xù)下依概率1收斂。隨后有學(xué)者提出基于正則化投影的SA方法求解問題(1)[4-5]，在單調(diào)并且Lipschitz連續(xù)下依概率1收斂。最近Kannan等人[6]提出了基于外梯度的SA方法求解，在偽單調(diào)并且有界或者Lipschitz連續(xù)下依概率1收斂。Iusem等人[7-8]修正外梯度算法，在偽單調(diào)并且Lipschitz連續(xù)下依概率1收斂。

基本投影需要一次投影，計算量小，但實際效果不好。外梯度方法明顯好于基本投影方法，但當(dāng)投影難以計算的時候外梯度方法計算代價大。為此本文結(jié)合兩種投影的優(yōu)點，受確定性VI問題次梯度外梯度算法[9]的啟發(fā)，將基于外梯度的SA方法的第二次投影改投在一個半空間上，提出基于次梯度外梯度的SA方法求解問題(1)，該方法減少了計算代價，在適當(dāng)?shù)募僭O(shè)下獲得全局收斂性。

1　預(yù)備知識

2　算法及其收斂性分析

在解決VI問題中投影算法迭代格式簡單且效果較好，為此本文考慮用投影算法解決SVI問題。目前用投影解決問題（1）的文獻(xiàn)甚少，自從文獻(xiàn)[3]提出基于基本投影的SA方法求解SVI問題后，后面就有學(xué)者提出基于外梯度的SA方法求解SVI問題。眾所周知當(dāng)投影難以計算的時候，外梯度就受限制，而基本投影反而有利。由于基本投影理論不好使用，為此本文考慮修正外梯度算法。受次梯度外梯度算法的啟發(fā)，提出基于次梯度外梯度算法的SA求解SVI問題，該將第二次投影改投在一個半空間上，大大地減少了計算成本，并且還得到好的理論收斂。

次梯度外梯度迭代格式：

為了獲得收斂性我們做如下假設(shè)：

下面將對算法進(jìn)行收斂性分析，首先給出下面的一個引理，該引理對收斂性分析有非常重要的作用。

通過(4)、(6)和引理2得到

因此得到

通過(7)、(8)得到

因此，有

結(jié)合(9)和(10)有

上面引理 3給出了迭代序列的一個遞推關(guān)系，下面定理1是對算法收斂性的證明。

3　總結(jié)

[1] Facchinei F, Pang J S. Finite-Dimensional Variational Inequalities and Complementarity Problems[M].New York: Springer,2003.

[2] Ferris M C, Pang J S. Engineering and economic applications of complementarity problems[J]. SIAM Review, 1997, 39(4): 669-713.

[3] Jiang H, Xu H. Stochastic approximation approaches to the stochastic variational inequality problem[J]. IEEE Transactions on Automatic Control, 2008, 53(6): 1462-1475.

[4] Koshal J, Nedi? A, Shanbhag U V. Regularized iterative stochastic approximation methods for stochastic variational inequality problems[J]. IEEE Transactions on Automatic Control, 2013, 58(3): 594-609.

[5] Yousefian F, Nedié A, Shanbhag U V. On smoothing, regularization, and averaging in stochastic approximation methods for stochastic variational inequality problems[J]. Mathematical Programming, 2017, 165(1): 391-431.

[6] Kannan A, Shanbhag U V. The pseudomonotone stochastic variational inequality problem: Analytical statements and stochastic extragradient schemes[C].American Control Conference (ACC), 2014. IEEE, 2014: 2930-2935.

[7] Iusem A N, Jofré A, Oliveira R I, et al. Extragradient method with variance reduction for stochastic variational inequalities[J]. SIAM Journal on Optimization, 2017, 27(2): 686-724.

[8] Iusem, Alfredo. Variance-based stochastic extragradient methods with linear search for stochastic variational inequalities[J].arXiv preprint arXiv,2017,1703:00262.

[9] Censor Y, Gibali A, Reich S. Extensions of Korpelevich’s extragradient method for the variational inequality problem in Euclidean space[J]. Optimization, 2012, 61(9): 1119-1132.

[10] Robbins H, Siegmund D. A convergence theorem for non negative almost supermartingales and some applications[J]. Optimizing Methods in Statistics, 1971(6):233-257.

Subgradient Extragradient Method for Solving Stochastic Variational Inequality

ZHANG Xiao-juan

(Chongqing Normal University of Mathematics and Science, Changqing, 401331, China)

Stochastic variational inequalities have a wide range of applications in supply chain networks, transportation and game theory. In this paper, the subgradient extragradient algorithm is proposed to solve the stochastic variational inequality, and the projection of the correction step is changed to the half space to reduce the cost of projection calculation . Under appropriate assumptions, we prove that the proposed algorithm has global convergence.

Stochastic variational inequality; stochastic approximation; projection algorithm; subgradient extragradient; global convergence

1674-8085(2019)01-0001-04

O178

A

10.3969/j.issn.1674-8085.2019.01.001

2018-06-11；

2018-11-19

張小娟(1993－)，女，重慶潼南人，碩士，主要從事全局最優(yōu)化理論與算法研究(E-mail:1143182877@qq.com).