Τεχνικές βελτίωσης της αποδοτικότητας αλγορίθμων επίλυσης προβλημάτων βελτιστοποίησης χωρίς περιορισμούς

Abstract

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 presentedto 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 thedirections given by them create a new direction on which the optimum is sought. Forthe implementation of the proposed idea we set out general principles and following theseprinciples the approximated problems of the given come out. The point used as the initialone for optimizing the given problem by an iterative method results from a preprocessingstep, the stages of which are as follows: (a) the construction of approximate problems whoseobjective functions are referred to as Approximated objective Functions (b) prioritizationof approximate problems and (c) the approximate problems' sequential and non-exhaustiveoptimization.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 behavior 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 behavior.In the third chapter of the dissertation, we present a proposed technique named TaylorLexicographic Sequential Optimization (TLSO) algorithm, where the Approximated Objectivefunctions (AOFs) are extracted using another proposed principle, the sequential principle.This algorithm utilizes the information contained in the non-infinity terms of Taylor'sexpansion, avoiding their calculation. Like LexOpt, the TLSO algorithm, if applied by selectingrandom initial points, converge 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 the objective function of the given problem and on the TLSO algorithm they are constructed by the approximation utilizing Taylor's expansion of the objective function of the given problem.The Trust Lexicographic Optimization (TrustLexOpt) algorithm technique has been proposedto reduce the computational cost of the algorithms already mentioned. The TrustLexOptalgorithm is based on the LexOpt algorithm and is presented in the fourth chapter of thisPh.D. dissertation. This algorithm reduces the number of problems used in the preprocessingstep, and it is suggested to use a combination of trust region and line search methods. TheTrustLexOpt 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 theutilized initial point of the given optimization problem. In the same chapter, a method ofcalculating the trust region radius is proposed.The conclusions drawn in the fourth chapter and in the Ph.D. dissertation, in general, havebeen formulated by adopting the principle that when comparing two algorithms, the finallypreferred 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 Ph.D. 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 relaxationparameters. We then calculated the ratio of the absolute value of the greater to the smallesteigenvalue of the objective function of the given problem at the points resulting from thepreprocessing step. From a first study of the above, it appears that if relaxation parametersare 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 thesetechniques to well-known test functions, it has emerged that the way that priorities are givenin the preprocessing step of the algorithms plays an important role in the results of theproposed algorithms. Thus, giving priorities is considered an issue for further research. Onepoint that is also worth studying is the ideal number of steps that an iterative method shouldbe applied in the preprocessing step. A field for further research is the implementation of theother general principles proposed in the second chapter of this thesis. It is also proposed tostudy the behavior of the algorithms presented in this thesis with the dynamic redefinitionof the problems involved. Finally, an interesting research topic is the application of what isproposed in this dissertation for solving single-objective constrained optimization problems.

Η βελτιστοποίηση χρησιμοποιείται κατά κόρον στο πεδίο των μαθηματικών αλλά και σε πολλούς άλλους τομείς της επιστήμης, όπως στη διοίκηση επιχειρήσεων, την οικονομία, τη βιολογία, κ.α.. Δεν είναι λίγες οι ϕορές που ακούμε ότι εταιρείες ή το κράτος ενεργούν για την βελτιστοποίηση της χρήσης των πληροϕοριών, της τεχνολογίας, της διαχείρισης των ανθρώπινων πόρων, του προσωπικού, των παρεχόμενων υπηρεσιών και των διαδικασιών. Το εύρος των εϕαρμογών της βελτιστοποίησης την καθιστά περιοχή που παρόλο που έχουνπροταθεί πολλές μέθοδοι η έρευνα έχει ακόμα μεγάλη σημασία.Αντικείμενο της παρούσας διατριβής είναι η επίλυση προβλημάτων βελτιστοποίησης χωρίς περιορισμούς με τη χρήση επαναληπτικών μεθόδων. Ένα μεγάλο πρόβλημα πολλών επαναληπτικών αλγορίθμων βελτιστοποίησης είναι το γεγονός ότι η επιτυχία τους εξαρτάται άμεσα από την αρχική προσέγγιση της λύσης. Στην εργασία αυτή, προτείνουμε τεχνικές οι οποίες διευθετούν αυτό το πρόβλημα και παρουσιάζουμε μία νέα οικογένεια αλγορίθμων βελτιστοποίησης χωρίς περιορισμούς. Στις παρουσιαζόμενες τεχνικές, ευρέως γνωστοί αλγόριθμοι βελτιστοποίησης ενσωματώνονται μέσα στις προτεινόμενες τεχνικές με αποτέλεσμα να ενισχύονται τα καλά τους χαρακτηριστικά και να βελτιώνεται η αποδοτικότητάτους.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) των εμπλεκόμενων προβλημάτων. Τέλος, ένα ενδιαϕέρον θέμα έρευνας είναι η εϕαρμογή των όσων προτείνονται στην παρούσα διατριβήστην επίλυση προβλημάτων μονοκριτηριακής βελτιστοποίησης με περιορισμούς.