Power Penalty Method for a Linear Complementarity Problem Arising from American Option Valuation

In this paper, we present a power penalty function approach to the linear complementarity problem arising from pricing American options. The problem is first reformulated as a variational inequality problem; the resulting variational inequality problem is then transformed into a nonlinear parabolic partial differential equation (PDE) by adding a power penalty term. It is shown that the solution to the penalized equation converges to that of the variational inequality problem with an arbitrary order. This arbitrary-order convergence rate allows us to achieve the required accuracy of the solution with a small penalty parameter. A numerical scheme for solving the penalized nonlinear PDE is also proposed. Numerical results are given to illustrate the theoretical findings and to show the effectiveness and usefulness of the method. This work was partially supported by a research grant from the University of Western Australia and the Research Grant Council of Hong Kong, Grants PolyU BQ475 and PolyU BQ493.     

A power penalty approach to a mixed quasilinear elliptic complementarity problem

In this paper, a power penalty approximation method is proposed for solving a mixed quasilinear elliptic complementarity problem. The mixed complementarity problem is first reformulated as a double obstacle quasilinear elliptic variational inequality problem. A nonlinear elliptic partial differential equation is then defined to approximate the resulting variational inequality by using a power penalty approach. The existence and uniqueness of the solution to the partial differential penalty equation are proved. It is shown that, under some mild assumptions, the sequence of solutions to the penalty equations converges to the unique solution of the variational inequality problem as the penalty parameter tends to infinity. The error estimates of the convergence of this penalty approach are also derived. At last, numerical experimental results are presented to show that the power penalty approximation method is efficient and robust.

     

Convergence analysis of power penalty method for American bond option pricing

This paper is concerned with the convergence analysis of power penalty method to pricing American options on discount bond, where the single factor Cox–Ingrosll–Ross model is adopted for the short interest rate. The valuation of American bond option is usually formulated as a partial differential complementarity problem. We first develop a power penalty method to solve this partial differential complementarity problem, which produces a nonlinear degenerated parabolic PDE. Within the framework of variational inequalities, the solvability and convergence properties of this penalty approach are explored in a proper infinite dimensional space. Moreover, a sharp rate of convergence of the power penalty method is obtained. Finally, we show that the power penalty approach is monotonically convergent with the penalty parameter.     

A penalty approximation method for a semilinear parabolic double obstacle problem

In this work, we present a novel power penalty method for the approximation of a global solution to a double obstacle complementarity problem involving a semilinear parabolic differential operator and a bounded feasible solution set. We first rewrite the double obstacle complementarity problem as a double obstacle variational inequality problem. Then, we construct a semilinear parabolic partial differential equation (penalized equation) for approximating the variational inequality problem. We prove that the solution to the penalized equation converges to that of the variational inequality problem and obtain a convergence rate that is corresponding to the power used in the formulation of the penalized equation. Numerical results are presented to demonstrate the theoretical findings.     

A penalty‐FEM for navier‐stokes type variational inequality with nonlinear damping term

In this article, we consider a penalty finite element (FE) method for incompressible Navier‐Stokes type variational inequality with nonlinear damping term. First, we establish penalty variational formulation and prove the well‐posedness and convergence of this problem. Then we show the penalty FE scheme and derive some error estimates. Finally, we give some numerical results to verify the theoretical rate of convergence. © 2017 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 33: 918–940, 2017     

An interior penalty method for a finite-dimensional linear complementarity problem in financial engineering

In this work we study an interior penalty method for a finite-dimensional large-scale linear complementarity problem (LCP) arising often from the discretization of stochastic optimal problems in financial engineering. In this approach, we approximate the LCP by a nonlinear algebraic equation containing a penalty term linked to the logarithmic barrier function for constrained optimization problems. We show that the penalty equation has a solution and establish a convergence theory for the approximate solutions. A smooth Newton method is proposed for solving the penalty equation and properties of the Jacobian matrix in the Newton method have been investigated. Numerical experimental results using three non-trivial test examples are presented to demonstrate the rates of convergence, efficiency and usefulness of the method for solving practical problems.     

A power penalty method for linear complementarity problems

