Fast Numerical Methods for Mixed-Integer Nonlinear Model-Predictive Control

Cover......Page 1
Advances in Numerical Mathematics......Page 3
Fast Numerical Methods
for Mixed-Integer Nonlinear
Model-Predictive Control......Page 4
ISBN 9783834815729......Page 5
Acknowledgments......Page 6
Abstract......Page 8
Contents......Page 10
List of Figures......Page 14
List of Tables......Page 18
List of Acronyms......Page 20
0 Introduction......Page 22
Model–Predictive Control......Page 23
Mixed–Integer Programming......Page 24
Mixed–Integer Model–Predictive Control......Page 25
Mixed–Integer Nonlinear Model Predictive Control......Page 26
Convexification and Relaxation......Page 27
Block Structured Linear Algebra......Page 28
Case Studies......Page 29
Realtime Predictive Cruise Control......Page 30
Thesis Overview......Page 31
Computing Environment......Page 33
1.1 Problem Formulations......Page 34
1.2.1 Indirect Methods......Page 39
1.2.2 Dynamic Programming......Page 40
1.2.3 Direct Single Shooting......Page 42
1.2.4 Direct Collocation......Page 43
1.3 The Direct Multiple Shooting Method for OptimalControl......Page 45
1.3.1 Control Discretization......Page 46
1.3.2 State Parameterization......Page 47
1.3.4 The Nonlinear Problem......Page 49
1.4 Summary......Page 50
2.1 Problem Formulations......Page 52
2.2.1 Discretization to a Mixed–Integer Nonlinear Program......Page 53
2.2.3 Branching Techniques......Page 55
2.2.4 Outer Approximation......Page 57
2.2.5 Reformulations......Page 58
2.3.1 Convexified and Relaxed Problems......Page 62
2.3.2 The Bang–Bang Principle......Page 65
2.3.3 Bounds on the Objective Function......Page 67
2.3.4 Bounds on the Infeasibility......Page 68
2.4 Rounding Strategies......Page 69
2.4.1 The Linear Case......Page 70
2.4.2 The Nonlinear Case......Page 72
2.4.3 The Discretized Case......Page 73
2.5.1 Frequent Switching......Page 74
2.5.2 Switch Costs in a MILP Formulation......Page 75
2.5.3 Switch Costs for Outer Convexification......Page 76
2.5.4 Reformulations......Page 77
2.6 Summary......Page 81
3.1.1 Definitions......Page 82
3.1.2 First Order Necessary Optimality Conditions......Page 84
3.1.3 Second Order Conditions......Page 86
3.2 Sequential Quadratic Programming......Page 87
3.2.1 Basic Algorithm......Page 88
3.2.2 The Full Step Exact Hessian SQP Method......Page 89
3.2.3 The Gauß-Newton Approximation......Page 91
3.2.4 BFGS Hessian Approximation......Page 92
3.2.5 Local Convergence......Page 93
3.2.6 Termination Criterion......Page 94
3.3.1 Analytical Derivatives......Page 95
3.3.2 Finite Difference Approximations......Page 96
3.3.3 Complex Step Approximation......Page 97
3.3.4 Automatic Differentiation......Page 98
3.3.5 Second Order Derivatives......Page 100
3.4.1 Runge–Kutta Methods for ODE IVPs......Page 101
3.4.2 Sensitivities of Initial Value Problems......Page 104
3.5 Summary......Page 108
4.1.1 Conventional NMPC Approach......Page 110
4.1.2 The Idea of Real–Time Iterations......Page 112
4.2.1 Parametric Sequential Quadratic Programming......Page 113
4.2.3 Moving Horizons......Page 116
4.2.4 Local Feedback Laws......Page 118
4.2.5 Immediate Feedback......Page 119
4.3.1 Fixed Control Formulation......Page 120
4.3.2 Contraction Constants......Page 121
4.3.3 Contractivity......Page 122
4.4 Mixed–Integer Model Predictive Control......Page 124
4.4.1 Mixed–Integer Real–Time Iterations......Page 126
4.4.2 Rounding Schemes......Page 127
4.4.4 Contractivity......Page 128
4.4.5 Upper Bounds on the Sampling Time......Page 134
4.5 Summary......Page 136
5.1.1 The Standard Formulation after Outer Convexification......Page 138
5.1.2 Outer Convexification of Constraints......Page 139
5.1.4 Perspective Cuts......Page 140
5.2 Lack of Constraint Qualification......Page 141
5.2.1 Constraint Qualifications......Page 142
5.2.2 Checking Constraint Qualifications......Page 143
5.2.3 Ill–Conditioning......Page 144
5.2.4 Infeasible and Suboptimal Steps......Page 145
5.2.5 Cycling of Active Set Methods......Page 146
5.3 Mathematical Programs with Vanishing Constraints......Page 148
5.3.1 Problem Formulations......Page 149
5.4 An MPVC Lagrangian Framework......Page 152
5.4.1 Notation and Auxiliary Problems......Page 153
5.4.2 Lack of Constraint Qualification for MPVCs......Page 155
5.4.3 An MPVC Lagrangian Framework......Page 157
5.5 Summary......Page 160
6.1 SQP for Nonconvex Programs......Page 162
6.1.1 SQP on Nonconvex Feasible Sets......Page 163
6.1.2 Nonconvex Subproblems......Page 164
6.1.3 SQP for a Special Family of MPVCs......Page 165
6.2.1 Parametric Quadratic Programs......Page 169
6.3 A Primal–Dual Parametric Active Set Strategy......Page 172
6.3.1 Active Set Methods......Page 173
6.3.2 A Primal–Dual Parametric Active Set Strategy......Page 174
6.3.3 Proof of the Algorithm......Page 178
6.3.4 Finding a Feasible Initializer......Page 181
6.3.5 Parametric Quadratic Programming for SQP MethodsLinearizations......Page 183
6.4 Parametric Quadratic Programming for NonconvexProblems......Page 184
6.4.1 Nonconvex Primal Strategy......Page 185
6.4.2 Nonconvex Dual Strategy......Page 187
6.4.3 A Heuristic for Global Optimality......Page 188
6.4.4 Continuations for a Parametric Active Set Method......Page 191
6.5 Summary......Page 193
7.1 Block Structure......Page 196
7.2.1 Condensing......Page 200
7.2.2 Riccati Recursion......Page 203
7.2.4 LU Factorization......Page 205
7.3.1 Fixed Variables Step......Page 206
7.3.2 Hessian Projection Step......Page 207
7.3.3 Schur Complement Step......Page 208
7.3.4 Block Tridiagonal Factorization and Backsolve......Page 209
7.3.5 Efficient Implementation......Page 211
7.3.6 Testing for Degeneracy and Boundedness......Page 212
7.3.7 A Simplification based on Conjugacy......Page 215
7.4 Properties and Extensions......Page 216
7.4.1 Applicability......Page 217
7.4.3 Stability......Page 218
7.4.4 A Dynamic Programming Interpretation......Page 219
7.5.1 Floating–Point Operations......Page 221
7.6 Summary......Page 224
8.1 Matrix Updates Overview......Page 226
8.1.1 Existing Techniques......Page 227
8.1.2 Orthogonal Eliminations......Page 229
8.2.1 Preliminaries......Page 232
8.2.2 Adding a Simple Bound......Page 236
8.2.3 Adding a Point Constraint......Page 241
8.2.4 Deleting a Simple Bound......Page 243
8.2.5 Deleting a Point Constraint......Page 246
8.3 Modifying the Block Tridiagonal Factorization......Page 250
8.3.1 A Rank 1 Update......Page 251
8.3.2 A Rank 1 Downdate......Page 253
8.4 Summary......Page 256
9 Numerical Results......Page 258
9.1.1 Problem Formulation......Page 259
9.1.2 Optimal Solutions......Page 261
9.1.3 Switch Cost Formulation......Page 264
9.1.4 Switch Cost Penalizing and Constraining Solutions......Page 265
9.1.5 Summary......Page 266
9.2.1 Problem Formulation......Page 270
9.2.2 Constants......Page 273
9.2.3 Sampling Time Estimate......Page 275
9.2.4 Observations......Page 278
9.2.5 Summary......Page 279
9.3.1 A Multiple Robot Path Coordination Problem......Page 284
9.3.2 NLP Problem Formulation and Solution......Page 285
9.3.3 Dynamic Optimal Control Problem Formulation and Solution......Page 291
9.3.4 Summary......Page 293
9.4.1 Vehicle Model......Page 295
9.4.2 Mixed–Integer Time–Optimal Control Problem......Page 300
9.4.4 Comparison of Runtimes......Page 304
9.4.5 Summary......Page 309
9.5.1 Overview......Page 310
9.5.2 Dynamic Truck Model......Page 311
9.5.3 Environment Model......Page 314
9.5.4 Design of a Performance Index......Page 318
9.5.5 Mixed–Integer Optimal Control Problem......Page 319
9.5.6 Exemplary Mixed–Integer Optimal Control Scenarios......Page 325
9.5.7 Mixed–Integer Predictive Control Results......Page 330
9.5.8 Computational Demand......Page 331
9.5.9 Summary......Page 340
A.1.1 Software Architecture......Page 342
A.1.2 Description, Implementation, and Solution of a Problem......Page 344
A.1.3 User Interface......Page 354
A.2.1 Software Architecture......Page 361
A.2.2 C Interface......Page 364
Bibliography......Page 368