Τεχνικές βελτίωσης της αποδοτικότητας αλγορίθμων επίλυσης προβλημάτων βελτιστοποίησης χωρίς περιορισμούς
Η βελτιστοποίηση χρησιμοποιείται κατά κόρον στο πεδίο των μαθηματικών αλλά και σε πολλούς άλλους τομείς της επιστήμης, όπως στη διοίκηση επιχειρήσεων, την οικονομία, τη βιολογία, κ.α.. Δεν είναι λίγες οι φορές που ακούμε ότι εταιρείες ή το κράτος ενεργούν για την βελτιστοποίηση της χρήσης των πληροφ...
| Κύριος συγγραφέας: | |
|---|---|
| Άλλοι συγγραφείς: | |
| Μορφή: | Thesis |
| Γλώσσα: | Greek |
| Έκδοση: |
2018
|
| Θέματα: | |
| Διαθέσιμο Online: | http://hdl.handle.net/10889/11824 |
| id |
nemertes-10889-11824 |
|---|---|
| record_format |
dspace |
| institution |
UPatras |
| collection |
Nemertes |
| language |
Greek |
| topic |
Ολική βελτιστοποίηση Προτεραιότητες Διαχωρισμός Μέθοδοι γραμμικής αναζήτησης Μέθοδοι που χρησιμοποιούν διαστήματα εμπιστοσύνης Λεξικογραφική βελτιστοποίηση Global optimization Priorities Partition Line search methods Trust region methods Lexicographic optimization 519.6 |
| spellingShingle |
Ολική βελτιστοποίηση Προτεραιότητες Διαχωρισμός Μέθοδοι γραμμικής αναζήτησης Μέθοδοι που χρησιμοποιούν διαστήματα εμπιστοσύνης Λεξικογραφική βελτιστοποίηση Global optimization Priorities Partition Line search methods Trust region methods Lexicographic optimization 519.6 Νικολακάκου, Γεωργία-Χριστίνα Τεχνικές βελτίωσης της αποδοτικότητας αλγορίθμων επίλυσης προβλημάτων βελτιστοποίησης χωρίς περιορισμούς |
| description |
Η βελτιστοποίηση χρησιμοποιείται κατά κόρον στο πεδίο των μαθηματικών αλλά και σε πολλούς άλλους τομείς της επιστήμης, όπως στη διοίκηση επιχειρήσεων, την οικονομία, τη βιολογία, κ.α.. Δεν είναι λίγες οι φορές που ακούμε ότι εταιρείες ή το κράτος ενεργούν για την βελτιστοποίηση της χρήσης των πληροφοριών, της τεχνολογίας, της διαχείρισης των ανθρώπινων πόρων, του προσωπικού, των παρεχόμενων υπηρεσιών και των διαδικασιών.
Το εύρος των εφαρμογών της βελτιστοποίησης την καθιστά περιοχή που παρόλο που έχουν προταθεί πολλές μέθοδοι η έρευνα έχει ακόμα μεγάλη σημασία. Αντικείμενο της παρούσας διατριβής είναι η επίλυση προβλημάτων βελτιστοποίησης χωρίς περιορισμούς με τη χρήση επαναληπτικών μεθόδων. Ένα μεγάλο πρόβλημα πολλών επαναληπτικών αλγορίθμων βελτιστοποίησης είναι το γεγονός ότι η επιτυχία τους εξαρτάται άμεσα από την αρχική προσέγγιση της λύσης. Στην εργασία αυτή, προτείνουμε τεχνικές οι οποίες διευθετούν αυτό το πρόβλημα και παρουσιάζουμε μία νέα οικογένεια αλγορίθμων βελτιστοποίησης χωρίς περιορισμούς. Στις παρουσιαζόμενες τεχνικές, ευρέως γνωστοί αλγόριθμοι βελτιστοποίησης ενσωματώνονται μέσα στις προτεινόμενες τεχνικές με αποτέλεσμα να ενισχύονται τα καλά τους χαρακτηριστικά και να βελτιώνεται η αποδοτικότητά τους.
Tο πρώτο κεφάλαιο της παρούσας διατριβής αποτελεί ένα εισαγωγικό κεφάλαιο στο οποίο, παρουσιάζονται βασικές έννοιες που βοηθούν στην καλύτερη κατανόηση των επόμενων κεφαλαίων.
Στο δεύτερο κεφάλαιο, αρχικά δίνεται η κύρια ιδέα των αλγορίθμων της παρούσας διατριβής, σύμφωνα με την οποία, γνωστές μέθοδοι βελτιστοποίησης συνδυάζονται με τέτοιον τρόπο ώστε οι κατευθύνσεις που δίνονται από αυτές, να δημιουργούν μια νέα κατεύθυνση πάνω στην οποία αναζητείται το βέλτιστο. Για την υλοποίηση της προτεινόμενης ιδέας ορίζονται γενικές αρχές και ακολουθώντας αυτές τις αρχές προκύπτουν προσεγγιστικά προβλήματα του δοθέντος. Το σημείο που χρησιμοποιείται ως αρχικό για την επίλυση του δοθέντος προβλήματος από μια μέθοδο βελτιστοποίησης είναι αυτό που προκύπτει από ένα προπαρασκευαστικό βήμα, του οποίου τα σταδια είναι τα εξής: (α) η κατασκευή προσεγγιστικών
προβλημάτων, των οποίων οι αντικειμενικές συναρτήσεις αναφέρονται και ως εμπλεκόμενες αντικειμενικές συναρτήσεις (β) η απόδοση προτεραιοτήτων στα προσεγγιστικά προβλήματα και (γ) η ακολουθιακή και μη εξαντλητική επίλυση των προσεγγιστικών προβλημάτων.
Στο ίδιο κεφάλαιο παρουσιάζεται η προτεινομένη τεχνική του Lexicographic Optimization (LexOpt) αλγορίθμου, όπου οι εμπλεκόμενες αντικειμενικές συναρτήσεις εξάγονται με τη χρήση μιας από τις προταθείσες αρχές, την αθροιστική αρχή. Συγκρίνοντας τα αποτελέσματα του LexOpt αλγορίθμου με τα αποτελέσματα των μεθόδων βελτιστοποίησης που χρησιμοποιεί, παρατηρείται διαφορετική συμπεριφορά σύγκλισης, είτε στο υπολογιστικό κόστος είτε στο πλήθος των ελαχίστων που συγκλίνει ή και στα δύο. Αξιοσημείωτο είναι ότι από την πλειοψηφία των συναρτήσεων δοκιμών διαπιστώνεται ότι υπάρχει τρόπος με τον οποίο ο LexOpt αλγόριθμος συγκλίνει, ξεκινώντας από τα ίδια αρχικά σημεία, σε μεγαλύτερο πλήθος ελαχίστων απ' ότι οι μέθοδοι που χρησιμοποιεί και μάλιστα με τέτοιο υπολογιστικό κόστος που μας οδηγεί σε καταφατική απάντηση στο ερώτημα αν χρειάζεται να υπάρξει συνέχιση της έρευνας ως προς τη συμπεριφορά του.
Στο τρίτο κεφάλαιο της διατριβής παρουσιάζεται η προτεινομένη τεχνική του Taylor Lexicographic Sequential Optimization (TLSO) αλγορίθμου, όπου οι εμπλεκόμενες αντικειμενικές συναρτήσεις εξάγονται με τη χρήση μιας άλλης προτεινόμενης αρχής, την ακολουθιακή αρχή. Στον αλγόριθμο αυτό αξιοποιείται η πληροφορία που περικλείεται στους άπειρους όρους του αναπτύγματος Taylor αποφεύγοντας τον υπολογισμό τους. Όπως ο LexOpt έτσι και ο TLSO αλγόριθμος αν εφαρμοστούν επιλέγοντας τυχαία αρχικά σημεία από μια περιοχή συγκλίνουν σε περισσότερα σημεία από ότι συγκλίνει η μέθοδος βελτιστοποίησης που χρησιμοποιούν, αν και αυτή ξεκινήσει από τα ίδια αρχικά σημεία. H κύρια διαφορά των LexOpt και TLSO αλγορίθμων είναι ότι στον LexOpt αλγόριθμο οι αντικειμενικές συναρτήσεις των προβλημάτων του προπαρασκευαστικού βήματος κατασκευάζονται από τον τύπο
της αντικειμενικής συνάρτησης του δοθέντος προβλήματος, ενώ στον TLSO αλγόριθμο κατασκευάζονται από την προσέγγιση κατά Taylor της αντικειμενικής συνάρτησης του δοθέντος προβλήματος.
Με κίνητρο το να μειωθεί το υπολογιστικό κόστος των αλγορίθμων που ήδη αναφέρθηκαν, προτάθηκε η τεχνική του Trust Lexicographic Optimization (TrustLexOpt) αλγορίθμου. Ο TrustLexOpt αλγόριθμος βασίζεται στον LexOpt αλγόριθμο και παρουσιάζεται στο τέταρτο κεφάλαιο της παρούσας διατριβής. Με τον αλγόριθμο αυτό μειώνεται το πλήθος των προβλημάτων που χρησιμοποιούνται στο προπαρασκευαστικό βήμα και παράλληλα προτείνεται η χρήση ενός συνδυασμού trust region και line search μεθόδων. Σε σχέση με τους αλγορίθμους που έχουν ήδη προταθεί ο TrustLexOpt αλγόριθμος χρησιμοποιεί ένα υποπρόβλημα, δηλαδή το ελάχιστο δυνατό πλήθος υποπροβλημάτων και συνδυάζει μεθόδους που χρησιμοπομοιούν διαστήματα εμπιστοσύνης (trust region) και μεθόδους γραμμικής αναζήτησης (line search) προκειμένου να καταλήξει στο σημείο θα χρησιμοποιήσει ως αρχικό για την εφαρμογή επαναληπτικής μεθόδου βελτιστοποίησης στο δοθέν πρόβλημα. Στο ίδιο κεφάλαιο, προτείνεται και ένας τρόπος υπολογισμού της ακτίνας της χρησιμοποιούμενης trust region μεθόδου.
Η διατύπωση των συμπερασμάτων του τετάρτου κεφαλαίου καθώς και της διατριβής εν γένει, γίνεται υιοθετώντας την αρχή ότι συγκρίνοντας δύο αλγορίθμους, θεωρούμε ότι έχει καλύτερη συμπεριφορά ο αλγόριθμος ο οποίος συγκλίνει στο μεγαλύτερο πλήθος ελαχίστων. Επίσης, αν δύο αλγόριθμοι συγκρινόμενοι μεταξύ τους συγκλίνουν στον ίδιο αριθμό ελαχίστων τότε θεωρούμε ότι ο αλγόριθμος με το μικρότερο υπολογιστικό κόστος είναι αυτός που υπερέχει έναντι των δύο αυτών αλγορίθμων. Υπό αυτή την οπτική γωνία, καταλήξαμε ότι υπάρχει τουλάχιστον ένας συνδυασμός των στοιχείων που προκύπτουν εφαρμόζοντας την αθροιστική αρχή, όπου ο TrustLexOpt γενικότερα υπερέχει έναντι των TLSO και LexOpt αλγορίθμων. Βάσει των αριθμητικών αποτελεσμάτων της παρούσας διατριβής, προτείνεται να γίνει περισσότερη μελέτη και έρευνα για το ποιος είναι ο κατάλληλος συνδυασμός
στοιχείων που αν χρησιμοποιηθούν από τον TrustLexOpt αλγόριθμο βελτιώνουν την απόδοσή του. Επίσης προτείνεται να διερευνηθεί ο λόγος για τον οποίο όταν ο TrustLexOpt αλγόριθμος χρησιμοποιεί την προτεινόμενη στη διατριβή trust region ακτίνα έχει καλύτερη συμπεριφορά από ότι αν χρησιμοποιηθεί η trust region ακτίνα που συνήθως χρησιμοποιείται.
Στο τελευταίο κεφάλαιο της διατριβής προτείνονται οι αλγόριθμοι Modified Lexicographic Optimization (MLX), Relaxation Lexicographic Optimization (RLX) και Modified Relaxation Lexicographic Optimization (MRLX). Ο λόγος για τον οποίο προτείνονται είναι προκειμένου να μελετήσουμε την επίδραση της προσθήκης βαρών σε τμήματα των αντικειμενικών συναρτήσεων που χρησιμοποιούνται στο προπαρασκευαστικό στάδιο του LexOpt αλγορίθμου.
Επίσης, προτείνονται προκειμένου να μελετηθεί η επίδραση του γεγονότος ότι οι αντικειμενικές συναρτήσεις των προβλημάτων του προπαρασκευαστικού βήματος δεν έχουν κοινούς όρους. Η προσθήκη βαρών υλοποιήθηκε χρησιμοποιώντας παραμέτρους τις οποίες ονομάσαμε
παράμετρους χαλάρωσης (relaxation parameters). Στη συνεχεια υπολογίσαμε το λόγο της απόλυτης τιμής της μεγαλύτερης προς τη μικρότερη ιδιοτιμή της αντικειμενικής συνάρτησης του δοθέντος προβλήματος στα σημεία που προκύπτουν από το προπαρασκευαστικό στάδιο. Από μια πρώτη μελέτη του λόγου αυτού, προκύπτει ότι αν χρησιμοποιηθούν παράμετροι χαλάρωσης, επιτυγχάνεται μια υπεροχή των αλγορίθμων LexOpt και MLX έναντι των RLX και MRLX. Τα αποτελέσματα και η μελέτη που παρουσιάζονται στο κεφάλαιο αυτό δεν έχουν δημοσιευτεί μέχρι σήμερα.
Συμπερασματικά, στην παρούσα διατριβή παρουσιάζονται τεχνικές για την βελτίωση της αποδοτικότητας αλγορίθμων επίλυσης προβλημάτων βελτιστοποίησης χωρίς περιορισμούς. Από τη μελέτη των αριθμητικών αποτελεσμάτων της εφαρμογής των τεχνικών αυτών σε γνωστές συναρτήσεις δοκιμών, προέκυψε ότι σημαντικό ρόλο για τα αποτελέσματα των προτεινόμενων αλγορίθμων παίζει ο τρόπος που δίνονται προτεραιότητες στο προπαρασκευαστικό στάδιο των αλγορίθμων. Έτσι, ο τρόπος απόδοσης προτεραιοτήτων θεωρείται ένα θέμα για το οποίο αξίζει να δαπανηθεί χρόνος για να μελετηθεί περαιτέρω. Ένα σημείο που αξίζει επίσης να μελετηθεί είναι το ποιος είναι ο ιδανικός αριθμός βημάτων που πρέπει να εφαρμοστεί μια επαναληπτική διαδικασία στο προπαρασκευαστικό βήμα. Ένα πεδίο για περαιτέρω έρευνα είναι η υλοποίηση και των υπολοίπων γενικών αρχών που προτείνονται στο δεύτερο κεφάλαιο της παρούσας διατριβής. Επίσης, προτείνεται να μελετηθεί η συμπεριφορά των αλγορίθμων που παρουσιάστηκαν στην παρούσα διατριβή με τον δυναμικό επαναπροσδιορισμό (dynamic redefinition) των εμπλεκόμενων προβλημάτων. Τέλος, ένα ενδιαφέρον θέμα έρευνας είναι η εφαρμογή των όσων προτείνονται στην παρούσα διατριβή στην επίλυση προβλημάτων μονοκριτηριακής βελτιστοποίησης με περιορισμούς. |
| author2 |
Γράψα, Θεοδούλα |
| author_facet |
Γράψα, Θεοδούλα Νικολακάκου, Γεωργία-Χριστίνα |
| format |
Thesis |
| author |
Νικολακάκου, Γεωργία-Χριστίνα |
| author_sort |
Νικολακάκου, Γεωργία-Χριστίνα |
| title |
Τεχνικές βελτίωσης της αποδοτικότητας αλγορίθμων επίλυσης προβλημάτων βελτιστοποίησης χωρίς περιορισμούς |
| title_short |
Τεχνικές βελτίωσης της αποδοτικότητας αλγορίθμων επίλυσης προβλημάτων βελτιστοποίησης χωρίς περιορισμούς |
| title_full |
Τεχνικές βελτίωσης της αποδοτικότητας αλγορίθμων επίλυσης προβλημάτων βελτιστοποίησης χωρίς περιορισμούς |
| title_fullStr |
Τεχνικές βελτίωσης της αποδοτικότητας αλγορίθμων επίλυσης προβλημάτων βελτιστοποίησης χωρίς περιορισμούς |
| title_full_unstemmed |
Τεχνικές βελτίωσης της αποδοτικότητας αλγορίθμων επίλυσης προβλημάτων βελτιστοποίησης χωρίς περιορισμούς |
| title_sort |
τεχνικές βελτίωσης της αποδοτικότητας αλγορίθμων επίλυσης προβλημάτων βελτιστοποίησης χωρίς περιορισμούς |
| publishDate |
2018 |
| url |
http://hdl.handle.net/10889/11824 |
| work_keys_str_mv |
AT nikolakakougeōrgiachristina technikesbeltiōsēstēsapodotikotētasalgorithmōnepilysēsproblēmatōnbeltistopoiēsēschōrisperiorismous AT nikolakakougeōrgiachristina techniquesforimprovingtheefficiencyofunconstrainedoptimizationalgorithms |
| _version_ |
1771297241191940096 |
| spelling |
nemertes-10889-118242022-09-05T14:00:28Z Τεχνικές βελτίωσης της αποδοτικότητας αλγορίθμων επίλυσης προβλημάτων βελτιστοποίησης χωρίς περιορισμούς Techniques for improving the efficiency of unconstrained optimization algorithms Νικολακάκου, Γεωργία-Χριστίνα Γράψα, Θεοδούλα Γράψα, Θεοδούλα Τσάντας, Νικόλαος Ανδρουλάκης, Γεώργιος Γιαννίκος, Ιωάννης Βραχάτης, Μιχαήλ Λάγαρης, Ισαάκ Ταραντίλης, Χρήστος Nikolakakou, Georgia-Christina Ολική βελτιστοποίηση Προτεραιότητες Διαχωρισμός Μέθοδοι γραμμικής αναζήτησης Μέθοδοι που χρησιμοποιούν διαστήματα εμπιστοσύνης Λεξικογραφική βελτιστοποίηση Global optimization Priorities Partition Line search methods Trust region methods Lexicographic optimization 519.6 Η βελτιστοποίηση χρησιμοποιείται κατά κόρον στο πεδίο των μαθηματικών αλλά και σε πολλούς άλλους τομείς της επιστήμης, όπως στη διοίκηση επιχειρήσεων, την οικονομία, τη βιολογία, κ.α.. Δεν είναι λίγες οι φορές που ακούμε ότι εταιρείες ή το κράτος ενεργούν για την βελτιστοποίηση της χρήσης των πληροφοριών, της τεχνολογίας, της διαχείρισης των ανθρώπινων πόρων, του προσωπικού, των παρεχόμενων υπηρεσιών και των διαδικασιών. Το εύρος των εφαρμογών της βελτιστοποίησης την καθιστά περιοχή που παρόλο που έχουν προταθεί πολλές μέθοδοι η έρευνα έχει ακόμα μεγάλη σημασία. Αντικείμενο της παρούσας διατριβής είναι η επίλυση προβλημάτων βελτιστοποίησης χωρίς περιορισμούς με τη χρήση επαναληπτικών μεθόδων. Ένα μεγάλο πρόβλημα πολλών επαναληπτικών αλγορίθμων βελτιστοποίησης είναι το γεγονός ότι η επιτυχία τους εξαρτάται άμεσα από την αρχική προσέγγιση της λύσης. Στην εργασία αυτή, προτείνουμε τεχνικές οι οποίες διευθετούν αυτό το πρόβλημα και παρουσιάζουμε μία νέα οικογένεια αλγορίθμων βελτιστοποίησης χωρίς περιορισμούς. Στις παρουσιαζόμενες τεχνικές, ευρέως γνωστοί αλγόριθμοι βελτιστοποίησης ενσωματώνονται μέσα στις προτεινόμενες τεχνικές με αποτέλεσμα να ενισχύονται τα καλά τους χαρακτηριστικά και να βελτιώνεται η αποδοτικότητά τους. Tο πρώτο κεφάλαιο της παρούσας διατριβής αποτελεί ένα εισαγωγικό κεφάλαιο στο οποίο, παρουσιάζονται βασικές έννοιες που βοηθούν στην καλύτερη κατανόηση των επόμενων κεφαλαίων. Στο δεύτερο κεφάλαιο, αρχικά δίνεται η κύρια ιδέα των αλγορίθμων της παρούσας διατριβής, σύμφωνα με την οποία, γνωστές μέθοδοι βελτιστοποίησης συνδυάζονται με τέτοιον τρόπο ώστε οι κατευθύνσεις που δίνονται από αυτές, να δημιουργούν μια νέα κατεύθυνση πάνω στην οποία αναζητείται το βέλτιστο. Για την υλοποίηση της προτεινόμενης ιδέας ορίζονται γενικές αρχές και ακολουθώντας αυτές τις αρχές προκύπτουν προσεγγιστικά προβλήματα του δοθέντος. Το σημείο που χρησιμοποιείται ως αρχικό για την επίλυση του δοθέντος προβλήματος από μια μέθοδο βελτιστοποίησης είναι αυτό που προκύπτει από ένα προπαρασκευαστικό βήμα, του οποίου τα σταδια είναι τα εξής: (α) η κατασκευή προσεγγιστικών προβλημάτων, των οποίων οι αντικειμενικές συναρτήσεις αναφέρονται και ως εμπλεκόμενες αντικειμενικές συναρτήσεις (β) η απόδοση προτεραιοτήτων στα προσεγγιστικά προβλήματα και (γ) η ακολουθιακή και μη εξαντλητική επίλυση των προσεγγιστικών προβλημάτων. Στο ίδιο κεφάλαιο παρουσιάζεται η προτεινομένη τεχνική του Lexicographic Optimization (LexOpt) αλγορίθμου, όπου οι εμπλεκόμενες αντικειμενικές συναρτήσεις εξάγονται με τη χρήση μιας από τις προταθείσες αρχές, την αθροιστική αρχή. Συγκρίνοντας τα αποτελέσματα του LexOpt αλγορίθμου με τα αποτελέσματα των μεθόδων βελτιστοποίησης που χρησιμοποιεί, παρατηρείται διαφορετική συμπεριφορά σύγκλισης, είτε στο υπολογιστικό κόστος είτε στο πλήθος των ελαχίστων που συγκλίνει ή και στα δύο. Αξιοσημείωτο είναι ότι από την πλειοψηφία των συναρτήσεων δοκιμών διαπιστώνεται ότι υπάρχει τρόπος με τον οποίο ο LexOpt αλγόριθμος συγκλίνει, ξεκινώντας από τα ίδια αρχικά σημεία, σε μεγαλύτερο πλήθος ελαχίστων απ' ότι οι μέθοδοι που χρησιμοποιεί και μάλιστα με τέτοιο υπολογιστικό κόστος που μας οδηγεί σε καταφατική απάντηση στο ερώτημα αν χρειάζεται να υπάρξει συνέχιση της έρευνας ως προς τη συμπεριφορά του. Στο τρίτο κεφάλαιο της διατριβής παρουσιάζεται η προτεινομένη τεχνική του Taylor Lexicographic Sequential Optimization (TLSO) αλγορίθμου, όπου οι εμπλεκόμενες αντικειμενικές συναρτήσεις εξάγονται με τη χρήση μιας άλλης προτεινόμενης αρχής, την ακολουθιακή αρχή. Στον αλγόριθμο αυτό αξιοποιείται η πληροφορία που περικλείεται στους άπειρους όρους του αναπτύγματος Taylor αποφεύγοντας τον υπολογισμό τους. Όπως ο LexOpt έτσι και ο TLSO αλγόριθμος αν εφαρμοστούν επιλέγοντας τυχαία αρχικά σημεία από μια περιοχή συγκλίνουν σε περισσότερα σημεία από ότι συγκλίνει η μέθοδος βελτιστοποίησης που χρησιμοποιούν, αν και αυτή ξεκινήσει από τα ίδια αρχικά σημεία. H κύρια διαφορά των LexOpt και TLSO αλγορίθμων είναι ότι στον LexOpt αλγόριθμο οι αντικειμενικές συναρτήσεις των προβλημάτων του προπαρασκευαστικού βήματος κατασκευάζονται από τον τύπο της αντικειμενικής συνάρτησης του δοθέντος προβλήματος, ενώ στον TLSO αλγόριθμο κατασκευάζονται από την προσέγγιση κατά Taylor της αντικειμενικής συνάρτησης του δοθέντος προβλήματος. Με κίνητρο το να μειωθεί το υπολογιστικό κόστος των αλγορίθμων που ήδη αναφέρθηκαν, προτάθηκε η τεχνική του Trust Lexicographic Optimization (TrustLexOpt) αλγορίθμου. Ο TrustLexOpt αλγόριθμος βασίζεται στον LexOpt αλγόριθμο και παρουσιάζεται στο τέταρτο κεφάλαιο της παρούσας διατριβής. Με τον αλγόριθμο αυτό μειώνεται το πλήθος των προβλημάτων που χρησιμοποιούνται στο προπαρασκευαστικό βήμα και παράλληλα προτείνεται η χρήση ενός συνδυασμού trust region και line search μεθόδων. Σε σχέση με τους αλγορίθμους που έχουν ήδη προταθεί ο TrustLexOpt αλγόριθμος χρησιμοποιεί ένα υποπρόβλημα, δηλαδή το ελάχιστο δυνατό πλήθος υποπροβλημάτων και συνδυάζει μεθόδους που χρησιμοπομοιούν διαστήματα εμπιστοσύνης (trust region) και μεθόδους γραμμικής αναζήτησης (line search) προκειμένου να καταλήξει στο σημείο θα χρησιμοποιήσει ως αρχικό για την εφαρμογή επαναληπτικής μεθόδου βελτιστοποίησης στο δοθέν πρόβλημα. Στο ίδιο κεφάλαιο, προτείνεται και ένας τρόπος υπολογισμού της ακτίνας της χρησιμοποιούμενης trust region μεθόδου. Η διατύπωση των συμπερασμάτων του τετάρτου κεφαλαίου καθώς και της διατριβής εν γένει, γίνεται υιοθετώντας την αρχή ότι συγκρίνοντας δύο αλγορίθμους, θεωρούμε ότι έχει καλύτερη συμπεριφορά ο αλγόριθμος ο οποίος συγκλίνει στο μεγαλύτερο πλήθος ελαχίστων. Επίσης, αν δύο αλγόριθμοι συγκρινόμενοι μεταξύ τους συγκλίνουν στον ίδιο αριθμό ελαχίστων τότε θεωρούμε ότι ο αλγόριθμος με το μικρότερο υπολογιστικό κόστος είναι αυτός που υπερέχει έναντι των δύο αυτών αλγορίθμων. Υπό αυτή την οπτική γωνία, καταλήξαμε ότι υπάρχει τουλάχιστον ένας συνδυασμός των στοιχείων που προκύπτουν εφαρμόζοντας την αθροιστική αρχή, όπου ο TrustLexOpt γενικότερα υπερέχει έναντι των TLSO και LexOpt αλγορίθμων. Βάσει των αριθμητικών αποτελεσμάτων της παρούσας διατριβής, προτείνεται να γίνει περισσότερη μελέτη και έρευνα για το ποιος είναι ο κατάλληλος συνδυασμός στοιχείων που αν χρησιμοποιηθούν από τον TrustLexOpt αλγόριθμο βελτιώνουν την απόδοσή του. Επίσης προτείνεται να διερευνηθεί ο λόγος για τον οποίο όταν ο TrustLexOpt αλγόριθμος χρησιμοποιεί την προτεινόμενη στη διατριβή trust region ακτίνα έχει καλύτερη συμπεριφορά από ότι αν χρησιμοποιηθεί η trust region ακτίνα που συνήθως χρησιμοποιείται. Στο τελευταίο κεφάλαιο της διατριβής προτείνονται οι αλγόριθμοι Modified Lexicographic Optimization (MLX), Relaxation Lexicographic Optimization (RLX) και Modified Relaxation Lexicographic Optimization (MRLX). Ο λόγος για τον οποίο προτείνονται είναι προκειμένου να μελετήσουμε την επίδραση της προσθήκης βαρών σε τμήματα των αντικειμενικών συναρτήσεων που χρησιμοποιούνται στο προπαρασκευαστικό στάδιο του LexOpt αλγορίθμου. Επίσης, προτείνονται προκειμένου να μελετηθεί η επίδραση του γεγονότος ότι οι αντικειμενικές συναρτήσεις των προβλημάτων του προπαρασκευαστικού βήματος δεν έχουν κοινούς όρους. Η προσθήκη βαρών υλοποιήθηκε χρησιμοποιώντας παραμέτρους τις οποίες ονομάσαμε παράμετρους χαλάρωσης (relaxation parameters). Στη συνεχεια υπολογίσαμε το λόγο της απόλυτης τιμής της μεγαλύτερης προς τη μικρότερη ιδιοτιμή της αντικειμενικής συνάρτησης του δοθέντος προβλήματος στα σημεία που προκύπτουν από το προπαρασκευαστικό στάδιο. Από μια πρώτη μελέτη του λόγου αυτού, προκύπτει ότι αν χρησιμοποιηθούν παράμετροι χαλάρωσης, επιτυγχάνεται μια υπεροχή των αλγορίθμων LexOpt και MLX έναντι των RLX και MRLX. Τα αποτελέσματα και η μελέτη που παρουσιάζονται στο κεφάλαιο αυτό δεν έχουν δημοσιευτεί μέχρι σήμερα. Συμπερασματικά, στην παρούσα διατριβή παρουσιάζονται τεχνικές για την βελτίωση της αποδοτικότητας αλγορίθμων επίλυσης προβλημάτων βελτιστοποίησης χωρίς περιορισμούς. Από τη μελέτη των αριθμητικών αποτελεσμάτων της εφαρμογής των τεχνικών αυτών σε γνωστές συναρτήσεις δοκιμών, προέκυψε ότι σημαντικό ρόλο για τα αποτελέσματα των προτεινόμενων αλγορίθμων παίζει ο τρόπος που δίνονται προτεραιότητες στο προπαρασκευαστικό στάδιο των αλγορίθμων. Έτσι, ο τρόπος απόδοσης προτεραιοτήτων θεωρείται ένα θέμα για το οποίο αξίζει να δαπανηθεί χρόνος για να μελετηθεί περαιτέρω. Ένα σημείο που αξίζει επίσης να μελετηθεί είναι το ποιος είναι ο ιδανικός αριθμός βημάτων που πρέπει να εφαρμοστεί μια επαναληπτική διαδικασία στο προπαρασκευαστικό βήμα. Ένα πεδίο για περαιτέρω έρευνα είναι η υλοποίηση και των υπολοίπων γενικών αρχών που προτείνονται στο δεύτερο κεφάλαιο της παρούσας διατριβής. Επίσης, προτείνεται να μελετηθεί η συμπεριφορά των αλγορίθμων που παρουσιάστηκαν στην παρούσα διατριβή με τον δυναμικό επαναπροσδιορισμό (dynamic redefinition) των εμπλεκόμενων προβλημάτων. Τέλος, ένα ενδιαφέρον θέμα έρευνας είναι η εφαρμογή των όσων προτείνονται στην παρούσα διατριβή στην επίλυση προβλημάτων μονοκριτηριακής βελτιστοποίησης με περιορισμούς. Optimization is widely used in the field of mathematics but also in many other fields of science, such as business administration, economics, biology, etc. There are a lot of times that companies or the state act to optimize the use of information, technology, human resources management, personnel, services and processes. The range of optimization applications makes it an area that research is still very important, despite the fact that many methods have already been proposed. The subject of this dissertation is to find the optimum solutions for unconstrained optimization problems using iterative methods. A major problem with many iterative optimization algoristhms is the fact that their success depends directly on the initial approach of the solution. In this dissertation, we propose techniques that solve this problem and present a new family of unconstrained optimization algorithms. In the presented techniques, well-known optimization algorithms are incorporated into the proposed techniques, a fact that enhances the well-known optimization algorithms' good features and improves their efficiency. The first chapter of this thesis is an introductory chapter in which basic ideas are presented to better understand the next chapters. In the second chapter, we first give the main idea of algorithms of the present thesis, according to which known optimization methods are combined in such a way that the directions given by them create a new direction on which the optimum is sought. For the implementation of the proposed idea we set out general principles and following these principles the approximated problems of the given come out. The point used as the initial one for optimizing the given problem by an iterative method results from a preprocessing step, the stages of which are as follows: (a) the construction of approximate problems whose objective functions are referred to as Approximated objective Functions (b) prioritization of approximate problems and (c) the approximate problems' sequential and non-exhaustive optimization. In the same chapter we present the proposed Lexicographic Optimization (LexOpt) algorithm, where the involved Approximated Objective Functions (AOFs)are extracted using one of the proposed principles, the cumulative principle. By comparing the results of the LexOpt algorithm with the results of the optimization methods it uses, different convergence behaviour is observed, either in the computational cost or the number of convergence minima, or both. It is worth to notice that the results from the most of the test functions indicate that there is a way with which the LexOpt algorithm converges, starting from the same initial points, into a larger number of minima than the methods it uses, and even with such computational cost that leads us to an affirmative answer to the question whether there is a need to pursue further research into the LexOpt algorithm behaviour. In the third chapter of the dissertation we present a proposed technique named Taylor Lexicographic Sequential Optimization (TLSO) algorithm, where the Approximated Objective functions (AOFs) are extracted using another proposed principle, the sequential principle. This algorithm utilizes the information contained in the non-infinity terms of the Taylor's expansion, avoiding their calculation. Like LexOpt, the TLSO algorithm, if applied by selecting random initial points, converges to more points than the utilized optimization method, although it starts from the same initial points. The main difference between LexOpt and TLSO algorithm is that in the LexOpt algorithm the objective functions of the preprocessing step problems are made by the formula of objective function of the given problem and on the TLSO algorithm they are constructed by the approximation utilizing the Taylor's expansion of the objective function of the given problem.The Trust Lexicographic Optimization (TrustLexOpt) algorithm technique has been proposed to reduce the computational cost of the algorithms already mentioned. The TrustLexOpt algorithm is based on the LexOpt algorithm and is presented in the fourth chapter of this PhD dissertation. This algorithm reduces the number of problems used in the preprocessing step, and it is suggested to use a combination of trust region and line search methods. The TrustLexOpt algorithm uses a sub-problem, that is the minimum number of utilized subproblems, and combines trust region and line search methods in order to end up to the utilized initial point of the given optimization problem. In the same chapter, a method of calculating the trust region radius is proposed. The conclusions drown in the fourth chapter and in the PhD dissertation in general have been formulated by adopting the principle that when comparing two algorithms, the finally preferred algorithm is the one that converges to the greatest number of minima. Furthermore, if two algorithms converge to the same number of minima, then we think that the algorithm with the smallest computational cost is the one that prevails over these two algorithms. From this point of view, we have concluded that there is at least one way to give priorities on the utilized elements that arise by applying the cumulative principle, where TrustLexOpt has generally excelled over TLSO and LexOpt algorithms. According to the numerical results of the PhD dissertation, it is suggested that more study and research should be made on the appropriate combination of elements that if used by the TrustLexOpt algorithm it then improves the algorithm's performance. It is also suggested to further research why, when the TrustLexOpt algorithm uses the proposed trust region radius it gives better results compared to utilizing the usual trust region radius. In the last chapter of the PhD dissertation, Modified Lexicographic Optimization (MLX), Relaxation Lexicographic Optimization (RLX) and Modified Relaxation Lexicographic Optimization (MRLX) algorithms are proposed. The reason why we propose these algorithms is to study the effect of weights on parts of the objective functions used in the LexOpt algorithm preprocessing step. They are also proposed to study the effect of the fact that the objective functions of the problems of the preprocessing step have no common terms. The use of weights was implemented by using parameters that we called relaxation parameters. We then calculated the ratio of the absolute value of the greater to the smallest eigenvalue of the objective function of the given problem at the points resulting from the preprocessing step. From a first study of the above, it appears that if relaxation parameters are used, a superiority of the LexOpt and MLX algorithms against RLX and MRLX is achieved. The results and the study presented in this chapter have not been published to date. In conclusion, the present thesis presents techniques for improving the efficiency of unconstrained optimization algorithms. While studying the numerical results of applying these techniques to well-known test functions, it has emerged that the way that priorities are given in the preprocessing step of the algorithms plays an important role in the results of the proposed algorithms. Thus, giving priorities is considered an issue for further research. One point that is also worth studying is the ideal number of steps that an iterative method should be applied in the preprocessing step. A field for further research is the implementation of the other general principles proposed in the second chapter of this thesis. It is also proposed to study the behaviour of the algorithms presented in this thesis with the dynamic redefinition of the problems involved. Finally, an interesting research topic is the application of what is proposed in this dissertation for solving single-objective constrained optimization problems. 2018-12-26T20:16:22Z 2018-12-26T20:16:22Z 2018-07-16 Thesis http://hdl.handle.net/10889/11824 gr Η ΒΚΠ διαθέτει αντίτυπο της διατριβής σε έντυπη μορφή στο βιβλιοστάσιο διδακτορικών διατριβών που βρίσκεται στο ισόγειο του κτιρίου της. 0 application/pdf |
