δείτε την πρωτότυπη σελίδα τεκμηρίου στον ιστότοπο του αποθετηρίου του φορέα για περισσότερες πληροφορίες και για να δείτε όλα τα ψηφιακά αρχεία του τεκμηρίου*
Sampling Methods, Spectrahedra and Convex Optimization
Παρουσιάζουμε αποτελέσματα σε αλγορίθμους, πολυπλοκότητα και υλοποίηση σχετικά με
το πρόβλημα δειγματοληψίας του εσωτερικού και του συνόρου ενός σπεκτραέδρου.
Το κύριο εργαλείο μας είναι οι τυχαίοι περίπατοι. Ορίζουμε και αναλύουμε ένα σύνολο
βασικών γεωμετρικών πράξεων, οι οποίες εκμεταλλεύονται τις αλγεβρικές ιδιότητες των
σπεκτραέδρων και το πολυωνυμικό πρόβλημα ιδιοτιμών, και οδηγούν στην πραγματοποίηση
μίας ευρείας συλλογής αποδοτικών τυχαίων περιπάτων. Δείχνουμε τυχαίους περιπάτους,
οι οποίοι πειραματικά έχουν ταχύτερο χρόνο σύγκλισης από όσους χρησιμοποιούνταν
μέχρι τώρα, είτε σε θεωρία είτε σε εφαρμογές. Αυτοί οι τυχαίοι περίπατοι μας επιτρέπουν
να κάνουμε δειγματοληψία από μία μεγάλη οικογένεια κατανομών, οι οποίες προκύπτουν
σε διάφορες εφαρμογές.
Χρησιμοποιούμε αυτά τα εργαλεία για να ειδικεύσουμε έναν τυχαιοκρατικό αλγόριθμο κυρτής
βελτιστοποίησης σε σπεκτράεδρα. Παρέχουμε μία C++ υλοποίηση ανοιχτού κώδικα, διαφόρων
τυχαίων περιπάτων (οι οποίοι δουλεύουν και σε περισσότερες από 300 διαστάσεις) και του
αλγορίθμου κυρτής βελτιστοποίησης για σπεκτράεδρα.
(EL)
We present algorithmic, complexity, and implementation results on the problem of sampling
points in the interior and the boundary of a spectrahedron, that is the feasible region of a
semidefinite program.
Our main tool is random walks. We define and analyze a set of primitive geometric
operations that exploits the algebraic properties of spectrahedra and the polynomial eigenvalue
problem, and leads to the realization of a broad collection of efficient random walks. We
demonstrate random walks that experimentally show faster mixing time than the ones
used previously for sampling from spectrahedra in theory or applications, for example Hit
and Run. Consecutively, the variety of random walks allows us to sample from general
probability distributions, for example the family of log-concave distributions which arise
frequently in numerous applications.
We apply our tools to specialize a randomized convex optimization algorithm for spectrahedra,
that is to solve semidefinite programs. We provide a C++ open source implementation
of several random walks that scale efficiently to a high number of dimensions (in our
experiments we tested till 300 dimensions) and of the convex optimization algorithm tailored
for spectrahedra.
(EN)
*Η εύρυθμη και αδιάλειπτη λειτουργία των διαδικτυακών διευθύνσεων των συλλογών (ψηφιακό αρχείο, καρτέλα τεκμηρίου στο αποθετήριο) είναι αποκλειστική ευθύνη των αντίστοιχων Φορέων περιεχομένου.
Βοηθείστε μας να κάνουμε καλύτερο το OpenArchives.gr.
Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
