Υλοποίηση ενός υπολογιστικού πακέτου στο Matlab, υλοποιώντας αλγορίθμους για βελτιστοποίηση χωρίς περιορισμούς με δυνατότητες επέκτασης.Επιπλέον παρουσιάζεται το θεωρητικό υπόβαθρο και γίνεται αξιολόγηση του πακέτου μέσω περίπου 30 συναρτήσεων δοκιμών και δίνονται τα αποτελέσματα. / Construction of a software in Matlab, with algorithms for uncostrained optimization with expansion abilities. Moreover we present the theory and we evaluate it throught almost 30 test functions giving the results.

Την τελευταία δεκαετία έχει παρατηρηθεί μια σημαντική διάδοση των συστημάτων πλοήγησης οχημάτων. Τα συστήματα αυτά συνδυάζοντας τις δυνατότητες που προσφέρει η τεχνολογία και χρησιμοποιώντας τη γεωγραφική αναπαράσταση του οδικού δικτύου, την τρέχουσα θέση του οχήματος και συχνά πληροφορίες για την κίνηση προτείνουν στους οδηγούς τη διαδρομή που πρέπει να ακολουθήσουν για να φτάσουν πιο γρήγορα στον προορισμό τους. Οι εφαρμογές πλοήγησης οχημάτων μπορούν να προσφέρουν τη δυνατότητα διαχείρισης της κυκλοφορίας με τέτοιο τρόπο που επιτρέπει την αύξηση της χωρητικότητας του οδικού δικτύου και επομένως τη μείωση της συμφόρησης, χωρίς να είναι απαραίτητη η υψηλού κόστους επέκταση της οδικής υποδομής. Σε αντίθεση με το βέλτιστο για το χρήστη μοντέλο που εφαρμόζεται στα κλασικά συστήματα πλοήγησης και που δεν παρέχει καμία εγγύηση βελτίωσης της κυκλοφοριακής κατάστασης, για το σκοπό αυτό έχει προταθεί το βέλτιστο για το σύστημα μοντέλο. Το μοντέλο προτείνει διαδρομές με στόχο τη βελτίωση της κυκλοφοριακής κατάστασης στο δίκτυο, αλλά η εφαρμογή του είναι μη ρεαλιστική καθώς οι προτεινόμενες διαδρομές μπορεί να είναι πολύ μακρύτερες από το αναμενόμενο. Στην παρούσα διπλωματική εργασία μελετάται μια τρίτη προσέγγιση: ένας βέλτιστος για το σύστημα υπό περιορισμούς αλγόριθμος. Πρόκειται για ένα συνδυασμό των δύο μοντέλων πλοήγησης με σκοπό τη μείωση της συμφόρησης και ταυτόχρονα τη διατήρηση της δικαιοσύνης στην επιλογή των προτεινόμενων διαδρομών για τους οδηγούς. Αφού γίνει θεωρητική μελέτη του προβλήματος παρουσιάζεται η υλοποίηση ενός συστήματος πρότασης διαδρομών που χρησιμοποιεί το βέλτιστο για το σύστημα υπό περιορισμούς αλγόριθμο. / During the last decade, vehicles' route guidance systems have known a significant spread. These systems, taking advantage of the available technological features and by using the geographical representation of the road network, the current position of a vehicle and often traffic data, propose to drivers the route they should follow in order to reach faster their destination. The applications of route guidance systems offer the chance to manage traffic in such a way that allows an increase in road network capacity and therefore a decrease in traffic congestion, without being necessary the high cost expansion of the road infrastructure. In contrast to the user optimal model that is followed by typical route guidance systems and provides no traffic improvement guarantees, the system optimal model has been proposed for this purpose. The model proposes paths with the goal of improving the traffic condition of the network, however its application is unrealistic since the proposed routes may be much longer than expected. In this thesis a third approach is studied: a constrained system optimal algorithm. The algorithm is a combination of the two navigation models with the goal of reducing congestion and at the same time remaining fair for drivers when selecting a route. After the theoretical study of the problem, the implementation of a route recommendation system that incorporates the constrained system optimal algorithm is presented.

