A Smoothing SAA Method for a Stochastic Linear Complementarity Problem

ZHANG JIE,ZHANG HONG-WEIAND ZHANG LI-WEI

(1.School of Mathematics,Liaoning Normal University,Dalian,Liaoning,116029) (2.School of Mathematical Sciences,Dalian University of Technology,Dalian,Liaoning,116024)

Communicated by Yin Jing-xue

A Smoothing SAA Method for a Stochastic Linear Complementarity Problem

ZHANG JIE1,ZHANG HONG-WEI2AND ZHANG LI-WEI2

(1.School of Mathematics,Liaoning Normal University,Dalian,Liaoning,116029) (2.School of Mathematical Sciences,Dalian University of Technology,Dalian,Liaoning,116024)

Communicated by Yin Jing-xue

Utilizing the well-known aggregation technique,we propose a smoothing sample average approximation(SAA)method for a stochastic linear complementarity problem,where the underlying functions are represented by expectations of stochastic functions.The method is proved to be convergent and the preliminary numerical results are reported.

aggregation technique,smoothing SAA method,stochastic linear complementarity problem

1 Introduction

In this paper,we consider the following stochastic linear complementarity problem(SLCP): fi ndsuch that

To ease the notation,we write ξ(ω)as ξ and this should be distinguished from ξ being a deterministic vector of Ξ in a context.

SLCP(1.1)is a natural extension of the deterministic complementarity problem and can be seen as a special case of the stochastic variational inequality problem which was f i rstproposed by G¨urkan et al.[1]Over the past several decades,the complementarity problem has been intensively studied for its extensively application in engineering,economics,game theory and networks(see[2]).While in practical,there are some important instances that the problem data contains some uncertain factors,and consequently,the stochastic complementarity models are proposed to ref l ect the uncertainties.Some examples of the stochastic complementarity problem,arising from the areas of economics,engineering and operations management can be found in[3].

In this paper,we focus on numerical methods for solving(1.1).Evidently,if the integral involved in the mathematical expectation problems exists or is computable,then the problem (1.1)is reduced to the usual LCP problem and the existing methods in[2]can be applied directly to it.However,in many cases,an exact evaluation of the expected value in(1.1)for x is either impossible or prohibitively expensive.The sample average approximation(SAA) method is suggested to handle this difficulty(see[4–6]).The basic idea of SAA is to generate an independent identically distributed(iid)sampleof ξ,and then approximate the expected value with a sample average.In this context,SLCP(1.1)is approximated by

where

is a sample-average mapping of Ψ(x).We refer to(1.1)as a true problem and(1.2)as an SAA problem to(1.1).

Recently,Chen and Fukushima[7]consider another type of stochastic linear complementarity problem:

They formulate(1.4)as a problem of minimizing an expected residual def i ned by an NCP function,which is referred to as the ERM method.Then,they employ a qusi-Monte Carlo method and give some convergence results under suitable assumptions on the associated matrices.

In this paper,inspired by ERM method,incorporating SAA method with the well known aggregation function,we propose a smoothing SAA method for solving(1.1).We study the almost sure existence of solutions of SAA problem when the sample size is sufficiently large and show that under moderate conditions,a sequence of SAA solutions converges to the solution of counterpart true problem with probability one at exponential rate as the sample size tends to inf i nity.Finally,some numerical results are also reported.

Throughout this paper we use the following notations.Let‖·‖denote the Euclidean norm of a vector or the Frobenius norm of a matrix and

denote the distance from a point x to a set D.Let B be the closed unite ball and B(x,δ) be the closed ball around x of radius δ＞0.For two sets,we denote bythe deviation of set A from the set C.Note that D(·,·)satisf i es the triangle inequality, i.e.,for sets,the following inequality holds:

2 Smoothing SAA Method Formulating

Aggregation function is a well known smoothing function for max-type functions.Let

where wi(i=1,···,m)are continuously dif f erentiable functions.It is clear that w(·)is continuous in Rnbut not dif f erentiable everywhere.For any t＞0,the aggregation function of w(x),noted as w(t,x):,is def i ned by

The function,viewed as an exponential penalty function for constrained minimization,is proposed by Kort and Bertsekas[8].Independently,Li[9-10]studied(2.1)and named it as the aggregation function.An interesting feature of w(t,x)(see Example 1.30 of[11])is

which implies

and the convergence is uniform with respect to x.We know from the def i nition that w(t,x) is a smoothing function with respect to x for t＞0,and hence utilizing this property,over the past decade,some authors have used the aggregation function to propose smoothing methods for generalized linear complementarity problems and nonlinear complementarity problems(see[12–13]and the references therein).

Notice that SLCP(1.1)is equivalent to

We def i ne

where

Then we know from the def i nition that Gt(x)is continuously dif f erentiable with respect to t for all t＞0,and

Therefore it is natural to def i ne

and

Let

