Option pricing with a direct adaptive sparse grid approach

We present an adaptive sparse grid algorithm for the solution of the Black–Scholes equation for option pricing, using the finite element method. Sparse grids enable us to deal with higher-dimensional problems better than full grids. In contrast to common approaches that are based on the combination technique, which combines different solutions on anisotropic coarse full grids, the direct sparse grid approach allows for local adaptive refinement. When dealing with non-smooth payoff functions, this reduces the computational effort significantly. In this paper, we introduce the spatially adaptive discretization of the Black–Scholes equation with sparse grids and describe the algorithmic structure of the numerical solver. We present several strategies for adaptive refinement, evaluate them for different dimensionalities, and demonstrate their performance showing numerical results.     

Spatially adaptive sparse grids for high-dimensional data-driven problems

Sparse grids allow one to employ grid-based discretization methods in data-driven problems. We present an extension of the classical sparse grid approach that allows us to tackle high-dimensional problems by spatially adaptive refinement, modified ansatz functions, and efficient regularization techniques. The competitiveness of this method is shown for typical benchmark problems with up to 166 dimensions for classification in data mining, pointing out properties of sparse grids in this context. To gain insight into the adaptive refinement and to examine the scope for further improvements, the approximation of non-smooth indicator functions with adaptive sparse grids has been studied as a model problem. As an example for an improved adaptive grid refinement, we present results for an edge-detection strategy.     

A new local reduced basis discontinuous Galerkin approach for heterogeneous multiscale problems

Inspired by the reduced basis approach and modern numerical multiscale methods, we present a new framework for an efficient treatment of heterogeneous multiscale problems. The new approach is based on the idea of considering heterogeneous multiscale problems as parametrized partial differential equations where the parameters are smooth functions. We then construct, in an offline phase, a suitable localized reduced basis that is used in an online phase to efficiently compute approximations of the multiscale problem by means of a discontinuous Galerkin method on a coarse grid. We present our approach for elliptic multiscale problems and discuss an a posteriori error estimate that can be used in the construction process of the localized reduced basis. Numerical experiments are given to demonstrate the efficiency of the new approach.     

A Sparse Grid Stochastic Collocation Discontinuous Galerkin Method for Constrained Optimal Control Problem Governed by Random Convection Dominated Diffusion Equations

A sparse grid stochastic collocation method combined with discontinuous Galerkin method is developed for solving convection dominated diffusion optimal control problem with random coefficients. By the optimal control theory, an optimality system is obtained for the problem, which consists of a state equation, a co-state equation and an inequality. Based on finite dimensional noise assumption of random field, the random coefficients are assumed to have finite term expansions depending on a finite number of mutually independent random variables in the probability space. An approximation scheme is established by using a discontinuous Galerkin method for the physical space and a sparse grid stochastic collocation method based on the Smolyak construction for the probability space, which leads to the solution of uncoupled deterministic problems. A priori error estimates are derived for the state, co-state and control variables. Numerical experiments are presented to illustrate the theoretical results.     

The generalized residual cutting method and its convergence characteristics

Iterative methods and especially Krylov subspace methods (KSM) are a very useful numerical tool in solving for large and sparse linear systems problems arising in science and engineering modeling. More recently, the nested loop KSM have been proposed that improve the convergence of the traditional KSM. In this article, we review the residual cutting (RC) and the generalized residual cutting (GRC) that are nested loop methods for large and sparse linear systems problems. We also show that GRC is a KSM that is equivalent to Orthomin with a variable preconditioning. We use the modified Gram–Schmidt method to derive a stable GRC algorithm. We show that GRC presents a general framework for constructing a class of “hybrid” (nested) KSM based on inner loop method selection. We conduct numerical experiments using nonsymmetric indefinite matrices from a widely used library of sparse matrices that validate the efficiency and the robustness of the proposed methods.     

Adaptive Markov Chain Monte Carlo for Bayesian Variable Selection

