A Projection and Contraction Method for P-Order Cone Constraint Stochastic Variational Inequality Problem

Mengdi Zheng, Xiaohui Xu, Juhe Sun

School of Science, Shenyang Aerospace University, Shenyang, China.

DOI: 10.4236/jamp.2022.104078                

Abstract

In this paper, we study the p-order cone constraint stochastic variational inequality problem. We first take the sample average approximation method to deal with the expectation and gain an approximation problem, further the rationality is given. When the underlying function is Lipschitz continuous, we acquire a projection and contraction algorithm to solve the approximation problem. In the end, the method is applied to some numerical experiments and the effectiveness of the algorithm is verified.

Keywords

Stochastic Variational Inequality, Sample Average Approximation, Projection and Contraction Method, Convergence Analysis, Numerical Experiments

1. Introduction

Variational inequality has important applications in many aspects such as physics, economic equilibrium theory, cybernetics, engineering, optimization, etc. [1] [2] [3]. Since there are many random factors that cannot be ignored in real life, such as weather, demand, price, etc., stochastic variational inequality has become a research hot-spot of many scholars in recent decades. In this paper, we consider the stochastic variational inequality problem with p-order cone (abbrevd.POSVI), which is to find $x\in C$, such that

$\langle E\left[f\left(x\mathrm{,}\xi \right)\right]\mathrm{,}y-x\rangle \ge \mathrm{0,}\forall y\in C$ (1)

where $\langle \cdot \mathrm{,}\cdot \rangle$ denotes the Euclidean inner product, $\xi$ is a random variable defined in probability $\Omega$, $E\left[f\left(x\mathrm{,}\xi \right)\right]={\displaystyle {\int }_{\Omega }}f\left(x\mathrm{,}\xi \left(\omega \right)\right)\text{d}P\xi \left(\omega \right)$ is the expectation of $\xi$, $f\left(x\mathrm{,}\xi \right)\mathrm{<mo>\; :\; </mo>}{R}^n\times \Omega \to R^n$ is a given mapping, $C=\left\{x\mathrm{<mo>\; |\; </mo>}x\in K_p\right\}$, $K_p$ is a p-order cone, $K_p^{\ast }$ is the dual cone of $K_p$, which can be expressed as [4]:

$\begin{array}{l}{K}_p:=\left\{x\in R^n|x_0\ge {\left({\displaystyle \underset{i=2}{\overset{n}{\sum }}}{\left|x_i\right|}^p\right)}^{\frac{1}{p}}\right\}\\ =\left\{x=\left(x_0,\bar{x}\right)\in R\times R^{n-1}|x_0\ge {\Vert \bar{x}\Vert }_p\right\}\left(p>1\right)\end{array}$

$\begin{array}{l}{K}_p^{\ast }:=\left\{y\in R^n|y_0\ge {\left({\displaystyle \underset{i=2}{\overset{n}{\sum }}}{\left|y_i\right|}^q\right)}^{\frac{1}{q}}\right\}\\ =\left\{y=\left(y_0,\bar{y}\right)\in R\times R^{n-1}|y_0\ge {\Vert \bar{y}\Vert }_q\right\}=K_q\end{array}$

where $q>1$ and satisfies $\frac{1}{p}+\frac{1}{q}=1$. $K_p$ and $K_p^{\ast }$ are both closed convex cone, $K_p$ is not a self-dual cone when $p\ne q$, in other words, the $K_p$ is not a symmetric cone for $p\ne 2$. It is clear that the p-order cone is the second-order cone with n-dimension when $p=2$, which means:

$K^n:=\left\{\left(x_1,x_2\right)\in R\times R^{n-1}|x_1\ge \Vert x_2\Vert \right\}$

Thus, the POSVI in this paper can be regarded as an extension of the second-order constrained stochastic variational inequality problem. The research of theory and algorithm has made great progress in recent decades. Our research focuses on transforming solving the POSVI into finding the zero point of equation and constructing optimization algorithm under certain condition. Hence, the work below is down first.

Assume that a closed convex subset of $R^n$ is C and $x\in R^n$, then the projection of x on C is [5]:

$P_C\left(x\right)=\arg \min \left\{\Vert y-x\Vert |y\in C\right\}$ (2)

Refer to reference [6], $x^{\mathrm{<mo>\; *\; </mo>}}$ is the solution of problem (1) if and only if for any $\alpha$, the equation holds below

$x^{*}=P_C\left(x^{*}-\alpha E\left[f\left(x^{*},\xi \right)\right]\right)$ (3)

Define the residual of the equation as $G\left(x\mathrm{,}\alpha \right)$

$G\left(x\mathrm{,}\alpha \right)\mathrm{<mo>\; :\; </mo>}=x-P_C\left(x-\alpha E\left[f\left(x\mathrm{,}\xi \right)\right]\right)$ (4)

