Μονάδα:
Κατεύθυνση Θεμελιώσεις Πληροφορικής και ΕφαρμογέςΠληροφορική
Ημερομηνία κατάθεσης:
2023-03-14
Συγγραφέας:
Ρεπούσκος Παναγιώτης
Στοιχεία επιβλεπόντων καθηγητών:
Ioannis Emiris, Professor, Department of Informatics & Telecoms, National & Kapodistrian University of Athens
Vassilis Zissimopoulos, Professor, Department of Informatics & Telecoms, National & Kapodistrian University of Athens
Gregory Karagiorgos, Associate Professor, Department of Informatics & Telecoms, University of Peloponnese
Πρωτότυπος Τίτλος:
Sampling Methods, Spectrahedra and Convex Optimization
Γλώσσες εργασίας:
Αγγλικά
Μεταφρασμένος τίτλος:
Μέθοδοι Δειγματοληψίας, Σπεκτράεδρα και Κυρτή Βελτιστοποίηση
Περίληψη:
Παρουσιάζουμε αποτελέσματα σε αλγορίθμους, πολυπλοκότητα και υλοποίηση σχετικά με
το πρόβλημα δειγματοληψίας του εσωτερικού και του συνόρου ενός σπεκτραέδρου.
Το κύριο εργαλείο μας είναι οι τυχαίοι περίπατοι. Ορίζουμε και αναλύουμε ένα σύνολο
βασικών γεωμετρικών πράξεων, οι οποίες εκμεταλλεύονται τις αλγεβρικές ιδιότητες των
σπεκτραέδρων και το πολυωνυμικό πρόβλημα ιδιοτιμών, και οδηγούν στην πραγματοποίηση
μίας ευρείας συλλογής αποδοτικών τυχαίων περιπάτων. Δείχνουμε τυχαίους περιπάτους,
οι οποίοι πειραματικά έχουν ταχύτερο χρόνο σύγκλισης από όσους χρησιμοποιούνταν
μέχρι τώρα, είτε σε θεωρία είτε σε εφαρμογές. Αυτοί οι τυχαίοι περίπατοι μας επιτρέπουν
να κάνουμε δειγματοληψία από μία μεγάλη οικογένεια κατανομών, οι οποίες προκύπτουν
σε διάφορες εφαρμογές.
Χρησιμοποιούμε αυτά τα εργαλεία για να ειδικεύσουμε έναν τυχαιοκρατικό αλγόριθμο κυρτής
βελτιστοποίησης σε σπεκτράεδρα. Παρέχουμε μία C++ υλοποίηση ανοιχτού κώδικα, διαφόρων
τυχαίων περιπάτων (οι οποίοι δουλεύουν και σε περισσότερες από 300 διαστάσεις) και του
αλγορίθμου κυρτής βελτιστοποίησης για σπεκτράεδρα.
Κύρια θεματική κατηγορία:
Τεχνολογία – Πληροφορική
Λέξεις-κλειδιά:
δειγματοληψία, κυρτή βελτιστοποίηση, σπεκτράεδρα, γεωμετρικοί τυχαίοι περίπατοι
Αρ. σελίδων ευρετηρίου:
4
Αρ. βιβλιογραφικών αναφορών:
42
