# An one step smoothing Newton method for a class of stochastic linear complementarity problems.

1 IntroductionThe stochastic linear complementarity problem (SLCP) is to find a vector x [member of] [R.sup.n] such that

x [greater than or equal to] 0, F(x, w) = M(w)x + q(w) [greater than or equal to] 0, [x.sup.T]F(x, w) = 0, (1)

where F : [R.sup.n] x [OMEGA] [right arrow] [R.sup.n] denotes a vector valued function, ([OMEGA], F, P) is a probability space with [OMEGA] [subset or equal to] [R.sup.m], M(w) [member of] [R.sup.nxn] and q(w) [member of] [R.sup.n] for w [member of] [OMEGA] are random matrices and vectors. Because of the existence of a random elements w, however, we cannot generally expect that there exists a vector [x.sup.*] satisfying (1). That is (1) may not have a solution in general. Therefore, to present an appropriate deterministic formulation of SLCP is an important issue. There have been proposed three types of formulations of SLCP, the expected value (EV) formulation [1, 2], the expected residual minimization (ERM) formulation [3,4,5,6], and the SMPEC formulation [7, 8].

This paper considers the following class of stochastic linear complementarity problems in which [OMEGA] only has finitely many elements. Let [OMEGA] = {[w.sub.1], [w.sub.2], ..., [w.sub.m]}. Find an x [member of] [R.sup.n] such that

x [greater than or equal to] 0, F(x, [w.sub.i]) = M([w.sub.i])x + q([w.sub.i]) > 0, [x.sup.T]F{x, [w.sub.i]) = 0, i = 1, 2, ..., m, m > 1. (2)

We suppose [p.sub.i] = P{[w.sub.i] [member of] [OMEGA]} > 0, i = 1, 2, ..., m. In [6], problem (2) was formulated equivalent to (3)-(4),

x [member of] 0, [bar.M]x + [bar.q] [greater than or equal to] 0, [x.sup.T]([bar.M]x + [bar.q]) = 0, (3)

M([w.sub.i])x + q([w.sub.i]) [greater than or equal to] 0, i = 1, 2, ..., m, (4)

where [bar.M] = [m.summation over (i=1)][p.sub.i]M([w.sub.i]) and [bar.q] = [m.summation over (i=1)][p.sub.i]q([w.sub.i]). Let [bar.F](x) be the expectation function of the random function F(x, w), then [bar.F](x) = E[F(x, w)} = [bar.M]x + [bar.q]. Paper [6] reformulated the problem (2) as a system of nonsmooth equations with nonnegative constraints.

In this paper, we aim at modifying the constrained minimization reformulation for (2) in [6]. By using the smoothing symmetric perturbed Fischer function (for short, denoted as the SSPF-function) [9], we propose a new formulation for SLCP (2) with smoothing parameter, which reformulates (3)-(4) as a system of smoothing equations without any constraints. We then extend the one step smoothing Newton method in [10] to this problem. Under the assumptions that [bar.M] is a [P.sub.0]-matrix and the solution set of the linear complementarity problem (3) is nonempty and bounded, the smoothing Newton algorithm is convergent globally and local quadratically.

Throughout this paper, we use the following notation. All vectors (vector functions) are column vectors (vector functions). [R.sub.++] denotes the positive orthant in R. For any vector u [member of] [R.sup.n], we denote by diag{[u.sub.i], i = 1, 2, ..., n} the diagonal matrix whose ith diagonal element is [u.sub.i]. The symbol [parallel] x [parallel] stands for the 2-norm. For any locally Lipschitzian function F : [R.sup.n] [right arrow] [R.sup.n], by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

denote the B-subdifferential and the Clark subdifferential of F at x respectively, in which [D.sub.F] [subset] [R.sup.n] denotes the set of points at which F is differentiable.

The following definitions will be used in this paper.

Definition 1. The mapping F : [R.sup.n] [right arrow] [R.sup.n] is said to be a [P.sub.0]-function if there is an index i such that