then, solving POSVI only needs to find a zero point of $G\left(x\mathrm{,}\alpha \right)$.

In the following, we concentrate on constructing algorithm to solve the problem. There are some optimization algorithms that have been applied to stochastic optimization problem, for example, Korpelevich and Antipin study the outer gradient projection algorithm and every iteration should compute the projection twice, see [7] [8]. On the basis of previous research, Tseng proposes a gradient projection algorithm and every iteration only should compute a projection one time, see [9]. Different from the first two algorithms, Duong and Yekini receive step size through Amjo-type search method, which can decrease the difficulty of [9] to estimate the Lipschitz constant, see [10] [11]. Under a mapping is monotone and Lipschitz continuous, Yang and Liu give a projection algorithm and the better of which is that the compute of the step size does not depend on Amjo-like search, see [12] [13] [14]. Combined the above algorithms, we propose a projection and contraction method.

The organizational framework of this paper is as follows: In part 2, we introduce some definitions and conclusions about the p-order cone. In part 3, the basic idea of sample average approximation method is shown and the revelent conclusions are given. In part 4, a projection and contraction method is proposed and it is proved that the sequence generated by the method converges to the real solution. In part 5, a numerical example is given, and the method is applied to solve it. The numerical results claim that the method is effective. In part 6, the work of this paper is summarized and future research topic is given.

2. Preliminaries

In this section, we give some basic concepts and conclusions related to p-order cone in order to facilitate the following research.

Definition 2.1 ( [15] ). Let $h\mathrm{<mo>\; :\; </mo>}{R}^n\to R^n$ be Lipschitz continuous then for any $x\mathrm{,}y\in R^n$ , there exist a constant $L>0$ , such that

$\Vert h\left(x\right)-h\left(y\right)\Vert \le L\Vert x-y\Vert$

Definition 2.2 ( [15] ). Let $h\mathrm{<mo>\; :\; </mo>}{R}^n\to R^n$. Then for any $x\mathrm{,}y\in R^n$ , the mapping h is said to be

(a) monotoneif

$\langle x-y\mathrm{,}h\left(x\right)-h\left(y\right)\rangle \ge 0$

(b) strictlymonotone if

$\langle x-y,h\left(x\right)-h\left(y\right)\rangle >0$

(c) stronglymonotone with constant $\beta >0$ if

$\langle x-y\mathrm{,}h\left(x\right)-h\left(y\right)\rangle \ge \beta {\Vert x-y\Vert }^2$

Definition 2.3. ( [4] ). For any $x=\left(x_0\mathrm{,}\bar{x}\right)\in R\times R^{n-1}$ and $y=\left(y_0\mathrm{,}\bar{y}\right)\in R\times R^{n-1}$ , the Jordan product of p-order cone is expressed by

$x\cdot y\mathrm{<mo>\; :\; </mo>}=\left[\begin{array}{c}\langle x\mathrm{,}y\rangle \\ w\end{array}\right]$

where $w\mathrm{<mo>\; :\; </mo>}={\left(w_2\mathrm{,}\cdots \mathrm{,}{w}_n\right)}^{\text{T}}$ , and $w_i={\left|x_0\right|}^{\frac{p}{q}}\left|y_i\right|-\left|y_0\right|{\left|x_i\right|}^{\frac{p}{q}}$ , $i=2,3,\cdots ,n$.

Definition 2.4. ( [16] ). Let $x=\left(x_0\mathrm{,}\bar{x}\right)\in R\times R^{n-1}$. Then, the projection of x onto $K_p$ is defined as

