RESTARTING POLICIES FOR ACCELERATED GRADIENT METHODS

Η παρούσα διπλωματική εργασία έχει ως σκοπό να παράσχει μία αυτοτελή περιγραφή της μεθόδου βελτιστοποίησης με επιτάχυνση και της heavy-ball μεθόδου με επανεκκίνηση. Στο πρώτο μέρος της εισάγονται οι μέθοδοι πρώτης τάξης για βελτιστοποίηση λείων κυρτών συναρτήσεων, η ιδιότητα καθόδου και οι ιδιότητες τύπου Fejer της καθόδου κλίσεως, και το χάσμα πολυπλοκότητας-μαντείου που οδηγεί στην επιτάχυνση. Στο δεύτερο μέρος παρουσιάζεται η οπτική γωνία των δυναμικών συστημάτων: η κάθοδος κλίσεως εμφανίζεται ως μία διακριτοποίηση κατά Euler της ροής καθόδου, ενώ οι αλγόριθμοι heavy-ball και τύπου Nesterov αντιστοιχούν σε ένα αποσβεστικό σύστημα δεύτερης τάξης. Στο τρίτο μέρος μελετώνται πολιτικές επανεκκίνησης σε μεθόδους επιτάχυνσης. Οι σταθερές επανεκκινήσεις επιτυγχάνουν έναν γραμμικό ρυθμό σύγκλισης στην περίπτωση της ισχυρής κυρτότητας όταν η περίοδος επανεκκίνησης επιλεγεί κατάλληλα για τον αριθμό συνθήκης της συνάρτησης, ενώ οι προσαρμοστικοί κανόνες επανεκκίνησης προσπαθούν να ανιχνεύσουν την έναρξη των ταλαντώσεων χωρίς προηγούμενη γνώση της παραμέτρου της ισχυρής κυρτότητας. Την ραχοκοκαλιά της παρούσας διπλωματικής αποτελούν: η ερμηνεία ως διαφορική εξίσωση της επιτάχυνσης Nesterov των by Su et al. [10], η θεωρία της ασυμπτωτικής μηδενικής απόσβεσης των Attouch et al. [11], και οι εξαρτώμενοι από τη γεωμετρία βελτιωμένοι ρυθμοί για αδρανειακούς αλγορίθμους βαθμίδας των Apidopoulos et al. [12].

Authors dc:creator

• ΚΟΥΤΣΗΣ ΠΕΤΡΟΣ ΑΝΤΩΝΙΟΣ
• KOUTSIS PETROS ANTONIOS

• Θετικές Επιστήμες
• Science

Language dc:language

English

Identifier

uoadl:5410203

OAI identifier oai:identifier

oai:lib.uoa.gr:uoadl:5410203