[x.sub.i] [not equal to] [y.sub.i] and ([x.sub.i] - [y.sub.i]) [[F.sub.i](x) - [F.sub.i](y)] [greater than or equal to] 0, for all x, y [member of] [R.sup.n], x [not equal to] y.

Definition 2. A matrix M [member of] [R.sup.nxn] is said to be a [P.sub.0]-matrix if all its principal minors are nonnegative.

Definition 3. Suppose that F : [R.sup.n] [right arrow] [R.sup.n] is a locally Lipschitzian function. F is said to be semismooth at x if F is directionally differentiable at x and for any V [member of] [partial derivative]F(x + h) and [parallel]h[parallel] [right arrow] 0,

[parallel]F(x + h) - F(x) - Vh[parallel] = o([parallel]h[parallel]).

F is said to be strongly semismooth at x if F is semismooth at x and

[parallel]F(x + h) - F(x) - Vh[parallel] = O([[parallel]h[parallel].sup.2]).

2 The New Formulation and Algorithm

In this section, we reformulate the problem (2) as an unconstrained optimization problem and then extend the one step smoothing Newton method in [10] to this problem.

In the rest of this paper, we assume that [bar.M] is a [P.sub.0]- matrix. Obviously, equation (3) is a standard linear complementarity problem. Therefore, we can reformulate it as a system of smooth equation by an NCP function. Here, we consider the smoothing symmetric perturbed Fischer function (SSPF-function) [9] [phi]: [R.sup.3] [right arrow] R defined by

