Μαθηματικές μέθοδοι βελτιστοποίησης προβλημάτων μεγάλης κλίμακας
Στην παρούσα διατριβή μελετάμε το πρόβλημα της βελτιστοποίησης μη γραμμικών συναρτήσεων πολλών μεταβλητών, όπου η αντικειμενική συνάρτηση είναι συνεχώς διαφορίσιμη σε ένα ανοιχτό υποσύνολο του Rn. Αναπτύσσουμε μαθηματικές μεθόδους βελτιστοποίησης αποσκοπώντας στην επίλυση προβλημάτων μεγάλης κλίμακα...
| Κύριος συγγραφέας: | |
|---|---|
| Άλλοι συγγραφείς: | |
| Μορφή: | Thesis |
| Γλώσσα: | Greek |
| Έκδοση: |
2012
|
| Θέματα: | |
| Διαθέσιμο Online: | http://hdl.handle.net/10889/5699 |
| id |
nemertes-10889-5699 |
|---|---|
| record_format |
dspace |
| spelling |
nemertes-10889-56992022-09-05T14:01:05Z Μαθηματικές μέθοδοι βελτιστοποίησης προβλημάτων μεγάλης κλίμακας Mathematical methods of optimization for large scale problems Αποστολοπούλου, Μαριάννα Πιντέλας, Παναγιώτης Μπότσαρης, Χαράλαμπος Γράψα, Θεοδούλα Ιορδανίδης, Κοσμάς Λυκοθανάσης, Σπυρίδωνας Τσάντας, Νικόλαος Ανδρουλάκης, Γεώργιος Apostolopoulou, Marianna Προβλήματα μεγάλης κλίμακας Υποπρόβλημα περιοχής εμπιστοσύνης Μέθοδος σχεδόν ακριβούς λύσης Καμπυλόγραμμη αναζήτηση Μέθοδοι Quasi-Newton Μέθοδος L-BFGS Κατεύθυνση αρνητικής καμπυλότητας Ιδιοτιμές-ιδιοδιανύσματα Large scale optimization Trust region subproblem Nearly exact method Curvilinear search Quasi-Newton method L-BFGS method Negative curvature direction Eigenvalues-eigenvectors 515.64 Στην παρούσα διατριβή μελετάμε το πρόβλημα της βελτιστοποίησης μη γραμμικών συναρτήσεων πολλών μεταβλητών, όπου η αντικειμενική συνάρτηση είναι συνεχώς διαφορίσιμη σε ένα ανοιχτό υποσύνολο του Rn. Αναπτύσσουμε μαθηματικές μεθόδους βελτιστοποίησης αποσκοπώντας στην επίλυση προβλημάτων μεγάλης κλίμακας, δηλαδή προβλημάτων των οποίων οι μεταβλητές είναι πολλές χιλιάδες, ακόμα και εκατομμύρια. Η βασική ιδέα των μεθόδων που αναπτύσσουμε έγκειται στη θεωρητική μελέτη των χαρακτηριστικών μεγεθών των Quasi-Newton ενημερώσεων ελάχιστης και μικρής μνήμης. Διατυπώνουμε θεωρήματα αναφορικά με το χαρακτηριστικό πολυώνυμο, τον αριθμό των διακριτών ιδιοτιμών και των αντίστοιχων ιδιοδιανυσμάτων. Εξάγουμε κλειστούς τύπους για τον υπολογισμό των ανωτέρω ποσοτήτων, αποφεύγοντας τόσο την αποθήκευση όσο και την παραγοντοποίηση πινάκων. Τα νέα θεωρητικά απoτελέσματα εφαρμόζονται αφενός μεν στην επίλυση μεγάλης κλίμακας υποπροβλημάτων περιοχής εμπιστοσύνης, χρησιμοποιώντας τη μέθοδο της σχεδόν ακριβούς λύσης, αφετέρου δε, στην καμπυλόγραμμη αναζήτηση, η οποία χρησιμοποιεί ένα ζεύγος κατευθύνσεων μείωσης, την Quasi-Newton κατεύθυνση και την κατεύθυνση αρνητικής καμπυλότητας. Η νέα μέθοδος μειώνει δραστικά τη χωρική πολυπλοκότητα των γνωστών αλγορίθμων του μη γραμμικού προγραμματισμού, διατηρώντας παράλληλα τις καλές ιδιότητες σύγκλισής τους. Ως αποτέλεσμα, οι προκύπτοντες νέοι αλγόριθμοι έχουν χωρική πολυπλοκότητα Θ(n). Τα αριθμητικά αποτελέσματα δείχνουν ότι οι νέοι αλγόριθμοι είναι αποδοτικοί, γρήγοροι και πολύ αποτελεσματικοί όταν χρησιμοποιούνται στην επίλυση προβλημάτων με πολλές μεταβλητές. In this thesis we study the problem of minimizing nonlinear functions of several variables, where the objective function is continuously differentiable on an open subset of Rn. We develop mathematical optimization methods for solving large scale problems, i.e., problems whose variables are many thousands, even millions. The proposed method is based on the theoretical study of the properties of minimal and low memory Quasi-Newton updates. We establish theorems concerning the characteristic polynomial, the number of distinct eigenvalues and corresponding eigenvectors. We derive closed formulas for calculating these quantities, avoiding both the storage and factorization of matrices. The new theoretical results are applied in the large scale trust region subproblem for calculating nearly exact solutions as well as in a curvilinear search that uses a Quasi-Newton and a negative curvature direction. The new method is drastically reducing the spatial complexity of known algorithms of nonlinear programming. As a result, the new algorithms have spatial complexity Θ(n), while they are maintaining good convergence properties. The numerical results show that the proposed algorithms are efficient, fast and very effective when used in solving large scale problems. 2012-12-21T07:40:00Z 2012-12-21T07:40:00Z 2011-03-21 2012-12-21 Thesis http://hdl.handle.net/10889/5699 gr Η ΒΚΠ διαθέτει αντίτυπο της διατριβής σε έντυπη μορφή στο βιβλιοστάσιο διδακτορικών διατριβών που βρίσκεται στο ισόγειο του κτιρίου της. 12 application/pdf |
| institution |
UPatras |
| collection |
Nemertes |
| language |
Greek |
| topic |
Προβλήματα μεγάλης κλίμακας Υποπρόβλημα περιοχής εμπιστοσύνης Μέθοδος σχεδόν ακριβούς λύσης Καμπυλόγραμμη αναζήτηση Μέθοδοι Quasi-Newton Μέθοδος L-BFGS Κατεύθυνση αρνητικής καμπυλότητας Ιδιοτιμές-ιδιοδιανύσματα Large scale optimization Trust region subproblem Nearly exact method Curvilinear search Quasi-Newton method L-BFGS method Negative curvature direction Eigenvalues-eigenvectors 515.64 |
| spellingShingle |
Προβλήματα μεγάλης κλίμακας Υποπρόβλημα περιοχής εμπιστοσύνης Μέθοδος σχεδόν ακριβούς λύσης Καμπυλόγραμμη αναζήτηση Μέθοδοι Quasi-Newton Μέθοδος L-BFGS Κατεύθυνση αρνητικής καμπυλότητας Ιδιοτιμές-ιδιοδιανύσματα Large scale optimization Trust region subproblem Nearly exact method Curvilinear search Quasi-Newton method L-BFGS method Negative curvature direction Eigenvalues-eigenvectors 515.64 Αποστολοπούλου, Μαριάννα Μαθηματικές μέθοδοι βελτιστοποίησης προβλημάτων μεγάλης κλίμακας |
| description |
Στην παρούσα διατριβή μελετάμε το πρόβλημα της βελτιστοποίησης μη γραμμικών συναρτήσεων πολλών μεταβλητών, όπου η αντικειμενική συνάρτηση είναι συνεχώς διαφορίσιμη σε ένα ανοιχτό υποσύνολο του Rn. Αναπτύσσουμε μαθηματικές μεθόδους βελτιστοποίησης αποσκοπώντας στην επίλυση προβλημάτων μεγάλης κλίμακας, δηλαδή προβλημάτων των οποίων οι μεταβλητές είναι πολλές χιλιάδες, ακόμα και εκατομμύρια. Η βασική ιδέα των μεθόδων που αναπτύσσουμε έγκειται στη θεωρητική μελέτη των χαρακτηριστικών μεγεθών των Quasi-Newton ενημερώσεων ελάχιστης και μικρής μνήμης. Διατυπώνουμε θεωρήματα αναφορικά με το χαρακτηριστικό πολυώνυμο, τον αριθμό των διακριτών ιδιοτιμών και των αντίστοιχων ιδιοδιανυσμάτων. Εξάγουμε κλειστούς τύπους για τον υπολογισμό των ανωτέρω ποσοτήτων, αποφεύγοντας τόσο την αποθήκευση όσο και την παραγοντοποίηση πινάκων. Τα νέα θεωρητικά απoτελέσματα εφαρμόζονται αφενός μεν στην επίλυση μεγάλης κλίμακας υποπροβλημάτων περιοχής εμπιστοσύνης, χρησιμοποιώντας τη μέθοδο της σχεδόν ακριβούς λύσης, αφετέρου δε, στην καμπυλόγραμμη αναζήτηση, η οποία χρησιμοποιεί ένα ζεύγος κατευθύνσεων μείωσης, την Quasi-Newton κατεύθυνση και την κατεύθυνση αρνητικής καμπυλότητας. Η νέα μέθοδος μειώνει δραστικά τη χωρική πολυπλοκότητα των γνωστών αλγορίθμων του μη γραμμικού προγραμματισμού, διατηρώντας παράλληλα τις καλές ιδιότητες σύγκλισής τους. Ως αποτέλεσμα, οι προκύπτοντες νέοι αλγόριθμοι έχουν χωρική πολυπλοκότητα Θ(n). Τα αριθμητικά αποτελέσματα δείχνουν ότι οι νέοι αλγόριθμοι είναι αποδοτικοί, γρήγοροι και πολύ αποτελεσματικοί όταν χρησιμοποιούνται στην επίλυση προβλημάτων με πολλές μεταβλητές. |
| author2 |
Πιντέλας, Παναγιώτης |
| author_facet |
Πιντέλας, Παναγιώτης Αποστολοπούλου, Μαριάννα |
| format |
Thesis |
| author |
Αποστολοπούλου, Μαριάννα |
| author_sort |
Αποστολοπούλου, Μαριάννα |
| title |
Μαθηματικές μέθοδοι βελτιστοποίησης προβλημάτων μεγάλης κλίμακας |
| title_short |
Μαθηματικές μέθοδοι βελτιστοποίησης προβλημάτων μεγάλης κλίμακας |
| title_full |
Μαθηματικές μέθοδοι βελτιστοποίησης προβλημάτων μεγάλης κλίμακας |
| title_fullStr |
Μαθηματικές μέθοδοι βελτιστοποίησης προβλημάτων μεγάλης κλίμακας |
| title_full_unstemmed |
Μαθηματικές μέθοδοι βελτιστοποίησης προβλημάτων μεγάλης κλίμακας |
| title_sort |
μαθηματικές μέθοδοι βελτιστοποίησης προβλημάτων μεγάλης κλίμακας |
| publishDate |
2012 |
| url |
http://hdl.handle.net/10889/5699 |
| work_keys_str_mv |
AT apostolopouloumarianna mathēmatikesmethodoibeltistopoiēsēsproblēmatōnmegalēsklimakas AT apostolopouloumarianna mathematicalmethodsofoptimizationforlargescaleproblems |
| _version_ |
1801184883534462976 |
