Back to search

National and Kapodistrian University of Athens

Efficient geometric random walks for high-dimensional sampling from convex bodies

Abstract

dc:description

High-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

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/51013

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Chalkis, Apostolos; Χαλκής, Απόστολος. Efficient geometric random walks for high-dimensional sampling from convex bodies. National and Kapodistrian University of Athens, 2021. http://hdl.handle.net/10442/hedi/51013