Stochastic absolute value equations

Abstract

We propose a new kind of stochastic absolute value equations involving absolute values of variables. By utilizing an equivalence relation to stochastic bilinear program, we investigate the expected value formulation for the proposed stochastic absolute value equations. We also consider the expected residual minimization formulation for the proposed stochastic absolute value equations. Under mild assumptions, we give the existence conditions for the solution of the stochastic absolute value equations. The solution of the stochastic absolute value equations can be gotten by solving the discrete minimization problem. And we also propose a smoothing gradient method to solve the discrete minimization problem. Finally, the numerical results and some discussions are given.

1 Introduction

Let $(\Omega , {{{{\mathcal {F}}}}}, \rho )$ be a probability space, where $\Omega \subseteq R^n$ and $\rho$ is a standard probability measure, we propose a new kind of stochastic absolute value equations, which is to find a vector $x\in R^n$ such that

$$\begin{aligned} A(\omega )x-|x|=b(\omega ),\end{aligned}$$

(1.1)

where $A(\omega )\in R^{n\times n}$ and $b(\omega )\in R^n$ for $\omega \in \Omega$ are random quantities on a probability space $(\Omega , {{{{\mathcal {F}}}}}, \rho )$, |x| is the componentwise absolute value of vector $x\in R^n$. We call (1.1) the stochastic absolute value equations (SAVE). When $A(\omega )$ is a deterministic matrix and $b(\omega )$ is a deterministic vector, then SAVE (1.1) reduces to the absolute value equation (AVE) which is equivalent to the general linear complementarity problem [1,2,3,4]. The AVE was widely used in solving linear programs, bimatrix games and fundamental problems of mathematical programming, one can see [2,3,4,5]. In the past few decades, the stochastic variational inequality problems [6, 7], the stochastic linear complementarity problems [8,9,10,11,12], the stochastic nonlinear complementarity problems [13, 14] and the stochastic tensor complementarity problems [15,16,17] were also widely studied in solving many optimization problems with uncertainty. However, no attention has been paid to SAVE (1.1) which contains the characteristics of AVE and stochastic optimization problems.

As the AVE is an NP hard problem [2], it is also a hard work to solve SAVE (1.1). Generally, for the stochastic optimization problems, there are two general approaches to get the solution of the problems [8,9,10]. The first approach applies the expected value (EV) method which formulates the problem as a deterministic problem by taking the expect of the stochastic quantity, and the second approach is the expected residual minimization (ERM) method, which is a natural extension of the least-squares method of minimizing the residual. In this paper, the equivalent relation between SAVE (1.1) and stochastic bilinear program is given. By using the EV formulation, we propose an expected value formulation for SAVE (1.1). We also study the ERM formulation for SAVE (1.1). We generate samples by the quasi-Monte Carlo methods and prove that every accumulation point of the discrete approximation problem is the solution of the expected residual minimization problem for SAVE (1.1).

The remainder of this paper is organized as follows. In Sect. 2, we show that SAVE (1.1) is equivalent to a stochastic bilinear program, which is a stochastic optimization problem with the formula as a stochastic generalized linear complementarity problem. Combined with an example, we give a discussion about the EV formulation. In Sect. 3, we first establish the boundedness of the solution set of the expected residual minimization problem, and then show that each accumulation point of the sequence generated by the ERM formulation is a solution of the expected residual minimization problem. In Sect. 4, we propose a smoothing gradient method for solving SAVE (1.1). Some numerical experiments are also given to verify the theoretical results of the ERM formulation. Finally, we complete our paper with some conclusions in Sect. 5.

2 Expected value formulation

We start by showing that SAVE (1.1) is equivalent to a stochastic bilinear program. By the equivalence of the stochastic bilinear program and the stochastic generalized linear complementarity problem, SAVE (1.1) can be reformulated as a stochastic generalized linear complementarity problem. Then the expected value formulation will be used to solve SAVE (1.1).

Theorem 2.1

SAVE (1.1) is equivalent to the stochastic bilinear program, i.e.,

$$\begin{aligned} 0= & {} \min _{x\in R^{n}}\{((A(\omega )+I)x-b(\omega ))^{T}((A(\omega )-I)x-b(\omega ))~|~(A(\omega )+I)x \\&-\, b(\omega )\ge 0,~(A(\omega )-I)x-b(\omega )\ge 0\}. \end{aligned}$$

Proof

By SAVE (1.1), from $|x|\le A(\omega )x-b(\omega )$, we have

$$\begin{aligned} (A(\omega )+I)x-b(\omega )\ge 0,~(A(\omega )-I)x-b(\omega )\ge 0, \end{aligned}$$

i.e., the above formulations are the equivalence of the constraints for the stochastic bilinear program. So we have

$$\begin{aligned}&|x|=A(\omega )x-b(\omega )\Updownarrow ((A(\omega )+I)x-b(\omega ))^{T}((A(\omega )-I)x-b(\omega ))=0,\\&\quad (A(\omega )+I)x-b(\omega )\ge 0,~(A(\omega )-I)x-b(\omega )\ge 0 \end{aligned}$$

We complete the proof. $\square$

Theorem 2.2

SAVE (1.1) is equivalent to the stochastic generalized linear complementarity problem, i.e.,

