{'fraction_non_alphanumeric': 0.04964424320827943, 'fraction_numerical': 0.019647477360931438, 'mean_word_length': 3.9122319301032564, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 4, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Projected trust region method for stochastic linear complementarity problems

ABSTRACT: In this paper, we consider the method for solving a kind of general stochastic linear complementarity problems. Based on Fischer-Burmeister function, we transform this kind of general stochastic linear complementarity problems into nonsmooth equations and present a projected trust region method to solve the nonsmooth equations. The global convergence of this method is also given. Finally, the numerical results are reported.


INTRODUCTION
With the continuous maturity and development of financial markets in various countries, the trading system and tools in the financial field are becoming more and more perfect. The types and forms of representative options in financial derivatives are constantly and increasingly developed. An option in a derivative is the right to buy and sell assets at a certain price. In the field of finance and mathematics, the pricing of derivative securities, represented by option pricing, has been studied a long time 1,2 . Because American option is more complex than European option, the current American option pricing problem is still one of the most important problems in the derivative securities pricing problem. In the case of no arbitrage, the equation was converted to a stochastic complementarity problem 3 , which is based on the definition of the portfolio. The portfolio is constructed when the Black-Scholes equation is derived. Besides, the prices of American options are depended on the asset price, the strike price, the expiration date, the risk-free rate and the volatility of the asset price, which is usually assumed as constant. However, since each expert has its own views on volatility, it is unsuitable to set up the volatility as a constant 4 . Ref. 5 provided the relationship of option pricing and linear complementarity problems and Ref. 4 proposed a kind of stochastic linear complementarity problems to solve the problem. They also gave the existence conditions of the solution. On the other hand, the stochastic linear complementarity problems has an important application in engineering 6 , transportation 7 and others 8 . For example, the refinery production and the demand depend on the output of oil and the weather 8 , respectively, which change every day with uncertainty. The refinery production problem can be transformed into a stochastic linear complementarity problem with four random variations. This shows that the stochastic linear complementarity problems is one of the important mathematical models in the financial problems. Hence in this study, we present a more general stochastic linear complementarity problem, which contains the models of the above problems.
Assume that (Ω, F, P) is a probability space with Ω ⊆ n , where the probability distribution P is known. A general stochastic linear complementarity problem is to find a vector x ∈ n such that where Ω ⊆ n is the underlying sample space and ω ∈ Ω = {ω 1 , ω 2 , . . . , ω n } is a random vector with given probability distribution P, λ ∈ and I is n× n identity matrix. For each ω, A 1 (ω), A 2 (ω), b 1 (ω), and b 2 (ω) are n × n matrices and n-dimensional vectors, respectively. When λ = 0, the above problem is transformed into the general stochastic linear complementarity problems 9 , i.e., to find a vector x ∈ n such that When F (x, ω) = x, the above problem is transformed into the stochastic linear complementarity problems 8,10 . This kind of problems is usually solved by expectancy value (EV) method and expected residue minimization method, which are widely studied in many articles 11, 12 . When Ω includes only one element, problem (1) is transformed into the general linear complementarity problems 13 , i.e., to find a vector x ∈ n such that where M 1 and M 2 are n × n matrices, q 1 and q 2 are n-dimensional vectors.
When G(x, ω) = x, the general linear complementarity problems are transformed into the linear complementarity problems (LCP), which are widely used in solving absolute value equations, equilibrium problems and the related problems. For more details of the applications of LCP see Refs. 14, 15. The interested readers can also refer to two monographs (Refs. 16,17) by Cottle et al. There are many well-known methods for solving LCP and we consider some methods to solve problem (1). To transform the problem (1) to LCP, we use the EV method to obtain the following equations. Denote where p i = P(ω i ∈ Ω) 0, i = 1, . . . , m. The problem (1) is equivalent to the problem defined as and  13 and differentiable at any point (a, b) = (0, 0). Furthermore, the square of the Fischer-Burmeister function is continuously differentiable at any point in the plane. Hence we use the Fischer-Burmeister function to transform problem (4) and solving problem (4) is equivalent to solve Φ(x) = 0, where To solve problem (4) and problem (5), it is equivalent to solve the following problem, where x , y) ∈ (2m+2)n and define a merit function of (6) as f (z) = 1 2 H(z) 2 . If problem (1) has a solution, then solving (6) is equivalent to find a global solution of the optimization problem, where To make the transformation of problem (1) more distinct, we give a concrete example to explain the transformation process. Consider problem (1), where www.scienceasia.org www.scienceasia.org Then We obtain and with y = ( y 11 , y 12 , y 21 , y 22 , y 31 , y 32 , y 41 , y 42 ) 0. The problem (9) is transformed into a nonnegative constrained optimization problem.
There are many methods to solve problem (8) and the related optimization problems, such as Refs. 21, 22. The Levenberg-Marquardt method is an important method that has been widely used in recent years 23,24 . It overcomes the fact that the Gauss-Newton method requires full rank of the Jacobian matrix's column of H in the iteration process. And the convergence rate of Levenberg-Marquardt method is quadratic. However, the descent direction of the Levenberg-Marquardt method is where V k ∈ ∂ H(z k ) and µ k is Lagrange multiplier. d k is related to the value of µ k and it is difficult to define a suitable value of µ k . Fortunately, trust region method is a method which is related closely to the Levenberg-Marquardt method. Furthermore, trust region method could adjust the radius by quadratic model to obtain a more sufficient descent of the objective function. The positivity of the Hessian matrix is not necessary in the projected trust region method. Hence the projected trust region method is also widely used 25,26 . In this work the projected trust region method is used to solve for the special structure of problem (1).

PROJECTED TRUST REGION METHOD
This section provides some preliminaries 17,27 and proposes the projected trust region method for solving the given general stochastic linear complementarity problems.

