Application Of Optimization Algorithms In Option Pricing And Random Partial Differential Equation Optimal Control Problems

Optimization methods are widely used in the fields of industrial production,daily life,financial investment,aerography,and so on[1,4,39].Linear complementarity problems and stochastic optimal control problems are and have became hot topics in the optimiza-tion field.They can be derived from practical applications[10,19,33,40].The former is a classical linear programming problem,which can be used to describe economic problems,such as the valuation of the financial derivatives,the actuarial insurance,and the supply chain management.The latter is a standard stochastic programming problem,which is mainly applied to describe the physical problems and material design,such as the steady heat source problems,the optimal flow problems,and the optimal shape design.With the development of science and technology,the theoretical and numerical analysis of the above two problems have been studied rapidly.In this paper,we focus on two specific problems—the American better-of option pricing and the random elliptical PDE constrained optimal control problem.The former is a special linear complementarity problem,while the latter is a typical RPDE optimal control problem.Based on the characteristics of these two problems,we will analyze the implementation challenges,give the corresponding strategy,and design the numeri-cal algorithms.Meanwhile,we will present the convergence analysis,and the numerical simulations are shown to confirm the efficiencies of our algorithms.The first part mainly studies the valuation of the American better-of option.This problem is a parabolic linear complementarity problem on a two-dimensional unbounded domain,which has no closed form solution.There are three main challenges for solving this problem:(1)The domain is unbounded,thus it is difficult to design the numeri-cal scheme directly;(2)The optimal exercise boundary is unknown,which leads to the computational domain is uncertain with unusual boundary conditions;(3)The option price is independent of the unknown optimal exercise boundary,which results in a highly nonlinear problem.Obtain the option price and the optimal exercise boundary simulta-neously is the key issue to the better-of option.In order to solve this problem efficiently,we simplify the original pricing model firstly,and then transform it into a free boundary(optimal exercise boundary)problem on a one-dimensional unbounded domain.Next,we will deal with the above issues step by step.For the first issue,the natural idea is to truncate the unbounded area and establish reasonable boundary conditions.The computational speed and accuracy are highly de-pendent on the truncation length and the boundary condition.We will use the far-field truncation method to deal with this issue,and convert the simplified pricing model into a parabolic problem on a bounded domain.The shortest truncation length X can be obtained by the following theorem.Lemma 0.1 For any given constant ??(0,1),we have(?) where(?)For the second issue,the existing methods includes front-fixing transformation and Landau transformation.The efficiencies of these two transformations are similar.Both of them transform the computational domain into a regular rectangular region.Here,we shall use the former one.The third issue is the key part.After the first two steps,the option price ?(y,?)is an implicit function with respect to the unknown free boundary b(?)=ln ?(T-?).Combining the finite element method and the Newton's iteration method,we shall obtain the approximation solution of the option price and the optimal exercise boundary,simul-taneously.For a fixed time level ?m,let bm=b(?m).Giving the initial guess of bm,we can get the vector ?m=(?0m,?1m,…,?N-1m)T related to the option price by FEM.Then,we use the Newton's method for solving(?) to obtain bm.From the simulation results,the proposed algorithm possesses faster com-putational speed.It can achieve the approximated solution of the option price and the optimal exercise boundary with high accuracy.It is an efficient and robust method to solve the better-of option pricing problem.Furthermore,we present the stability result and non-negativity of the numerical solutions.Theorem 0.2 Assume(?) where C1,C2 are positive constants.If 0<??(?+1)q2-??(1+?),when ?=0 or 0.5,the discretized systems(2.24)-(2.25)are stable,i.e.(?) where {?hm} denote the discretized solution,and ?·? denotes the norm of the space L2(?).Theorem 0.3 If a<0,and(?) are small enough,then the discretized solutions are nonnegative,that is ?jm?0,j=1,2,…,N,m=1,2,…,M.The second part includes the third chapter and fourth chapter.We shall focus on the optimal control problem governed by elliptic PDE with random coefficients.This problem arises from physical problems,such as random steady-state heat sources problem and random diffusion problem.The theoretical and numerical analysis are of significant importance.Compared with the traditional deterministic PDE optimal control problems,the RPDE optimal control problem can be used to describe the actual problem with more flexibility.However,it also leads to more challenges in numerical design.There are three challenges for solving RPDE optimal control problem:(1)Choose a suitable method to approximate the random space;(2)Approximate the random state variable and deterministic control variable reasonably;(3)Propose an efficient algorithm to avoid the curse of dimensionality caused by random space,in order to reduce the computation and storage cost.Chapter 3 is devoted to solving elliptical optimal control problems with random co-efficients based on finite element method(FEM),multi-modes expansion(MME),and alternating direction multiplier method(ADMM).Three numerical methods are proposed for the concerned RPDE optimal control problem improvedly.The advantages and disad-vantages are presented.Finally,an efficient algorithm is established.Now,we present details for resolving these issues.The methods approximating the random space mainly include sample methods,pro-jection methods,and power series expansion methods[18,27,37,104].Compared with other types of methods,the Monte Carlo(MC)method is the standard sample method,wh ich has been developed rapidly.It is easy for parallel and is suitable for solving high-dimensional problems.Here,we adopt MME method and MC method for approximating the random spac e.It is easy to find that the error estimate of MC is given by(?)For the issue(2),we use FEM to discretize the state variables y(x,?i),i=1,2,…,M and the control variable u(x).According to the separable structure of the state variable and control variable,the ADMM is used to solve the discretized optimal problem.Theorem 0.4 Let F and FM,h be the continuous and discretized objective func-tionals.Then(?) where y*represents the desired optimal state,u*represents optimal control,R is the vec-tor valued function formed by finite element basis,and yt and ut denote the t-th iteration solutions by ADMM.It is obvious that Algorithm 3.1 is simple,and reasonable.However,it is not easy for implementation.If the degree of freedom of FEM discretization is N,then Algorithm 3.1 needs to compute M inverse matrices with dimension(N × N),and the storage cost is O(MN2)matrices.The more accuracy is required,the bigger M is needed.This leads to high computational and storage cost,which are insufferable.Resolving the issue(3)is the highlight of Chapter 3.Based on Algorithm 3.1,the MME technique is used to formulate Algorithm 3.2.We expand the random state variable with multi-modes representation as a power series of the perturbation parameter,where the system decouple into recursive elliptical equations with random coefficient.Combining the multi-modes expansion,Monte Carlo technique,FEM discretization,and alternating direction method of multipliers technique,we propose the so-called FEM-MME-MC-ADMM(Algorithm 3.2).In this algorithm,the stiffness matrix of the left hand side is invariant for all samples,which means we need only to compute the LU decomposition of the stiffness matrix once.However,the memory cost is still O(MN2),which is the same as FEM-MC-ADMM(Algorithm 3.1).Finally,in order to reduce the memory consumption sharply,we pre-compute the expectation of certain quantities before the ADMM iteration,so that no random variable is in the inner iteration.The computational cost of this algorithm is the same as Algorithm 3.2,but the memory cost is reduced to O(N2).This algorithm is more efficient and is easy to implement.We denote it by FEM-SMME-MC-ADVM(Algorithm 3.3).We shall also establish the global L2-error estimates for these three algorithms with respect to the objective functional.It is worthwhile to point out that Algorithm 3.1,although is the least efficient one,is a general purpose procedure,while Algorithm 3.2 and Algorithm 3.3 work only when the optimization problem is suitable for multi-modes expansions.Based on the similar analysis of the Algorithm 3.1 and 3.2,the global error estimate of the Algorithm 3.3 can be obtained as follows.Theorem 0.5 Let(y*,u*)be the exact solution,and(yQ,t,ut)represent for the solution of Algorithm 3.3 in t-th iteration,then we can derive(?) Here,F(·,·)and FM,h(·,·)denote the continuous and discretized objective functionals,respectively.In Chapter 4,we focus on RPDE optimal control problem with Box-constraints based on FEM and mirrored descent stochastic approximation(MDSA).The MDSA is a stochas-tic gradient algorithm,which is widely used to deal with stochastic optimal problem.The most notable feature is that it does not require a large number of random samples in each iteration when computing the gradient.Therefore,the computational and storage costs are reduced sharply.The metric function in the MDSA algorithm depends on the distance generating function.Different distance generating functions(such as the distance generating functions related to the L2 norm)will generate different MDSA algorithms.In this paper,the classical L2 norm is used to define the distance generating function,and the MDSA algorithm is proposed to solve RPDE optimal control problem.The main issue is the randomness.We reconsider this problem from the point of view of stochastic optimization.Firstly,we discretize the state variable and control variable with FEM.Then,the original optimal control problem can be transformed into a random optimization problem in finite space.Secondly,it can be rewritten as a random saddle point problem.Finally,the MDSA method is adopted to solve this problem.Convergence of the proposed algorithm is presented to verify its effectiveness.