${\Pi }_{K_p}\left(x\right)=\{\begin{array}{l}x,x\in K_p\\ 0,x\in -K_p^{*}=-K_q\\ \nu ,-{\Vert \bar{x}\Vert }_q<x_0<{\Vert \bar{x}\Vert }_p\end{array}$ (5)

where $\nu =\left({\nu }_0\mathrm{,}\bar{\nu }\right)$, $\bar{\nu }={\left({\nu }_2,{\nu }_3\mathrm{,}\cdots \mathrm{,}{\nu }_n\right)}^{\text{T}}\in R^{n-1}$ with

${\nu }_0={\Vert \bar{\nu }\Vert }_p={\left({\left|{\nu }_2\right|}^p+{\left|{\nu }_3\right|}^p+\cdots +{\left|{\nu }_n\right|}^p\right)}^{\frac{1}{p}}$

${\nu }_i-x_i+\frac{{\nu }_0-x_0}{{\nu }_0^{p-1}}{\left|{\nu }_i\right|}^{p-2}{\nu }_i=0,\forall i=2,\cdots ,n.$

Definition 2.5. ( [16] ). Let $x=\left(x_0\mathrm{,}\bar{x}\right)\in R\times R^{n-1}$ , then x can be decomposed into

$x={\rho }_1\left(x\right)\cdot v^{\left(1\right)}\left(x\right)+{\rho }_2\left(x\right)\cdot v^{\left(2\right)}(\; x\; )$

where

$\begin{array}{l}{\rho }_1\left(x\right)=\frac{x_0+{\Vert \bar{x}\Vert }_p}{2}\\ {\rho }_2\left(x\right)=\frac{x_0-{\Vert \bar{x}\Vert }_p}{2}\end{array}$

$\begin{array}{l}{v}^{\left(1\right)}\left(x\right)=\left[\begin{array}{c}1\\ w\end{array}\right]\\ v^{\left(2\right)}\left(x\right)=\left[\begin{array}{c}1\\ -w\end{array}\right]\end{array}$

and $w=\frac{\bar{x}}{\Vert \bar{x}\Vert }$ if $\bar{x}\ne 0$. If $\bar{x}=0$, then any vector in $R^{n-1}$ satisfying $\Vert w\Vert =1$ .

Lemma 2.1. ( [5] ). If the projection formula is defined as (2), then the properties below can be received:

(i) ${\left\{x-P_C\left(x\right)\right\}}^{\text{T}}\left\{\kappa -P_C\left(x\right)\right\}\le \mathrm{0,}\forall x\in R^n\mathrm{,}\forall \kappa \in C\mathrm{.}$

(ii) ${\left\{x-y\right\}}^{\text{T}}\left\{P_C\left(x\right)-P_C\left(y\right)\right\}\ge {\Vert P_C\left(x\right)-P_C\left(y\right)\Vert }^2\mathrm{,}\forall x\mathrm{,}y\in R^n\mathrm{.}$

(iii) $\Vert P_C\left(x\right)-P_C\left(y\right)\Vert \le \Vert x-y\Vert \mathrm{,}\forall x\mathrm{,}y\in R^n\mathrm{.}$

(iv) ${\Vert P_C\left(x\right)-\lambda \Vert }^2\le {\Vert x-\lambda \Vert }^2-{\Vert x-P_C\left(x\right)\Vert }^2\mathrm{,}\forall \lambda \in C\mathrm{.}$

3. Sample Average Approximation

If the integral involved in POSVI can be evaluated, then it can be solved as a deterministic stochastic variational inequality problem. However, $E\left[f\left(x\mathrm{,}\xi \right)\right]$ are usually not accurately evaluated, because the distribution of $\xi$ is unknown and the information of $\xi$ can only be acquired from the past data samples, which inspires us to search a function to approximate $E\left[f\left(x\mathrm{,}\xi \right)\right]$. Many scholars have explored approximation methods [17] [18] [19]: sample-path optimization (SPO), sample average approximation (SAA) and stochastic approximation (SA). In this paper, we select SAA method, whose main idea is to generate N independent and identically distributed (i.i.d.) samples ${\xi }_1\mathrm{,}{\xi }_2\mathrm{,}\cdots \mathrm{,}{\xi }_N$, and use the sample average function

$F^N\left(x\right)=\frac{1}{N}{\displaystyle \underset{i=1}{\overset{N}{\sum }}}f\left(x,{\xi }_i\right)$

to approximate $E\left[f\left(x\mathrm{,}\xi \right)\right]$. Then we acquire the problem: find $x\in C$, such that

$\langle F^N\left(x\right)\mathrm{,}y-x\rangle \ge \mathrm{0,}\forall y\in C$ (6)

where $C=\left\{x\mathrm{<mo>\; |\; </mo>}x\in K_p\right\}$, we call (1) as true problem and (6) as SAA problem.

Definition 3.1 ( [20] ) Let $f_j\left(x\mathrm{,}\xi \right)$ denote jth component of $f\left(x\mathrm{,}\xi \right)$ , $j=1,2,\cdots ,N$. Define the moment function of $f_j\left(x\mathrm{,}\xi \right)$ as:

$M_{f_j}\left(t\right)\mathrm{<mo>\; :\; </mo>}=E\left[{\text{e}}^{t{f}_j\left(x\mathrm{,}\xi \right)}\right]$

andthe moment function of $f_j\left(x\mathrm{,}\xi \right)-E\left[f_j\left(x\mathrm{,}\xi \right)\right]$ is

$M_x\left(t\right):=E\left[{\text{e}}^{t\left(f_j\left(x,\xi \right)-E\left[f_j\left(x,\xi \right)\right]\right)}\right]$

thus,

$M_{f_j}^N\left(t\right):=E\left[{\text{e}}^{t\left(F_j^N\left(x\right)-E\left[f_j\left(x\mathrm{,}\xi \right)\right]\right)}\right]$

Lemma 3.1. ( [20] ) Let X be a compact subset of C, $j=1,2,\cdots ,n$. Suppose the conditions hold below:

1) The moment function $M_x\left(t\right)$ is finite with respect to (w.r.t.) x in a certain neighborhood of zero;