Definition 1 For a local Lipschitzian function
Clarke's generalized Jacobian of F at z ∈ n is where conv denotes the convex hull of a set. Note For any z = (x , x , y) ∈ (2m+2)n , we have , I is the n × n identity matrix, and λ ∈ .
exists for any h ∈ n .
Definition 3 F is said to be strongly semi-smooth at z if F is semi-smooth at z and www.scienceasia.org The projected trust region method contains elements from affine-scaling methods. By the methods proposed 28,29 , the first-order optimization condition of problem (8) is equivalent to the nonlinear system is a suitable scaling matrix for z ∈ Ω 1 that satisfies conditions for i = 1, . . . , n and z ∈ Ω 1 .
To solve problem (8), let z k be the kth iteration point, denote ∈ (0, 1). The trust region subproblem of kth iteration has the form where ∆ k is the radius of projected trust region and z k is the mean of kth iteration. Suppose that the optimum solution of problem (10) is d k , the actual decrease of f in the kth step is and the predicted decrease is with the ratio r k = ∆ f k /∆q k . The solution p k of problem (10) satisfies the Cauchy decrease condition where α ∈ (0, 1) and p c k = p(t k ) is the scaled Cauchy step, when t k is a solution of min p(t)=−t D 2 k g k , t 0 p(t) ∆ k , z k +p(t) 0 q k (p(t)).
Step 1: Compute g k = ∇ f (z k ). If D k g k < ε, stop. Step Step 3: and go to Step 7. Otherwise, go to Step 4.
Step 4: Solve subproblem (10) to obtain the solution p k and compute Pred(p k ) = ∆q k , Ared(p k ) = ∆ f k , and r k .
Step 7: Set k = k + 1 and go to Step 1.

CONVERGENCE ANALYSIS
This section provides the global and local convergence properties of the projected trust region method based on the following lemmas proposed in Ref. 29.

Lemma 1 (Ref. 29)
Let p k be a solution of the subproblem (10) satisfying (11). Then Proof : From the definition of V k , V T k V k is positive semidefinite. Thus V T k V k + µ k I is positive definite. Then the result is similar to the proof of Lemma 1 in Ref. 25.
www.scienceasia.org , the projected Levenberg-Marquardt method. Suppose that the descent direction is obtained by Step 4 and obtain ∇ f (z k ) = 0. To prove by contradiction, we assume that lim inf k→∞ ∇ f (z k ) = 0. This gives

Assumption 1 For the initial point z 0 , f (z) has a lower bound and is continuously differentiable on the level set L(z
From Taylor expansion, Since V k is upper semicontinuous 32 , ∂ B H(z k ) is nonempty compact set at any point and bounded in bounded set of points. Thus ∂ C H(z k ) is bounded. Since V k is bounded for any V k ∈ ∂ C H(z k ), B k = V T k V k + µ k I is bounded and there exists a positive constant c such that This gives From Ref. 29, there exists a positive constant ε 0 such that D k ∇ f (z k ) ε 0 . By Lemma 1, we have and |r k −1| → 0 as ∆ k → 0. By the monotone descent property, continuity, and the boundedness of f (z k ) on L(z 0 ), we obtain However, by (16) and Method 1, we know that r k η 2 holds for k sufficiently large and ∆ k+1 ∆ k . Thus there exists ∆ > 0 and γ > 0 that ∆ k γ∆ > 0 hold for any k satisfying ∆ k ∆ , and obtain Clearly, (17) and (18) are contradictory, therefore, Theorem 2 Let {z k } be a sequence generated by Method 1. If z * , an accumulation point of {z k }, is a solution of problem (8) and any V k ∈ ∂ C H(z * ) has full rank. Then we know that {z k } is Q-quadratic convergent.
In the numerical experiments, the initial points are given randomly. We use n to denote the dimension of the problem, and x * the minimum point of f (z).
In this example, we select different dimensions n.
The problems numerical results corresponding to different n are given in Table 2, where the numerical experiments were carried out 10 times for each n.
The values of f are degressive rapidly showing that the Method 1 is effective for solving Examples 1 and 2, see Fig. 1. The problem is complex when n = 800 in Example 2, which has x , x ∈ 800 , y i ∈ 800 , i = 1, . . . , 1600, and z ∈ 1281600 . The numerical results of Example 2 show that Method 1 is effective in solving this kind of general stochastic linear complementarity problems.
Example 3 Consider the refinery production problem 8,33 , where A 1 (ω) is an identity matrix, b 1 (ω) = 0, 3, 4, 2x 1 + 3x 2 is the initial production cost, and ω j satisfy the distribution N (0, 12), Generated samples ω k j , j = 1, . . . , 4, k = 1, 2, . . . , K, from their respective 99% confidence intervals are, except for uniform distributions, For each ( j, i), the mean of the samples ω k j that belong to the subinterval I j,i is v j,i and the estimate probability of v j,i is p j,i = k j,i /K, where k j,i is the number of samples ω k j ∈ I j,i . Denote N = m 1 × m 2 × m 3 × m 4 and the joint distribution {(ω l , p l ) | l = 1, 2, . . . , N } as Tables 3 and 4 show that the minimization of f and the minimum product cost 2x k 1 + 3x k 2 are all computed effectively by Method 1. The numerical results sufficiently show that the projected trust region method is a reliable solver for the proposed general stochastic complementarity problems.

CONCLUSIONS
In this study, a kind of general stochastic complementarity problem is considered and solved by a projected trust region method. This kind of general stochastic complementarity problem is more general and contains many models of practical problems, such as the refinery production problem. The global convergence of the projected trust region method is proved under general conditions, which is also verified by some numerical results.