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

Abstract

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.

Η δειγματοληψία υψηλών διαστάσεων είναι ένα θεμελιώδες πρόβλημα με πολλές εφαρμογές στην επιστήμη των υπολογιστών, την εφαρμοσμένη στατιστική και τη μηχανική. Πολλά προβλήματα είναι υπολογιστικά δύσκολα για γενική διάσταση, και ως εκ τούτου, έχει καταβληθεί μεγάλη προσπάθεια στην ανάπτυξη προσεγγιστικών τυχαιοκρατικών αλγορίθμων που βασίζονται σε δειγματοληψία και επιλύουν το εκάστοτε προβλήματα σε πολυωνυμικό χρόνο. Σε αυτή τη διατριβή, παρουσιάζουμε αποτελέσματα αλγοριθμικής πολυπλοκότητας και υλοποίησης για το πρόβλημα της δειγματοληψίας από μια λογαριθμική κοίλη κατανομή όταν ο δειγματικός χώρος είναι ένα κυρτό πολύτοπο -την εφικτή περιοχή ενός γραμμικού προγράμματος- ή ένα σπεκτράεδρο -την εφικτή περιοχή ενός ημικαθορισμένου προγράμματος (ΗΜΠ). Αναπτύσσουμε πρακτικούς πολυβηματικούς αλγόριθμους Monte Carlo για να επιλύσουμε το πρόβλημα της προσέγγισης του όγκου ενός κυρτού σώματος, τη δειγματοληψία από τον χώρο καταστάσεων ενός μεταβολικού δικτύου στη Βιολογία Συστημάτων, και την εκτίμηση της βέλτιστης λύσης ενός ΗΜΠ. Οι αντίστοιχες υλοποιήσεις πραγματοποιούν υπολογισμούς σε χιλιάδες ή εκατοντάδες διαστάσεις, ανάλογα με το πρόβλημα. Επιπλέον, χρησιμοποιούμε αυτές τις μεθόδους και αναπτύσσουμε νέα γεωμετρικά και μαθηματικά εργαλεία για την επίλυση τριών σημαντικών προβλημάτων της χρηματοοικονομικής επιστήμης: (i) την αξιολόγηση χαρτοφυλακίων, (ii) τη βελτιστοποίηση της απόδοσης χαρτοφυλακίων και (iii) την ανίχνευση κρίσεων στα χρηματιστήρια. Για το πρόβλημα (i) εισάγουμε ένα πρωτότυπο υπολογιστικό και μαθηματικό πλαίσιο για τη μοντελοποίηση στρατηγικών επένδυσης, το οποίο έχει ανεξάρτητο ενδιαφέρον για τη χρηματοοικονομική επιστήμη και τις εφαρμογές της. Για το πρόβλημα (ii) αναπτύσσουμε νέα μαθηματικά και υπολογιστικά εργαλεία για τη μοντελοποίηση της κατανομής των αποδόσεων χαρτοφυλακίων. Χρησιμοποιούμε αυτά τα εργαλεία για να ορίσουμε νέα μέτρα (συναρτήσεις) απόδοσης χαρτοφυλακίου που οδηγούν άμεσα σε νέα βέλτιστα χαρτοφυλάκια. Για το πρόβλημα (iii) χρησιμοποιούμε μια γεωμετρική αναπαράσταση μιας χρηματιστηριακής αγοράς για να υπολογίσουμε την από κοινού κατανομή μεταξύ της απόδοσης και του ρίσκου στο χώρο των χαρτοφυλακίων όταν οι περιθώριες κατανομές ακολουθούν την ομοιόμορφη κατανομή. Η ανάλυση αυτών των κατανομών οδηγεί σε έναν νέο δείκτη που εντοπίζει με επιτυχία όλες τις προηγούμενες ιστορικά οικονομικές κρίσεις.