Η συνεισφορά της παρούσας διατριβής επικεντρώνεται στην ανάπτυξη και στη Μαθηματική θεμελίωση νέων μεθόδων συζυγών κλίσεων για βελτιστοποίηση χωρίς περιορισμούς και στη μελέτη νέων μεθόδων εκπαίδευσης νευρωνικών δικτύων και εφαρμογών τους. Αναπτύσσουμε δύο νέες μεθόδους βελτιστοποίησης, οι οποίες ανήκουν στην κλάση των μεθόδων συζυγών κλίσεων. Οι νέες μέθοδοι βασίζονται σε νέες εξισώσεις της τέμνουσας με ισχυρά θεωρητικά πλεονεκτήματα, όπως η προσέγγιση με μεγαλύτερη ακρίβεια της επιφάνεια της αντικειμενικής συνάρτησης. Επιπλέον, μία σημαντική ιδιότητα και των δύο προτεινόμενων μεθόδων είναι ότι εγγυώνται επαρκή μείωση ανεξάρτητα από την ακρίβεια της γραμμικής αναζήτησης, αποφεύγοντας τις συχνά αναποτελεσματικές επανεκκινήσεις. Επίσης, αποδείξαμε την ολική σύγκλιση των προτεινόμενων μεθόδων για μη κυρτές συναρτήσεις. Με βάση τα αριθμητικά μας αποτελέσματα καταλήγουμε στο συμπέρασμα ότι οι νέες μέθοδοι έχουν πολύ καλή υπολογιστική αποτελεσματικότητα, όπως και καλή ταχύτητα επίλυσης των προβλημάτων, υπερτερώντας σημαντικά των κλασικών μεθόδων συζυγών κλίσεων. Το δεύτερο μέρος της διατριβής είναι αφιερωμένο στην ανάπτυξη και στη μελέτη νέων μεθόδων εκπαίδευσης νευρωνικών δικτύων. Προτείνουμε νέες μεθόδους, οι οποίες διατηρούν τα πλεονεκτήματα των κλασικών μεθόδων συζυγών κλίσεων και εξασφαλίζουν τη δημιουργία κατευθύνσεων μείωσης αποφεύγοντας τις συχνά αναποτελεσματικές επανεκκινήσεις. Επιπλέον, αποδείξαμε ότι οι προτεινόμενες μέθοδοι συγκλίνουν ολικά για μη κυρτές συναρτήσεις. Τα αριθμητικά αποτελέσματα επαληθεύουν ότι οι προτεινόμενες μέθοδοι παρέχουν γρήγορη, σταθερότερη και πιο αξιόπιστη σύγκλιση, υπερτερώντας των κλασικών μεθόδων εκπαίδευσης. Η παρουσίαση του ερευνητικού μέρους της διατριβής ολοκληρώνεται με μία νέα μέθοδο εκπαίδευσης νευρωνικών δικτύων, η οποία βασίζεται σε μία καμπυλόγραμμη αναζήτηση. Η μέθοδος χρησιμοποιεί τη BFGS ενημέρωση ελάχιστης μνήμης για τον υπολογισμό των κατευθύνσεων μείωσης, η οποία αντλεί πληροφορία από την ιδιοσύνθεση του προσεγγιστικού Eσσιανού πίνακα, αποφεύγοντας οποιαδήποτε αποθήκευση ή παραγοντοποίηση πίνακα, έτσι ώστε η μέθοδος να μπορεί να εφαρμοστεί για την εκπαίδευση νευρωνικών δικτύων μεγάλης κλίμακας. Ο αλγόριθμος εφαρμόζεται σε προβλήματα από το πεδίο της τεχνητής νοημοσύνης και της βιοπληροφορικής καταγράφοντας πολύ καλά αποτελέσματα. Επίσης, με σκοπό την αύξηση της ικανότητας γενίκευσης των εκπαιδευόμενων δικτύων διερευνήσαμε πειραματικά και αξιολογήσαμε την εφαρμογή τεχνικών μείωσης της διάστασης δεδομένων στην απόδοση της γενίκευσης των τεχνητών νευρωνικών δικτύων σε μεγάλης κλίμακας δεδομένα βιοϊατρικής. / The contribution of this thesis focuses on the development and the Mathematical foundation of new conjugate gradient methods for unconstrained optimization and on the study of new neural network training methods and their applications. We propose two new conjugate gradient methods for unconstrained optimization. The proposed methods are based on new secant equations with strong theoretical advantages i.e. they approximate the surface of the objective function with higher accuracy. Moreover, they have the attractive property of ensuring sufficient descent independent of the accuracy of the line search, avoiding thereby the usual inefficient restarts. Further, we have established the global convergence of the proposed methods for general functions under mild conditions. Based on our numerical results we conclude that our proposed methods outperform classical conjugate gradient methods in both efficiency and robustness. The second part of the thesis is devoted on the study and development of new neural network training algorithms. More specifically, we propose some new training methods which preserve the advantages of classical conjugate gradient methods while simultaneously ensure sufficient descent using any line search, avoiding thereby the usual inefficient restarts. Moreover, we have established the global convergence of our proposed methods for general functions. Encouraging numerical experiments on famous benchmarks verify that the presented methods provide fast, stable and reliable convergence, outperforming classical training methods. Finally, the presentation of the research work of this dissertation is fulfilled with the presentation of a new curvilinear algorithm for training large neural networks which is based on the analysis of the eigenstructure of the memoryless BFGS matrices. The proposed method preserves the strong convergence properties provided by the quasi-Newton direction while simultaneously it exploits the nonconvexity of the error surface through the computation of the negative curvature direction without using any storage and matrix factorization. Our numerical experiments have shown that the proposed method outperforms other popular training methods on famous benchmarks. Furthermore, for improving the generalization capability of trained ANNs, we explore the incorporation of several dimensionality reduction techniques as a pre-processing step. To this end, we have experimentally evaluated the application of dimensional reduction techniques for increasing the generalization capability of neural network in large biomedical datasets.