2)There is a metric function $k\left(\xi \right)\mathrm{<mo>\; :\; </mo>}\Omega \to R_{+}$ ,such that for any $\xi \in \Omega$,and $x^{\prime }\mathrm{,}x\in X$ , there is

$\left|f_j\left(x^{\prime }\mathrm{,}\xi \right)-f_j\left(x\mathrm{,}\xi \right)\right|\le k_j\left(\xi \right)\Vert x^{\prime }-x\Vert$

3) The moment function $M_k\left(t\right)=E\left[{\text{e}}^{tk\left(\xi \right)}\right]$ of $k\left(\xi \right)$ is finite w.r.t. t in a certain neighborhood of zero.

Then for any $\epsilon >0$, there exists $c\left(\epsilon \right)>0$, $\beta \left(\epsilon \right)>0$,independent of N, such that

$\text{Prob}\left\{\underset{x\in X}{\sup }\Vert E\left[f\left(x\mathrm{,}\xi \right)\right]-F^N\left(x\right)\Vert \ge \epsilon \right\}\le c\left(\epsilon \right){\text{e}}^{-N\beta (\; \epsilon \; )}$

Lemma 3.1 guarantees that the approximation by the SAA method is reasonable.

Lemma 3.2. ( [21] ). Let $\left\{x^N\right\}$ be a solution of SAA problem (6) and $x^{\mathrm{<mo>\; *\; </mo>}}$ be set of solutions to true problem (1). Suppose that:

a) Lemma 3.1 holds;

b) $M_{f_j}\left(t\right):={\lim }_{N\to \infty }{M}_{f_j}^N\left(t\right)$ ( $j=1,2,\cdots ,n$ ) exists, for every $x\in X$ and $t\in R$ ;

Then for every $\epsilon >0$ , there is $c\left(\epsilon \right)>0$, $\beta \left(\epsilon \right)>0$, independent of N, such that

$\text{Prob}\left\{d\left(x^N,x^{*}\right)\ge \epsilon \right\}\le c\left(\epsilon \right){\text{e}}^{-N\beta \left(\epsilon \right)}$ w.p.1 (7)

forN sufficiently large. $d\left(x,D\right):={\inf }_{x^{\prime }\in D}\Vert x-x^{\prime }\Vert$ denotes the distance from point x to set D.

Lemma 3.2 studies the optimal solution set of SAA problem (6) convergences to optimal solution of true problem (1) with probability one (w.p.1.). Let

$G\left(x\mathrm{,}\alpha \right)\mathrm{<mo>\; :\; </mo>}=x-P_C\left(x-\alpha F^N(\; x\; )\right)$

again, according to (4) and (3), solving SAA problem (6) is equivalent to find a zero of $G\left(x\mathrm{,}\alpha \right)$.

4. Projection and Contraction Method and Convergence Analysis

In this part, we propose the projection and contraction method based on the former research and certify the algorithm is convergent. At last, the algorithm is applied to numerical examples that we give. To facilitate our research, we denote the projection of x onto $K_p$ as $x_{+}$ and the projection of $-x$ onto $K_p^{\ast }$ as $x_{-}$. Hence, it is clear that $\langle x_{+},x_{-}\rangle =0$ for any $x\in R^n$.

Algorithm 3.1.

Step 0 Given $\epsilon >0$, let $0<u<w<1$, $\tau \in \left(0,2\right)$, $s\in \left(0,1\right)$, ${\alpha }_0=1$, and $x^0$ denotes an arbitrary initial iteration point, Set $k:=0$.

Step 1 Compute $G\left(x^k\mathrm{,}{\alpha }_k\right)$, if $\Vert G\left(x^k,{\alpha }_k\right)\Vert <\epsilon$, stop; Otherwise, go to step 2.

Step 2 Let $l_k$ be the smallest nonnegative integer, which satisfies ${\alpha }_k=\alpha s^{l_k}$, such that

$\frac{{\alpha }_k\Vert F^N\left(x^k\right)-F^N\left(x^k-G\left(x^k\mathrm{,}{\alpha }_k\right)\right)\Vert }{\Vert G\left(x^k\mathrm{,}{\alpha }_k\right)\Vert }\le w$ (8)

if

$\frac{{\alpha }_k\Vert F^N\left(x^k\right)-F^N\left(x^k-G\left(x^k\mathrm{,}{\alpha }_k\right)\right)\Vert }{\Vert G\left(x^k\mathrm{,}{\alpha }_k\right)\Vert }\le u$ (9)

then $\alpha =\frac{3}{2}{\alpha }_k$.

Step 3 Calculate

