Τεχνικές βελτίωσης της αποδοτικότητας αλγορίθμων επίλυσης προβλημάτων βελτιστοποίησης χωρίς περιορισμούς
Authors: Νικολακάκου Γεωργία-Χριστίνα 
Published: September 2021

Η βελτιστοποίηση χρησιμοποιείται κατά κόρον στο πεδίο των μαθηματικών αλλά και σε πολλούς άλλους τομείς της επιστήμης, όπως στη διοίκηση επιχειρήσεων, την οικονομία, τη βιολογία, κ.α.. Δεν είναι λίγες οι ϕορές που ακούμε ότι εταιρείες ή το κράτος ενεργούν για την βελτιστοποίηση της χρήσης των πληροϕοριών, της τεχνολογίας, της διαχείρισης των ανθρώπινων πόρων, του προσωπικού, των παρεχόμενων υπηρεσιών και των διαδικασιών. Το εύρος των εϕαρμογών της βελτιστοποίησης την καθιστά περιοχή που παρόλο που έχουνπροταθεί πολλές μέθοδοι η έρευνα έχει ακόμα μεγάλη σημασία.Αντικείμενο της παρούσας διατριβής είναι η επίλυση προβλημάτων βελτιστοποίησης χωρίς περιορισμούς με τη χρήση επαναληπτικών μεθόδων. Ένα μεγάλο πρόβλημα πολλών επαναληπτικών αλγορίθμων βελτιστοποίησης είναι το γεγονός ότι η επιτυχία τους εξαρτάται άμεσα από την αρχική προσέγγιση της λύσης. Στην εργασία αυτή, προτείνουμε τεχνικές οι οποίες διευθετούν αυτό το πρόβλημα και παρουσιάζουμε μία νέα οικογένεια αλγορίθμων βελτιστοποίησης χωρίς περιορισμούς. Στις παρουσιαζόμενες τεχνικές, ευρέως γνωστοί αλγόριθμοι βελτιστοποίησης ενσωματώνονται μέσα στις προτεινόμενες τεχνικές με αποτέλεσμα να ενισχύονται τα καλά τους χαρακτηριστικά και να βελτιώνεται η αποδοτικότητάτους.Tο πρώτο κεϕάλαιο της παρούσας διατριβής αποτελεί ένα εισαγωγικό κεϕάλαιο στο οποίο, παρουσιάζονται βασικές έννοιες που βοηθούν στην καλύτερη κατανόηση των επόμενων κεϕαλαίων.Στο δεύτερο κεϕάλαιο, αρχικά δίνεται η κύρια ιδέα των αλγορίθμων της παρούσας διατριβής, σύμϕωνα με την οποία, γνωστές μέθοδοι βελτιστοποίησης συνδυάζονται με τέτοιον τρόπο ώστε οι κατευθύνσεις που δίνονται από αυτές, να δημιουργούν μια νέα κατεύθυνση πάνω στην οποία αναζητείται το βέλτιστο. Για την υλοποίηση της προτεινόμενης ιδέας ορίζονται γενικές αρχές και ακολουθώντας αυτές τις αρχές προκύπτουν προσεγγιστικά προβλήματα του δοθέντος. Το σημείο που χρησιμοποιείται ως αρχικό για την επίλυση του δοθέντος προβλήματος από μια μέθοδο βελτιστοποίησης είναι αυτό που προκύπτει από ένα προπαρασκευαστικό βήμα, του οποίου τα σταδια είναι τα εξής: (α) η κατασκευή προσεγγιστικών προβλημάτων, των οποίων οι αντικειμενικές συναρτήσεις αναϕέρονται και ως εμπλεκόμενες αντικειμενικές συναρτήσεις (β) η απόδοση προτεραιοτήτων στα προσεγγιστικά προβλήματα και (γ) η ακολουθιακή και μη εξαντλητική επίλυση των προσεγγιστικών προβλημάτων.Στο ίδιο κεϕάλαιο παρουσιάζεται η προτεινομένη τεχνική του Lexicographic Optimization(LexOpt) αλγορίθμου, όπου οι εμπλεκόμενες αντικειμενικές συναρτήσεις εξάγονται με τη χρήση μιας από τις προταθείσες αρχές, την αθροιστική αρχή. Συγκρίνοντας τα αποτελέσματα του LexOpt αλγορίθμου με τα αποτελέσματα των μεθόδων βελτιστοποίησης που χρησιμοποιεί, παρατηρείται διαϕορετική συμπεριϕορά σύγκλισης, είτε στο υπολογιστικόκόστος είτε στο πλήθος των ελαχίστων που συγκλίνει ή και στα δύο. Αξιοσημείωτο είναιότι από την πλειοψηϕία των συναρτήσεων δοκιμών διαπιστώνεται ότι υπάρχει τρόπος μετον οποίο ο LexOpt αλγόριθμος συγκλίνει, ξεκινώντας από τα ίδια αρχικά σημεία, σε μεγαλύτερο πλήθος ελαχίστων απ' ότι οι μέθοδοι που χρησιμοποιεί και μάλιστα με τέτοιουπολογιστικό κόστος που μας οδηγεί σε καταϕατική απάντηση στο ερώτημα αν χρειάζεταινα υπάρξει συνέχιση της έρευνας ως προς τη συμπεριϕορά του.Στο τρίτο κεϕάλαιο της διατριβής παρουσιάζεται η προτεινομένη τεχνική του TaylorLexicographic 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 LexicographicOptimization (MLX), Relaxation Lexicographic Optimization (RLX) και Modified RelaxationLexicographic Optimization (MRLX). Ο λόγος για τον οποίο προτείνονται είναι προκειμένουνα μελετήσουμε την επίδραση της προσθήκης βαρών σε τμήματα των αντικειμενικών συναρτήσεων που χρησιμοποιούνται στο προπαρασκευαστικό στάδιο του LexOpt αλγορίθμου.Επίσης, προτείνονται προκειμένου να μελετηθεί η επίδραση του γεγονότος ότι οι αντικειμενικές συναρτήσεις των προβλημάτων του προπαρασκευαστικού βήματος δεν έχουν κοινούς όρους.Η προσθήκη βαρών υλοποιήθηκε χρησιμοποιώντας παραμέτρους τις οποίες ονομάσαμε παράμετρους χαλάρωσης (relaxation parameters). Στη συνεχεια υπολογίσαμε το λόγο τηςαπόλυτης τιμής της μεγαλύτερης προς τη μικρότερη ιδιοτιμή της αντικειμενικής συνάρτη-σης του δοθέντος προβλήματος στα σημεία που προκύπτουν από το προπαρασκευαστικόστάδιο. Από μια πρώτη μελέτη του λόγου αυτού, προκύπτει ότι αν χρησιμοποιηθούν παράμετροι χαλάρωσης, επιτυγχάνεται μια υπεροχή των αλγορίθμων LexOpt και MLX έναντι των RLX και MRLX. Τα αποτελέσματα και η μελέτη που παρουσιάζονται στο κεϕάλαιοαυτό δεν έχουν δημοσιευτεί μέχρι σήμερα.Συμπερασματικά, στην παρούσα διατριβή παρουσιάζονται τεχνικές για την βελτίωση τηςαποδοτικότητας αλγορίθμων επίλυσης προβλημάτων βελτιστοποίησης χωρίς περιορισμούς.Από τη μελέτη των αριθμητικών αποτελεσμάτων της εϕαρμογής των τεχνικών αυτών σεγνωστές συναρτήσεις δοκιμών, προέκυψε ότι σημαντικό ρόλο για τα αποτελέσματα τωνπροτεινόμενων αλγορίθμων παίζει ο τρόπος που δίνονται προτεραιότητες στο προπαρασκευαστικό στάδιο των αλγορίθμων. Έτσι, ο τρόπος απόδοσης προτεραιοτήτων θεωρείται ένα θέμα για το οποίο αξίζει να δαπανηθεί χρόνος για να μελετηθεί περαιτέρω. Ένα σημείο που αξίζει επίσης να μελετηθεί είναι το ποιος είναι ο ιδανικός αριθμός βημάτων που πρέπει να εϕαρμοστεί μια επαναληπτική διαδικασία στο προπαρασκευαστικό βήμα. Ένα πεδίο για περαιτέρω έρευνα είναι η υλοποίηση και των υπολοίπων γενικών αρχών που προτείνονταιστο δεύτερο κεϕάλαιο της παρούσας διατριβής. Επίσης, προτείνεται να μελετηθεί η συμπεριϕορά των αλγορίθμων που παρουσιάστηκαν στην παρούσα διατριβή με τον δυναμικόεπαναπροσδιορισμό (dynamic redefinition) των εμπλεκόμενων προβλημάτων. Τέλος, ένα ενδιαϕέρον θέμα έρευνας είναι η εϕαρμογή των όσων προτείνονται στην παρούσα διατριβήστην επίλυση προβλημάτων μονοκριτηριακής βελτιστοποίησης με περιορισμούς.