$$\begin{aligned} \begin{aligned} (A(\omega )+I)x-b(\omega )\ge 0,~(A(\omega )-I)x-b(\omega )\ge 0,\\ ((A(\omega )+I)x-b(\omega ))^{T}((A(\omega )-I)x-b(\omega ))=0. \end{aligned} \end{aligned}$$

(2.1)

Proof

By the equivalence of the stochastic bilinear program and the stochastic generalized linear complementarity problem, we get this theorem. $\square$

In the following of this paper, $E[\cdot ]$ stands for the expectation of every elements of matrix and vector. ${\bar{A}}$ denotes the expectation of $A(\omega )$ and ${\bar{b}}$ denotes the expectation of $b(\omega )$, i.e.,

$$\begin{aligned} {\bar{A}}=E[A(\omega )],~{\bar{b}}=E[b(\omega )]. \end{aligned}$$

Then, we get the expected value formulation of the stochastic generalized linear complementarity problem as

$$\begin{aligned} \begin{aligned} (({\bar{A}}+I)x-{\bar{b}})^{T}(({\bar{A}}-I)x-{\bar{b}})=0,\\ ({\bar{A}}+I)x-{\bar{b}}\ge 0,~({\bar{A}}-I)x-{\bar{b}}\ge 0. \end{aligned} \end{aligned}$$

(2.2)

In general, the solution set of (2.1) is not equivalent to the solution set of (2.2) for all $\omega \in \Omega$. So, in this section, we consider a kind of discrete probability space, which has only finitely many elements, i.e., $\Omega =\{\omega _{1},\omega _{2},\cdots ,\omega _{m}\}$. Now, (2.1) is equivalent to

