Παραμετρική βελτιστοποίηση: θεωρία, αλγόριθμοι και εφαρμογές στο βέλτιστο και τον προβλεπτικό έλεγχο στοχαστικών διακοπτικών συστημάτων και δικτυωμένων συστημάτων υπό περιορισμούς

Abstract

One of the most important and fundamental problems in control is the development of systematic tools for the computation of controllers for general constrained non-linear and hybrid systems, that can guarantee stability, feasibility and optimality for the closed-loop system. Model Predictive Control (MPC) plays the central role in this research area, the application of which, till recently, was limited to systems with large sampling time, due its demanding on-line computations. However, recently the emergence of parametric optimization in optimal control of constrained systems allowed the analytical solution of such kind of problems, off-line, and the derivation of the explicit optimal and predictive control law. The explicit control law is usually a piecewise affine mapping, and on-line, its implementation requires merely the determination of the region of the state-space to which the current state of the system belongs. The main topic of the present doctoral thesis is the development of new algorithms for parametric optimization and their application to the explicit solution of optimal and predictive control problems for constrained stochastic switching systems and constrained networked control systems. To be more specific, in the present thesis, notions and tools stemming from Variational Analysis are employed in order to develop a new algorithm for convex parametric quadratic optimization problems. This kind of problems usually appear in model predictive control of constrained linear systems, and this new proposed approach comes to fill in the gaps of existing algorithms proposed in the literature. In particular, unlike most methods proposed in the literature, the proposed algorithm guarantees the enumeration of all the critical regions for the parametric optimization problem. Next, convex parametric piecewise quadratic optimization problems are studied, and the first systematic algorithm in the literature for their solution is proposed. Here too, the basic mathematical tool is the graphical derivative of the solution mapping. The algorithm, coupled with dynamic programming allows the explicit solution of optimal control problems for various classes of constrained systems that have never been solved analytically before. Specifically, we introduce constrained Markovian Switching Systems, a class of stochastic switching systems, where a Markov chain orchestrates the switching among its various subsystems. Appropriate notions of invariance and stability are established, and Lyapunov like sufficient conditions are derived for this kind of systems. Furthermore, finite and infinite horizon optimal control are studied, and sufficient conditions that the terminal cost and terminal set of the finite horizon optimal control problem must satisfy, in order to guarantee invariance and mean square stability for the Markovian switching system in closed-loop with the model predictive controller. Next, the thesis focuses on networked control systems, a rapidly evolving research area. Specifically, a new MPC algorithm is proposed for linear continuous-time networked systems, that guarantees constraint satisfaction in the continuous-time. Under the assumption that the time-varying transmission delay takes its values according to a Markov chain, the networked control system is cast under the Markovian switching framework, developed in the present thesis. However, since the application of explicit MPC is limited to medium scale systems due to the exponential increase in the number of critical regions with respect to the dimension of the problem, a new on-line MPC algorithm is proposed in the last part of the thesis. The proposed approach is based on the reformulation of the quadratic optimization problem as the unconstrained minimization of a smooth, convex piecewise quadratic function. A piecewise smooth Newton method with exact line search is proposed for the solution of the reformulated problem. The proposed algorithm is compared against state-of-the-art solvers in a series of benchmark problems, demonstrating considerably smaller running times. This result is very important since it renders MPC applicable to large-scale systems with small sampling times.