We propose a power penalty approach to a linear complementarity problem (LCP) in Rⁿ based on approximating the LCP by a nonlinear equation. We prove that the solution to this equation converges to that of the LCP at an exponential rate when the penalty parameter tends to infinity.     

Convergence analysis of a monotonic penalty method for American option pricing

This paper is devoted to study the convergence analysis of a monotonic penalty method for pricing American options. A monotonic penalty method is first proposed to solve the complementarity problem arising from the valuation of American options, which produces a nonlinear degenerated parabolic PDE with Black-Scholes operator. Based on the variational theory, the solvability and convergence properties of this penalty approach are established in a proper infinite dimensional space. Moreover, the convergence rate of the combination of two power penalty functions is obtained.     

A non-interior-point smoothing method for variational inequality problem

In this paper, we focus on the variational inequality problem. Based on the Fischer-Burmeister function with smoothing parameters, the variational inequality problem can be reformulated as a system of parameterized smooth equations, a non-interior-point smoothing method is presented for solving the problem. The proposed algorithm not only has no restriction on the initial point, but also has global convergence and local quadratic convergence, moreover, the local quadratic convergence is established without a strict complementarity condition. Preliminary numerical results show that the algorithm is promising.     

Global Method for Monotone Variational Inequality Problems with Inequality Constraints

We consider optimization methods for monotone variational inequality problems with nonlinear inequality constraints. First, we study the mixed complementarity problem based on the original problem. Then, a merit function for the mixed complementarity problem is proposed, and some desirable properties of the merit function are obtained. Through the merit function, the original variational inequality problem is reformulated as simple bounded minimization. Under certain assumptions, we show that any stationary point of the optimization problem is a solution of the problem considered. Finally, we propose a descent method for the variational inequality problem and prove its global convergence.     

一类线性约束变分不等式问题的幂罚函数法

本文研究了一类线性约束变分不等式(Ⅵ)的幂罚函数法求解问题.利用Ⅵ的KKT条件,将Ⅵ转化为等价的混合互补问题和一个新的Ⅵ问题,并在一定条件下分析了解的存在性和唯一性.利用度理论证明了幂罚方程组解的存在性与唯一性.由以上结果最终证明了幂罚函数法的收敛性,即幂罚方程组的解收敛于Ⅵ问题的解.     

A matrix-splitting method for symmetric affine second-order cone complementarity problems

The affine second-order cone complementarity problem (SOCCP) is a wide class of problems that contains the linear complementarity problem (LCP) as a special case. The purpose of this paper is to propose an iterative method for the symmetric affine SOCCP that is based on the idea of matrix splitting. Matrix-splitting methods have originally been developed for the solution of the system of linear equations and have subsequently been extended to the LCP and the affine variational inequality problem. In this paper, we first give conditions under which the matrix-splitting method converges to a solution of the affine SOCCP. We then present, as a particular realization of the matrix-splitting method, the block successive overrelaxation (SOR) method for the affine SOCCP involving a positive definite matrix, and propose an efficient method for solving subproblems. Finally, we report some numerical results with the proposed algorithm, where promising results are obtained especially for problems with sparse matrices.     

A Gauss–Newton Approach for Solving Constrained Optimization Problems Using Differentiable Exact Penalties

We propose a Gauss–Newton-type method for nonlinear constrained optimization using the exact penalty introduced recently by André and Silva for variational inequalities. We extend their penalty function to both equality and inequality constraints using a weak regularity assumption, and as a result, we obtain a continuously differentiable exact penalty function and a new reformulation of the KKT conditions as a system of equations. Such reformulation allows the use of a semismooth Newton method, so that local superlinear convergence rate can be proved under an assumption weaker than the usual strong second-order sufficient condition and without requiring strict complementarity. Besides, we note that the exact penalty function can be used to globalize the method. We conclude with some numerical experiments using the collection of test problems CUTE.     

A penalty method for a mixed nonlinear complementarity problem

