Multi-parametric Optimization and Control

Preface v 1 Introduction 1 1.1 Concepts of Optimization 1 1.1.1 Convex Analysis 1 1.1.2 Optimality Conditions 3 1.1.3 Interpretation of Lagrange Multipliers 4 1.2 Concepts of Multiparametric Programming 5 1.2.1 Basic Sensitivity Theorem 5 1.3 Polytopes 8 1.3.1 Approaches for the removal of redundant constraints 10 1.3.2 Projections 11 1.3.3 Modelling of the union of polytopes 12 1.4 Organization of the Book 13 Part I Multi-parametric Optimization 17 2 Multi-parametric linear programming 19 2.1 Solution properties 20 2.1.1 Local properties 20 2.1.2 Global properties 22 2.2 Degeneracy 24 2.3 Critical region definition 27 2.4 An Example: Chicago to Topeka 28 2.4.1 The deterministic solution 29 2.4.2 Considering demand uncertainty 30 2.4.3 Interpretation of the results 32 2.5 Literature review 32 3 Multi-parametric quadratic programming 39 3.1 Calculation of the parametric solution 40 3.1.1 Solution via the Basic Sensitivity Theorem 40 3.1.2 Solution via the parametric solution of the KKT conditions 41 3.2 Solution properties 42 3.2.1 Local properties 42 3.2.2 Global properties 42 3.2.3 Structural analysis of the parametric solution 44 3.3 Chicago to Topeka with quadratic distance cost 47 3.3.1 Interpretation of the results 50 3.4 Literature review 51 4 Solution strategies for mp-LP and mp-QP problems 55 4.1 General overview 56 4.2 The geometrical approach 57 4.2.1 Define a starting point _0 57 4.2.2 Fix _0 in problem (4.1), and solve the resulting QP 58 4.2.3 Identify the active set for the solution of the QP problem 58 4.2.4 Move outside the found critical region and explore the parameter space 59 4.3 The combinatorial approach 62 4.3.1 Pruning criterion 62 4.4 The connected-graph approach 63 4.5 Discussion 66 4.6 Literature Review 67 5 Multi-parametric mixed-integer linear programming 71 5.1 Solution properties 72 5.1.1 From mp-LP to mp-MILP problems 72 5.1.2 The properties 72 5.2 Comparing the solutions from different mp-LP problems 74 5.3 Multi-parametric integer linear programming 76 5.4 Chicago to Topeka featuring a purchase decision 78 5.4.1 Interpretation of the results 79 5.5 Literature review 82 6 Multi-parametric mixed-integer quadratic programming 85 6.1 Solution properties 86 6.1.1 From mp-QP to mp-MIQP problems 86 6.1.2 The properties 86 6.2 Comparing the solutions from different mp-QP problems 88 6.3 Envelope of solutions 90 6.4 Chicago to Topeka featuring quadratic cost and a purchase decision 91 6.4.1 Interpretation of the results 95 6.5 Literature review 95 7 Solution strategies for mp-MILP and mp-MIQP problems 99 7.1 General Framework 99 7.2 Global optimization 100 7.2.1 Introducing suboptimality 102 7.3 Branch-and-bound 103 7.4 Exhaustive enumeration 105 7.5 The comparison procedure 106 7.6 Discussion 111 7.6.1 Integer Handling 111 7.6.2 Comparison procedure 112 7.7 Literature Review 113 8 Solving multi-parametric programming problems using MATLAB(r) 117 8.1 An overview over the functionalities of POP 117 8.2 Problem solution 118 8.2.1 Solution of mp-QP problems 118 8.2.2 Solution of mp-MIQP problems 118 8.2.3 Requirements and Validation 118 8.2.4 Handling of equality constraints 119 8.2.5 Solving problem (7.2) 119 8.3 Problem generation 119 8.4 Problem library 120 8.4.1 Merits and shortcomings of the problem library 121 8.5 Graphical User Interface (GUI) 123 8.6 Computational performance for test sets 123 8.6.1 Continuous problems 124 8.6.2 Mixed-integer problems 127 8.7 Discussion 130 8.8 Acknowledgments 130 9 Other developments in multi-parametric optimization 133 9.1 Multi-parametric nonlinear programming 133 9.1.1 The convex case 134 9.1.2 The non-convex case 134 9.2 Dynamic programming via multi-parametric programming 135 9.2.1 Direct and indirect approaches 136 9.3 Multi-parametric linear complementarity problem 136 9.4 Inverse multi-parametric programming 137 9.5 Bilevel programming using multi-parametric programming 138 9.6 Multi-parametric multi-objective optimization 139 Part II Multi-parametric Model Predictive Control 147 10 Multi-parametric/explicit Model Predictive Control 149 10.1 Introduction 149 10.3 From discrete time state-space models to multi-parametric programming 154 10.4 Explicit LQR - an example of mp-MPC 158 10.4.1 Problem formulation and solution 158 10.4.2 Results and validation 159 10.5 Size of the solution and online computational effort 163 11 Extensions to other classes of problems 167 11.1 Hybrid Explicit MPC 167 11.1.1 Explicit Hybrid MPC - an example of mp-MPC 169 11.1.2 Results and validation 170 11.2 Disturbance rejection 174 11.2.1 Explicit disturbance rejection - an example of mp-MPC 175 11.2.2 Results and validation 176 11.3 Reference trajectory tracking 180 11.3.1 Reference tracking to LQR reformulation 181 11.3.2 Explicit reference tracking - an example of mp-MPC 184 11.3.3 Results and validation 186 11.4 Moving Horizon Estimation 190 11.4.1 Multi-parametric Moving Horizon Estimation 190 11.5 Other developments in explicit MPC 192 12 PAROC: PARametric Optimization and Control 197 12.1 Introduction 197 12.2 The PAROC Framework 198 12.2.1 'High Fidelity' Modeling and Analysis 198 12.2.2 Model Approximation 199 12.2.3 Multi-parametric Programming 208 12.2.4 Multi-parametric Moving Horizon Policies 208 12.2.5 Software Implementation and Closed-loop Validation 209 12.3 Case study: Distillation Column 210 12.3.1 'High Fidelity' Modeling 211 12.3.2 Model Approximation 212 12.3.3 Multi-parametric Programming, Control and Estimation 214 12.3.4 Closed loop validation 215 12.3.5 Conclusion 216 12.4 Case study: Simple Buffer Tank 216 12.5 The tank example 216 12.5.1 'High Fidelity' Dynamic Modeling 217 12.5.2 Model Approximation 217 12.5.3 Design of the Multi-parametric Model Predictive Controller 217 12.5.4 Closed-Loop Validation 218 12.5.5 Conclusion 220 12.6 Concluding remarks 220 A Appendix 225 A.1 Appendix for the mp-MPC Chapter 10 225 B Appendix 229 B.1 Appendix for the mp-MPC Chapter 11 229 B.1.1 Matrices for the mp-QP problem corresponding to the example of section 11.3.2 229