Ένα από τα πιο σημαντικά και θεμελιώδη προβλήματα στον αυτόματο έλεγχο είναι η ανάπτυξη συστηματικών εργαλείων υπολογισμού ρυθμιστών για συστήματα υπό περιορισμούς, που εξασφαλίζουν την ευστάθεια, την εφικτότητα και τη βέλτιστη λειτουργία συστημάτων κλειστού βρόγχου. Κεντρικό ρόλο στην εν λόγω ερευνητική περιοχή διαδραματίζει ο προβλεπτικός έλεγχος, η χρήση του οποίου όμως μέχρι πρότινος περιοριζόταν σε συστήματα με αρκετό μεγάλο χρόνο δειγματοληψίας, λόγω των υψηλών υπολογιστικών απαιτήσεών του σε πραγματικό χρόνο. Ωστόσο πρόσφατα, η εισαγωγή της παραμετρικής βελτιστοποίησης στο βέλτιστο έλεγχο συστημάτων υπό περιορισμούς επέτρεψε την αναλυτική επίλυση των προβλημάτων πριν την έναρξη λειτουργίας του συστήματος και την εξαγωγή του ρητού νόμου βέλτιστου και προβλεπτικού ελέγχου σε κλειστή μορφή. Ο ρητός νόμος ελέγχου είναι συνήθως μία τμηματικά αφφινική απεικόνιση και κατά τη λειτουργία του συστήματος, η υλοποίηση του απαιτεί μόνο τον εντοπισμό της περιοχής του χώρου κατάστασης στην οποία ανήκει η τρέχουσα κατάσταση. Το βασικό αντικείμενο της παρούσας διδακτορικής διατριβής είναι η ανάπτυξη νέων αλγόριθμων παραμετρικής βελτιστοποίησης με βελτιωμένα χαρακτηριστικά και η εφαρμογή τους στην αναλυτική επίλυση προβλημάτων βέλτιστου και προβλεπτικού ελέγχου στοχαστικών διακοπτικών και δικτυωμένων συστημάτων με περιορισμούς. Συγκεκριμένα, στην παρούσα διατριβή γίνεται χρήση εννοιών και εργαλείων της μεταβολικής ανάλυσης προκειμένου να αναπτυχθεί ένας νέος αλγόριθμος επίλυσης προβλημάτων κυρτής παραμετρικής τετραγωνικής βελτιστοποίησης. Τα προβλήματα αυτού του τύπου συναντώνται κυρίως στον προβλεπτικό έλεγχο γραμμικών συστημάτων με γραμμικούς περιορισμούς, και η νέα προσέγγιση που ακολουθείται στην παρούσα διατριβή έρχεται να καλύψει τα κενά των προϋπαρχόντων αλγόριθμων στη βιβλιογραφία. Συγκεκριμένα ο προτεινόμενος αλγόριθμος, εν αντιθέσει με τις περισσότερες μεθοδολογίες που έχουν προταθεί μέχρι σήμερα, καταφέρνει να απαριθμήσει και να προσδιορίσει αποτελεσματικά όλες τις κρίσιμες περιοχές του προβλήματος παραμετρικής βελτιστοποίησης. Στη συνέχεια, μελετάται το πρόβλημα της κυρτής παραμετρικής τμηματικά τετραγωνικής βελτιστοποίησης και για πρώτη φορά στη βιβλιογραφία προτείνεται ένας συστηματικός αλγόριθμος επίλυσής του. Και εδώ, το βασικό εργαλείο είναι η γραφική παράγωγος της απεικόνισης των λύσεων. Ο εν λόγω αλγόριθμος, συζευγμένος με το δυναμικό προγραμματισμό επιτρέπει την αναλυτική επίλυση προβλημάτων βέλτιστου ελέγχου για διάφορες κλάσεις συστημάτων, για τα οποία δεν έχουν παρουσιαστεί μέχρι σήμερα λύσεις στη βιβλιογραφία. Συγκεκριμένα, στην παρούσα διατριβή εισάγονται τα Μαρκοβιανά διακοπτικά συστήματα με περιορισμούς, μία κλάση στοχαστικών υβριδικών συστημάτων, όπου η μεταγωγή μεταξύ των καταστάσεων λειτουργία ενορχηστρώνεται από μία Μαρκοβιανή αλυσίδα. Αναπτύσσονται οι κατάλληλες έννοιες αναλλοιότητας και ευστάθειας και διατυπώνονται ικανές συνθήκες τύπου Lyapunov για τα εν λόγω συστήματα. Μελετάται το πρόβλημα του βέλτιστου ελέγχου πεπερασμένου και άπειρου ορίζοντα, και διατυπώνονται ικανές συνθήκες που πρέπει να πληρούν το τερματικό κόστος και το τερματικό σύνολο, προκειμένου να εξασφαλιστεί μέση τετραγωνική ευστάθεια και εφικτότητα για το Μαρκοβιανό διακοπτικό σύστημα σε κλειστό βρόγχο με το νόμο προβλεπτικού ελέγχου. Στη συνέχεια, η διατριβή ασχολείται με τη ραγδαία αναπτυσσόμενη περιοχή των δικτυωμένων συστημάτων ελέγχου. Συγκεκριμένα, προτείνεται για πρώτη φορά μία μεθοδολογία προβλεπτικού ελέγχου για γραμμικά δικτυωμένα συστήματα συνεχούς χρόνου που εξασφαλίζει την ικανοποίηση των περιορισμών στο συνεχή χρόνο. Υπό την υπόθεση ότι η υστέρηση διαβίβασης λαμβάνει τιμές σύμφωνα με μία Μαρκοβιανή αλυσίδα, το δικτυωμένο σύστημα ελέγχου αναδιαμορφώνεται ως ένα Μαρκοβιανό διακοπτικό σύστημα. Ωστόσο, επειδή η εφαρμογή του ρητού προβλεπτικού ελέγχου περιορίζεται σε συστήματα μεσαίας κλίμακας λόγω της εκθετικής αύξησης του αριθμού των κρίσιμων περιοχών με τη διάσταση του προβλήματος, στο τελευταίο κεφάλαιο της διατριβής προτείνεται μία νέα μεθοδολογία επίλυσης προβλημάτων προβλεπτικού ελέγχου σε πραγματικό χρόνο. Η εν λόγω μεθοδολογία βασίζεται στην αναδιαμόρφωση του προβλήματος τετραγωνικής βελτιστοποίησης ως ένα πρόβλημα ελαχιστοποίησης μια λείας, κυρτής τμηματικά τετραγωνικής συνάρτησης άνευ περιορισμών. Για την επίλυση του αναδιαμορφωμένου προβλήματος, προτείνεται μία τμηματικά λεία μέθοδος Newton. O προτεινόμενος αλγόριθμος συγκρίνεται έναντι state-of-the-art αλγόριθμων που έχουν προταθεί πολύ πρόσφατα στη βιβλιογραφία σε μία σειρά από benchmark προβλήματα προβλεπτικού ελέγχου, επιδεικνύοντας σημαντικά μικρότερους χρόνους εκτέλεσης. Το αποτέλεσμα αυτό είναι ιδιαίτερα σημαντικό αφού καθιστά τον προβλεπτικό έλεγχο εφαρμόσιμο σε συστήματα μεγάλης κλίμακας με μικρό χρόνο δειγματοληψίας.