It is then obvious that the nonnegative function f is zero at a point x if and only if x is a solution of SLCP(1.1),so that solving SLCP(1.1)is equivalent to f i nding the unconstrained global solutions of the problem(2.4).By taking independently and identically distributed random samples ξi(i=1,···,N)and introducing the smoothing function Gt(·)in(2.3), we obtain the following approximation of the problem(2.4):

where

with

We denote by SLthe solution set of(2.4),bythe solution set of(2.5),and by S0the solution set of SLCP(1.1).

3 Existence and Almost Sure Convergence

It is well known that the R0property relates closely to the boundedness of level sets in the literature of the complementarity problem.Recall that M∈Rn×nis called an R0matrix if for x∈Rn

If we denote

then we have

Lemma 3.1Ifis an R0matrix,then there existssuch thatis almost surely an R0matrix for all N≥.

Proof.Assume that this lemma were not true.Then for any＞0,there would exist ansuch thatis not an R0matrix almost surely.So we can choose a sequence {Nk}?N such that Nk→+∞as k→+∞andis not an R0matrix almost surely for each k.That is,for each k,we can f i ndsatisfying

Let

Then we have

Notice that

Therefore,letting k→+∞,we obtain a vectorsatisfying

This contradicts the assumption thatis an R0matrix and completes the proof.

By the def i nition of gt(·,·)and Proposition 3.2 of[13],we have the following lemma.

Lemma 3.2Let t≥0.Then for any real numbers a and b,we have

(i)g0(a,b)-tln2≤gt(a,b)≤g0(a,b).

(ii)There exist δ＞0 and L＞0 such that

Lemma 3.3Assume thatis an R0matrix.Then there existsˉN＞0 such that for any positive numbers γ and tN,the level set

is bounded almost surely for each N≥

Proof.By Lemma 3.1,there exists an＞0 such thatis almost surely an R0matrix for all N≥.To prove this lemma,we only need to show that→+∞almost surely for all N≥whenever→+∞for any sequence.Suppose that→+∞as k→+∞.From the def i nition we know that if→-∞or→-∞almost surely for some i as k→+∞,then it follows that

for tN＞0.So it suffices to consider the case when both sequencesandare bounded below almost surely for all i.Then,by dividing each element of these sequences byand passing to the limit,we obtain that for all N≥

which,in turn,by Lemma 3.2,means

Theorem 3.1Assume thatis an R0matrix.Then there exists an＞0 such thatis nonempty and bounded almost surely for each N≥.Letalmost surely andas.Then,every accumulation point of the sequenceis contained inalmost surely.

Proof.By Lemma 2.2,there exists an＞0 such that for＞0 and γ＞0,the level set(3.1)is bounded almost surely for each N≥which,by Theorem 1.9 in[11],implies thatis nonempty and bounded almost surely for each N≥

where

Since

we have

which implies that

and by Lemma 3.2,there exists an L＞0 such that for N sufficiently large,

Then combining(3.2),(3.4)and(3.5),we obtain

In a similar way,we can also show

Therefore,we have

The proof is completed.

We know from the knowledge of the deterministic linear complementarity problem that the matrixin(1.1)being a P matrix(for matrices M,for all x/=0 there exists an i such that＞0)is a necessary and sufficient condition for the existence and uniqueness of the solution of SLCP(1.1).Thus we have the following result.

Corollary 3.1Assume thatis a P matrix.Then there exists an＞0 such thatis nonempty and bounded almost surely for each N≥.Letalmost surely for each N and tN↘0 as N→+∞.Then,every accumulation point of the sequenceis contained inalmost surely.

4 Exponential Convergence Rate

In this section,under suitable conditions,we show that with the increase of sample size the optimal solutions of the approximation problem(2.5)converge exponentially to a solution of SLCP(1.1)with probability approaching one.For this purpose,we need to make the following assumption:

Assumption AFor every i∈{1,···,n},we have the following properties:

(A1)For all x∈X,the moment generating function

of the random variable[M(ξ)x]i-[E(M(ξ)x)]iis f i nite valued for all t in a neighborhood of zero.

(A2)‖M(ξ)‖is measurable for all ξ∈Ξ.

(A3)The moment generating

of‖M(ξ)‖is f i nite valued for all t in a neighborhood of zero.

Then by Theorem 6.52 in[6],we obtain the following lemma.

Lemma 4.1Suppose that Assumption A holds and the set X is compact.Then for any ε＞0,there exist positive constants

independent of N such that .

We need the following lemma which can be obtained by using a local upper Lipschitz property of a polyhedral multifunction given by Robinson[14].

Lemma 4.2There exist positive numbers δ and α such that

and

Theorem 4.1Letalmost surely,tN↘0 and

Suppose that

(i)S0is nonempty;

(ii)Assumption A holds;

(iii){xN}?X w.p.1 and X is compact.

Then for any ε＞0,there exist positive constants

independent of N such that for N sufficiently large

Proof.We know from S0being nonempty that

almost surely,which,by Lemma 4.1,implies that there exists an α＞0 such that for N sufficiently large

By the proof of Theorem 3.1,we have for N sufficiently large

which means

