Ταχύτητα Σύγκλισης εναντίον Μνήμης στη Διαμόρφωση Απόψεων

Abstract

Αντικείμενο της κυρτής βελτιστοποίησης είναι η ελαχιστοποίηση μίας κυρτής αντικειμενικής συνάρτησης, δεδομένων κάποιων περιορισμών. Συχνά, η επίλυση τέτοιων προβλημάτων στηρίζεται σε επαναληπτικούς αλγορίθμους, ενώ χρήσιμη είναι και η μελέτη κατανεμημένων παραλλαγών τους, που μπορούν να εφαρμοστούν για την επίλυση προβλημάτων βελτιστοποίησης σε δίκτυα.

Ωστόσο, η επίλυση προβλημάτων σε δίκτυα στην πράξη περιέχει διάφορους περιορισμούς και απαιτεί ιδιαίτερο χειρισμό. Δύο από τους βασικότερους τέτοιους περιορισμούς αποτελούν η ποσότητα μνήμης που είναι διαθέσιμη στους κόμβους ενός δικτύου και ο όγκος της επικοινωνίας που είναι εφικτός μεταξύ αυτών.

Στη διπλωματική αυτή εργασία, επικεντρωνόμαστε σε ένα συγκεκριμένο επαναληπτικό αλγόριθμο βελτιστοποίησης, τη μέθοδο gradient descent, και μελετάμε πειραματικά την επίδραση της περιορισμένης μνήμης και επικοινωνίας σε ένα δίκτυο σε μία παραλλαγή της κατανεμημένης της εκδοχής, μέσω του τρόπου που φυσικά αυτή εφαρμόζεται στο μοντέλο διαμόρφωσης απόψεων των Friedkin και Johnsen.

Για τη διεξαγωγή των πειραμάτων μας, υλοποιήσαμε έναν προσομοιωτή σε Python.