Efficient formulations for pricing under attraction demand models

We propose a modeling and optimization framework to cast a broad range of fundamental multi-product pricing problems as tractable convex optimization problems. We consider a retailer offering an assortment of differentiated substitutable products to a population of customers that are price-sensitive. The retailer selects prices to maximize profits, subject to constraints on sales arising from inventory and capacity availability, market share goals, bounds on allowable prices and other considerations. Consumers’ response to price changes is represented by attraction demand models, which subsume the well known multinomial logit (MNL) and multiplicative competitive interaction demand models. Our approach transforms seemingly non-convex pricing problems (both in the objective function and constraints) into convex optimization problems that can be solved efficiently with commercial software. We establish a condition which ensures that the resulting problem is convex, prove that it can be solved in polynomial time under MNL demand, and show computationally that our new formulations reduce the solution time from days to seconds. We also propose an approximation of demand models with multiple overlapping customer segments, and show that it falls within the class of demand models we are able to solve. Such mixed demand models are highly desirable in practice, but yield a pricing problem which appears computationally challenging to solve exactly.     

Numerical valuation of options under Kou's model

Numerical methods are developed for pricing European and American options under Kou's jump-diffusion model which assumes the price of the underlying asset to behave like a geometrical Brownian motion with a drift and jumps whose size is log-double-exponentially distributed. The price of a European option is given by a partial integro-differential equation (PIDE) while American options lead to a linear complementarity problem (LCP) with the same operator. Spatial differential operators are discretized using finite differences on nonuniform grids and time stepping is performed using the implicit Rannacher scheme. For the evaluation of the integral term easy to implement recursion formulas are derived which have optimal computational cost. When pricing European options the resulting dense linear systems are solved using a stationary iteration. Also for pricing American options similar iterations can be employed. A numerical experiment demonstrates that the described method is very efficient as accurate option prices can be computed in a few milliseconds on a PC. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Carr's randomization for American options in regime-switching models

In the paper, we solve the pricing problem for American put-like options in Markov-modulated Lévy models. The early exercise boundaries and prices are calculated using a generalization of Carr's randomization for regime-switching models. An efficient iteration pricing procedure is developed. The computational time is of order m², where m is the number of states, and of order m, if the parallel computations are allowed. The payoffs, riskless rates and class of Lévy processes may depend on a state. Special cases are stochastic volatility models and models with stochastic interest rate; both must be modelled as finite-state Markov chains. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

An inverse iteration method using multigrid for quantum chemistry

We present a method to compute the lowest eigenpairs of a generalized eigenvalue problem resulting from the discretization of a stationary Schrödinger equation by a fourth order finite difference scheme of Numerov type. We propose to use an inverse iteration method combined with a Rayleigh-Ritz procedure to correct several eigenvectors at the same time. The linear systems in the inverse iteration scheme are regularized by projections on lower dimensional spaces and approximately solved by a multigrid algorithm.We apply the method to the electronic structure calculation in quantum chemistry.     

SAA-regularized methods for multiproduct price optimization under the pure characteristics demand model

Utility-based choice models are often used to determine a consumer’s purchase decision among a list of available products; to provide an estimate of product demands; and, when data on purchase decisions or market shares are available, to infer consumers’ preferences over observed product characteristics. These models also serve as a building block in modeling firms’ pricing and assortment optimization problems. We consider a firm’s multiproduct pricing problem, in which product demands are determined by a pure characteristics model. A sample average approximation (SAA) method is used to approximate the expected market share of products and the firm profit. We propose an SAA-regularized method for the multiproduct price optimization problem. We present convergence analysis and numerical examples to show the efficiency and the effectiveness of the proposed method.     

Spectral Method for the Black-Scholes Model of American Options Valuation

In this paper, we devote ourselves to the research of numerical methods for American option pricing problems under the Black-Scholes model. The optimal exercise boundary which satisfies a nonlinear Volterra integral equation is resolved by a high-order collocation method based on graded meshes. For the other spatial domain boundary, an artificial boundary condition is applied to the pricing problem for the effective truncation of the semi-infinite domain. Then, the front-fixing and stretching transformations are employed to change the truncated problem in an irregular domain into a one-dimensional parabolic problem in [−1,1]. The Chebyshev spectral method coupled with fourth-order Runge-Kutta method is proposed for the resulting parabolic problem related to the options. The stability of the semi-discrete numerical method is established for the parabolic problem transformed from the original model. Numerical experiments are conducted to verify the performance of the proposed methods and compare them with some existing methods.     

A new algorithm for total variation based image denoising

We propose a new algorithm for the total variation based on image denoising problem. The split Bregman method is used to convert an unconstrained minimization denoising problem to a linear system in the outer iteration. An algebraic multi-grid method is applied to solve the linear system in the inner iteration. Furthermore, Krylov subspace acceleration is adopted to improve convergence in the outer iteration. Numerical experiments demonstrate that this algorithm is efficient even for images with large signal-to-noise ratio.     

Multi-phase dynamic constraint aggregation for set partitioning type problems

Dynamic constraint aggregation is an iterative method that was recently introduced to speed up the linear relaxation solution process of set partitioning type problems. This speed up is mostly due to the use, at each iteration, of an aggregated problem defined by aggregating disjoint subsets of constraints from the set partitioning model. This aggregation is updated when needed to ensure the exactness of the overall approach. In this paper, we propose a new version of this method, called the multi-phase dynamic constraint aggregation method, which essentially adds to the original method a partial pricing strategy that involves multiple phases. This strategy helps keeping the size of the aggregated problem as small as possible, yielding a faster average computation time per iteration and fewer iterations. We also establish theoretical results that provide some insights explaining the success of the proposed method. Tests on the linear relaxation of simultaneous bus and driver scheduling problems involving up to 2,000 set partitioning constraints show that the partial pricing strategy speeds up the original method by an average factor of 4.5.     

A computationally efficient state-space partitioning approach to pricing high-dimensional American options via dimension reduction

This paper studies the problem of pricing high-dimensional American options. We propose a method based on the state-space partitioning algorithm developed by Jin et al. (2007) and a dimension-reduction approach introduced by Li and Wu (2006). By applying the approach in the present paper, the computational efficiency of pricing high-dimensional American options is significantly improved, compared to the extant approaches in the literature, without sacrificing the estimation precision. Various numerical examples are provided to illustrate the accuracy and efficiency of the proposed method. Pseudcode for an implementation of the proposed approach is also included.     

Robust numerical methods for contingent claims under jump diffusion processes

An implicit method is developed for the numerical solution ofoption pricing models where it is assumed that the underlyingprocess is a jump diffusion. This method can be applied to avariety of contingent claim valuations, including American options,various kinds of exotic options, and models with uncertain volatilityor transaction costs. Proofs of timestepping stability and convergenceof a fixed-point iteration scheme are presented. For typicalmodel parameters, it is shown the error is reduced by two ordersof magnitude at each iteration. The correlation integral iscomputed using a fast Fourier transform method. Numerical testsof convergence for a variety of options are presented.