for N sufficiently large.Together with(4.1),by Lemma 3.2,it means that there exists an L＞0 such that for N sufficiently large,

dist(xN,S0)

Since tN↘0,,by the proof of Theorem 3.1,and

we have that for any positive number ε,

hold for all N sufficiently large.On the other hand,for the above ε,by Lemma 4.1,there exist positive constants

independent of N such that

which,together with(4.3)and(4.4),implies that for N sufficiently large,

where

We have completed the proof.

Corollary 4.1Assume thatis a P matrix and Assumptions(i)–(iii)in Theorem 4.1 hold.Let

Then for any ε＞0,there exist positive constants

independent of N such that for N sufficiently large

5 Numerical Results

In this section,we present some preliminary numerical results obtained by the smoothing SAA method.Our numerical experiments are carried out in Matlab 7.1 running on a PC with Intel Pentium M of 1.60 GHz CPU and our tests are focused on dif f erent values of the smoothing parameter t and the sample size N.

In our experiments,we set the initial values of Nkand tkas N1=100 and t1=5, respectively.Then,we employ the random number generator“unifrnd”in Matlab 7.1 to generate independently and identically distributed random samples{ξ1,ξ2,···,ξNk}.We solve the problems(2.5)with N=Nkand t=tkby the solver“fminsearch”in Matlab 7.1 to obtain the approximated optimal solution xNk.The initial point is

The obtained solution xNkis used as the starting point in the next iteration.In addition, the parameters are updated by“Obj”denotes the values of the objective function of the problem(2.5)at xNk.

Example 5.1Consider the stochastic linear complementary problem(1.1)in which ξ is uniformly distributed on[0,1].M(ξ(ω))and q(ξ(ω))are given by

respectively.This problem has a unique solution

for each ω∈Ω.The optimal values of the approximation problem(2.5)with Nkand tkcorresponding to this example is zero,which is shown in Table 5.1.

Table 5.1The computational results for Example 5.1

Example 5.2Consider the stochastic complementary problem(1.1)in which ξ is uniformly distributed on[0,1].M(ξ(w))and q(ξ(w))is given by

respectively.This problem has a solution

for each ω∈Ω.The numerical results of the approximation problem(2.5)with Nkand tkcorresponding to this example are shown in Table 5.2.

Table 5.2The computational results for Example 5.2

Our preliminary numerical results shown in Tables 5.1 and 5.2 reveal that our proposed method yields a reasonable solution of the problems considered.

6 Conclusion

In this paper,utilizing the aggregation technique,we propose a smoothing SAA method for a stochastic linear complementarity problem.Under suitable conditions,we obtain the almost surely convergence and exponential rate of this method.The preliminary numerical results indicate that the proposed method is able to solve SLCP successfully.

[1]G¨urkan G,¨Ozge A Y,Robinson S M.Sample-path solution of stochastic variational inequalities.Math.Programming,1999,84:313–333.

[2]Facchinei F,Pang J S.Finite-dimensional Variational Inequalities and Complementarity Problems.vol.I/II.New York:Springer-Verlag,2003.

[3]Jiang H,Xu H.Stochastic approximation approaches to the stochastic variational inequality problem.IEEE Trans.Automat.Control,2008,53:1462–1475.

[4]Rusczyˊnski A,Shapiro A.Stochastic Programming.Handbooks in OR&MS 10.Amsterdam: North-Holland,2003.

[5]Xu H.An implicit programming approach for a class of stochastic mathematical programs with equilibrium constraints.SIAM J.Optim.,2006,16:670–696.

[6]Shapiro A,Dentcheva D,Ruszczynski A.Lectures on Stochastic Programming:Modeling and Theory.Philadelphia:SIAM,2009.

[7]Chen X J,Fukushima M.Expected residual minimization method for stochastic linear complementarity problems.Math.Oper.Res.,2005,30:1022–1038.

[8]Kort B W,Bertsekas D P.A New Penalty Function Algorithm for Constrained Minimization. Proceedings of the 1972 IEEE Conference on Decision and Control.Louisiana:New Orleans, 1972.

[9]Li X S.An aggregate function method for nonlinear programming.Sci.China Ser.A,1991, 34:1467–1473.

[10]Li X S.An entropy-based aggregate method for minimax optimization.J.Engrg.Optim.,1992, 18:277–185.

[11]Rockafellar R T,Wets R J B.Variational Analysis.Berlin-Heidelberg-New York:Springer-Verlag,1998.

[12]Peng J,Lin Z.A non-interior continuation method for generalized linear complementarity problems.Math.Programming,1999,86:533–563.

[13]Qi H,Liao L.A smoothing Newton method for extended vertical linear complementarity problems.SIAM J.Matrix Anal.Appl.,1999,21:45–66.

[14]Robinson S M.Some continuity properties of polyhedral multifunctions.Math.Program.Study, 1981,14:206–214.

tion:90C30

A

1674-5647(2013)02-0097-11

Received date:Aug.19,2010.

The NSF(11071029 and 11171138)of China.

E-mail address:zj04212001@yahoo.com.cn(Zhang J).