Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben

2014 | Buch

Solving Stochastic Dynamic Programs by Convex Optimization and Simulation Kapitel lesen Erstes Kapitel lesen

Extraction of Quantifiable Information from Complex Systems

herausgegeben von: Stephan Dahlke, Wolfgang Dahmen, Michael Griebel, Wolfgang Hackbusch, Klaus Ritter, Reinhold Schneider, Christoph Schwab, Harry Yserentant

Verlag: Springer International Publishing

Buchreihe : Lecture Notes in Computational Science and Engineering

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

In April 2007, the Deutsche Forschungsgemeinschaft (DFG) approved the Priority Program 1324 “Mathematical Methods for Extracting Quantifiable Information from Complex Systems.” This volume presents a comprehensive overview of the most important results obtained over the course of the program. Mathematical models of complex systems provide the foundation for further technological developments in science, engineering and computational finance. Motivated by the trend toward steadily increasing computer power, ever more realistic models have been developed in recent years. These models have also become increasingly complex, and their numerical treatment poses serious challenges. Recent developments in mathematics suggest that, in the long run, much more powerful numerical solution strategies could be derived if the interconnections between the different fields of research were systematically exploited at a conceptual level. Accordingly, a deeper understanding of the mathematical foundations as well as the development of new and efficient numerical algorithms were among the main goals of this Priority Program. The treatment of high-dimensional systems is clearly one of the most challenging tasks in applied mathematics today. Since the problem of high-dimensionality appears in many fields of application, the above-mentioned synergy and cross-fertilization effects were expected to make a great impact. To be truly successful, the following issues had to be kept in mind: theoretical research and practical applications had to be developed hand in hand; moreover, it has proven necessary to combine different fields of mathematics, such as numerical analysis and computational stochastics. To keep the whole program sufficiently focused, we concentrated on specific but related fields of application that share common characteristics and as such, they allowed us to use closely related approaches.

Inhaltsverzeichnis