$\rho \left(x^k\mathrm{,}{\alpha }_k\right)=G{\left(x^k\mathrm{,}{\alpha }_k\right)}^{\text{T}}\frac{d\left(x^k\mathrm{,}{\alpha }_k\right)}{{\Vert d\left(x^k\mathrm{,}{\alpha }_k\right)\Vert }^2}$ (10)

with

$d\left(x^k\mathrm{,}{\alpha }_k\right)=G\left(x^k\mathrm{,}{\alpha }_k\right)-{\alpha }_k\left[F^N\left(x^k\right)-F^N\left(x^k-G\left(x^k\mathrm{,}{\alpha }_k\right)\right)\right]$ (11)

Step 4 Compute

$x^{k+1}={\left(x^k-\tau \rho \left(x^k\mathrm{,}{\alpha }_k\right)d\left(x^k\mathrm{,}{\alpha }_k\right)\right)}_{+}$ (12)

Set $k:=k+1$ ; go to step 1.

Next, the convergence of Algorithm 3.1 is researched.

Lemma 4.1 Suppose that $x^{\mathrm{<mo>\; *\; </mo>}}$ is a solution of the SAA problem (6), $\rho \left(x\mathrm{,}\alpha \right)$ and $d\left(x\mathrm{,}\alpha \right)$ are respectively defined by (10) and (11). Then, the inequality holds

$\langle x-x^{\mathrm{<mo>\; *\; </mo>}}\mathrm{,}d\left(x\mathrm{,}\alpha \right)\rangle \ge \langle G\left(x\mathrm{,}\alpha \right)\mathrm{,}d\left(x\mathrm{,}\alpha \right)\rangle$

Proof. From the definition of projection in formula (2), we know $G\left(x\mathrm{,}\alpha \right)\mathrm{<mo>\; :\; </mo>}=x-P_C\left(x-\alpha F^N\left(x\right)\right)$, obviously the lemma holds.

Lemma 4.2. Let $x\in R^n$ and $\tilde{\alpha }>\alpha >0$ , the following formula holds:

$\Vert G\left(x\mathrm{,}\tilde{\alpha }\right)\Vert \ge \Vert G\left(x\mathrm{,}\alpha \right)\Vert$

Proof. Prove the above inequality is equivalent to proof

$G{\left(x,\alpha \right)}^{\text{T}}\left(G\left(x,\tilde{\alpha }\right)-G\left(x,\alpha \right)\right)\ge 0,\forall \tilde{\alpha }>\alpha >0$ (13)

From Formula (2), we can get

$P_C\left(x-\alpha F^N\left(x\right)\right)-P_C\left(x-\tilde{\alpha }{F}^N\left(x\right)\right)=G\left(x,\tilde{\alpha }\right)-G\left(x,\alpha \right)$ (14)

then from Lemma 2.1 (1) and (13), we get

${\left\{\left(x-\alpha F^N\left(x\right)\right)-P_C\left(x-\alpha F^N\left(x\right)\right)\right\}}^{\text{T}}\left\{G\left(x\mathrm{,}\tilde{\alpha }\right)-G\left(x\mathrm{,}\alpha \right)\right\}\ge 0$ (15)

thus we have

$G{\left(x,\alpha \right)}^{\text{T}}\left\{G\left(x,\tilde{\alpha }\right)-G\left(x,\alpha \right)\right\}\ge \alpha F^N{\left(x\right)}^{\text{T}}\left\{G\left(x,\tilde{\alpha }\right)-G\left(x,\alpha \right)\right\}$ (16)

Let $\mu :=x-\tilde{\alpha }{F}^N\left(x\right)$ and $\eta :=x-\alpha F^N\left(x\right)$, the formula holds

$\left(\tilde{\alpha }-\alpha \right)F^N{\left(x\right)}^{\text{T}}\left\{G\left(x\mathrm{,}\tilde{\alpha }\right)-G\left(x\mathrm{,}\alpha \right)\right\}\ge {\Vert G\left(x\mathrm{,}\tilde{\alpha }\right)-G\left(x\mathrm{,}\alpha \right)\Vert }^2$ (17)

the above formula holds because of Lemma 2.1. So the inequality (16) and (17) hold, the proof is complete.

Theorem 4.1. Assume that $f\left(\cdot \mathrm{,}\xi \right)$ is monotonous and Lipschitz continuous w.r.t. x, and constant $0<L<1$. Let the solution set of SAA problem (6) be nonempty. Then the sequence $\left\{x_k\right\}$ obtained by Algorithm 3.1 converges to the solution of (6).

Proof. From (10) and (11), it gets that