We describe adaptive Markov chain Monte Carlo (MCMC) methods for sampling posterior distributions arising from Bayesian variable selection problems. Point-mass mixture priors are commonly used in Bayesian variable selection problems in regression. However, for generalized linear and nonlinear models where the conditional densities cannot be obtained directly, the resulting mixture posterior may be difficult to sample using standard MCMC methods due to multimodality. We introduce an adaptive MCMC scheme that automatically tunes the parameters of a family of mixture proposal distributions during simulation. The resulting chain adapts to sample efficiently from multimodal target distributions. For variable selection problems point-mass components are included in the mixture, and the associated weights adapt to approximate marginal posterior variable inclusion probabilities, while the remaining components approximate the posterior over nonzero values. The resulting sampler transitions efficiently between models, performing parameter estimation and variable selection simultaneously. Ergodicity and convergence are guaranteed by limiting the adaptation based on recent theoretical results. The algorithm is demonstrated on a logistic regression model, a sparse kernel regression, and a random field model from statistical biophysics; in each case the adaptive algorithm dramatically outperforms traditional MH algorithms. Supplementary materials for this article are available online.     

Dimension-wise integration of high-dimensional functions with applications to finance

We present a new general class of methods for the computation of high-dimensional integrals. The quadrature schemes result by truncation and discretization of the anchored-ANOVA decomposition. They are designed to exploit low effective dimensions and include sparse grid methods as special case. To derive bounds for the resulting modelling and discretization errors, we introduce effective dimensions for the anchored-ANOVA decomposition. We show that the new methods can be applied in locally adaptive and dimension-adaptive ways and demonstrate their efficiency by numerical experiments with high-dimensional integrals from finance.     

自适应稀疏伪谱逼近新方法

自适应稀疏伪谱逼近法是广义混沌多项式类方法的最新进展,相对于其它方法具有计算精度高、速度快的优点.但它仍存在如下缺点：1）终止判据对逼近误差的估计精度偏低;2）只适用于单输出问题.本文提出了适用于多输出问题且具有更高逼近精度的自适应稀疏伪谱逼近新方法.本文首先提出了新型终止判据及基于此新型终止判据的自适应稀疏伪谱逼近新方法,并以命题的形式证明了新型终止判据相比于现有终止判据具有更高的估计精度,从而使基于此的逼近函数精度更接近于预期精度;进而,本文基于指标集的统一策略和新型终止判据,提出了适用于多输出问题的自适应稀疏伪谱逼近新方法,该方法因能充分利用各输出变量的抽样结果,具有比将单输出方法直接推广到多输出问题更高的计算效率.多个算例验证了本文所提出新方法的有效性和正确性.     

Local Walsh-average-based estimation and variable selection for single-index models

We propose a robust estimation procedure based on local Walsh-average regression(LWR) for single-index models. Our novel method provides a root-n consistent estimate of the single-index parameter under some mild regularity conditions; the estimate of the unknown link function converges at the usual rate for the nonparametric estimation of a univariate covariate. We theoretically demonstrate that the new estimators show significant efficiency gain across a wide spectrum of non-normal error distributions and have almost no loss of efficiency for the normal error. Even in the worst case, the asymptotic relative efficiency(ARE) has a lower bound compared with the least squares(LS) estimates; the lower bounds of the AREs are 0.864 and 0.8896 for the single-index parameter and nonparametric function, respectively. Moreover, the ARE of the proposed LWR-based approach versus the ARE of the LS-based method has an expression that is closely related to the ARE of the signed-rank Wilcoxon test as compared with the t-test. In addition, to obtain a sparse estimate of the single-index parameter, we develop a variable selection procedure by combining the estimation method with smoothly clipped absolute deviation penalty; this procedure is shown to possess the oracle property. We also propose a Bayes information criterion(BIC)-type criterion for selecting the tuning parameter and further prove its ability to consistently identify the true model. We conduct some Monte Carlo simulations and a real data analysis to illustrate the finite sample performance of the proposed methods.     

Wavelet-based adaptive grids for multirate partial differential-algebraic equations