Frontmatter
Chapter 1. Solving Stochastic Dynamic Programs by Convex Optimization and Simulation
Abstract
In this chapter we review some recent progress on Monte Carlo methods for a class of stochastic dynamic programming equations, which accommodates optimal stopping problems and time discretization schemes for backward stochastic differential equations with convex generators. We first provide a primal maximization problem and a dual minimization problem, based on which confidence intervals for the value of the dynamic program can be constructed by Monte Carlo simulation. For the computation of the lower confidence bounds we apply martingale basis functions within a least-squares Monte Carlo implementation. For the upper confidence bounds we suggest a multilevel simulation within a nested Monte Carlo approach and, alternatively, a generic sieve optimization approach with a variance penalty term.
Denis Belomestny, Christian Bender, Fabian Dickmann, Nikolaus Schweizer
Chapter 2. Efficient Resolution of Anisotropic Structures
Abstract
We highlight some results obtained in the DFG-SPP project “Adaptive Anisotropic Discretization Concepts”. We focus on new developments concerning the sparse representation of possibly high-dimensional functions exhibiting strong anisotropic features and low regularity in isotropic Sobolev or Besov scales. Specifically, we focus on the solution of transport equations which exhibit propagation of singularities where, additionally, high-dimensionality enters when the convection field, and hence the solutions, depend on parameters varying over some compact set. Important constituents of our approach are directionally adaptive discretization concepts motivated by compactly supported shearlet systems, and well-conditioned stable variational formulations that support trial spaces with anisotropic refinements with arbitrary directionalities. We prove that they provide tight error-residual relations which are used to contrive rigorously founded adaptive refinement schemes which converge in L 2. Moreover, in the context of parameter dependent problems we discuss two approaches serving different purposes and working under different regularity assumptions. For “frequent query problems”, making essential use of the novel well-conditioned variational formulations, a new Reduced Basis Method is outlined which exhibits a certain rate-optimal performance for indefinite, unsymmetric or singularly perturbed problems. For the radiative transfer problem with scattering a sparse tensor method is presented which mitigates or even overcomes the curse of dimensionality under suitable (so far still isotropic) regularity assumptions. Numerical examples for both methods illustrate the theoretical findings.
Wolfgang Dahmen, Chunyan Huang, Gitta Kutyniok, Wang-Q Lim, Christoph Schwab, Gerrit Welper
Chapter 3. Regularity of the Parameter-to-State Map of a Parabolic Partial Differential Equation
Abstract
In this paper, we present results that have been obtained in the DFG-SPP project “Adaptive Wavelet Frame Methods for Operator Equations: Sparse Grids, Vector-Valued Spaces and Applications to Nonlinear Inverse Problems”. This project has been concerned with (nonlinear) elliptic and parabolic operator equations on nontrivial domains as well as with related inverse parameter identification problems. In this paper we study analytic properties of the underlying parameter-to-state map, which is motivated by a parabolic model for the embryonal development of drosophila melanogaster.
Rudolf Ressel, Patrick Dülk, Stephan Dahlke, Kamil S. Kazimierski, Peter Maass
Chapter 4. Piecewise Tensor Product Wavelet Bases by Extensions and Approximation Rates
Abstract
In this chapter, we present some of the major results that have been achieved in the context of the DFG-SPP project “Adaptive Wavelet Frame Methods for Operator Equations: Sparse Grids, Vector-Valued Spaces and Applications to Nonlinear Inverse Problems”. This project has been concerned with (nonlinear) elliptic and parabolic operator equations on nontrivial domains as well as with related inverse parameter identification problems. One crucial step has been the design of an efficient forward solver. We employed a spatially adaptive wavelet Rothe scheme. The resulting elliptic subproblems have been solved by adaptive wavelet Galerkin schemes based on generalized tensor wavelets that realize dimension-independent approximation rates. In this chapter, we present the construction of these new tensor bases and discuss some numerical experiments.
Nabi G. Chegini, Stephan Dahlke, Ulrich Friedrich, Rob Stevenson
Chapter 5. Adaptive Wavelet Methods for SPDEs
Abstract
We review a series of results that have been obtained in the context of the DFG-SPP 1324 project “Adaptive wavelet methods for SPDEs”. This project has been concerned with the construction and analysis of adaptive wavelet methods for second order parabolic stochastic partial differential equations on bounded, possibly nonsmooth domains \(\mathcal{O}\subset \mathbb{R}^{d}\). A detailed regularity analysis for the solution process u in the scale of Besov spaces \(B_{\tau,\tau }^{s}(\mathcal{O})\), 1∕τ = s∕d + 1∕p, α > 0, p ≥ 2, is presented. The regularity in this scale is known to determine the order of convergence that can be achieved by adaptive wavelet algorithms and other nonlinear approximation schemes. As it turns out, in general, for solutions of SPDEs this regularity exceeds the \(L_{p}(\mathcal{O})\)-Sobolev regularity, which determines the order of convergence for uniform approximation schemes. We also study nonlinear wavelet approximation of elliptic boundary value problems on \(\mathcal{O}\) with random right-hand side. Such problems appear naturally when applying Rothe’s method to the parabolic stochastic equation. A general stochastic wavelet model for the right-hand side is introduced and its Besov regularity as well as linear and nonlinear approximation is studied. The results are matched by computational experiments.
Petru A. Cioica, Stephan Dahlke, Nicolas Döhring, Stefan Kinzel, Felix Lindner, Thorsten Raasch, Klaus Ritter, René L. Schilling
Chapter 6. Constructive Quantization and Multilevel Algorithms for Quadrature of Stochastic Differential Equations
Abstract
In this article we summarise the progress made in the project Constructive Quantization and Multilevel Algorithms for Quadrature of Stochastic Differential Equations. Research was conducted along the following three lines. First we focus on deterministic quadrature formulas to approximate expectations with respect to marginal distributions of SDEs. Here we provide a complexity analysis for deterministic algorithms in a worst case setting with respect to classes of SDEs that are defined in terms of smoothness constraints on the coefficients, and we present an algorithm that is based on weak Itô-Talyor steps and performs almost asymptotically optimal. Next, we are concerned with computing expectations of quantities that depend discontinuously on the SDE at the terminal time. We present an efficient method for quadrature in the Heston model based on multilevel schemes and a Malliavin calculus-based payoff smoothing. Finally, we consider expected values of quantities that depend on the whole trajectory of a Lévy-driven SDE. We establish error estimates and central limit theorems for a multilevel Monte Carlo algorithm that achieves error rates of order \(N^{-\frac{1} {2} +o(1)}\) as the runtime N of the algorithm tends to infinity.
Martin Altmayer, Steffen Dereich, Sangmeng Li, Thomas Müller-Gronbach, Andreas Neuenkirch, Klaus Ritter, Larisa Yaroslavtseva
Chapter 7. Bayesian Inverse Problems and Kalman Filters
Abstract
We provide a brief introduction to Bayesian inverse problems and Bayesian estimators emphasizing their similarities and differences to the classical regularized least-squares approach to inverse problems. We then analyze Kalman filtering techniques for nonlinear systems, specifically the well-known Ensemble Kalman Filter (EnKF) and the recently proposed Polynomial Chaos Expansion Kalman Filter (PCE-KF), in this Bayesian framework and show how they relate to the solution of Bayesian inverse problems.
Oliver G. Ernst, Björn Sprungk, Hans-Jörg Starkloff
Chapter 8. Robustness in Stochastic Filtering and Maximum Likelihood Estimation for SDEs
Abstract
We consider complex stochastic systems in continuous time and space where the objects of interest are modelled via stochastic differential equations, in general high dimensional and with nonlinear coefficients. The extraction of quantifiable information from such systems has a long history and many aspects. We shall focus here on the perhaps most classical problems in this context: the filtering problem for nonlinear diffusions and the problem of parameter estimation, also for nonlinear and multidimensional diffusions. More specifically, we return to the question of robustness, first raised in the filtering community in the mid-1970s: will it be true that the conditional expectation of some observable of the signal process, given an observation (sample) path, depends continuously on the latter? Sadly, the answer here is no, as simple counterexamples show. Clearly, this is an unhappy state of affairs for users who effectively face an ill-posed situation: close observations may lead to vastly different predictions. A similar question can be asked in the context of (maximum likelihood) parameter estimation for diffusions. Some (apparently novel) counter examples show that, here again, the answer is no. Our contribution (Crisan et al., Ann Appl Probab 23(5):2139–2160, 2013); Diehl et al., A Levy-area between Brownian motion and rough paths with applications to robust non-linear filtering and RPDEs (2013, arXiv:1301.3799; Diehl et al., Pathwise stability of likelihood estimators for diffusions via rough paths (2013, arXiv:1311.1061) changed to yes, in other words: well-posedness is restored, provided one is willing or able to regard observations as rough paths in the sense of T. Lyons.
Joscha Diehl, Peter K. Friz, Hilmar Mai, Harald Oberhauser, Sebastian Riedel, Wilhelm Stannat
Chapter 9. Adaptive Sparse Grids in Reinforcement Learning
Abstract
We propose a model-based online reinforcement learning approach for continuous domains with deterministic transitions using a spatially adaptive sparse grid in the planning stage. The model learning employs Gaussian processes regression and allows a low sample complexity. The adaptive sparse grid is introduced to allow the representation of the value function in the planning stage in higher dimensional state spaces. This work gives numerical evidence that adaptive sparse grids are applicable in the case of reinforcement learning.
Jochen Garcke, Irene Klompmaker
Chapter 10. A Review on Adaptive Low-Rank Approximation Techniques in the Hierarchical Tensor Format
Abstract
The hierarchical tensor format allows for the low-parametric representation of tensors even in high dimensions d. On the one hand, this format provides a robust framework for approximate arithmetic operations with tensors based on rank truncations, which can be exploited in iterative algorithms. On the other hand, it can be used for the direct approximation of high-dimensional data stemming, e.g., from the discretisation of multivariate functions. In this review, we discuss several strategies for an adaptive approximation of tensors in the hierarchical format by black box type techniques, including problems of tensor reconstruction and tensor completion.
Jonas Ballani, Lars Grasedyck, Melanie Kluge
Chapter 11. A Bond Order Dissection ANOVA Approach for Efficient Electronic Structure Calculations
Abstract
In this article, we present a new decomposition approach for the efficient approximate calculation of the electronic structure problem for molecules. It is based on a dimension-wise decomposition of the space the underlying Schrödinger equation lives in, i.e. \(\mathbb{R}^{3(M+N)}\), where M is the number of nuclei and N is the number of electrons. This decomposition is similar to the ANOVA-approach (analysis of variance) which is well-known in statistics. It represents the energy as a finite sum of contributions which depend on the positions of single nuclei, of pairs of nuclei, of triples of nuclei, and so on. Under the assumption of locality of electronic wave functions, the higher order terms in this expansion decay rapidly and may therefore be omitted. Furthermore, additional terms are eliminated according to the bonding structure of the molecule. This way, only the calculation of the electronic structure of local parts, i.e. small subsystems of the overall system, is necessary to approximate the total ground state energy. To determine the required subsystems, we employ molecular graph theory combined with molecular bonding knowledge. In principle, the local electronic subproblems may be approximately evaluated with whatever technique is appropriate, e.g. HF, CC, CI, or DFT. From these local energies, the total energy of the overall system is then approximately put together in a telescoping sum like fashion. Thus, if the size of the local subproblems is independent of the size of the overall molecular system, linear scaling is directly obtained. We discuss the details of our new approach and apply it to both, various small test systems and interferon alpha as an example of a large biomolecule.
Michael Griebel, Jan Hamaekers, Frederik Heber
Chapter 12. Tensor Spaces and Hierarchical Tensor Representations
Abstract
In the present report we provide a brief introduction into recently developed hierarchical tensor representations. The new formats extend the well-known Tucker format into a hierarchical framework, by combining its favourable characteristics with low-order scaling properties. We demonstrate the basic concept of subspace approximation and higher order SVD (HOSVD), and how to extend this in a hierarchical way. We highlight that the present tensor representations are constituting smooth manifolds, and give a perspective how these properties can be used to develop numerical solvers for tensor equations and tensor optimisation problems.
Wolfgang Hackbusch, Reinhold Schneider
Chapter 13. Nonlinear Eigenproblems in Data Analysis: Balanced Graph Cuts and the RatioDCA-Prox
Abstract
It has been recently shown that a large class of balanced graph cuts allows for an exact relaxation into a nonlinear eigenproblem. We review briefly some of these results and propose a family of algorithms to compute nonlinear eigenvectors which encompasses previous work as special cases. We provide a detailed analysis of the properties and the convergence behavior of these algorithms and then discuss their application in the area of balanced graph cuts.
Leonardo Jost, Simon Setzer, Matthias Hein
Chapter 14. Adaptive Approximation Algorithms for Sparse Data Representation
Abstract
We survey our latest results on the development and analysis of adaptive approximation algorithms for sparse data representation, where special emphasis is placed on the Easy Path Wavelet Transform (EPWT), nonlinear dimensionality reduction (NDR) methods, and their application to signal separation and detection.
Mijail Guillemard, Dennis Heinen, Armin Iske, Sara Krause-Solberg, Gerlind Plonka
Chapter 15. Error Bound for Hybrid Models of Two-Scaled Stochastic Reaction Systems
Abstract
Biochemical reaction systems are often modeled by a Markov jump process in order to account for the discreteness of the populations and the stochastic nature of their evolution. The associated time-dependent probability distribution is the solution of the Chemical Master Equation (CME), but solving the CME numerically is a considerable challenge due to the high dimension of the state space. In many applications, however, species with rather small population numbers interact with abundant species, and only the former group exhibits stochastic behavior. This has motivated the derivation of hybrid models where a low-dimensional CME is coupled to a set of ordinary differential equations representing the abundant species. Using such a hybrid model decreases the number of unknowns significantly but – in addition to the numerical error – causes a modeling error. We investigate the accuracy of the MRCE (= model reduction based on conditional expectations) approach with respect to a particular scaling of the reaction system and prove that the error is proportional to the scaling parameter.
Tobias Jahnke, Vikram Sunkara
Chapter 16. Valuation of Structured Financial Products by Adaptive Multiwavelet Methods in High Dimensions
Abstract
We introduce a new numerical approach to value structured financial products. These financial products typically feature a large number of underlying assets and require the explicit modeling of the dependence structure of these assets. We follow the approach of Kraft and Steffensen (Rev Finance 11:209–252, 2006), who explicitly describe the possible value combinations of the assets via a Markov chain with a portfolio state space. As the number of states increases exponentially with the number of assets in the portfolio, this model so far has been – despite its theoretical appeal – not computationally tractable. The price of a structured financial product in this model is determined by a coupled system of parabolic PDEs, describing the value of the portfolio for each state of the Markov chain depending on the time and macroeconomic state variables. A typical portfolio of n assets leads to a system of N = 2 n coupled parabolic partial differential equations. It is shown that this high number of PDEs can be solved by combining an adaptive multiwavelet method with the Hierarchical Tucker Format. We present numerical results for n = 128.
Rüdiger Kiesel, Andreas Rupp, Karsten Urban
Chapter 17. Computational Methods for the Fourier Analysis of Sparse High-Dimensional Functions
Abstract
A straightforward discretisation of high-dimensional problems often leads to a curse of dimensions and thus the use of sparsity has become a popular tool. Efficient algorithms like the fast Fourier transform (FFT) have to be customised to these thinner discretisations and we focus on two major topics regarding the Fourier analysis of high-dimensional functions: We present stable and effective algorithms for the fast evaluation and reconstruction of multivariate trigonometric polynomials with frequencies supported on an index set \(\mathcal{I}\subset \mathbb{Z}^{d}\).
Lutz Kämmerer, Stefan Kunis, Ines Melzer, Daniel Potts, Toni Volkmer
Chapter 18. Sparsity and Compressed Sensing in Inverse Problems
Abstract
This chapter is concerned with two important topics in the context of sparse recovery in inverse and ill-posed problems. In first part we elaborate conditions for exact recovery. In particular, we describe how both ℓ 1-minimization and matching pursuit methods can be used to regularize ill-posed problems and moreover, state conditions which guarantee exact recovery of the support in the sparse case. The focus of the second part is on the incomplete data scenario. We discuss extensions of compressed sensing for specific infinite dimensional ill-posed measurement regimes. We are able to establish recovery error estimates when adequately relating the isometry constant of the sensing operator, the ill-posedness of the underlying model operator and the regularization parameter. Finally, we very briefly sketch how projected steepest descent iterations can be applied to retrieve the sparse solution.
Evelyn Herrholz, Dirk Lorenz, Gerd Teschke, Dennis Trede
Chapter 19. Low-Rank Dynamics
Abstract
This note reviews differential equations on manifolds of matrices or tensors of low rank. They serve to approximate, in a low-rank format, large time-dependent matrices and tensors that are either given explicitly via their increments or are unknown solutions of differential equations. Furthermore, low-rank differential equations are used in novel algorithms for eigenvalue optimisation, for instance in robust-stability problems.
Christian Lubich
Chapter 20. Computation of Expectations by Markov Chain Monte Carlo Methods
Abstract
Markov chain Monte Carlo (MCMC) methods are a very versatile and widely used tool to compute integrals and expectations. In this short survey we focus on error bounds, rules for choosing the burn in, high dimensional problems and tractability versus curse of dimension.
Erich Novak, Daniel Rudolf
Chapter 21. Regularity, Complexity, and Approximability of Electronic Wavefunctions
Abstract
The electronic Schrödinger equation describes the motion of N electrons under Coulomb interaction forces in a field of clamped nuclei. The solutions of this equation, the electronic wavefunctions, depend on 3N variables, three spatial dimensions for each electron. Approximating the solutions is thus inordinately challenging, and it is conventionally believed that a reduction to simplified models, such as those of the Hartree-Fock method or density functional theory, is the only tenable approach. The situation is, however, more complicated: the regularity of the solutions, which increases with the number of electrons, the decay behavior of their mixed derivatives, and the antisymmetry enforced by the Pauli principle contribute properties that allow these functions to be approximated with an order of complexity which comes arbitrarily close to that of a system of two or even only one electron.
Harry Yserentant
Backmatter
Metadaten
Titel
Extraction of Quantifiable Information from Complex Systems
herausgegeben von
Stephan Dahlke
Wolfgang Dahmen
Michael Griebel
Wolfgang Hackbusch
Klaus Ritter
Reinhold Schneider
Christoph Schwab
Harry Yserentant
Copyright-Jahr
2014
Electronic ISBN
978-3-319-08159-5
Print ISBN
978-3-319-08158-8
DOI
https://doi.org/10.1007/978-3-319-08159-5

Premium Partner

    Bildnachweise