[phi]([mu], a, b) = (1 + [mu])(a + b) - [square root of [(a + [micro]b).sup.2] + [([mu]a + b).sup.2] + [[mu].sup.2]. (5)

For [mu] = 0, [phi](0, a, b) is the Fischer-Burmeister function with the following property

[phi](0, a, b) = 0 [??] a [greater than or equal to] 0, b [greater than or equal to] 0, ab = 0.

Define the function [PHI] : [R.sup.n+1] [right arrow] [R.sup.n] by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (6)

Then, (3) is equivalent to the equation [PHI](0, x) = 0.

For any x [member of] [R.sup.n] and [mu] [member of] R, define the function f : [R.sup.n] [right arrow] [R.sup.n] and g : [R.sup.n+1] [right arrow] [R.sup.n], respectively, as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (7)

Thus, f(x) [greater than or equal to] 0, for all x [member of] [R.sup.n].

Set y = [[[y.sub..1], [y.sub..2], ..., [y.sub..m]].sup.T] [member of] [R.sup.mn], where [y.sub..i] [member of] [R.sup.n], i = 1, 2, ..., m. Let z = ([mu], x, y) [member of] [R.sup.n(m+1)+1] and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (8)

Hence, (3)-(4) is equivalent to finding a root of the following equation

H(z) = 0. (9)

Lemma 1. Lei [PHI] : [R.sup.n+1] [right arrow] [R.sup.n] and H : [R.sup.n(m+1)+1] [right arrow] [R.sup.n(m+1)+1] be defined by (6) and (8), respectively. Then

(i) [PHI] is continuously differentiable at any ([mu], x) [member of] [R.sup.n+1] with [mu] [not equal to] 0. For [mu] = 0, [PHI] is semismooth on [R.sup.n+1].

(ii) H is continuously differentiable and its Jacobian H' is nonsingular at any z = ([mu], x, y) [member of] [R.sub.++] x [R.sup.n] x [R.sup.mn].

(iii) H is locally Lipschitzian and strongly semismooth on [R.sup.n(m+1)+1].

Proof. (i) By Lemma 2.4 (a) in [10], (i) holds.

(ii) It follows from (i) and the definition (7) that H is continuously differentiable on [R.sub.++] x [R.sup.n] x [R.sup.mn]. For any z = ([mu], x, y) [member of] [R.sub.++] x [R.sup.n] x [R.sup.mn], we have that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (10)

where [u.sub.i](z) = [g'.sub.[mu]]([mu], [y.sub..i]) and [[DELTA].sub.i] = [g'.sub.y]([mu], [y.sub..i]), i = 1, 2, ..., m.

For any x [member of] [R.sup.n], [mu] [not equal to] 0, a straightforward calculation yields

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

It is not difficult to see that ([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then we have

[absolute value of [[DELTA].sub.i]] [not equal to] 0, i = 1, 2, ..., m. (11)

Since [bar.M] is a [P.sub.0]-matrix, [bar.F](x) must be a [P.sub.0]-function. In view of Lemma 2.4 (b) in [10], the matrix [[PHI]'.sub.x]([mu], x) is nonsingular. This together with (11) imply H'(x) is nonsingular at any z = ([mu], x, y) [member of] [R.sub.++] x [R.sup.n] x [R.sup.mn].

(iii) Since [bar.F](x) = [bar.M]x + [bar.q], there must exist a constant L > 0 such that

[parallel][bar.F']([x.sup.1]) - [bar.F']([x.sup.2])[parallel] = [parallel][bar.M] - [bar.M][parallel] [less than or equal to] L [parallel][x.sup.1] - [x.sup.2][parallel], [for all][x.sup.1], [x.sup.2] [member of] [R.sup.n].

By Lemma 2.4 (c) in [10], H is strongly semismooth on [R.sup.n(m+1)+1].

Next, we employ the algorithm in [10] to solve the equation (9).

Define

[rho](z) = [gamma][parallel]H(z)[parallel] x min{1, [parallel]H(z)[parallel]}, 0 < [gamma] < 1.

Algorithm

Step 0 Choose 0 < [[mu].sub.0]] < 1 and [delta], [sigma] [member of] (0, 1). Let [bar.u] = ([[mu].sub.0], 0) [member of] [R.sub.++] x [R.sup.n(m+1)] and ([x.sup.0], [y.sup.0]) [member of] [R.sup.n] x [R.sup.mn], Let [z.sup.0] = ([[mu].sub.0], [x.sup.0], [y.sup.0]). Choose [gamma] (0,1) such that [gamma][parallel]H([z.sup.0])[parallel] < 1. Set k = 0.

Step 1 If [parallel]H([z.sup.k])[parallel] = 0, stop. Otherwise, let [[rho].sub.k] = [rho]([z.sup.k]).

Step 2 Compute [DELTA][z.sup.k] = ([DELTA][[mu].sub.k], [DELTA][x.sup.k], [DELTA][y.sup.k]) [member of] [R.sup.n(m+1)+1] by

H([z.sup.k]) + H'([z.sup.k])[DELTA][z.sup.k] = [[rho].sub.k][bar.u]. (12)

Step 3 Let [m.sub.k] be the smallest nonnegative integer such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (13)

Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Step 4 Set [z.sup.k+1] = [z.sup.k] + [[alpha].sub.k][DELTA][z.sup.k] and k = k + 1. Go to Step 1.

Like the analysis in [10], in order to prove the algorithm is well-defined, we should define the set

[bar.[OMEGA]] = {z [member of] [R.sup.n(m+1)+1]| [mu] [greater than or equal to] [rho](z)[[mu].sub.0]}.

Lemma 2. The algorithm is well-defined and generates an infinite sequence {[z.sup.k] = ([[mu].sub.k], [x.sup.k], [y.sup.k])} with [[mu].sub.k] [member of] [R.sub.++] and [z.sup.k] [member of] [bar.[OMEGA]] for all k [greater than or equal to] 0.

Proof. The result can be obtained immediately from Theorem 2.5 in [10].

3 Convergence Analysis

The convergence properties of this method are summarized in the following theorem.

Assumption 1. The solution set of (3) is nonempty and bounded.

Theorem 1. Suppose that Assumption 1 is satisfied and [bar.M] is a [P.sub.0]-matrix. Let {[z.sup.k] = ([[mu].sub.k], [x.sup.k], [y.sup.k])} be the iteration sequence generated by the algorithm. Then

(i) {[z.sup.k]} is bounded.

(ii) The sequences {[parallel]H([z.sup.k])[parallel]} and {[[mu].sup.k]} tend to zero and hence it has at least one accumulation point [z.sup.*] = ([[mu].sub.*], [x.sup.*], [y.sup.*]) with H([z.sup.*]) = 0. Therefore, [x.sup.*] is a solution of (3)-(4).

(iii) If all V [member of] [partial derivative]H([z.sup.*]) are nonsingular, then the whole sequence {[z.sup.k]} converges to [z.sup.*] and the rate of convergence is quadratic.

Proof. (i) Define the level set

L(c) = {z [member of] [R.sup.n(m+1)+1][parallel]H(z)[parallel] [less than or equal to] [parallel]H([z.sup.0]])[parallel] = c}.

Let [bar.L](c) = {x [member of] [R.sup.n]|[parallel][PHI]([mu], x)[parallel] [less than or equal to] c}. Then [bar.L](c) [subset] L(c). From line search (13), we know {[z.sup.k]} [subset] L(c). It follows from Assumption 1 and Theorem 3.6 (ii) in [10] that {[[mu].sub.k], [x.sup.k]} is bounded. So, we only to prove {[y.sup.k]} is bounded. Suppose [parallel][y.sup.k][parallel] [right arrow] [infinity], then

[parallel]M([w.sub.i])[x.sup.k] + q([w.sub.i]) - g([[mu].sub.k], [y.sup.k.sub..i])[parallel][infinity], i = 1/2, ... m.

This contradicts the fact that [z.sup.k] [member of] L(c).

(ii) From Lemma 2, we known

[[mu].sub.k+1] = [[mu].sub.k] + [[alpha].sub.k][DELTA]k = (1 - [alpha].sub.k])[[mu].sub.k] + [[alpha].sub.k][[rho].sub.k][[mu].sub.0] [less than or equal to] [[mu].sub.k],

which implies that {[[mu].sub.k]} is monotonically decreasing and bounded. Thus, {[[mu].sub.k]} is convergent. On the other hand, by (i) and (13), {[parallel]H([z.sup.k])[parallel]} is also monotonically decreasing and bounded and hence is convergent. Let [z.sup.*] = ([[mu].sub.*], [x.sup.*], [y.sup.*]) be an accumulation point of {[z.sup.k]}. Without loss of generality, we assume that {[z.sup.k]} converges to [z.sup.*]. Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

If {[parallel]H([z.sup.k])[parallel]} does not converge to zero. Then

[parallel]H([z.sup.*])[parallel] > 0, [[rho].sub.*] > 0, 0 < [[rho].sub.*][[mu].sub.0] [less than or equal to] [[mu].sub.*] [less than or equal to] [[mu].sub.0]. (14)

So [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] from (13). Thus, the stepsize [??] = [[alpha].sub.k]/[delta] does not satisfy the line search criterion in Step 3 for any sufficiently large k, i.e., the following inequality holds

[parallel]H([z.sup.k] + [??][DELTA][z.sup.k])[parallel] > [1 - [sigma] (1 - [gamma])[??]][parallel]H([z.sup.k])[parallel]

for any sufficiently large k, which implies that

[parallel]H([z.sup.k] + [??][[DELTA][z.sup.k])[parallel] - [parallel]H([z.sup.k])[parallel]/[??] > -[sigma](1 - [gamma])[parallel]H([z.sup.k])[parallel].

From [[mu].sub.*] [not equal to] 0, we know that H(x) is continuously differentiable at [z.sup.*]. Letting k [right arrow] [infinity], then above inequality gives

1/[parallel]H([z.sup.*])[parallel][(H([z.sup.*])).sup.T]H'([z.sup.*]) [DELTA][z.sup.*] [greater than or equal to] -[sigma](1 - [gamma])[parallel]H([z.sup.*])[parallel]. (15)

Additionally, by taking the limit on (12), we get

H'([z.sup.*]) [DELTA][z.sup.*] = -H([z.sup.*]) + [[rho].sub.*][bar.u]. (16)

Combining (15) with (16), we have

[[rho].sub.*][parallel]H([z.sup.*])[parallel][[mu].sub.0] [greater than or equal to] [1 - [sigma](1 - [gamma])][[parallel]H([z.sup.*])[parallel].sup.2].

Noting 0 < [[mu].sub.0] < 1 and the definition of [[rho].sub.k], then

[gamma][[parallel]H([z.sup.*])[parallel].sup.2] [greater than or equal to] [1 - [sigma](1 - [gamma])][[parallel]H([z.sup.*])[parallel].sup.2] . (17)

(17) indicates (1 - [sigma])(1 - [gamma]) [less than or equal to] 0, which contradicts the fact that [sigma], [gamma] [member of] (0, 1). Thus, H([z.sup.*]) = 0 and [[mu].sub.*] = 0. According to the definition of H, we obtain

M([w.sub.i])[x.sup.*] + q([w.sub.i]) [greater than or equal to] 0, i = 1, 2, ..., m and [PHI](0, [x.sup.*]) = 0.

Therefore, [x.sup.*] is a solution of (3)-(4).

(iii) These results can be proved by following from Theorem 3.7 in [10].

Remark The conditions of global and local convergence in this paper are weaker than those required by [6].

References

[1] G. Gurkan, A.Y. Ozge and S.M. Robinson, Sample-path solution of stochastic variational inequalities, Mathematical Programming, 1999, 84: 313-333.

[2] H. Jiang and H. Xu, Stochastic approximation approaches to the stochastic variational inequality problem, IEEE Transactions on Automatic Control, 2008, 53: 1462-1475.

[3] X. Chen and M. Fukushima, Expected residual minimization method for stochastic linear complementarity problems, Mathematics of Operations Research, 2005,30: 1022-1038.

[4] X. Chen, C. Zhang and M. Fukushima, Robust solution of monotone stochastic linear complementarity problems, Mathematical Programming, 2009, 117: 51-80.

[5] H. Fang, X. Chen and M. Fukushima, Stochastic R0 matrix linear complementarity problems, SIAM Journal on Optimization, 2007, 18: 482-506.

[6] G.L. Zhou and L. Caccetta, Feasible semismooth Newton method for a class of stochastic linear complementarity problems, Journal of Optimization Theory and Applications, 2008, 139: 379-392.

[7] G.H. Lin, Combined Monte Carlo sampling and penalty method for stochastic nonlinear complementarity problems, Mathematics of Computation, 2009, 78: 1671-1686.

[8] G.H. Lin and M. Fukushima, New reformulations for stochastic complementarity problems, Optimization Methods and Software, 2006, 21: 551-564.

[9] Z.H. Huang, J.Y. Han, D.C. Xu, and L.P. Zhang, The non-interior continuation methods for solving the [P.sub.0]-function nonlinear complementarity problem, Science in China, 2001, 44: 1107-1114.

[10] L.P. Zhang, J.Y. Han and Z.H. Huang, Superlinear/Quadratic one-step smoothing Newton method for [P.sub.0]-NCP, Acta Mathematica Sinica, English Series, 2005, 21: 117-128.

* Project supported by Program of Higher-level talents of Inner Mongolia University, Z20090135 and the Natural Science Foundation of Inner Mongolia Autonomous Region, 2010BS0108.

Received by the editors August 2010.

Communicated by A. Weiermann.

2000 Mathematics Subject Classification : 90C33.

College of Mathematics Science, Inner Mongolia University, Hohhot 010021 P. R. China email: wucaiyingyun@163.com

Printer friendly Cite/link Email Feedback | |

Author: | Wu, Caiying |
---|---|

Publication: | Bulletin of the Belgian Mathematical Society - Simon Stevin |

Article Type: | Report |

Date: | May 1, 2011 |

Words: | 3003 |

Previous Article: | On functions convex in the direction of the real axis with real coefficients. |

Next Article: | Core theorems for subsequences of double complex sequences. |

Topics: |