The mathematical model of electric circuits yields systems of differential-algebraic equations (DAEs). In radio frequency applications, a multivariate model of oscillatory signals transforms the DAEs into a system of multirate partial differential-algebraic equations (MPDAEs). Considering quasiperiodic signals, an approach based on a method of characteristics yields efficient numerical schemes for the MPDAEs in time domain. If additionally digital signal structures occur, an adaptive grid is required to achieve the efficiency of the technique. We present a strategy applying a wavelet transformation to construct a mesh for resolving steep gradients in respective signals. Consequently, we employ finite difference methods to determine an approximative solution of characteristic systems in according grid points. Numerical simulations demonstrate the performance of the adaptive grid generation, where radio frequency signals with digital structures are resolved.     

Adaptive multi-element polynomial chaos with discrete measure: Algorithms and application to SPDEs

We develop a multi-element probabilistic collocation method (ME-PCM) for arbitrary discrete probability measures with finite moments and apply it to solve partial differential equations with random parameters. The method is based on numerical construction of orthogonal polynomial bases in terms of a discrete probability measure. To this end, we compare the accuracy and efficiency of five different constructions. We develop an adaptive procedure for decomposition of the parametric space using the local variance criterion. We then couple the ME-PCM with sparse grids to study the Korteweg–de Vries (KdV) equation subject to random excitation, where the random parameters are associated with either a discrete or a continuous probability measure. Numerical experiments demonstrate that the proposed algorithms lead to high accuracy and efficiency for hybrid (discrete–continuous) random inputs.     

A posteriori error estimation and adaptive mesh-refinement techniques

We analyse three different a posteriori error estimators for elliptic partial differential equations. They are based on the evaluation of local residuals with respect to the strong form of the differential equation, on the solution of local problems with Neumann boundary conditions, and on the solution of local problems with Dirichlet boundary conditions. We prove that all three are equivalent and yield global upper and local lower bounds for the true error. Thus adaptive mesh-refinement techniques based on these estimators are capable to detect local singularities of the solution and to appropriately refine the grid near these singularities. Some numerical examples prove the efficiency of the error estimators and the mesh-refinement techniques.     

Solving Examination Timetabling Problems through Adaption of Heuristic Orderings

Heuristic ordering based methods, very similar to those used for graph colouring problems, have long been applied successfully to the examination timetabling problem. Despite the success of these methods on real life problems, even with limited computing resources, the approach has the fundamental flaw that it is only as effective as the heuristic that is used. We present a method that adapts to suit a particular problem instance “on the fly.” This method provides an alternative to existing forms of ‘backtracking,’ which are often required to cope with the possible unsuitability of a heuristic. We present a range of experiments on benchmark problems to test and evaluate the approach. In comparison to other published approaches to solving this problem, the adaptive method is more general, significantly quicker and easier to implement and produces results that are at least comparable (if not better) than the current state of the art. We also demonstrate the level of generality of this approach by starting it with the inverse of a known good heuristic, a null ordering and random orderings, showing that the adaptive method can transform a bad heuristic ordering into a good one.     

An adaptive estimation of MAVE

Minimum average variance estimation (MAVE, Xia et al. (2002) [29]) is an effective dimension reduction method. It requires no strong probabilistic assumptions on the predictors, and can consistently estimate the central mean subspace. It is applicable to a wide range of models, including time series. However, the least squares criterion used in MAVE will lose its efficiency when the error is not normally distributed. In this article, we propose an adaptive MAVE which can be adaptive to different error distributions. We show that the proposed estimate has the same convergence rate as the original MAVE. An EM algorithm is proposed to implement the new adaptive MAVE. Using both simulation studies and a real data analysis, we demonstrate the superior finite sample performance of the proposed approach over the existing least squares based MAVE when the error distribution is non-normal and the comparable performance when the error is normal.     

A new error estimation approach based on fuzzy logic system for H-R adaptive boundary element method

Conventional adaptive boundary element method cannot be universally applied to solve many more problems than the subject it discussed, and different error estimation formulas need to be designed for varied problems. This paper put forward a new error analysis method based on the fuzzy logic system, which is able to make error estimation effectively using human expert experience, and solve the two classical elasticity problems in conjunction with the H-R adaptive boundary element method. Numerical examples have illustrated the effectiveness, superiority and potential of a fuzzy logic approach in the adaptive boundary element method.     

Adaptive wavelet methods for elliptic partial differential equations with random operators

