Distributed Model Predictive Controller Design Based on Distributed Optimization Doãn Minh Đăng Ph. Thesis DISTRIBUTED MODEL PREDICTIVE CONTROLLER DESIGN BASED ON DISTRIBUTED OPTIMIZATION PROEFSCHRIFT ter verkrijging van de graad van doctor aan de Technische Universiteit Delft, op gezag van de Rector Magnificus Prof. Luyben, voorzitter van het College voor Promoties, in het openbaar te verdedigen op woensdag 21 november 2012 om 12:30 uur door Minh Dang DOAN Master of Science in Systems and Control Delft University of Technology geboren te Cantho, Vietnam Dit proefschrift is goedgekeurd door de promotor: Prof. De Schutter Copromotor: Dr.
Keviczky Samenstelling promotiecommisie: Rector Magnificus, voorzitter Prof. De Schutter, Technische Universiteit Delft, promotor Dr. Keviczky, Technische Universiteit Delft, copromotor Prof. Hans Hellendoorn, Technische Universiteit Delft Prof.
Fred van Keulen, Technische Universiteit Delft Prof. Riccardo Scattolini, Politecnico di Milano Prof. Anders Rantzer, Lunds Universitet Prof. Maurice Heemels, Technische Universiteit Eindhoven HD−MPC The work presented in this thesis has been supported by the European Union Seventh Framework STREP project Hierarchical and Distributed Model Predictive Control (HD- MPC) with contract number INFSO-ICT-223854.
ISBN: 978-94-6203-214-9 Copyright c 2012 by Minh Dang Doan under the Creative Commons license Attribution-ShareAlike: http://creativecommons.org/licenses/by-sa/3.0 You may copy and distribute this work if you attribute it to Minh Dang Doan. If you alter, transform, or build upon this work, you may distribute the resulting work only under the same or similar license to this one. An electronic copy of this thesis is stored at the repository of Delft University of Technology (free access): http://repository. Printed by Wöhrmann Print Service in The Netherlands.
dedicated to my parents Kính tặng Bố Mẹ Acknowledgments Writing this Ph. thesis is a continuing process which began in November 2008. Through- out these four years, from single papers to this thesis, a variety of people have left their footprints in my life and contributed to my Ph. research in their own ways.
First and foremost, I would like to express my deepest gratitude to my supervisors Bart De Schutter and Tamás Keviczky. In the last four years, they have constantly helped me with writing my research papers as well as this Ph. They have patiently guided me to develop my research skills through their supervision, support and discussions which have been valuable and helpful. Without them, I have never been able to come to this point of my thesis.
Next, I would like to thank Amol, Lakshmi, Samira, Alfredo, Yashar, Bart, Ismini, Nicolas, Max, and Juan for the relaxing chit-chat during the time we worked in the same office. My special thank goes to Amol, who always shared the office with me when we had the overlapping time working in the TU Delft. He brought back uncountable interesting facts and thoughts to our daily conversations, which help provoke my thinking. Huge thanks to Pontus, Andrea, Felipe, Quốc, Ion, Valentin, and Brett for our discussions and collaborations during my research.
I would like to thank Justin, Paolo, Andrea, Alfredo, Amol, Ali, and Quốc for being my travel companions and sharing pleasant moments when we were attending conferences together. I also would like to thank my colleagues involving in the HD-MPC project for the collabo- rations and scientific discussions, and would like especially thank Rudy, Alfredo, Holger, Felipe, Jairo, Laura, Marcello, Attila, and Carlo for our interactions during the meetings and workshops of the project. I am grateful to the members of my Ph. committee for providing me with constructive remarks, which helped me to improve this thesis.
Many thanks to Noortje for helping me with Dutch translation, and Arne and Gijs for proofreading the propositions and summary of my Ph. I would like to thank my friends in the Vietnamese Community in Delft (VCiD) for the friendship and mutual support we had when we were studying far away from our homeland. I would like to thank my colleagues in Delft Center for Systems and Control, especially Ph. fellows, for the friendly environment with scientific discussions we shared when I vii viii Acknowledgments worked in the block 8C of 3mE building.
I will remember the lunches, sport activities, coffee breaks, movie nights, and amusing email discussions we have had together. I would like to thank the Department of Automatic Control at Lund University for hosting me from April to June 2011, with a warm and peaceful atmosphere, as well as active research activities from which I also benefitted. My thanks also go to my friends and colleagues in Vietnam for their encouragement and understanding when I study abroad. I am grateful to my formers professors at Ho Chi Minh City of Technology for equipping me with a competent scientific background.
I am thankful to the Mekong1000 Project and Cantho150 Program for generously funding my M. study that provided me an opportunity for pursuing this Ph. Then, I would like to extend my heartfelt indebtedness to my parents for devotedly bringing me up, taking the best care of me and constantly encouraging me to achieve more. Their endless love is the reason I have been trying my best to complete my Ph.
research, and this thesis is considered as a gift I especially dedicated to them when they have just entered their retirement. Finally, I am grateful to my wife Cẩm Tâm and my daughter Thủy An for sharing ups and downs during my Ph. candidacy in TU Delft. They have been making my days bright despites the Dutch weather, especially my dear daughter, who is growing up and cheering up every day.
Delft, October 2012 Dang Summary Due to the size and structure of control design problems for large-scale complex systems, standard approaches using a centralized controller are impractical, and in some cases in- tractable due to the number and complexity of interactions between subsystems. This fact has stimulated renewed interest and research on distributed control for large-scale complex systems. This thesis aims to provide tools for designing distributed model predictive controllers for linear systems. The essence of model predictive control (MPC) is to formulate the control problem as a repeated solution to a finite-time optimization problem.
This enables straight- forward controller design for multi-input multi-output systems with hard constraints, thus making this method widely adopted in the industry. However, for large-scale complex sys- tems, this practice gives rise to several serious issues: a global communication mechanism is needed for sending measurement data to a central node; the complexity of the resulting centralized optimization problem leads to a high computational burden; the whole system’s performance and safety depend on the result generated by the single central controller, thus lowering the resilience of the system. In order to design distributed model predictive controllers, our research focuses on solving the resulting large-scale MPC optimization problem in a distributed way. In particular, this thesis addresses two issues: 1.
Designing distributed optimization algorithms for solving convex optimization prob- lems arising in MPC for discrete-time linear systems. Determining conditions for achieving feasibility and stability of the closed-loop sys- tem. The control setting consists of a group of local controllers associated with subsystems that have limited communications among them, and where each controller has a processor for handling local computation tasks. The original centralized MPC optimization problem is formulated as a quadratic program, with a separable cost function and linear constraints, and each constraint involves a small number of subsystems, i., there is a sparse cou- pling pattern introduced by the constraints.
In order to solve such problem in a distributed fashion, dual decomposition techniques are used. With a proper definition of the local variables (including states and control inputs) and the subsystem neighborhoods (i., the subsystems that can directly interact and communicate with the given subsystem), algo- rithms using first-order derivatives can be used to solve the dual problem in a distributed ix x Summary way. We propose three main distributed and hierarchical algorithms: distributed Han’s, dis- tributed accelerated proximal gradient, and hierarchical primal feasible using dual gradient algorithms. First, Fenchel duality is used to formulate the dual function, and the indicator function is used to relax the constraints.
The underlying algorithm is Han’s parallel method, which be- longs to the class of projected gradient algorithms. We show that the main subproblems of Han’s method have analytical solutions, and thus the algorithm involves only iterative lin- ear algebra computations, which are cheap and can be implemented in a distributed setting. The resulting distributed Han’s method is proved to generate results that are equivalent to those of the centralized counterpart, and thus to converge to the centralized MPC solution at every sampling step. Based on the convergence of the algorithm, feasibility and stability of the closed-loop system are inherited from the original centralized MPC setting.
Next, an accelerated proximal gradient algorithm is used to solve the dual problem that can be obtained by either Fenchel or Lagrange duality. This algorithm belongs to the class of accelerated gradient-based algorithms, which are known to achieve the best convergence rate among all gradient-based algorithms. We show that this accelerated proximal gradient algorithm can be considered as an extended and improved version of Han’s algorithm, as it converges one order of magnitude faster than the classical proximal gradient algorithm, which is equivalent to Han’s method for quadratic programs. Moreover, by using the in- dicator function, we can treat a problem with a mixed 2-norm and 1-norm cost function by constructing a differentiable dual function for the nondifferentiable original problem.
As the additional computation task for acceleration is only a linear combination of solu- tions obtained in the two preceding iterations, this accelerated algorithm only needs more memory to store previous iterates, while performing computations that are just as cheap as those of the classical version. Hence, this algorithm can be implemented in a distributed fashion similarly to the distributed Han’s algorithm. In the third method, a two-layer iterative hierarchical approach is used to solve the La- grange’s dual problem of the centralized MPC convex optimization problem. In the outer loop, the dual function is maximized using a projected gradient method in combination with an averaging scheme that provides bounds for the feasibility violation and the subop- timality of the primal function.
In the inner loop, a hierarchical optimization algorithm is used to provide either an exact or an approximate solution with a desired precision to the minimization of the Lagrangian function. We present two algorithms for the inner loop: a hierarchical conjugate gradient method and a distributed Jacobi optimization algorithm. This method can be applied to MPC problems that are feasible in the first sampling step and when the Slater condition holds (i., there exists a solution that strictly satisfies the inequality constraints). Using this method, the controller can generate feasible solutions of the MPC problem even when the dual solution does not reach optimality, and closed-loop stability is also achieved.
In addition to developing novel algorithms, this thesis also emphasizes implementation issues by considering an application of hydro power production control. We consider the control problem of a hydro power valley with nonlinear system dynamics. Different top- ics have been considered, including model reduction and reformulation of the MPC opti- mization problem so that the resulting optimization problem is suitable for applying the distributed algorithms developed in this thesis. We show that by implementing our pro- posed distributed accelerated proximal gradient algorithm, the distributed controller yields Summary xi a performance that is as good as that of a centralized controller, while the distributed algo- rithm uses remarkably less CPU time for computation than a centralized solver.
The results from this application example confirm and support the applicability of distributed MPC on large-scale complex systems. Samenvatting Vanwege de omvang en de structuur van regelaarsontwerpproblemen voor grootschalige complexe systemen zijn standaard benaderingen die gebruik maken van gecentraliseerde regelaars onuitvoerbaar, en in sommige gevallen onhandelbaar vanwege het aantal en de complexiteit van de interacties tussen de deelsystemen. Dit feit heeft hernieuwde belang- stelling voor en onderzoek naar gedistribueerde regeling van grootschalige complexe sys- temen gestimuleerd. Deze dissertatie beoogt hulpmiddelen te ontwikkelen voor het ontwerpen van gedistribueerde model-gebaseerde voorspellende regelaars voor lineaire systemen.