$\begin{array}{l}\langle G\left(x_k,{\alpha }_k\right),d\left(x_k,{\alpha }_k\right)\rangle \\ =\langle G\left(x_k,{\alpha }_k\right),F^N\left(x_k,{\alpha }_k\right)-{\alpha }_k\left[F^N(x_k)-F^N\left(x_k-G\left(x_k,{\alpha }_k\right)\right)\right]\rangle \\ ={\Vert G\left(x_k,{\alpha }_k\right)\Vert }^2-\langle G\left(x_k,{\alpha }_k\right),{\alpha }_k\left[F^N\left(x_k\right)-F^N\left(x_k-G\left(x_k,{\alpha }_k\right)\right)\right]\rangle \\ \ge \left(1-L\right){\Vert G\left(x_k,{\alpha }_k\right)\Vert }^2\end{array}$ (18)

$\begin{array}{l}2\langle G\left(x_k,{\alpha }_k\right),d\left(x_k,{\alpha }_k\right)\rangle -{\Vert d\left(x_k,{\alpha }_k\right)\Vert }^2\\ =\langle 2G\left(x_k,{\alpha }_k\right)-d\left(x_k,{\alpha }_k\right),d\left(x_k,{\alpha }_k\right)\rangle \\ =\langle G\left(x_k,{\alpha }_k\right)+{\alpha }_k\left[F^N\left(x_k\right)-F^N\left(x_k-G\left(x_k,{\alpha }_k\right)\right)\right],d\left(x_k,{\alpha }_k\right)\rangle \\ =\langle G\left(x_k,{\alpha }_k\right)+{\alpha }_k\left[F^N\left(x_k\right)-F^N\left(x_k-G\left(x_k,{\alpha }_k\right)\right)\right],G\left(x_k,{\alpha }_k\right)\\ -{\alpha }_k\left[F^N\left(x_k\right)-F^N\left(x_k-G\left(x_k,{\alpha }_k\right)\right)\right]\rangle \end{array}$

$\begin{array}{l}={\Vert G\left(x_k,{\alpha }_k\right)\Vert }^2-{\alpha }_k^2{\Vert F^N\left(x_k\right)-F^N\left(x_k-G\left(x_k,{\alpha }_k\right)\right)\Vert }^2\\ \ge \left(1-L\right){\Vert G\left(x_k,{\alpha }_k\right)\Vert }^2\\ \ge 0\end{array}$ (19)

which is equivalent to

$G{\left(x_k,{\alpha }_k\right)}^{\text{T}}\frac{d\left(x_k,{\alpha }_k\right)}{{\Vert d\left(x_k,{\alpha }_k\right)\Vert }^2}\ge \frac{1}{2}$

that is

$\rho \left(x_k\mathrm{,}{\alpha }_k\right)\ge \frac{1}{2}$

the above inequality holds since the function $f\left(\cdot \mathrm{,}\xi \right)$ is Lipschitz continuous. Let $x^{\mathrm{<mo>\; *\; </mo>}}$ be a solution of SAA problem (6), then

$\begin{array}{c}{\Vert x_{k+1}-x^{*}\Vert }^2={\Vert {\left(x_k-\tau \rho \left(x_k,{\alpha }_k\right)d\left(x_k,{\alpha }_k\right)\right)}_{+}-x^{*}\Vert }^2\\ \le {\Vert x_k-x^{*}-\tau \rho \left(x_k,{\alpha }_k\right)d\left(x_k,{\alpha }_k\right)\Vert }^2\\ ={\Vert x_k-x^{*}\Vert }^2+{\tau }^2{\rho }^2\left(x_k,{\alpha }_k\right){\Vert d\left(x_k,{\alpha }_k\right)\Vert }^2\\ -2\tau \rho \left(x_k,{\alpha }_k\right)\langle x_k-x^{*},d\left(x_k,{\alpha }_k\right)\rangle \\ \le {\Vert x_k-x^{*}\Vert }^2-\tau \left(2-\tau \right)\rho \left(x_k,{\alpha }_k\right)\langle G\left(x_k,{\alpha }_k\right),d\left(x_k,{\alpha }_k\right)\rangle \\ \le {\Vert x_k-x^{*}\Vert }^2-\frac{\tau \left(2-\tau \right)\left(1-L\right)}{2}{\Vert G\left(x_k,{\alpha }_k\right)\Vert }^2\end{array}$

the first inequality holds since the projection operator is non-expansive, the second inequality holds since Lemma 4.1, and the last inequality holds from inequality (18) and (19). Obviously, the sequence $\left\{x_k\right\}$ is bounded.

Let ${\hat{x}}^{\mathrm{<mo>\; *\; </mo>}}$ be a cluster point of $\left\{x_k\right\}$ and $\left\{x_{k_j}\right\}$ is a subsequence of $\left\{x_k\right\}$, which converges to ${\hat{x}}^{\mathrm{<mo>\; *\; </mo>}}$. Denote $\inf \left\{{\alpha }_k\right\}={\alpha }_{\min }$, since $G\left(x_k\mathrm{,}{\alpha }_k\right)$ is continuous, then

