Randomized Algorithms for Analysis and Control of Uncertain Systems

1852335246......Page 1
Contents......Page 11
1.1 Uncertainty and robustness......Page 16
1.2 Probability and robustness of uncertain systems......Page 17
1.3 Some historical notes......Page 18
1.4 Structure of the book......Page 19
2.1.1 Probability space......Page 23
2.1.2 Real and complex random variables......Page 24
2.1.4 Expected value and covariance......Page 25
2.2 Marginal and conditional densities......Page 26
2.3 Univariate and multivariate density functions......Page 27
2.4 Convergence of random variables......Page 28
3.1.1 Vector norms and balls......Page 29
3.1.2 Matrix norms and balls......Page 30
3.2.1 Deterministic signals......Page 32
3.2.2 Stochastic signals......Page 33
3.3 Linear time-invariant systems......Page 34
3.4 Linear matrix inequalities......Page 36
3.5 Computing H[sub(2)] and H[sub(∞)] norms......Page 38
3.6 Modeling uncertainty of linear systems......Page 40
3.7.1 Dynamic uncertainty and stability radii......Page 44
3.7.2 Structured singular value and μ analysis......Page 47
3.7.3 Computation of bounds on μ[sub(D)]......Page 49
3.7.4 Rank-one μ problem and Kharitonov theory......Page 50
3.8 Robustness analysis with parametric uncertainty......Page 51
4.1 H[sub(∞)] design......Page 57
4.1.1 Regular H[sub(∞)] problem......Page 61
4.1.2 Alternative LMI solution for H[sub(∞)] design......Page 62
4.1.3 μ synthesis......Page 64
4.2 H[sub(2)] design......Page 66
4.2.1 Linear quadratic regulator......Page 68
4.2.2 Quadratic stabilizability and guaranteed-cost control......Page 70
4.3 Discussion......Page 72
5. Some Limits of the Robustness Paradigm......Page 73
5.1.1 Decidable and undecidable problems......Page 74
5.1.2 Time complexity......Page 75
5.1.3 NP-completeness and NP-hardness......Page 76
5.1.4 Some NP-hard problems in systems and control......Page 77
5.2 Conservatism of robustness margin......Page 79
5.3 Discontinuity of robustness margin......Page 82
6.1 Performance function for robustness......Page 85
6.2 The good and the bad sets......Page 88
6.3 Probabilistic robustness analysis......Page 91
6.4 Distribution-free robustness......Page 101
7.1 Probability and expected value estimation......Page 104
7.2 Monte Carlo methods for integration......Page 108
7.3 Monte Carlo methods for optimization......Page 110
7.4.1 Discrepancy and error bounds for integration......Page 111
7.4.2 One-dimensional low discrepancy sequences......Page 114
7.4.3 Low discrepancy sequences for n > 1......Page 115
7.4.4 Dispersion and point sets for optimization......Page 117
8.1 Probabilistic robustness via randomized algorithms......Page 120
8.2 Randomized algorithms for analysis......Page 121
8.3 Randomized algorithms for synthesis......Page 123
8.3.1 Randomized algorithms for average synthesis......Page 124
8.3.2 Randomized algorithms for robust synthesis......Page 125
8.4 Computational complexity of randomized algorithms......Page 127
9.1 Probability inequalities......Page 129
9.2 Deviation inequalities for sums of random variables......Page 131
9.3 Sample size bounds for probability estimation......Page 134
9.4 Sample size bounds for estimation of extrema......Page 139
10.1 Deviation inequalities for finite families......Page 143
10.2 Vapnik–Chervonenkis theory......Page 144
10.2.1 Computing the VC dimension......Page 149
10.3 A learning theory approach for control design......Page 151
11.1 A paradigm for probabilistic robust design......Page 161
11.1.1 Technical preliminaries......Page 163
11.2 Sequential algorithms for LQR design......Page 165
11.2.1 Violation function for LQR......Page 166
11.2.2 Update rule and subgradient computation......Page 167
11.2.3 Iterative algorithms and convergence results......Page 168
11.2.4 Further convergence properties......Page 177
11.3 Sequential algorithm for uncertain LMIs......Page 178
11.4 Ellipsoid algorithm for uncertain LMIs......Page 184
11.5 Sequential algorithm for (possibly) unfeasible LMIs......Page 186
12.1 Classical and probabilistic LPV settings......Page 191
12.2 Quadratic LPV L[sub(2)] control problem......Page 193
12.3 Randomized algorithm for LPV systems......Page 195
12.3.1 Violation function for LPV systems......Page 196
12.3.2 Update rule and subgradient computation......Page 197
12.3.3 Iterative algorithm and convergence results......Page 198
13. Scenario Approach for Probabilistic Robust Design......Page 202
13.1 Three robustness paradigms......Page 203
13.1.1 Advantages of scenario design......Page 204
13.2 Scenario-robust design......Page 205
14.1 Random number generators......Page 210
14.1.1 Linear congruential generators......Page 211
14.1.2 Linear and nonlinear random number generators......Page 212
14.2 Non uniform random variables......Page 215
14.2.1 Statistical tests for pseudo-random numbers......Page 219
14.3 Methods for multivariate random generation......Page 221
14.3.1 Rejection methods......Page 222
14.3.2 Conditional density method......Page 226
14.4.1 Random walks on graphs......Page 227
14.4.2 Asymptotic methods for continuous distributions......Page 229
14.4.3 Uniform sampling in a convex body......Page 231
15.1 Radially symmetric densities......Page 233
15.2 Statistical properties of l[sub(p)] radial real vectors......Page 234
15.3 Statistical properties of l[sub(p)] radial complex vectors......Page 237
15.4 l[sub(p)] radial vectors and uniform distribution in B[sub(∥·∥p)]......Page 239
15.5 Statistical properties of l[sup(W)][sub(2)] radial vectors......Page 241
16.1 Rejection methods for uniform vector generation......Page 247
16.2 The generalized Gamma density......Page 249
16.3 Uniform sample generation of real vectors......Page 251
16.4 Uniform sample generation of complex vectors......Page 255
17.1.1 Hilbert–Schmidt l[sub(p)] radial matrix densities......Page 257
17.1.2 l[sub(p)] induced radial matrix densities......Page 258
17.2.1 Real matrices with l[sub(1)] and l[sub(∞)] induced densities......Page 259
17.2.2 Complex matrices with l[sub(1)] and l[sub(∞)] induced densities......Page 262
17.3.1 Positive definite matrices with σ radial densities......Page 263
17.3.2 Real σ radial matrix densities......Page 269
17.3.3 Complex σ radial matrix densities......Page 274
17.4 Statistical properties of unitarily invariant matrices......Page 279
18.2 Uniform sampling in l[sub(1)] and l[sub(∞)] induced norm balls......Page 282
18.3 Rejection methods for uniform matrix generation......Page 283
18.4.1 Sample generation of singular values......Page 285
18.4.2 Uniform sample generation of unitary matrices......Page 293
18.5.1 Sample generation of singular values......Page 294
18.5.2 Uniform sample generation of orthogonal matrices......Page 297
19.1.1 Network model......Page 299
19.1.2 Cost function......Page 301
19.1.3 Robustness analysis for symmetric single bottleneck......Page 302
19.1.4 Randomized algorithms for non symmetric case......Page 304
19.1.5 Monte Carlo simulation......Page 305
19.1.6 Quasi-Monte Carlo simulation......Page 306
19.1.7 Numerical results......Page 307
19.2 Probabilistic robustness of a flexible structure......Page 309
19.3 Stability of quantized sampled-data systems......Page 313
19.3.1 Problem setting......Page 314
19.3.2 Randomized algorithm and violation function......Page 317
19.3.3 Numerical experiments......Page 319
A.1 Transformations between random matrices......Page 324
A.2 Jacobians of transformations......Page 325
A.3 Selberg integral......Page 326
A.4 Dyson–Mehta integral......Page 327
List of Symbols......Page 328
References......Page 331
G......Page 347
N......Page 348
S......Page 349
V......Page 350