National and Kapodistrian University of Athens
Efficient geometric random walks for high-dimensional sampling from convex bodies
Abstract
dc:descriptionHigh-dimensional sampling is a fundamental problem with many applications in science and engineering. Several problems are computationally hard for general dimension, and therefore, a great effort has been devoted to randomized approximation algorithms based on sampling that addresses those problems in polynomial time. In this thesis, we present algorithmic, complexity, and implementation results on the problem of sampling points from a log-concave distribution restricted to a convex polytope –the feasible region of a linear program– or a spectrahedron –the feasible region of a semidefinite program (SDP). We develop practical Multiphase Monte Carlo algorithms to address the problem of approximating the volume of a convex body, sampling from the flux space of metabolic networks in Systems Biology, and estimating the optimal solution of an SDP. The corresponding implementations scale up to thousands or hundred dimensions, depending on the problem. We use those methods and develop new geometric and mathematical tools to address three important problems in finance: (i) portfolio scoring, (ii) portfolio optimization, and (iii) crises detection in stock markets. For problem (i) we introduce an original computational framework to model asset allocation strategies, which is of independent interest for finance and its applications. For problem (ii) we develop new mathematical and computational tools for modeling the distribution of portfolio returns across portfolios. We use these tools to define novel portfolio performance measures that directly lead to new optimal portfolios. For problem (iii) we use a geometric representation of a stock market to compute the copula between portfolios' return and volatility. The analysis of copulae leads to a new indicator that successfully detects all the past financial crises.
Degree
thesis:*- Grantor dc:publisher
- National and Kapodistrian University of Athens
- Year dc:date
- 2021
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Chalkis, Apostolos
- Χαλκής, Απόστολος
Subjects
dc:subject × 10- Αποδοτικοί γεωμετρικοί τυχαίοι περίπατοι για τη δειγματοληψία από υψηλών διαστάσεων κυρτά σώματα
- Απόστολος Χαλκής
- Efficient geometric random walks for high-dimensional sampling from convex bodies
- Apostolos Chalkis
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Φυσικές Επιστήμες
- Επιστήμη ηλεκτρονικών υπολογιστών, θεωρία και μέθοδοι
- Computer and Information Sciences
- Natural Sciences
- Computer science, theory and methods
Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/51013