Multi-parametric Optimization and Control
Description
Multi-Parametric Optimization and Control provides comprehensive coverage of recent methodological developments for optimal model-based control through parametric optimization. It also shares real-world research applications to support deeper understanding of the material.
Researchers and practitioners can use the book as reference. It is also suitable as a primary or a supplementary textbook. Each chapter looks at the theories related to a topic along with a relevant case study. Topic complexity increases gradually as readers progress through the chapters. The first part of the book presents an overview of the state-of-the-art multi-parametric optimization theory and algorithms in multi-parametric programming. The second examines the connection between multi-parametric programming and model-predictive control--from the linear quadratic regulator over hybrid systems to periodic systems and robust control.
The third part of the book addresses multi-parametric optimization in process systems engineering. A step-by-step procedure is introduced for embedding the programming within the system engineering, which leads the reader into the topic of the PAROC framework and software platform. PAROC is anintegrated framework and platform for the optimization and advanced model-based control of process systems.
* Uses case studies to illustrate real-world applications for a better understanding of the concepts presented
* Covers the fundamentals of optimization and model predictive control
* Provides information on key topics, such as the basic sensitivity theorem, linear programming, quadratic programming, mixed-integer linear programming, optimal control of continuous systems, and multi-parametric optimal control
An appendix summarizes the history of multi-parametric optimization algorithms. It also covers the use of the parametric optimization toolbox (POP), which is comprehensive software for efficiently solving multi-parametric programming problems.
More details
Other editions
Additional editions
Persons
EFSTRATIOS N. PISTIKOPOULOS is the Director of the Texas A&M Energy Institute and a TEES Eminent Professor in the Artie McFerrin Department of Chemical Engineering at Texas A&M University. He holds a Ph.D. degree from Carnegie Mellon University (1988) and was with Shell Chemicals in Amsterdam before joining Imperial. He has authored or co-authored over 500 major research publications in the areas of modelling, control and optimization of process, energy and systems engineering applications, 15 books and 2 patents.
NIKOLAOS A. DIANGELAKIS is an Optimization Specialist at Octeract Ltd. He holds a PhD and MSc on Advanced Chemical Engineering from Imperial College London and was a member of the Multi-Parametric Optimization and Control group at Imperial and then Texas A&M since 2011. He is the co-author of 16 journal papers, 11 conference papers and 3 book chapters.
RICHARD OBERDIECK is a Technical Account Manager at Gurobi Optimization, LLC. He obtained a bachelor and MSc degrees from ETH Zurich in Switzerland (2009-1013), before pursuing a PhD in Chemical Engineering at Imperial College London, UK, which he completed in 2017. He has published 21 papers and 2 book chapters, has an h-index of 11 and was awarded the FICO Decisions Award 2019 in Optimization, Machine Learning and AI.
Content
Short Bios of the Authors xvii
Preface xxi
1 Introduction 1
1.1 Concepts of Optimization 1
1.1.1 Convex Analysis 1
1.1.1.1 Properties of Convex Sets 2
1.1.1.2 Properties of Convex Functions 2
1.1.2 Optimality Conditions 3
1.1.2.1 Karush-Kuhn-Tucker Necessary Optimality Conditions 5
1.1.2.2 Karun-Kush-Tucker First-Order Sufficient Optimality Conditions 5
1.1.3 Interpretation of Lagrange Multipliers 6
1.2 Concepts of Multi-parametric Programming 6
1.2.1 Basic Sensitivity Theorem 6
1.3 Polytopes 9
1.3.1 Approaches for the Removal of Redundant Constraints 11
1.3.1.1 Lower-Upper Bound Classification 12
1.3.1.2 Solution of Linear Programming Problem 13
1.3.2 Projections 13
1.3.3 Modeling of the Union of Polytopes 14
1.4 Organization of the Book 16
References 16
Part I Multi-parametric Optimization 19
2 Multi-parametric Linear Programming 21
2.1 Solution Properties 22
2.1.1 Local Properties 23
2.1.2 Global Properties 25
2.2 Degeneracy 28
2.2.1 Primal Degeneracy 29
2.2.2 Dual Degeneracy 30
2.2.3 Connections Between Degeneracy and Optimality Conditions 31
2.3 Critical Region Definition 32
2.4 An Example: Chicago to Topeka 33
2.4.1 The Deterministic Solution 34
2.4.2 Considering Demand Uncertainty 35
2.4.3 Interpretation of the Results 36
2.5 Literature Review 38
References 39
3 Multi-Parametric Quadratic Programming 45
3.1 Calculation of the Parametric Solution 47
3.1.1 Solution via the Basic Sensitivity Theorem 47
3.1.2 Solution via the Parametric Solution of the KKT Conditions 48
3.2 Solution Properties 49
3.2.1 Local Properties 49
3.2.2 Global Properties 50
3.2.3 Structural Analysis of the Parametric Solution 52
3.3 Chicago to Topeka with Quadratic Distance Cost 55
3.3.1 Interpretation of the Results 56
3.4 Literature Review 61
References 63
4 Solution Strategies for mp-LP and mp-QP Problems 67
4.1 General Overview 68
4.2 The Geometrical Approach 70
4.2.1 Define A Starting Point ¿¿¿¿0 70
4.2.2 Fix ¿¿¿¿0 in Problem (4.1), and Solve the Resulting QP 71
4.2.3 Identify The Active Set for The Solution of The QP Problem 72
4.2.4 Move Outside the Found Critical Region and Explore the Parameter Space 72
4.3 The Combinatorial Approach 75
4.3.1 Pruning Criterion 76
4.4 The Connected-Graph Approach 78
4.5 Discussion 81
4.6 Literature Review 83
References 85
5 Multi-parametric Mixed-integer Linear Programming 89
5.1 Solution Properties 90
5.1.1 From mp-LP to mp-MILP Problems 90
5.1.2 The Properties 91
5.2 Comparing the Solutions from Different mp-LP Problems 92
5.2.1 Identification of Overlapping Critical Regions 93
5.2.2 Performing the Comparison 95
5.2.3 Constraint Reversal for Coverage of Parameter Space 95
5.3 Multi-parametric Integer Linear Programming 96
5.4 Chicago to Topeka Featuring a Purchase Decision 99
5.4.1 Interpretation of the Results 99
5.5 Literature Review 102
References 103
6 Multi-parametric Mixed-integer Quadratic Programming 107
6.1 Solution Properties 109
6.1.1 From mp-QP to mp-MIQP Problems 109
6.1.2 The Properties 109
6.2 Comparing the Solutions from Different mp-QP Problems 110
6.2.1 Identification of overlapping critical regions 112
6.2.2 Performing the Comparison 112
6.3 Envelope of Solutions 113
6.4 Chicago to Topeka Featuring Quadratic Cost and A Purchase Decision 114
6.4.1 Interpretation of the Results 115
6.5 Literature Review 119
References 121
7 Solution Strategies for mp-MILP and mp-MIQP Problems 125
7.1 General Framework 126
7.2 Global Optimization 127
7.2.1 Introducing Suboptimality 129
7.3 Branch-and-Bound 130
7.4 Exhaustive Enumeration 133
7.5 The Comparison Procedure 134
7.5.1 Affine Comparison 135
7.5.2 Exact Comparison 137
7.6 Discussion 138
7.6.1 Integer Handling 138
7.6.2 Comparison Procedure 141
7.7 Literature Review 142
References 144
8 Solving Multi-parametric Programming Problems Using MATLAB® 147
8.1 An Overview over the Functionalities of POP 148
8.2 Problem Solution 148
8.2.1 Solution of mp-QP Problems 148
8.2.2 Solution of mp-MIQP Problems 148
8.2.3 Requirements and Validation 149
8.2.4 Handling of Equality Constraints 149
8.2.5 Solving Problem (7.2) 149
8.3 Problem Generation 150
8.4 Problem Library 151
8.4.1 Merits and Shortcomings of The Problem Library 152
8.5 Graphical User Interface (GUI) 153
8.6 Computational Performance for Test Sets 154
8.6.1 Continuous Problems 154
8.6.2 Mixed-integer Problems 154
8.7 Discussion 156
Acknowledgments 162
References 162
9 Other Developments in Multi-parametric Optimization 165
9.1 Multi-parametric Nonlinear Programming 165
9.1.1 The Convex Case 166
9.1.2 The Non-convex Case 167
9.2 Dynamic Programming via Multi-parametric Programming 167
9.2.1 Direct and Indirect Approaches 169
9.3 Multi-parametric Linear Complementarity Problem 170
9.4 Inverse Multi-parametric Programming 171
9.5 Bilevel Programming Using Multi-parametric Programming 172
9.6 Multi-parametric Multi-objective Optimization 173
References 174
Part II Multi-parametric Model Predictive Control 187
10 Multi-parametric/Explicit Model Predictive Control 189
10.1 Introduction 189
10.2 From Transfer Functions to Discrete Time State-Space Models 191
10.3 From Discrete Time State-Space Models to Multi-parametric Programming 195
10.4 Explicit LQR - An Example of mp-MPC 200
10.4.1 Problem Formulation and Solution 200
10.4.2 Results and Validation 202
10.5 Size of the Solution and Online Computational Effort 206
References 207
11 Extensions to Other Classes of Problems 211
11.1 Hybrid Explicit MPC 211
11.1.1 Explicit Hybrid MPC - An Example of mp-MPC 213
11.1.2 Results and Validation 215
11.2 Disturbance Rejection 219
11.2.1 Explicit Disturbance Rejection - An Example of mp-MPC 220
11.2.2 Results and Validation 222
11.3 Reference Trajectory Tracking 222
11.3.1 Reference Tracking to LQR Reformulation 227
11.3.2 Explicit Reference Tracking - An Example of mp-MPC 230
11.3.3 Results and Validation 232
11.4 Moving Horizon Estimation 232
11.4.1 Multi-parametric Moving Horizon Estimation 232
11.4.1.1 Current State 237
11.4.1.2 Recent Developments 237
11.4.1.3 Future Outlook 238
11.5 Other Developments in Explicit MPC 239
References 240
12 PAROC: PARametric Optimization and Control 243
12.1 Introduction 243
12.2 The PAROC Framework 246
12.2.1 "High Fidelity" Modeling and Analysis 247
12.2.2 Model Approximation 247
12.2.2.1 Model Approximation Algorithms: A User Perspective Within the PAROC Framework 247
12.2.3 Multi-parametric Programming 257
12.2.4 Multi-parametric Moving Horizon Policies 259
12.2.5 Software Implementation and Closed-LoopValidation 259
12.2.5.1 Multi-parametric Programming Software 259
12.2.5.2 Integration of PAROC in gPROMS® ModelBuilder 260
12.3 Case Study: Distillation Column 261
12.3.1 "High Fidelity" Modeling 262
12.3.2 Model Approximation 264
12.3.3 Multi-parametric Programming, Control, and Estimation 265
12.3.4 Closed-Loop Validation 267
12.3.5 Conclusion 268
12.4 Case Study: Simple Buffer Tank 269
12.5 The Tank Example 269
12.5.1 "High Fidelity" Dynamic Modeling 269
12.5.2 Model Approximation 270
12.5.3 Design of the Multi-parametric Model Predictive Controller 271
12.5.4 Closed-Loop Validation 272
12.5.5 Conclusion 273
12.6 Concluding Remarks 273
References 273
A Appendix for the mp-MPC Chapter 10 281
B Appendix for the mp-MPC Chapter 11 285
B.1 Matrices for the mp-QP Problem Corresponding to the
Example of Section 11.3.2 285
Index 291
1
Introduction
In this chapter, the fundamental concepts of mathematical optimization and multi-parametric programming will be presented. Such concepts will be the foundation towards the development of state-of-the-art multi-parametric programming strategies and applications, which will appear in this book in the next chapters.
1.1 Concepts of Optimization
1.1.1 Convex Analysis
This section presents the idea of convex sets and introduces function convexity. Convexity plays a vital role to establish the required properties which will enable a multi-parametric solution to hold. In this setting, the following definitions are established.
1.1.1.1 Properties of Convex Sets
Let and be convex sets defined in . Then
- The intersection of is a convex set.
- The summation of two convex sets is a convex set.
- Let be a real number. The product is a convex set.
Examples of convex sets include lines, polytopes and polyhedra, and open and closed halfspaces.
1.1.1.2 Properties of Convex Functions
- Let be convex functions defined on a convex subset . Their summation (1.5) is convex, and if at least of one is a strictly convex function, then their summation is strictly convex.
- Let a be a positive number and be a (strictly) convex function defined in a convex subset . Then the product is (strictly) convex.
- Let be a (strictly) convex function defined in , and be an increasing convex function defined on the range of in . Then, the composite function defined in is a (strictly) convex function.
- Let be convex functions defined on a convex subset . If these functions are bounded from above, their pointwise supremum (1.6) is a convex function on .
- Let be concave functions defined on a convex subset . If these functions are bounded from below, their pointwise infimum (1.7) is a concave function on .
1.1.2 Optimality Conditions
We introduce the following definitions for the solution of general nonlinear optimization problems:
A constrained nonlinear optimization problem, which aims to minimize a real valued function subject to the inequality constraints and equality constraints is denoted as
(1.10)Problem (1.10) is a nonlinear optimization problem, if and only if, at least one of is a nonlinear function. We assume that the aforementioned functions are continuous and differentiable.
The first-order constraint qualifications that will be presented in the following text are necessary prerequisites to identify whether a feasible point is a local optimum of the function .
- Linear independence constraint qualification: The gradients for all and for all are linearly independent.
- Slater constraint qualification: The constraints for all are pseudo-convex1 at , while the constraints for all are quasi-convex or quasi-concave.2 In addition, the gradients are linearly independent and there exists such that and .
1.1.2.1 Karush-Kuhn-Tucker Necessary Optimality Conditions
Let and be differentiable at a feasible solution , and let have continuous partial derivatives at . In addition, let be the number of active inequality constraints at . Then if one of the aforementioned constraint qualifications hold, there exist Lagrange multipliers such that
(1.11)These conditions are the Karush-Kuhn-Tucker (KKT) Necessary Conditions and they are the basis for the solution of nonlinear optimization problems.
1.1.2.2 Karun-Kush-Tucker First-Order Sufficient Optimality Conditions
Consider the sets and . Then, if the following conditions hold:
- is pseudo-convex at with respect to all other feasible points x.
- for all are quasi-convex at with respect to all other feasible points x.
- for all are quasi-convex at with respect to all other feasible points x.
- for all are quasi-concave at with respect to all other feasible points x.
then is a global optimum of problem (1.10). If the aforementioned conditions hold only within a ball of radius around , then is a local optimum of problem (1.10).
1.1.3 Interpretation of Lagrange Multipliers
Consider the following problem:
(1.12)Let be the global minimum of problem (1.12), and that the gradient of the equality constraints are linearly independent. In addition, assume that the corresponding Lagrange multiplier is . The vector is a perturbation vector. The solution of problem (1.12) is a function of the perturbation vector along with the multiplier. Hence, the Lagrange function can be written as
(1.13)Calculating the partial derivative of the Lagrange function with respect to the perturbation vector, we have
(1.14)which yields
(1.15)Hence, the Lagrange multipliers can be interpreted as a measure of sensitivity of the objective function with respect to the perturbation vector of the constraints at the optimum point .
1.2 Concepts of Multi-parametric Programming
1.2.1 Basic Sensitivity Theorem
Having the essentials of optimization for the purposes of this book covered, the objective of this subchapter is to introduce the role of parameters in an optimization formulation. In this context, the following multi-parametric programming problem is considered:
(1.16)where is the vector of the continuous optimization variables, is the vector of the uncertain parameters, and the sets , correspond to the inequality and equality constraint sets, respectively.
If there exist Lagrange multipliers, and , such that the first-order KKT conditions hold, then we have:
(1.17)and the vector is defined as follows:
(1.18)Furthermore, if there exists for which
(1.19)the Basic Sensitivity Theorem holds, and it is identically satisfied for a neighborhood around and can be differentiated with respect to to yield explicit expressions for the partial derivatives of the vector function .
The first-order estimate of the variation of an isolated local solution x() of (1.16) and the associated unique Lagrange multipliers and can be approximated, given that is known and that is available.
In particular, let be the concatenation of the vectors and . The first-order Taylor expansion of the vector F around can be expressed as follows:
(1.20)Under the assumptions and the principles of the Basic Sensitivity Theorem, in a neighborhood of the first-order KKT conditions hold and the value of F() around remains zero. For systems that consist of polynomial objective functions of up to second degree and linear constraints, with respect to the optimization variables and the uncertain parameters, the first-order Taylor expansion is exact. Hence, the exact multi-parametric solution can be obtained for the following multi-parametric quadratic programming problem
(1.21)where matrices , and , , and the scalars , correspond to the and inequality and equality constraints of the sets and , respectively. This problem serves as the basis that will be discussed in Part I, where its solution properties and solution strategies among other things are in focus. Part II then focusses on the application of such problems to optimal control, as the use of parameters enables the formulation of explicit model predictive control problems.
1.3 Polytopes
Multi-parametric programming is intimately related to the properties and operations applicable to polytopes. In the following, some basic definitions on polytopes are stated, which are used throughout the book.
A schematic representation of a polytope is given in Figure 1.1.
Figure 1.1 A schematic representation of a two-dimensional polytope .
In addition to Definition...