$G\left({\hat{x}}^{*},{\alpha }_{\min }\right)=\underset{j\to \infty }{lim}G\left(x_{k_j},{\alpha }_{\min }\right)=0$

Hence, ${\hat{x}}^{\mathrm{<mo>\; *\; </mo>}}$ is a solution of (6).

Next, it proves that the sequence $\left\{x_k\right\}$ has only one cluster point. Suppose that there is $\hat{x}\in C$ such that $\left\{x_k\right\}$ converges to $\hat{x}$, and denote

$\delta :=\Vert \hat{x}-{\hat{x}}^{*}\Vert >0$

since ${\hat{x}}^{\mathrm{<mo>\; *\; </mo>}}$ is a cluster point of the sequence $\left\{x_k\right\}$, there is a $k_i>0$ such that

$\Vert x_{k_i}-{\hat{x}}^{\mathrm{<mo>\; *\; </mo>}}\Vert \le \frac{\sigma }{2}$

thus, it follows that

$\Vert x_k-{\hat{x}}^{\mathrm{<mo>\; *\; </mo>}}\Vert \le \Vert x_{k_i}-{\hat{x}}^{\mathrm{<mo>\; *\; </mo>}}\Vert \le \frac{\sigma }{2}\mathrm{,}\forall k\ge k_i$

and

$\Vert x_k-\hat{x}\Vert \ge \Vert \hat{x}-{\hat{x}}^{*}\Vert -\Vert x_k-{\hat{x}}^{*}\Vert >\sigma -\frac{\sigma }{2}>\frac{\sigma }{2}$

which contradicts the assumption. Thus it is certified completely, and the sequence $\left\{x_k\right\}$ converges to the solution of SAA problem (6).

5. Numerical Experiment

In this section, we certify the effectiveness of algorithm 3.1 by giving some numerical experiments. The tasks are completed by Matlab 2018b, which are installed on a computer that has 3.3 GHz CPU and 4.0 GB memory. We set parameters $u=0.75,\gamma =1.95$ respectively, and $\epsilon$ denotes error defined by $\Vert x\left(t\right)-x^{\mathrm{<mo>\; *\; </mo>}}\Vert$, further, ITER represents average number of iterations and ACPU is the average run time.

Example 5.1. Consider the POSVI below: find x, such that

$\langle \frac{1}{2}Dx\xi \mathrm{,}y-x\rangle \ge \mathrm{0,}\forall y\in C$

where $x\in R^n$, $C=\left\{x|x\in K_p\right\}$, D is a real symmetric matrix with n dimension, and the element of D is selected randomly by Matlab from the interval $\left[\mathrm{0,1}\right]$. The SAA problem: find $x\in C$, such that

$\langle \frac{1}{2}\frac{1}{N}{\displaystyle \underset{i=1}{\overset{N}{\sum }}}Dx{\xi }_i,y-x\rangle \ge 0,\forall y\in C$

We choose $p=2,3,5,10$ respectively, and the corresponding numerical results are exhibited in Tables 1-4.

Table 1. Solving numerical results when $p=2$.

Table 2. Solving numerical results when $p=3$.

Table 3. Solving numerical results when $p=5$.

The error $\epsilon$ corresponding to every p we choose changes with time as shown in Figures 1-4.

Table 4. Solving numerical results when $p=10$.

Figure 1. When $p=2$.

Figure 2. When $p=3$.

Figure 3. When $p=5$.

Figure 4. When $p=10$.

From Tables 1-4 and Figures 1-4, we can analyze that for different p, as the dimension n increases, ITER and ACPU both become larger and relatively stable, and the error $\epsilon$ becomes smaller and tends to zero. Therefore, generally speaking, the algorithm we proposed is effective.

Specially, p = 2 is a special case. When p = 2, P-order cone degenerates into second order cone. From the numerical results, when p = 2 and p = 3, the operation result is better when n is larger. 3 is the smallest number greater than 2. After many numerical experiments, it is found that with the increase of p, the time for large-scale problems will become longer and longer, until p = 10, the calculation results tend to be stable. That is, after p is greater than 10, the calculation result does not change much. So we chose a middle number, 5.

6. Conclusion