Τα τελευταία χρόνια και κυρίως μετά το 1996 έχει παρουσιαστεί ένα έντονο ενδιαφέρον γύρω από τα ασύρματα συστήματα MIMO (Συστήματα Πολλών Εισόδων και Πολλών Εξόδων). Η βασική αιτία που δημιούργησε αυτό το ενδιαφέρον ήταν η θεωρητική ανάλυση της χωρητικότητας που επιτυγχάνεται με τη χρήση πολλαπλών κεραιών τόσο στο δέκτη όσο και στον πομπό. Ωστόσο πέρα από την αύξηση της χωρητικότητας τα συστήματα MIMΟ έχουν μια σειρά από επιπλέον πλεονεκτήματα, επιτυγχάνουν ανεκτικότητα στην εξασθένιση, αυξάνουν την φασματική αποδοτικότητα, μειώνουν την κατανάλωση ενέργειας καθώς και το κόστος χρήσης και κατασκευής ασύρματων δικτύων. Έχοντας λάβει υπ’ όψιν τα παραπάνω και έχοντας κάνει ήδη μια αρχική έρευνα στο τι υπάρχει στην επιστημονική βιβλιογραφία γύρω από τα συστήματα MIMO, επιλέξαμε να ασχοληθούμε με την συγκεκριμένη τεχνολογία και πιο συγκεκριμένα με την προ-κωδικοποίηση πομπού, όταν τα κανάλια που διαθέτουμε είναι συχνοτικά επιλεκτικά (frequency selective). Το πρόβλημα που μας απασχόλησε είναι η διερεύνηση τεχνικών κωδικοποίησης των δεδομένων του πομπού, πριν αυτά μεταδοθούν, ούτως ώστε να μπορέσει να απλοποιηθεί η σχεδίαση του δέκτη. Στην περίπτωση των συχνοτικά επιλεκτικών καναλιών πέρα από τον πανταχού παρόντα Γκαουσιανό θόρυβο έχουμε να αντιμετωπίσουμε και τη διασυμβολική παρεμβολή (Intersymbol Interference - ISI) . Στόχος μας είναι να μπορέσουμε να μετατοπίσουμε τη διαδικασία της ισοστάθμισης από το δέκτη στον πομπό, όπου, στην περίπτωση που ο πομπός είναι ένας σταθμός βάσης, η δυνατότητα υλοποίησης πολύπλοκων διεργασιών είναι μεγαλύτερη, τόσο μεγαλύτερης ανοχής στην κατανάλωση ενέργειας όσο κυρίως, και στη δυνατότητα χρήσης πολύπλοκου υλικού. Το πρόβλημα που τίθεται στην περίπτωση που η ισοστάθμιση γίνει στην μεριά του πομπού είναι η ποιότητα και η ποσότητα της γνώσης του πραγματικού καναλιού. Είναι σχεδόν αδύνατο ο πομπός να έχει πλήρη γνώση του πραγματικού καναλιού, με αποτέλεσμα να πρέπει να αρκεστεί σε γνώση, που στην καλύτερη περίπτωση προσεγγίζει αυτή του πραγματικού καναλιού. Επίσης, πολλές φορές, η ποσότητα της γνώσης που μπορεί να αποσταλεί από το δέκτη – όταν δεν ισχύει η αρχή της αμοιβαιότητας (reciprocity) – είναι περιορισμένη. Από τα παραπάνω καταλαβαίνουμε ότι θα είχε ενδιαφέρον η μελέτη τεχνικών που παρουσιάζουν ανοχή στην ποιότητα της γνώσης του καναλιού καθώς και η συμπεριφορά τους όταν αυτές διαθέτουν μερική ή και περιορισμένη γνώση του πραγματικού καναλιού. Ένας από τους τρόπου αντιμετώπισης όταν συναντούνται συχνοτικά επιλεκτικά κανάλια είναι η χρήση του OFDM με όσα αρνητικά αυτό συνεπάγεται (π.χ. η δυσκολία συγχρονισμού πομπού και δέκτη). Ένας άλλος τρόπος αντιμετώπισης, στην περίπτωση μονής φέρουσας (single carrier), είναι η χρήση προκωδικοποιητων Bezout. Επιλέξαμε να ασχοληθούμε με αυτόν τον τύπου προκωδικοποίητων. Πιο συγκεκριμένα, όταν ο αριθμός των κεραιών του πομπού είναι μεγαλύτερος από τον αριθμό των κεραιών του δέκτη, είναι δυνατόν να εφαρμόσουμε την ταυτότητα Bezout (Bezout Identity) στην μεριά του δέκτη. Με απλά λόγια θα εφαρμόσουμε ένα προ-ισοσταθμιστή επιβολής μηδενικών (zero forcing). Όπως είναι αναμενόμενο, μιας και ο προκωδικοποιητής εφαρμόζεται στην μεριά του πομπού, πριν εμφανιστεί ο Γκαουσιανός θόρυβος, δεν έχουμε ενίσχυση αυτού του θορύβου, ωστόσο είναι δυνατόν να έχουμε σημαντική αύξηση της μεταδιδόμενης ισχύος. Για να λυθεί αυτό το πρόβλημα έχει προταθεί στη βιβλιογραφία η σχεδίαση προκωδικοποιητών Bezout με την χρήση περιορισμών ισχύος. Αυτό που εμείς μελετήσαμε στην περίπτωση των προκωδικοποιητών Bezout (ή FIR προκωδικοποιητών), είναι η συμπεριφορά τους στην περίπτωση που ο πομπός διαθέτει πλήρη ή μερική γνώση του καναλιού. Είδαμε την περίπτωση του σχεδιασμού ενός FIR προκωδικοποιητή κάτω από τον περιορισμό ισχύος μετάδοσης μέσω της μεθόδου Tikhonov Regularization, ενός σημαντικού εργαλείου επίλυσης του προβλήματος των ελαχίστων τετραγώνων κάτω από τη δι-κριτήριο διατύπωση. Τέλος, προτείναμε δύο FIR σχεδιασμούς προκωδικοποιητών για την περίπτωση που ο πομπός διαθέτει παραμετρική (στατιστική) περιγραφή του καναλιού. / The last years, but mainly after 1996 there is an intensive interest in MIMO systems. The reason that created this interest was the capacity that can be achieved by the use of multiple antennas to the transmitter and to receiver. Furthermore, the use of multiple antennas has a number of advantages except from the capacity increase; MIMO can achieve tolerance to fading, spectral efficiency, increased coverage etc. By having considered the above information we decided to work with MIMO systems and especially with precoding techniques for frequency selective channels. In the case of frequency selective channels except from the Gaussian noise we have to treat and with intersymbol interference (ISI) which is an important degradation factor. A very serious reason to handle intersymbol interference at the transmitter side - especially when transmitter is a base station - is to simplify receiver's design. When transmitter is a base station there is a tolerance in power consuming and in the implementation of more complicated hardware. After an extensive bibliographical we concluded to use the theory of Bezout Identity. In the case where the number of antennas at the transmitter is greater than the number of antennas at the receiver it is formed a left-coprime FIR channel. By using the Bezout identity matrix, it is possible to be designed a FIR MIMO precoder that reduce intersymbol interference. Bezout precoder (pre-equalizer) is a zero-forcing (ZF) equalizer. As it is known from bibliography ZF equalizer has the disadvantage that amplifies noise power in deep fades. For the case of Bezout precoder it is not true since there is no noise - noise will appear at the receiver. But there is another disadvantage, Bezout precoder may increase transmit power significantly to overcome deep fades in the singular values of the channel matrix. The solution to the previous phenomenon can be taken by designing ZF precoders under power constraints. The main problem in the case of transmit precoding is the channel knowledge - when reciprocity principle is not valid. In most cases it is not possible to have perfect channel knowledge or even the knowledge that we have may be of bad quality. Another drawback that appears in the case of frequency selective channels is the amounts of information (number of bits) that can be send back to the transmitter - limited feedback. Many works assumed a quasi-static channel - channel doesn't changes for a number of symbols - and perfect channel knowledge. In real world this may not be true. In this master thesis we investigated three things. Firstly, the behavior of Bezout precoders under channel mismatch at the side of transmitter. Secondly, ways that will allows us to decrease channel feedback. And thirdly, which was the most interesting, we proposed two FIR designs that uses statistical channel knowledge.

