Hochdimensionale numerische Integration: Komplexität, Konstruktion von Integrationspunkten und Anwendungen in der Finanzmathematik
Final Report Abstract
Die wichtigsten wissenschaftlichen Fortschritte im Gesamtprojekt wurden in der unendlich-dimensionalen Integration sowie der Erzeugung von Niedrigdiskrepanzmengen und der Berechnung von Diskrepanzmaßen erzielt. Bei der unendlich-dimensionalen Integration, die enge Bezüge zur Simulation stochastischer Differentialgleichungen aufweist, wurden neue deterministische und randomisierte Multilevelalgorithmen und multivariate Dekompositionsmethoden (die auch als “Changing Dimension Algorithms” bezeichnet werden) entwickelt und theoretisch untersucht. Die Algorithmen nutzen als Bausteine Quasi-Monte-Carlo-Algorithmen, die auf sogenannten Lattice Rules und Polynomial Lattice Rules basieren. Die Integrationspunkte lassen sich effizient durch schnelle Component-by-Component-Konstruktionen erzeugen. Für verschiedene Räume von Integranden und verschiedene Kostenmodelle für die Funktionsauswertung von Funktionen mit unendlich vielen Variablen wurden bzgl. des deterministischen und des randomisierten Fehlerkriteriums untere Schranken für beliebige Algorithmen und obere Schranken für die neu entwickelten Multilevelalgorithmen und multivariaten Dekompositionsmethoden bewiesen. Diese Schranken sind in den meisten Fällen scharf und zeigen, dass die neuen Algorithmen die bestmöglichen Konvergenzraten erzielen. Diese optimalen Schranken verbessern die vorher bekannten Resultate substantiell. Diese Ergebnisse wurden z.T. in Zusammenarbeit mit J. Baldeaux (UTS Sydney) und J. Dick (UNSW Sydney) fertiggestellt. Eine weitere Arbeit mit S. Mayer (Uni. Bonn) und K. Ritter (TU Kaiserslautern) untersucht die verschiedenen in der Literatur vorkommenden unendlich-dimensionalen Integrationsprobleme, setzt diese in Beziehung und grenzt sie ab und schließt ferner in der Literatur auftretende Beweislücken. Im Rahmen einer von mir betreuten Masterarbeit im Studiengang “Mathematical Finance” der University of Oxford wurden neue Resultate für Monte-Carlo- und Quasi-Monte-Carlo-Hybridfolgen bewiesen und solche Folgen als Bausteine von Multilevelalgorithmen verwendet. Diese neuen Multilevelalgorithmen wurden implementiert und in der Finanzderivatbewertung numerisch getestet. In einer weiteren Arbeit des Projekts wurde der Zusammenhang zwischen gewichteten L2-Diskrepanzmaßen und der multivariaten und unendlich-dimensionalen Integration auf gewichteten Hilbert-Räumen mit reproduzierendem Kern untersucht. Die Arbeit löst insbesondere das “Open Problem 35” des neuen dreibändigen Werks von E. Novak und H. Woźniakowski über “Tractability of Multivariate Problems”. Mit B. Doerr und M. Wahlström (MPI f. Informatik, Saarbrücken) wurde ein neuer Algorithmus zur Konstruktion kleiner Punktmengen im d-dimensionalen Einheitswürfel mit niedriger Diskrepanz entwickelt und getestet. Er erweißt sich insbesondere dann als kompetativ mit den besten bekannten klassischen Konstruktionen, wenn die Anzahl der Punkte klein im Vergleich zur Dimension d ist. Mit C. Doerr (vormals Winzen) und M. Wahlström (MPI f. Informatik, Saarbrücken) wurde ein neuer Algorithmus zur randomisierten Approximation der Sterndiskrepanz beliebiger Punktemengen entworfen und implementiert. Er zeigt sich in numerischen Tests allen anderen bekannten Methoden überlegen und dieser Qualitätsunterschied wird besonders in hohen Dimensionen deutlich. Neben diesen Resultaten wurde in der Projektlaufzeit eine Arbeit mit H. Woźniakowski abgeschlossen, in der der Begriff der “Quasi-Polynomial Tractability” für hochdimensionale Approximationsprobleme eingeführt, motiviert und studiert wird.
Publications
- Algorithmic construction of low-discrepancy point sets via dependent randomized rounding. Journal of Complexity 26 (2010), 490–507
B. Doerr, M. Gnewuch, M. Wahlström
- Quasi-polynomial tractability. Journal of Complexity 27 (2011) 312-330
M. Gnewuch, H. Woźniakowski
- A new randomized algorithm to approximate the star discrepancy based on threshold accepting. SIAM Journal of Numerical Analysis 50 (2012), 781-807
M. Gnewuch, M. Wahlström, C. Winzen
(See online at https://doi.org/10.1137/110833865) - Infinite-dimensional integration on weighted Hilbert spaces. Mathematics of Computation 81 (2012), 2175-2205
M. Gnewuch
- Weighted geometric discrepancies and numerical integration on reproducing kernel Hilbert spaces. Journal of Complexity 28 (2012), 2-17
M. Gnewuch
(See online at https://doi.org/10.1016/j.jco.2011.02.003) - Optimal randomized multilevel algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition. SIAM Journal of Numerical Analysis
J. Baldeaux, M. Gnewuch
