{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:3298451"},"canonical_url":"https://search.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:3298451","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"Sampling Methods, Spectrahedra and Convex Optimization","abstract":"Παρουσιάζουμε αποτελέσματα σε αλγορίθμους, πολυπλοκότητα και υλοποίηση σχετικά με το πρόβλημα δειγματοληψίας του εσωτερικού και του συνόρου ενός σπεκτραέδρου. Το κύριο εργαλείο μας είναι οι τυχαίοι περίπατοι. Ορίζουμε και αναλύουμε ένα σύνολο βασικών γεωμετρικών πράξεων, οι οποίες εκμεταλλεύονται τις αλγεβρικές ιδιότητες των σπεκτραέδρων και το πολυωνυμικό πρόβλημα ιδιοτιμών, και οδηγούν στην πραγματοποίηση μίας ευρείας συλλογής αποδοτικών τυχαίων περιπάτων. Δείχνουμε τυχαίους περιπάτους, οι οποίοι πειραματικά έχουν ταχύτερο χρόνο σύγκλισης από όσους χρησιμοποιούνταν μέχρι τώρα, είτε σε θεωρία είτε σε εφαρμογές. Αυτοί οι τυχαίοι περίπατοι μας επιτρέπουν να κάνουμε δειγματοληψία από μία μεγάλη οικογένεια κατανομών, οι οποίες προκύπτουν σε διάφορες εφαρμογές. Χρησιμοποιούμε αυτά τα εργαλεία για να ειδικεύσουμε έναν τυχαιοκρατικό αλγόριθμο κυρτής βελτιστοποίησης σε σπεκτράεδρα. Παρέχουμε μία C++ υλοποίηση ανοιχτού κώδικα, διαφόρων τυχαίων περιπάτων (οι οποίοι δουλεύουν και σε περισσότερες από 300 διαστάσεις) και του αλγορίθμου κυρτής βελτιστοποίησης για σπεκτράεδρα.","abstract_html":"Παρουσιάζουμε αποτελέσματα σε αλγορίθμους, πολυπλοκότητα και υλοποίηση σχετικά με το πρόβλημα δειγματοληψίας του εσωτερικού και του συνόρου ενός σπεκτραέδρου. Το κύριο εργαλείο μας είναι οι τυχαίοι περίπατοι. Ορίζουμε και αναλύουμε ένα σύνολο βασικών γεωμετρικών πράξεων, οι οποίες εκμεταλλεύονται τις αλγεβρικές ιδιότητες των σπεκτραέδρων και το πολυωνυμικό πρόβλημα ιδιοτιμών, και οδηγούν στην πραγματοποίηση μίας ευρείας συλλογής αποδοτικών τυχαίων περιπάτων. Δείχνουμε τυχαίους περιπάτους, οι οποίοι πειραματικά έχουν ταχύτερο χρόνο σύγκλισης από όσους χρησιμοποιούνταν μέχρι τώρα, είτε σε θεωρία είτε σε εφαρμογές. Αυτοί οι τυχαίοι περίπατοι μας επιτρέπουν να κάνουμε δειγματοληψία από μία μεγάλη οικογένεια κατανομών, οι οποίες προκύπτουν σε διάφορες εφαρμογές. Χρησιμοποιούμε αυτά τα εργαλεία για να ειδικεύσουμε έναν τυχαιοκρατικό αλγόριθμο κυρτής βελτιστοποίησης σε σπεκτράεδρα. Παρέχουμε μία C++ υλοποίηση ανοιχτού κώδικα, διαφόρων τυχαίων περιπάτων (οι οποίοι δουλεύουν και σε περισσότερες από 300 διαστάσεις) και του αλγορίθμου κυρτής βελτιστοποίησης για σπεκτράεδρα.","abstract_has_math":false,"creators":["Ρεπούσκος Παναγιώτης","Repouskos Panagiotis"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2023,"date_issued":"2023","date_published":"2023","updated_at":"2026-11-19T06:21:45Z","subjects":["Τεχνολογία – Πληροφορική","Technology - Computer science"],"languages":["English"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:3298451"],"render_values":[{"text":"uoadl:3298451","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/3298451","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/3298451","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Alib.uoa.gr%3Auoadl%3A3298451","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Ρεπούσκος Παναγιώτης","Repouskos Panagiotis"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2023"]},{"key":"dc:type","label":"Dc Type","values":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Τεχνολογία – Πληροφορική","Technology - Computer science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:3298451","https://pergamos.lib.uoa.gr/uoa/dl/object/3298451"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Παρουσιάζουμε αποτελέσματα σε αλγορίθμους, πολυπλοκότητα και υλοποίηση σχετικά με το πρόβλημα δειγματοληψίας του εσωτερικού και του συνόρου ενός σπεκτραέδρου. Το κύριο εργαλείο μας είναι οι τυχαίοι περίπατοι. Ορίζουμε και αναλύουμε ένα σύνολο βασικών γεωμετρικών πράξεων, οι οποίες εκμεταλλεύονται τις αλγεβρικές ιδιότητες των σπεκτραέδρων και το πολυωνυμικό πρόβλημα ιδιοτιμών, και οδηγούν στην πραγματοποίηση μίας ευρείας συλλογής αποδοτικών τυχαίων περιπάτων. Δείχνουμε τυχαίους περιπάτους, οι οποίοι πειραματικά έχουν ταχύτερο χρόνο σύγκλισης από όσους χρησιμοποιούνταν μέχρι τώρα, είτε σε θεωρία είτε σε εφαρμογές. Αυτοί οι τυχαίοι περίπατοι μας επιτρέπουν να κάνουμε δειγματοληψία από μία μεγάλη οικογένεια κατανομών, οι οποίες προκύπτουν σε διάφορες εφαρμογές. Χρησιμοποιούμε αυτά τα εργαλεία για να ειδικεύσουμε έναν τυχαιοκρατικό αλγόριθμο κυρτής βελτιστοποίησης σε σπεκτράεδρα. Παρέχουμε μία C++ υλοποίηση ανοιχτού κώδικα, διαφόρων τυχαίων περιπάτων (οι οποίοι δουλεύουν και σε περισσότερες από 300 διαστάσεις) και του αλγορίθμου κυρτής βελτιστοποίησης για σπεκτράεδρα.","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."]},{"key":"dc:title","label":"Title","values":["Sampling Methods, Spectrahedra and Convex Optimization"]}]}],"canonical_facts":{"dc:creator":["Ρεπούσκος Παναγιώτης","Repouskos Panagiotis"],"dc:date":["2023"],"dc:description":["Παρουσιάζουμε αποτελέσματα σε αλγορίθμους, πολυπλοκότητα και υλοποίηση σχετικά με το πρόβλημα δειγματοληψίας του εσωτερικού και του συνόρου ενός σπεκτραέδρου. Το κύριο εργαλείο μας είναι οι τυχαίοι περίπατοι. Ορίζουμε και αναλύουμε ένα σύνολο βασικών γεωμετρικών πράξεων, οι οποίες εκμεταλλεύονται τις αλγεβρικές ιδιότητες των σπεκτραέδρων και το πολυωνυμικό πρόβλημα ιδιοτιμών, και οδηγούν στην πραγματοποίηση μίας ευρείας συλλογής αποδοτικών τυχαίων περιπάτων. Δείχνουμε τυχαίους περιπάτους, οι οποίοι πειραματικά έχουν ταχύτερο χρόνο σύγκλισης από όσους χρησιμοποιούνταν μέχρι τώρα, είτε σε θεωρία είτε σε εφαρμογές. Αυτοί οι τυχαίοι περίπατοι μας επιτρέπουν να κάνουμε δειγματοληψία από μία μεγάλη οικογένεια κατανομών, οι οποίες προκύπτουν σε διάφορες εφαρμογές. Χρησιμοποιούμε αυτά τα εργαλεία για να ειδικεύσουμε έναν τυχαιοκρατικό αλγόριθμο κυρτής βελτιστοποίησης σε σπεκτράεδρα. Παρέχουμε μία C++ υλοποίηση ανοιχτού κώδικα, διαφόρων τυχαίων περιπάτων (οι οποίοι δουλεύουν και σε περισσότερες από 300 διαστάσεις) και του αλγορίθμου κυρτής βελτιστοποίησης για σπεκτράεδρα.","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."],"dc:identifier":["uoadl:3298451","https://pergamos.lib.uoa.gr/uoa/dl/object/3298451"],"dc:language":["English"],"dc:subject":["Τεχνολογία – Πληροφορική","Technology - Computer science"],"dc:title":["Sampling Methods, Spectrahedra and Convex Optimization"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-11-19T06:21:45Z"}