Το αντικείμενο της διατριβής αφορά την ανάλυση και τον έλεγχο δυναμικών συστημάτων με περιορισμούς στο διάνυσμα της εισόδου ή/ και στις μεταβλητές κατάστασης. Τα θεωρητικά εργαλεία που χρησιμοποιήθηκαν για την εξαγωγή των αποτελεσμάτων προέρχονται από τη θεωρία ευστάθειας Lyapunov, την αρχή σύγκρισης συστημάτων και τη θεωρία συνόλων, και οδήγησαν στην εδραίωση συνθηκών ευστάθειας και την ανάπτυξη συστηματικών μεθόδων εύρεσης λύσης στο πρόβλημα ελέγχου συγκεκριμένων κατηγοριών δυναμικών συστημάτων με περιορισμούς. Πιο συγκεκριμένα, για την κατηγορία των γραμμικών συστημάτων συνεχούς και διακριτού χρόνου, προτάθηκε μια νέα μέθοδος επίλυσης του προβλήματος ευσταθειοποίησης συνόλου αρχικών συνθηκών και του υπολογισμού του μέγιστου θετικά αμετάβλητου ή αμετάβλητου με έλεγχο συνόλου παρουσία περιορισμών στις εισόδους ή/και στις καταστάσεις. Τα αποτελέσματα επεκτάθηκαν και στην κατηγορία των γραμμικών συστημάτων με πολυτοπικη αβεβαιότητα. Επίσης, μελετήθηκε η κατηγορία των αυτοανάδρομων μοντέλων κινούμενου μέσου όρου (ARMA models). Αρχικά εδραιώθηκαν συνθήκες που εγγυώνται ευστάθεια για ένα συγκεκριμένο σύνολο αρχικών συνθηκών παρουσία περιορισμών. Τα αποτελέσματα αυτά εφαρμόστηκαν στην κατηγορία των δικτυωμένων συστημάτων ελέγχου (NCS), όπου υπολογίστηκε ένας κοινός γραμμικός νόμος ελέγχου ανατροφοδότησης κατάστασης για όλο το εύρος της καθυστέρησης της εισόδου. Τέλος, μελετήθηκε η κατηγορία των διγραμμικών συστημάτων συνεχούς και διακριτού χρόνου. Αρχικά διατυπώθηκαν ικανές συνθήκες ύπαρξης πολυεδρικών συναρτήσεων Lyapunov για αυτήν την κατηγορία συστημάτων. Το πρόβλημα που μελετήθηκε είναι η ευσταθειοποίηση μιας συγκεκριμένης περιοχής του χώρου κατάστασης παρουσία περιορισμών στις εισόδους και τις καταστάσεις και προτάθηκε μια υποβέλτιστη λύση που οδηγεί στον υπολογισμό γραμμικού νόμου ελέγχου ανατροφοδότησης κατάστασης. Όλα τα αποτελέσματα προκύπτουν από την επιλογή πολυεδρικών συναρτήσεων Lyapunov οι οποίες οδηγούν στο χαρακτηρισμό πολυεδρικών εκτιμήσεων της περιοχής ελκτικότητας και θετικά αμετάβλητων συνόλων. Τα κυριότερα οφέλη της επιλογής τέτοιων συναρτήσεων είναι η μη συντηρητική εκτίμησης της περιοχή ευστάθειας και η εδράιωση συνθηκών που οδηγούν σε συστηματικές μεθόδους επίλυσης των προβλημάτων ανάλυσης και ελέγχου, η λύση των οποίων προκύπτει από τη λύση γραμμικών προβλημάτων βελτιστοποίησης. / This dissertation considers the problem of stability analysis and control of dynamical systems under constraints in the input and/or state vector. The theoretical tools used arise from Lyapunov stability theory, comparison systems theory and set theoretic methods and lead to the determination of stability conditions and development of systematic methods that solve the control problem of constrained systems of particular type. In specific, for linear discrete or continuous time systems, a novel method that leads to the solution of the initial condition set stabilization problem as well as the maximal controlled invariant set computation problem is presented. These results have been extended for the case of linear systems with polytopic uncertainty. Also, the category of auto regressive moving average (ARMA) models is investigated. First, conditions that guarantee stability for a preassigned initial conditions set for constrained ARMA models are established. These results are applied to the category of networked control systems (NCS), were a single linear state feedback control law is computed for the whole range of the input delay. Finally, the category of bilinear discrete-time or continuous-time systems is investigated. Initially, sufficient conditions which guarantee existence of polyhedral Lyapunov functions are presented. The problem studied here is the stabilization of an initial condition set in the presence of input and state constraints. The solution proposed is suboptimal and leads to the determination of a linear state feedback control law. The choice of Lyapunov functions leads to the determination of a polyhedral approximation of the domain of attraction as well as polyhedral positively invariant sets. The main benefits of choosing this type of functions is the nonconservative estimation of the domain of attraction and the establishment of stability conditions that lead to systematic control design methods through the solution of linear programming problems.