We propose a power penalty method for a mixed nonlinear complementarity problem (MNCP) and show that the solution to the penalty equation converges to that of the MNCP exponentially as the penalty parameter approaches infinity, provided that the mapping involved in the MNCP is both continuous and ξ-monotone. Furthermore, a convergence theorem is established when the monotonicity assumption on the mapping is removed. To demonstrate the usefulness and the convergence rates of this method, we design a non-trivial test MNCP problem arising in shape-preserving bi-harmonic interpolation and apply our method to this test problem. The numerical results confirm our theoretical findings.     

A numerical scheme for the impulse control formulation for pricing variable annuities with a guaranteed minimum withdrawal benefit (GMWB)

In this paper, we outline an impulse stochastic control formulation for pricing variable annuities with a guaranteed minimum withdrawal benefit (GMWB) assuming the policyholder is allowed to withdraw funds continuously. We develop a numerical scheme for solving the Hamilton–Jacobi–Bellman (HJB) variational inequality corresponding to the impulse control problem. We prove the convergence of our scheme to the viscosity solution of the continuous withdrawal problem, provided a strong comparison result holds. The scheme can be easily generalized to price discrete withdrawal contracts. Numerical experiments are conducted, which show a region where the optimal control appears to be non-unique.     

A Self-Adaptive Projection and Contraction Method for Linear Complementarity Problems

In this paper we develop a self-adaptive projection and contraction method for the linear complementarity problem (LCP). This method improves the practical performance of the modified projection and contraction method in [10] by adopting a self-adaptive technique. The global convergence of our new method is proved under mild assumptions. Our numerical tests clearly demonstrate the necessity and effectiveness of our proposed method.     

An algorithm based on a sequence of linear complementarity problems applied to a walrasian equilibrium model: An example

The Walrasian equilibrium problem is cast as a complementarity problem, and its solution is computed by solving a sequence of linear complementarity problems (SLCP). Earlier numerical experiments have demonstrated the computational efficiency of this approach. So far, however, there exist few relevant theoretical results that characterize the performance of this algorithm. In the context of a simple example of a Walrasian equilibrium model, we study the iterates of the SLCP algorithm. We show that a particular LCP of this process may have no, one or more complementary solutions. Other LCPs may have both homogeneous and complementary solutions. These features complicate the proof of convergence for the general case. For this particular example, however, we are able to show that Lemke's algorithm computes a solution to an LCP if one exists,and that the iterative process converges globally.     

On the Smoothing of the Square-Root Exact Penalty Function for Inequality Constrained Optimization

In this paper we propose two methods for smoothing a nonsmooth square-root exact penalty function for inequality constrained optimization. Error estimations are obtained among the optimal objective function values of the smoothed penalty problem, of the nonsmooth penalty problem and of the original optimization problem. We develop an algorithm for solving the optimization problem based on the smoothed penalty function and prove the convergence of the algorithm. The efficiency of the smoothed penalty function is illustrated with some numerical examples, which show that the algorithm seems efficient.     

Smoothing approach to Nash equilibrium formulations for a class of equilibrium problems with shared complementarity constraints

The equilibrium problem with equilibrium constraints (EPEC) can be looked on as a generalization of Nash equilibrium problem (NEP) and the mathematical program with equilibrium constraints (MPEC) whose constraints contain a parametric variational inequality or complementarity system. In this paper, we particularly consider a special class of EPECs where a common parametric P-matrix linear complementarity system is contained in all players?? strategy sets. After reformulating the EPEC as an equivalent nonsmooth NEP, we use a smoothing method to construct a sequence of smoothed NEPs that approximate the original problem. We consider two solution concepts, global Nash equilibrium and stationary Nash equilibrium, and establish some results about the convergence of approximate Nash equilibria. Moreover we show some illustrative numerical examples.     

Convergence of the Neumann parallel scheme of the domain decomposition method for problems of frictionless contact between several elastic bodies

Based on the variational formulation and penalty method, we have considered the Neumann parallel scheme of the domain decomposition method for the solution of problems of one-sided contact between three-dimensional elastic bodies. We have shown the existence and uniqueness of a solution of the variational problem with penalty and convergence in the penalty parameter. The convergence of this scheme has been proved, and the optimal value of iteration parameter has been determined.