Μαθηματικές μέθοδοι βελτιστοποίησης προβλημάτων μεγάλης κλίμακας
Loading...
Date
2012-12-21
Authors
Αποστολοπούλου, Μαριάννα
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Στην παρούσα διατριβή μελετάμε το πρόβλημα της βελτιστοποίησης μη γραμμικών συναρτήσεων πολλών μεταβλητών, όπου η αντικειμενική συνάρτηση είναι συνεχώς διαφορίσιμη σε ένα ανοιχτό υποσύνολο του Rn. Αναπτύσσουμε μαθηματικές μεθόδους βελτιστοποίησης αποσκοπώντας στην επίλυση προβλημάτων μεγάλης κλίμακας, δηλαδή προβλημάτων των οποίων οι μεταβλητές είναι πολλές χιλιάδες, ακόμα και εκατομμύρια. Η βασική ιδέα των μεθόδων που αναπτύσσουμε έγκειται στη θεωρητική μελέτη των χαρακτηριστικών μεγεθών των Quasi-Newton ενημερώσεων ελάχιστης και μικρής μνήμης. Διατυπώνουμε θεωρήματα αναφορικά με το χαρακτηριστικό πολυώνυμο, τον αριθμό των διακριτών ιδιοτιμών και των αντίστοιχων ιδιοδιανυσμάτων. Εξάγουμε κλειστούς τύπους για τον υπολογισμό των ανωτέρω ποσοτήτων, αποφεύγοντας τόσο την αποθήκευση όσο και την παραγοντοποίηση πινάκων. Τα νέα θεωρητικά απoτελέσματα εφαρμόζονται αφενός μεν στην επίλυση μεγάλης κλίμακας υποπροβλημάτων περιοχής εμπιστοσύνης, χρησιμοποιώντας τη μέθοδο της σχεδόν ακριβούς λύσης, αφετέρου δε, στην καμπυλόγραμμη αναζήτηση, η οποία χρησιμοποιεί ένα ζεύγος κατευθύνσεων μείωσης, την Quasi-Newton κατεύθυνση και την κατεύθυνση αρνητικής καμπυλότητας. Η νέα μέθοδος μειώνει δραστικά τη χωρική πολυπλοκότητα των γνωστών αλγορίθμων του μη γραμμικού προγραμματισμού, διατηρώντας παράλληλα τις καλές ιδιότητες σύγκλισής τους. Ως αποτέλεσμα, οι προκύπτοντες νέοι αλγόριθμοι έχουν χωρική πολυπλοκότητα Θ(n). Τα αριθμητικά αποτελέσματα δείχνουν ότι οι νέοι αλγόριθμοι είναι αποδοτικοί, γρήγοροι και πολύ αποτελεσματικοί όταν χρησιμοποιούνται στην επίλυση προβλημάτων με πολλές μεταβλητές.
Description
Keywords
Προβλήματα μεγάλης κλίμακας, Υποπρόβλημα περιοχής εμπιστοσύνης, Μέθοδος σχεδόν ακριβούς λύσης, Καμπυλόγραμμη αναζήτηση, Μέθοδοι Quasi-Newton, Μέθοδος L-BFGS, Κατεύθυνση αρνητικής καμπυλότητας, Ιδιοτιμές-ιδιοδιανύσματα