We apply adaptive wavelet methods to boundary value problems with random coefficients, discretized by wavelets in the spatial domain and tensorized polynomials in the parameter domain. Greedy algorithms control the approximate application of the fully discretized random operator, and the construction of sparse approximations to this operator. We suggest a power iteration for estimating errors induced by sparse approximations of linear operators.     

Parallel interior-point solver for structured quadratic programs: Application to financial planning problems

Many practical large-scale optimization problems are not only sparse, but also display some form of block-structure such as primal or dual block angular structure. Often these structures are nested: each block of the coarse top level structure is block-structured itself. Problems with these characteristics appear frequently in stochastic programming but also in other areas such as telecommunication network modelling. We present a linear algebra library tailored for problems with such structure that is used inside an interior point solver for convex quadratic programming problems. Due to its object-oriented design it can be used to exploit virtually any nested block structure arising in practical problems, eliminating the need for highly specialised linear algebra modules needing to be written for every type of problem separately. Through a careful implementation we achieve almost automatic parallelisation of the linear algebra. The efficiency of the approach is illustrated on several problems arising in the financial planning, namely in the asset and liability management. The problems are modelled as multistage decision processes and by nature lead to nested block-structured problems. By taking the variance of the random variables into account the problems become non-separable quadratic programs. A reformulation of the problem is proposed which reduces density of matrices involved and by these means significantly simplifies its solution by an interior point method. The object-oriented parallel solver achieves high efficiency by careful exploitation of the block sparsity of these problems. As a result a problem with over 50 million decision variables is solved in just over 2 hours on a parallel computer with 16 processors. The approach is by nature scalable and the parallel implementation achieves nearly perfect speed-ups on a range of problems. Supported by the Engineering and Physical Sciences Research Council of UK, EPSRC grant GR/R99683/01     

An interior point algorithm with inexact step computation in function space for state constrained optimal control

We consider an interior point method in function space for PDE constrained optimal control problems with state constraints. Our emphasis is on the construction and analysis of an algorithm that integrates a Newton path-following method with adaptive grid refinement. This is done in the framework of inexact Newton methods in function space, where the discretization error of each Newton step is controlled by adaptive grid refinement in the innermost loop. This allows to perform most of the required Newton steps on coarse grids, such that the overall computational time is dominated by the last few steps. For this purpose we propose an a-posteriori error estimator for a problem suited norm.     

Deep Composition of Tensor-Trains Using Squared Inverse Rosenblatt Transports

Characterising intractable high-dimensional random variables is one of the fundamental challenges in stochastic computation. The recent surge of transport maps offers a mathematical foundation and new insights for tackling this challenge by coupling intractable random variables with tractable reference random variables. This paper generalises the functional tensor-train approximation of the inverse Rosenblatt transport recently developed by Dolgov et al. (Stat Comput 30:603–625, 2020) to a wide class of high-dimensional non-negative functions, such as unnormalised probability density functions. First, we extend the inverse Rosenblatt transform to enable the transport to general reference measures other than the uniform measure. We develop an efficient procedure to compute this transport from a squared tensor-train decomposition which preserves the monotonicity. More crucially, we integrate the proposed order-preserving functional tensor-train transport into a nested variable transformation framework inspired by the layered structure of deep neural networks. The resulting deep inverse Rosenblatt transport significantly expands the capability of tensor approximations and transport maps to random variables with complicated nonlinear interactions and concentrated density functions. We demonstrate the efficiency of the proposed approach on a range of applications in statistical learning and uncertainty quantification, including parameter estimation for dynamical systems and inverse problems constrained by partial differential equations.

     

An adaptive time stepping method with efficient error control for second-order evolution problems

This work is concerned with time stepping fnite element methods for abstract second order evolution problems.We derive optimal order a posteriori error estimates and a posteriori nodal superconvergence error estimates using the energy approach and the duality argument.With the help of the a posteriori error estimator developed in this work,we will further propose an adaptive time stepping strategy.A number of numerical experiments are performed to illustrate the reliability and efciency of the a posteriori error estimates and to assess the efectiveness of the proposed adaptive time stepping method.