In this paper, a sample average approximation method is applied to approximate stochastic inequality problem with p-order cone. In order to solve p-order cone stochastic variational inequality problem, under moderate condition, we propose a projection and contraction method and prove the iteration sequence produced by the method converges to the solution of the SAA problem. At last, based on the projection and contraction method, we give some numerical examples and the experimental results verify the accuracy of the method. Next, we expect to investigate the numerical solution of circular cone constrained stochastic variational inequality problem. Find other suitable methods to further solve the p-order cone-constrained stochastic variational inequality problem in this paper, and carry out numerical simulation comparison.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Shapiro, A., Dentcheva, D. and Ruszczyński (2009) A Lectures on Stochastic Programming: Modeling and Theory. SIAM, Philadelphia. https://doi.org/10.1137/1.9780898718751
[2]	Gürkan, G., Özge, A.Y. and Robinson, S.M. (1996) Sample-Path Solution of Stochastic Variational Inequalities with Applications to Option Pricing. Proceedings Winter Simulation Conference, Coronado, 8-11 December 1996, 337-344. https://doi.org/10.1145/256562.256646
[3]	Agdeppa, R.P., Yamashita, N. and Fukushima, M. (2007) Convex Expected Residual Models for Stochastic Affine Variational Inequality Problems and Its Application to the Traffic Equilibrium Problem. Pacific Journal of Optimization, 49, 211.
[4]	Miao, X.H., Qi, Y.L. and Chen, J.S. (2017) On Merit Functions for p-Order Cone Complementarity Problem. Computational Optimization and Applications, 67, 155-173.
[5]	He, B.S. and Liao, L. (2002) Improvements of Some Projection Methods for Monotone Nonlinear Variational Inequalities. Journal of Optimization Theory and Applications, 112, C111-C128.
[6]	Facchinei, F. and Pang, J.S. (2003) Finite-Dimensional Variational Inequalities and Complementarity Problem. Springer-Verlag, New York. https://doi.org/10.1007/b97544
[7]	Korpelevich, G.M. (1976) The Extragradient Method for Finding Saddle Points and Other Problem. Ekonomika i Matematicheskie Metody, 12, C747-C756.
[8]	Antipin, A.S. (1976) On a Method for Convex Programs Using a Symmetrical Modifification of the Lagrange Function. Ekonomika i Matematicheskie Metody, 12, 1164-1173.
[9]	Tseng, P. (2000) A Modified Forward-Backward Splitting Method for Maximal Monotone Mapping. SIAM Journal on Control and Optimization, 38, 431-446. https://doi.org/10.1137/S0363012998338806
[10]	Yekini, S. and Olaniyi, S.I. (2017) Strong Convergence Result for Monotone Variational Inequalities. Numerical Algorithms, 76, 259-282. https://doi.org/10.1007/s11075-016-0253-1
[11]	Duong, V.T. and Dang, V.H. (2018) Weak and Strong Convergence Theorems for Variational Inequality Problems. Numerical Algorithms, 78, 1045-1060. https://doi.org/10.1007/s11075-017-0412-z
[12]	Yang, J., Liu, H.W. and Liu, Z.X. (2018) Modified Subgradient Extragradient Algorithms for Solving Monotone Variational Inequalities. Optimization, 67, 2247-2258. https://doi.org/10.1080/02331934.2018.1523404
[13]	Yang, J. and Liu, H.W. (2019) Strong Convergence Result for Solving Monotone Variational Inequalities in Hilbert Space. Numerical Algorithms, 80, 741-752. https://link.springer.com/article/10.1007/s11075-018-0504-4 https://doi.org/10.1007/s11075-018-0504-4
[14]	Yang, J. and Liu, H.W. (2018) A Modified Projected Gradient Method for Monotone Variational Inequalities. Journal of Optimization Theory and Applications, 179, 197-211. https://doi.org/10.1007/s10957-018-1351-0
[15]	Fang, Y.P. and Huang, N.J. (2003) H-Monotone Operator and Resolvent Operator Technique for Variational Inclusions. Applied Mathematics and Computation, 145, 795-803. https://doi.org/10.1016/S0096-3003(03)00275-3
[16]	Miao, X.H., Qi, N. and Chen, J.S. (2017) Projection Formula and One Type of Spectral Factorization Associated with p-Order Cone. Journal of Nonlinear and Convex Analysis, 18, C1699-C1705.
[17]	Robbins, H. and Monro, S. (1951) On a Stochastic Approximation Method. Annals of Mathematical Statistic, 22, 400-407. https://doi.org/10.1214/aoms/1177729586
[18]	Jiang, H.Y. and Xu, H.F. (2008) Stochastic Approximation Approaches to the Stochastic Variational Inequality Problems. Transactions on Automatic Control, 53, 1462-1475. https://doi.org/10.1109/TAC.2008.925853
[19]	Huseyin, T. (2008) A Stochastic Approximation Method to Compute Bid Price in Network Revenue Management Problems. Journal on Computing, 20, 596-610. https://doi.org/10.1287/ijoc.1080.0269
[20]	Xu, H.F. (2010) Sample Average Approximation Methods for a Class of Stochastic Variational Inequality Problems. Asia-Pacific Journal of Operational Research, 27, 103-119. https://doi.org/10.1142/S0217595910002569
[21]	Xu, H.F. (2010) Uniform Exponential Convergence of Sample Average Random Functions under General Sampling with Applications in Stochastic Programming. Journal of Mathematical Analysis and Applications, 368, 692-710. https://doi.org/10.1016/j.jmaa.2010.03.021