$$\begin{aligned} \left\{ \begin{aligned} G(x)\ge 0,~H(x)\ge 0,~G(x)^{T}H(x)=0,\\ (A(\omega _{i})+I)x-b(\omega _{i})\ge 0,\\ (A(\omega _{i})-I)x-b(\omega _{i})\ge 0, \end{aligned} \right. \end{aligned}$$

(2.3)

where $G(x)=({\bar{A}}+I)x-{\bar{b}}$, $H(x)=({\bar{A}}-I)x-{\bar{b}}$, $i=1,2,\cdots ,m$.

In the following of this section, we reformulate (2.3) as a nonlinear equations with nonnegative constraints, i.e., the expected value formulation of SAVE (1.1). (2.2) is a generalized linear complementarity problem, and it can be reformulated as a semismooth equations by Fischer-Burmeister (FB) function. FB function is an NCP function [1], which is defined as

$$\begin{aligned} \phi _{FB}(a,b)=\sqrt{a^{2}+b^{2}}-a-b, \end{aligned}$$

where $a,b\in R$. Then x is a solution of (2.3) if and only if

$$\begin{aligned} {\tilde{H}}(x,y)=0,~y\ge 0, \end{aligned}$$

(2.4)

where

$$\begin{aligned} {\tilde{H}}(x,y)=\begin{pmatrix} \Phi (x) \\ (A(\omega _{1})+I)x-b(\omega _{1})-y_{1}\\ (A(\omega _{1})-I)x-b(\omega _{1})-y_{2}\\ \vdots \\ (A(\omega _{m})+I)x-b(\omega _{m})-y_{2m-1}\\ (A(\omega _{m})-I)x-b(\omega _{m})-y_{2m}\\ \end{pmatrix} \end{aligned}$$

and

$$\begin{aligned} \Phi (x)=\begin{pmatrix} \phi _{FB}(({\bar{A}}+I)x-{\bar{b}})_{1},(({\bar{A}}-I)x-{\bar{b}})_{1} \\ \vdots \\ \phi _{FB}(({\bar{A}}+I)x-{\bar{b}})_{n},(({\bar{A}}-I)x-{\bar{b}})_{n} \end{pmatrix}, \end{aligned}$$

with

$$\begin{aligned} y=(y_{1}^{T},y_{2}^{T},\cdots ,y_{2m}^{T})^{T},~y_{i}\in R^{n}, ~i=1,2,\cdots ,2m. \end{aligned}$$

Now, we give a simple example to illustrate the transformation process.

Example 2.1

Consider SAVE (1.1), where

$$\begin{aligned} A(\omega )=\begin{pmatrix}10+\omega &{}1&{}2&{}0\\ 1&{}11+\omega &{}3&{}1\\ 0&{}2&{}12+\omega &{}1\\ 1&{}7&{}0&{}13+\omega \end{pmatrix}, b(\omega )=\begin{pmatrix}12+\omega \\ 15+\omega \\ 14+\omega \\ 20+\omega \end{pmatrix}, \end{aligned}$$

$\Omega =\{\omega _1,\omega _2\}=\{0,2\},P_i={\mathcal {P}}(\omega _i\in \Omega )=\frac{1}{2}, i=1,2.$

We know that $(1, 1, 1, 1)^T$ is the solution of this example. Now, we use the EV formulation to solve the above example. Firstly, we get

$$\begin{aligned} {\overline{A}}=\begin{pmatrix}11&{}1&{}2&{}0\\ 1&{}12&{}3&{}1\\ 0&{}2&{}13&{}1\\ 1&{}7&{}0&{}14\end{pmatrix}, {\overline{b}}=\begin{pmatrix}13\\ 16\\ 15\\ 21\end{pmatrix}. \end{aligned}$$

Then by (2.4), we know that Example 2.1 can be transformed into the following constrained equations

$$\begin{aligned} {\widetilde{H}}(x,y)=\begin{pmatrix}\phi _{FB}(12x_1+x_2+2x_3-13,10x_1+x_2+2x_3-13)\\ \phi _{FB}(x_1+13x_2+3x_3+x_4-16,x_1+11x_2+3x_3+x_4-16)\\ \phi _{FB}(2x_2+14x_3+x_4-15,2x_2+12x_3+x_4-15)\\ \phi _{FB}(x_1+7x_2+15x_4-21,x_1+7x_2+13x_4-21)\\ 11x_1+x_2+2x_3-12-y_1\\ x_1+12x_2+3x_3+x_4-15-y_2\\ 2x_2+13x_3+x_4-14-y_3\\ x_1+7x_2+14x_4-20-y_4\\ 9x_1+x_2+2x_3-12-y_5\\ x_1+10x_2+3x_3+x_4-15-y_6\\ 2x_2+11x_3+x_4-14-y_7\\ x_1+7x_2+12x_4-20-y_8\\ 13x_1+x_2+2x_3-14-y_9\\ x_1+13x_2+3x_3+x_4-17-y_{10}\\ 2x_2+15x_3+x_4-16-y_{11}\\ x_1+7x_2+16x_4-22-y_{12}\\ 11x_1+x_2+2x_3-14-y_{13}\\ x_1+12x_2+3x_3+x_4-17-y_{14}\\ 2x_2+13x_3+x_4-16-y_{15}\\ x_1+7x_2+14x_4-22-y_{16}\end{pmatrix}, \end{aligned}$$

where $y_i\ge 0,i=1,2,\cdots ,16$. The optimization solution of the above constrained equations is equivalence to the optimization solution of the following constrained optimization problem

$$\begin{aligned} \min&\frac{1}{2}\Vert {\widetilde{H}}(x,y)\Vert ^2\\ s.t.&y\ge 0. \end{aligned}$$

We use fmincon function in Matlab Optimization Toolbox to solve the transformed constrained optimization problem. The numerical results are given in the following table, where $x^0$ denotes the initial point, $x^*$ denotes the optimum solution.

Table 1 Numerical results for Example 2.1

Remark

From the numerical results of the above example, we know that the SAVE (1.1) with finite discrete distribution can be solved by constrained optimization methods. But the EV transformation is a more complicated form with nonsmooth complementarity function and only solve SAVE (1.1) with finite discrete distribution. So, in the following section, we consider the expected residual minimization formulation, which can avoid transforming the SAVE into a complicated constrained optimization problem. And the expected residual minimization formulation can also be used to solve SAVE (1.1) with any distribution involving the finite discrete distribution.

3 Expected residual minimization formulation

To apply the expected residual minimization formulation to solve SAVE (1.1), we first formulate the problem as the following optimization problem

$$\begin{aligned} \min _{x\in R^n} F(x),\end{aligned}$$

(3.1)

where $F(x)=E[\Vert A(\omega )x-|x|-b(\omega )\Vert ^2]=\int _{\Omega }\Vert A(\omega )x-|x|-b(\omega )\Vert ^2\rho (\omega )\,{\mathrm d}\omega$. Discrete the involved problem by the quasi-Monte Carlo method, then the solution of the original problem can be approximated obtained by solving the discrete minimization problem.

To proceed, we give the following assumption.

Assumption 3.1

Let $\rho :\Omega \rightarrow R_{+}$ be a continuous probability density function on probability space $(\Omega , {{{{\mathcal {F}}}}}, P)$. Suppose that

$$\begin{aligned} \int _{\Omega }(\Vert A(\omega )\Vert +1)^2\rho (\omega )\,{\mathrm d}\omega<\infty , ~~\int _{\Omega }\Vert b(\omega )\Vert ^2\rho (\omega )\,{\mathrm d}\omega <\infty , \end{aligned}$$

where $A(\omega )\in R^{n\times n}$, $b(\omega )\in R^n$, $\omega \in \Omega$.

For $\gamma >0$, we denote the level set of function F by $\Xi (\gamma )$, i.e.,

$$\begin{aligned} \Xi (\gamma )=\{x~|~F(x)\le \gamma \}. \end{aligned}$$

Lemma 3.1

Suppose that there exists an ${\bar{\omega }}\in \Omega$, such that $\rho ({\bar{\omega }})>0$ and $A(\omega )\ne diag(sign(x))$. Then the level set $\Xi (\gamma )$ is bounded.

Proof

By $\rho$ is continuous, there exists $\rho _0>0$ such that

$$\begin{aligned} \rho (\omega )\ge \rho _0,~~\texttt {for all}~ \omega \in B=D({\bar{\omega }},\delta )\cap \Omega , \end{aligned}$$

where $D({\bar{\omega }},\delta )$ is a closed sphere with center ${\bar{\omega }}$ and radius $\delta$. We now consider a sequence $\{x_k\}\in R^n$. By the continuity of $\phi$, then there exists $\omega _k\in B$, such that

$$\begin{aligned} \Vert \phi (x_k,\omega _k)\Vert =\min _{\omega \in B}\Vert \phi (x_k,\omega )\Vert , \end{aligned}$$

where $\phi (x_k,\omega )=A(\omega )x_k-|x_k|-b(\omega )$.

Denote $\lambda =\int _{B}d\omega >0$. Then

$$\begin{aligned} \begin{array}{rl}F(x_k)\ge &{}\int _{B}\Vert \phi (x_k,\omega )\Vert ^2\rho (\omega )\,{\mathrm d}\omega \\ \ge &{}\Vert \phi (x_k,\omega _k)\Vert ^2{\bar{\rho }}\int _{B}\,{\mathrm d}\omega \\ =&{}\lambda {\bar{\rho }}\Vert \phi (x_k,\omega _k)\Vert ^2.\end{array} \end{aligned}$$

Now, we only need to prove $\Vert \phi (x_k,\omega _k)\Vert \rightarrow +\infty$ as $\Vert x_k\Vert \rightarrow +\infty$. Suppose $\Vert x_k\Vert \rightarrow +\infty$ holds, we know that $x_k^i\rightarrow +\infty$ or $x_k^i\rightarrow -\infty$ for some i. So, we get

$$\begin{aligned}&((A(\omega _k)-diag(sign(x_k)))x_k-b(\omega _k))_i \rightarrow +\infty ~~ \texttt {or}~~ ((A(\omega _k)\\&\quad -diag(sign(x_k)))x_k-b(\omega _k))_i \rightarrow -\infty \end{aligned}$$

for some i, i.e., we get $\Vert \phi (x_k,\omega _k)\Vert \rightarrow +\infty$ holds for $\Vert x_k\Vert \rightarrow +\infty$. Hence, the proof is completed. $\square$

In the following of this section, the quasi-Monte Carlo method for numerical integration is used as in [8, 18]. The transformation function $\omega =u(\nu )$ is used to go from an integral on $\Omega$ to the integral on the unit hypercube $[0,1]^m$. And the observations $\{\nu _i\}, i=1,\cdots ,{\bar{N}}$ are generated in this unit hypercube.

Then, we get

$$\begin{aligned} \begin{array}{rl}F(x)=&{}\int _{\Omega }\Vert \phi (x,\omega )\Vert ^2\rho (\omega )\,{\mathrm d}\omega \\ =&{}\int _{{\bar{\Omega }}}\Vert \phi (x,u(\nu ))\Vert ^2\rho (u(\nu ))u'(\nu )\,{\mathrm d}\nu \\ =&{}\int _{{\bar{\Omega }}}\Vert \phi (x,u(\nu ))\Vert ^2{\bar{\rho }}(\nu )\,{\mathrm d}\nu ,\end{array} \end{aligned}$$

where ${\bar{\rho }}(\nu )=\rho (u(\nu ))u'(\nu ),~{\bar{\Omega }}=[0,1]^m$.

For each k, we denote

$$\begin{aligned} F_k(x)=\frac{1}{\bar{N_k}}\sum _{\nu _i\in {\bar{\Omega }}_k}\Vert \phi (x,\nu _i)\Vert ^2\rho (\nu _i), \end{aligned}$$

where $\phi (x,\nu _i)=A(\nu _i)x-|x|-b(\nu _i)$, ${\bar{\Omega }}_k:=\{\nu _i,i=1,\cdots ,\bar{N_k}\}$ is a set of observations generated by a quasi-Monte Carlo method such that ${\bar{\Omega }}_k\subseteq \Omega ,~\bar{N_k}\rightarrow \infty$ as $k\rightarrow \infty$. In the remainder of this section, to simplify the natation, we suppose $\Omega =[0,1]^m$ and let $\omega$ denote $\nu$.

Now, we consider

$$\begin{aligned} \min _{x\in R^n}F_k(x).\end{aligned}$$

(3.2)

Obviously, (3.2) is the approximation problem to (3.1).

Lemma 3.2

 For any fixed $x\in R^n$, we get

$$\begin{aligned} \lim _{k\rightarrow \infty }F_k(x)=F(x). \end{aligned}$$

Proof

From the definition of $\phi$, we get

$$\begin{aligned} \begin{array}{rl}\Vert \phi (x,\omega )\Vert =&{}\Vert A(\omega )x-|x|-b(\omega )\Vert \\ \le &{}\Vert A(\omega )x\Vert +\Vert x\Vert +\Vert b(\omega )\Vert \\ \le &{}(\Vert A(\omega )\Vert +1)\Vert x\Vert +\Vert b(\omega )\Vert ,\end{array} \end{aligned}$$

i.e.,

$$\begin{aligned} 0\le \Vert \phi (x,\omega )\Vert ^2\le 2[((\Vert A(\omega )\Vert +1)\Vert x\Vert )^2+\Vert b(\omega )\Vert ^2]. \end{aligned}$$

By Assumption 3.1, we know that $(\Vert A(\omega )\Vert +1)^2\rho (\omega )$ is a nonnegative continuous function and it is also bounded. Therefore, we get $\Vert \phi (x,\cdot )\Vert ^2\rho (\cdot )$ is integrable and $0\le F(x)<\infty$. By $\Vert \phi (x,\cdot )\Vert ^2\rho (\cdot )$ is continuous, we have

$$\begin{aligned} \lim _{k\rightarrow \infty }F_k(x)=F(x), \end{aligned}$$

for $x\in R^n.$ This completes the proof. $\square$

Denote $\vartheta$ as the optimal solution set of (3.1), and $\vartheta _k$ as the optimal solution set of (3.2). Now, we give the following theorem to show the relation of the expected residual minimization problem (3.1) and the approximate expected residual minimization problem (3.2).

Theorem 3.1

If $\rho ({\bar{\omega }})>0$ holds for ${\bar{\omega }}\in \Omega$, then $\vartheta _k$ is nonempty and bounded when k is large enough. And every accumulation point of $\{x_k\}\subseteq \vartheta _k$ is contained in the set $\vartheta$.

Proof

We assume that $x_k\rightarrow {\bar{x}}, k\rightarrow \infty$. Let $F({\overline{x}})<\gamma$, by the continuity of F, we know that $F(x_k)\le \gamma$ for all large k, i.e., $x_k\in {\bar{D}}(\gamma )$ for all large k. Now, we show that

$$\begin{aligned} |F_k(x_k)-F_k({\overline{x}})|\rightarrow 0,~\mathrm{when ~~}k\rightarrow \infty . \end{aligned}$$

For all $x,y\in R^n$, we get

$$\begin{aligned} \begin{array}{rl}\Vert \phi (x,\omega )-\phi (y,\omega )\Vert =&{}\Vert A(\omega )x-|x|-b(\omega )-A(\omega )y+|y|+b(\omega )\Vert \\ =&{}\Vert A(\omega )x-A(\omega )y+|y|-|x|\Vert \\ \le &{}\Vert A(\omega )\Vert \Vert x-y\Vert +\Vert x-y\Vert \\ =&{}(\Vert A(\omega )\Vert +1)\Vert x-y\Vert .\end{array} \end{aligned}$$

Denote $L(\omega )=\Vert A(\omega )\Vert +1$, we also get

$$\begin{aligned} \begin{array}{rl}\Vert \phi (x,\omega )\Vert \le &{}(\Vert A(\omega )\Vert +1)\Vert x\Vert +\Vert b(\omega )\Vert \\ =&{}(\Vert A(\omega )\Vert +1)\Vert x\Vert +\Vert b(\omega )\Vert .\end{array} \end{aligned}$$

By Lemma 3.1, ${\bar{D}}(\gamma )$ is closed and bounded, we have

$$\begin{aligned} \begin{array}{rl}|\Vert \phi (x,\omega )\Vert ^2-\Vert \phi (y,\omega )\Vert ^2|=&{}|(\Vert \phi (x,\omega )\Vert +\Vert \phi (y,\omega )\Vert )(\Vert \phi (x,\omega )\Vert -\Vert \phi (y,\omega )\Vert )|\\ \le &{}((\Vert A(\omega )\Vert +1)\Vert x\Vert +(\Vert A(\omega )\Vert +1)\Vert y\Vert +2\Vert b(\omega )\Vert )\\ &{}(\Vert A(\omega )\Vert +1)\Vert x-y\Vert \\ =&{}(L(\omega )\Vert x\Vert +L(\omega )\Vert y\Vert +2\Vert b(\omega )\Vert )L(\omega )\Vert x-y\Vert \\ \le &{}(2L(\omega )C_1+2\Vert b(\omega )\Vert )L(\omega )\Vert x-y\Vert ,\end{array} \end{aligned}$$

where $C_1=\max \{\Vert x\Vert |x\in {\bar{D}}(\gamma )\},$ $x,y\in {\bar{D}}(\gamma )$. By

$$\begin{aligned} \begin{array}{rl}(2L(\omega )C_1+2\Vert b(\omega )\Vert )L(\omega )\le &{}(L(\omega )C_1+\Vert b(\omega )\Vert )^2+[L(\omega )]^2\\ =&{}[L(\omega )C_1]^2+\Vert b(\omega )\Vert ^2+[L(\omega )]^2+2C_1L(\omega )\Vert b(\omega )\Vert \\ \le &{}[L(\omega )C_1]^2+\Vert b(\omega )\Vert ^2+[L(\omega )]^2+[C_1L(\omega )]^2+\Vert b(\omega )\Vert ^2\\ =&{}(2C_1^2+1)[L(\omega )]^2+2\Vert b(\omega )\Vert ^2,\end{array} \end{aligned}$$

we obtain

$$\begin{aligned} \begin{array}{rl}|F_k(x_k)-F_k({\overline{x}})|\le &{}\frac{1}{\bar{N_k}}\sum \limits _{i=1}^{\bar{N_k}}|\Vert \phi (x_k,\omega _i)\Vert ^2-\Vert \phi ({\overline{x}},\omega _i)\Vert ^2|\rho (\omega _i)\\ \le &{}\frac{1}{\bar{N_k}}\sum \limits _{i=1}^{\bar{N_k}}((2C_1^2+1)[L(\omega _i)]^2+2\Vert b(\omega _i)\Vert ^2)\rho (\omega _i)\Vert x_k-{\overline{x}}\Vert \\ \le &{} \digamma \Vert x_k-{\overline{x}}\Vert ,\end{array} \end{aligned}$$

where $\digamma$ is a constant and for all large k satisfying

$$\begin{aligned} \digamma \ge \frac{1}{\bar{N_k}}\sum \limits _{i=1}^{\bar{N_k}}(((2C_1^2+1)[L(\omega _i)]^2+2\Vert b(\omega _i)\Vert ^2)\rho (\omega _i)). \end{aligned}$$

So, for $k\rightarrow \infty$, we get

$$\begin{aligned} |F_k(x_k)-F_k({\overline{x}})|\rightarrow 0. \end{aligned}$$

From the above results and Lemma 3.2, we obtain

$$\begin{aligned} |F_k(x_k)-F({\overline{x}})|\le |F_k(x_k)-F_k({\overline{x}})|+|F_k({\overline{x}})-F({\overline{x}})|\rightarrow 0, \end{aligned}$$

when $k\rightarrow \infty$. By $x_k\in \vartheta _k$, we get

$$\begin{aligned} F_k(x_k)\le F_k(x),~for~x\in R^n. \end{aligned}$$

Therefore, we have

$$\begin{aligned} F({\overline{x}})=\lim _{k\rightarrow \infty }F_k(x_k)\le \lim _{k\rightarrow \infty }F_k(x)=F(x),~x\in R^n. \end{aligned}$$

We complete the proof. $\square$

Now, we give two special kinds of SAVE (1.1), which can be solved without using discrete approximation.

Case I. Let $\Omega =[{\tilde{\alpha }}_1,{\tilde{\beta }}_1]\times \cdots \times [{\tilde{\alpha }}_N,{\tilde{\beta }}_N]$ with ${\tilde{\alpha }}_j<{\tilde{\beta }}_j,~j=1,\cdots ,N$, and ${\tilde{\omega }}_j,j=1,\cdots ,N$ are independent. When $\rho$ satisfies Assumption 3.1 and $\rho _j$ denotes the density function for ${\tilde{\omega }}_j$, $j=1,\cdots ,N$. We know that

$$\begin{aligned} F(x)=\sum \limits _{i=1}^nF_i(x), \end{aligned}$$

where

$$\begin{aligned} \begin{array}{l} F_i(x)=\int _{{\tilde{\alpha }}_1}^{{\tilde{\beta }}_1}\cdots \int _{{\tilde{\alpha }}_N}^{{\tilde{\beta }}_N}[(A({\tilde{\omega }})x-|x|-b({\tilde{\omega }}))_i]^2\rho _1({\tilde{\omega }}_1)\cdots \rho _N({\tilde{\omega }}_N)\,{\mathrm d}{\tilde{\omega }}_1\cdots \,{\mathrm d}{\tilde{\omega }}_N.\end{array} \end{aligned}$$

Case II. Let $A(\omega )\equiv A$ and $b(\omega )\equiv {\tilde{b}}+T\omega$, where $A\in R^{n\times n}$, ${\tilde{b}}\in R^n$ and $T\in R^{n\times m}$ are given constants. For each i, the $i\hbox {th}$ row of the matrix T has just one positive element $t_i$, and the density function $\rho$ is defined by

$$\begin{aligned} \rho (\omega )=\left\{ \begin{array}{rcl} 1,~~\omega \in [0,1]^m\\ 0,~~otherwise.\\ \end{array}\right. \end{aligned}$$

In this case, we get $F(x)=\sum \limits _{i=1}^nF_i(x)$, where

$$\begin{aligned} \begin{array}{rl}F_i(x)=&{}\int _0^1\cdots \int _0^1[(Ax-|x|-b(\omega ))_i]^2\rho _1(\omega _1)\rho _2(\omega _2)\cdots \rho _m(\omega _m)\,{\mathrm d}\omega _1\,{\mathrm d}\omega _2\cdots \,{\mathrm d}\omega _m\\ =&{}\int _0^1\cdots \int _0^1\int _0^1[(Ax-|x|-{\tilde{b}}-t_i\omega _j)_i]^2\rho _j(\omega _j)\,{\mathrm d}\omega _j\rho _1(\omega _1)\cdots \rho _{j-1}(\omega _{j-1})\\ &{}\rho _{j+1}(\omega _{j+1})\cdots \rho _m(\omega _m)\,{\mathrm d}\omega _1\cdots \,{\mathrm d}\omega _{j-1}\,{\mathrm d}\omega _{j+1}\cdots \,{\mathrm d}\omega _m\\ =&{}[Ax-|x|-{\tilde{b}}]_i^2+\frac{1}{3}t_i^2-[Ax-|x|-{\tilde{b}}]_it_i.\end{array} \end{aligned}$$

4 A smoothing gradient method

In this section, we use the ERM formulation to transform SAVE (1.1) into an unconstrained optimization problem. For SAVE (1.1) contains nonsmooth term |x|, we consider smoothing method to solve it. Smoothing gradient method is an effective smoothing method to deal with this kind of problems [19,20,21], so we use the smoothing gradient method to solve SAVE (1.1).

Firstly, we generate samples $\omega ^i, i=1,2,\cdots ,N$, i.e.,

$$\begin{aligned} f(x)=\frac{1}{N}\sum _{i=1}^N\Vert A(\omega _i)x-|x|-b(\omega _i)\Vert ^2\rho (\omega _i), \end{aligned}$$

and we choose the smoothing function of $|x_i|$ as

$$\begin{aligned} \psi (x_i,\mu )=\sqrt{x_i^2+\mu }, i=1,2,\cdots ,n, \end{aligned}$$

where $\mu \ge 0$. Denote $\psi (x,\mu )=(\sqrt{x_1^2+\mu }, \sqrt{x_2^2+\mu }, \cdots , \sqrt{x_n^2+\mu })^{T}$. Then SAVE (1.1) can be transformed into the following unconstrained optimization problem

$$\begin{aligned} \underset{x\in R^n}{\min }\;{\widetilde{f}}(x,\mu )=\frac{1}{N}\sum _{i=1}^N\Vert A(\omega _i)x-\psi (x,\mu )-b(\omega _i)\Vert ^2\rho (\omega _i). \end{aligned}$$

(4.1)

And the gradient of the objective function in (4.1) is

$$\begin{aligned} \nabla _{x}{{\widetilde{f}}(x,\mu )}=\frac{2}{N}\sum _{i=1}^NJ(A(\omega _i)x-\psi (x,\mu )-b(\omega _i))^{T}(A(\omega _i)x-\psi (x,\mu )-b(\omega _i))\rho (\omega _i), \end{aligned}$$

where $J(A(\omega _i)x-\psi (x,\mu )-b(\omega _i))$ is the Jacobian of $(A(\omega _i)x-\psi (x,\mu )-b(\omega _i))$.

Next, we give the smoothing gradient method for SAVE (1.1).

It is easy to find that ${\widetilde{f}}(\cdot ,\mu )\ge 0$ for any constant $\mu \ge 0$ and $\forall x\in R^n$, $\nabla _{x}{{\widetilde{f}}(\cdot ,\mu )}$ is uniformly continuous on the level set $L(x_0,\mu )=\{x\in R^n|{\widetilde{f}}(x,\mu )\le {\widetilde{f}}(x_0,\mu )\}$. Next, we give the global convergence of the proposed smoothing gradient method. From [22], we get the following lemma.

Lemma 4.1

Given a constant ${\overline{\mu }}\ge 0$. Let $\{x_k\}$ be the sequence generated by Algorithm 1, then

$$\begin{aligned} \underset{k\rightarrow \infty }{\lim }\Vert \nabla _{x}{{\widetilde{f}}(x_{k},{\overline{\mu }})}\Vert =0. \end{aligned}$$

Theorem 4.1

Let $\{\mu _k\}$ and $\{x_k\}$ be the sequence generated by Algorithm 1. Then

$$\begin{aligned} \underset{k\rightarrow \infty }{\lim }\Vert \nabla _{x}{{\widetilde{f}}(x_{k+1},\mu _k)}\Vert =0. \end{aligned}$$

Proof

Define $K=\{k|\mu _{k+1}=\sigma \mu _k\}$. Suppose K is a finite set, then there exists an integer ${\widehat{k}}$ such that for all $k>{\widehat{k}}$,

$$\begin{aligned} \Vert \nabla _{x}{{\widetilde{f}}(x_{k},\mu _{k-1})}\Vert \ge {\bar{\gamma }} \mu _k, \end{aligned}$$

(4.2)

set $\mu _k=\mu _{{\widehat{k}}}={\overline{\mu }}$, we get

$$\begin{aligned} \underset{x\in {\mathbb {R}}^n}{\min }\;{\widetilde{f}}(x,{\overline{\mu }}). \end{aligned}$$

From Lemma 4.1, we have

$$\begin{aligned} \underset{k\rightarrow \infty }{\lim }\Vert \nabla _{x}{\widetilde{f}}(x_k,{\overline{\mu }})\Vert =0, \end{aligned}$$

which contradicts with (4.2). So K is an infinite set, i.e., $\underset{k\rightarrow \infty }{\lim }\mu _k=0$. Set $K=\{k_0, k_1, \cdots \}$, for $k_0<k_1<\cdots$, then

$$\begin{aligned} \underset{k\rightarrow \infty }{\lim }\Vert \nabla _{x}{\widetilde{f}}(x_{k_i+1},\mu _{k_i})\Vert \le {\bar{\gamma }}\underset{i\rightarrow \infty }{\lim }\mu _{k_i}=0. \end{aligned}$$

The proof is completed. $\square$

In the following of this section, we verify the effectiveness of Algorithm 1 via the following given examples. The parameters used in Algorithm 1 are chosen as $\rho =0.5$, $\sigma =0.5$, $\delta =0.5$, $\mu _0=0.01$, ${\bar{\gamma }}=0.5$. We terminate our algorithm if $k\ge 10000$ or $\Vert \nabla _{x}{\widetilde{f}}(x_{k},\mu _{k})\Vert <1.0e-5$ satisfied. We implement all numerical test in MATLAB R2019b and run the codes on a PC with 1.80GHz CPU.

Example 4.1

Consider SAVE (1.1), where

$$\begin{aligned} A(\omega )=\left( \begin{array}{rcl} 2+\omega &{} 1\\ 5 &{} 1+\omega \end{array}\right) ,~~b(\omega )=\left( \begin{array}{rcl} 4+\omega \\ 5+3\omega \end{array}\right) . \end{aligned}$$

We generate samples $\omega ^i$, $i=1,2,\cdots ,N$, which obey the uniform distribution of [0, 1]. The numerical results of Example 4.1 are shown in Table 2 and Fig. 1, where N denotes the number of $\omega ^i$, $x^0$, $x^*$ and $f(x^*)$ denote the initial point, the optimum solution and the optimum value, respectively.

Table 2 Numerical results of Example 4.1

Fig. 1

Numerical results of Example 4.1

Example 4.2

Consider SAVE (1.1), where

$$\begin{aligned} A(\omega )=\begin{pmatrix}2+\omega &{}1&{}0&{}0\\ 2&{}1+\omega &{}0&{}0\\ 0&{}0&{}2+\omega &{}1\\ 0&{}2&{}0&{}1+\omega \end{pmatrix}, b(\omega )=\begin{pmatrix}2+\omega \\ 2+\omega \\ 2+\omega \\ 2+\omega \end{pmatrix}. \end{aligned}$$

We generate samples $\omega ^i$, $i=1,2,\cdots ,N$, which obey the uniform distribution of [0, 1]. The detailed numerical results are shown in Table 3 and Fig. 2, where N denotes the number of $\omega ^i$, $x^0$, $x^*$ and $f(x^*)$ denote the initial point, the optimum solution and the optimum value, respectively.

Table 3 Numerical results of Example 4.2

Fig. 2

Numerical results of Example 4.2

Example 4.3

Consider SAVE (1.1), where

$$\begin{aligned} A(\omega )=\begin{pmatrix}5+\omega &{}0&{}0&{}0&{}0&{}2&{}1&{}0&{}0&{}3\\ \frac{1}{2}&{}2+\omega &{}0&{}\frac{1}{2}&{}1&{}0&{}1&{}0&{}6&{}0\\ 0&{}\frac{1}{4}&{}7+\omega &{}\frac{3}{4}&{}0&{}2&{}0&{}0&{}\frac{1}{2}&{}\frac{1}{2}\\ 1&{}1&{}2&{}2+\omega &{}\frac{1}{2}&{}0&{}\frac{3}{2}&{}2&{}0&{}1\\ 0&{}0&{} \frac{2}{5}&{}\frac{1}{4}&{}6+\omega &{}2&{}0&{}1&{}\frac{7}{20}&{}1\\ 2&{}\frac{1}{2}&{}4&{}0&{}0&{}1+\omega &{}\frac{1}{2}&{}2&{}1&{}0\\ 0&{}5&{}0&{}\frac{2}{3}&{}0&{}\frac{2}{3}&{}3+\omega &{}\frac{1}{4}&{}1&{}\frac{5}{12}\\ 2&{}1&{}1&{}1&{}1&{}\frac{1}{2}&{}0&{}4+\omega &{}\frac{1}{2}&{}0\\ \frac{1}{7}&{}\frac{5}{7}&{}0&{}0&{}1&{}0&{}\frac{1}{7}&{}0&{}9+\omega &{}0\\ 3&{}0&{}2&{}1&{}\frac{5}{2}&{}0&{}\frac{1}{2}&{}\frac{1}{4}&{}\frac{1}{4}&{}1+\omega \end{pmatrix}, \end{aligned}$$

and

$$\begin{aligned} b(\omega )=(10+\omega ,10+\omega ,\cdots ,10+\omega )^{T}\in R^{10}. \end{aligned}$$

We generate samples $\omega ^i$, $i=1,2,\cdots ,N$, which obey the uniform distribution of [0, 1]. The initial points are randomly generated. The detailed numerical results are shown in Table 4 and Fig. 3, where N denotes the number of $\omega ^i$, $x^*$ and $f(x^*)$ denote the optimum solution and the optimum value respectively.

Table 4 Numerical results of Example 4.3

Fig. 3

Numerical results of Example 4.3

Example 4.4

Consider SAVE (1.1), where

$$\begin{aligned} A(\omega )={\begin{pmatrix}2+\omega &{}1&{}&{}&{}&{}\\ 1&{}2+\omega &{}1&{}&{}&{}\\ {} &{}1&{}2+\omega &{}1&{}&{}\\ &{}&{}\ddots &{}\ddots &{}\ddots &{}\\ &{}&{}&{}1&{}2+\omega &{}1\\ &{}&{}&{}&{}1&{}2+\omega \end{pmatrix}}_{n\times n}, \end{aligned}$$

and

$$\begin{aligned} b(\omega )=(2+\omega ,3+\omega ,3+\omega ,\cdots ,3+\omega ,2+\omega )^{T}\in R^n. \end{aligned}$$

We generate samples $\omega ^i$, $i=1,2,\cdots ,N$, which obey the uniform distribution of [0, 1]. The initial points are randomly generated. The detailed numerical results are shown in Tables 5, 6, Figs. 4 and 5, where n denotes the dimension, N denotes the number of $\omega ^i$, $x^*$ and $f(x^*)$ denote the optimum solution and the optimum value respectively.

Table 5 Numerical results of Example 4.4 ($\hbox {n}=100$)

Fig. 4

Numerical results of Example 4.4 ($\hbox {n}=100$)

Table 6 Numerical results of Example 4.4 ($\hbox {n}=500$)

Fig. 5

Numerical results of Example 4.4 ($\hbox {n}=500$)

From the above numerical results, we can see that SAVE (1.1) can be solved by simple unconstrained optimization method. And the ERM formulation can avoid transforming SAVE (1.1) into a complicated constrained optimization problem.

5 Conclusions

In this paper, we propose a new kind of absolute value equation problem with random quantities, which is called stochastic absolute value equations. The properties of the proposed stochastic absolute value equations are studied. The expected value formulation and expected residual minimization formulation for solving the proposed stochastic absolute value equations are also given. Absolute value equations is widely used in studying engineering problems, economics and management problems. It is very meaningful to study this kind of stochastic absolute value equations, which is a more extensive problem than the absolute value equations.