Employing a closed set-theoretic foundation for interval computations, Global Optimization Using Interval Analysis simplifies algorithm construction and increases generality of interval arithmetic. This Second Edition contains an up-to-date discussion of interval methods for solving systems of nonlinear equations and global optimization problems. It expands and improves various aspects of its forerunner and features significant new discussions, such as those on the use of consistency methods to enhance algorithm performance. Provided algorithms are guaranteed to find and bound all solutions to these problems despite bounded errors in data, in approximations, and from use of rounded arithmetic.
Author(s): Eldon Hansen, G. William Walster
Series: Monographs and textbooks in pure and applied mathematics 264
Edition: 2nd ed., revised and expanded
Publisher: Marcel Dekker
Year: 2004
Language: English
Pages: 492
City: New York
Tags: Математика;Методы оптимизации;
Global Optimization Using Interval Analysis......Page 1
Contents......Page 12
Dedication......Page 9
Foreword......Page 10
Preface......Page 20
1.1 An Overview......Page 22
Contents......Page 0
1.3 The Scope Of This Book......Page 23
1.4 Virtues And Drawbacks Of Interval Mathematics......Page 24
1.4.1 Rump’s Example......Page 25
1.4.2 Real Examples......Page 26
1.4.3 Ease Of Use......Page 27
1.4.4 Performance Benchmarks......Page 29
1.4.5 Interval Virtues......Page 31
1.5 The Future Of Intervals......Page 34
2.1 Interval Numbers......Page 35
2.2 Notation And Relations......Page 36
2.3 Finite Interval Arithmetic......Page 37
2.4 Dependence......Page 38
2.4.1 Dependent Interval Arithmetic Operations......Page 39
2.5 Extended Interval Arithmetic......Page 41
3.1 Real Functions Of Intervals......Page 42
3.2 Interval Functions......Page 43
3.3 The Forms Of Interval Functions......Page 49
3.4 Splitting Intervals......Page 51
3.5 Endpoint Analysis......Page 52
3.6 Monotonic Functions......Page 55
3.7 Practicalevaluationofintervalfunctions......Page 57
3.8 Thick And Thin Functions......Page 60
4.1 Introduction......Page 62
4.2.1 Generality......Page 64
4.2.2 Speed Andwidth......Page 66
4.4 The Containment Constraint......Page 67
4.4.2 The (extended) Containment Constraint......Page 68
4.5.1 Historical Context......Page 69
4.5.2 A Simple Example:......Page 70
4.5.3 Cset Notation......Page 72
4.5.4 The Containment Set Of......Page 73
4.6 Arithmetic Over The Extended Real Numbers......Page 74
4.6.1 Empty Sets And Intervals......Page 75
4.7 Closed Interval Systems......Page 77
4.7.1 Closed Interval Algorithm Operations......Page 78
4.8.1 Containment Sets And Topological Closures......Page 81
4.8.2 Multi-valued Expressions......Page 84
4.8.3 Containment-set Inclusion Isotonicity......Page 91
4.8.4 Fundamental Theorem Of Interval Analysis......Page 92
4.8.5 Continuity......Page 96
4.9 Vector And Matrix Notation......Page 98
4.10 Conclusion......Page 101
5.1 Definitions......Page 102
5.2 Introduction......Page 103
5.3 The Solution Set......Page 105
5.4 Gaussian Elimination......Page 108
5.5 Failure Of Gaussian Elimination......Page 110
5.6 Preconditioning......Page 111
5.7 The Gauss-seidel Method......Page 115
5.8.1 Theoretical Algorithm......Page 118
5.8.2 Practical Procedure......Page 120
5.9 Combining Gauss-seidel And Hull Methods......Page 121
5.10 The Hull Of The Solution Set Of A'x=b......Page 122
5.11 A Special Preconditioning Matrix......Page 123
5.12 Overdetermined Systems......Page 124
6.1 Introduction......Page 125
6.2 A Single Inequality......Page 127
6.3 Systems Of Inequalities......Page 128
6.4 Ordering Inequalities......Page 132
6.5 Secondary Pivots......Page 133
6.6 Column Interchanges......Page 135
6.7 The Preconditioning Matrix......Page 136
6.8 Solving Inequalities......Page 138
7.1 Introduction......Page 141
7.2 Bounding The Remainder In Taylor Expansions......Page 142
7.3 The Multidimensional Case......Page 144
7.4 The Jacobian And Hessian......Page 150
7.5 Automatic Differentiation......Page 152
7.6 Sharper Bounds Using Taylor Expansions......Page 156
7.7 Expansions Using Slopes......Page 157
7.8 Slopes For Irrational Functions......Page 162
7.9 Multidimensional Slopes......Page 166
7.10 Higher Order Slopes......Page 168
7.11 Slopeexpansionsofnonsmoothfunctions......Page 169
7.12 Automatic Evaluation Of Slopes......Page 170
7.13 Equivalent Expansions......Page 174
8.1 Introduction......Page 176
8.2 A Procedure......Page 179
8.3 The Steps Of The Algorithm......Page 181
9.1 Introduction......Page 183
9.2 The Interval Newton Method......Page 185
9.3 A Procedure When......Page 189
9.4 Stopping Criteria......Page 192
9.5 The Algorithm Steps......Page 196
9.6 Properties Of The Algorithm......Page 198
9.7 A Numerical Example......Page 205
9.8 The Slope Interval Newton Method......Page 206
9.9 An Example Using The Slope Method......Page 208
9.10 Perturbed Problems......Page 209
10.1 Introduction......Page 211
10.2 Box Consistency......Page 212
10.3 Hull Consistency......Page 219
10.4 Analysis Of Hull Consistency......Page 221
10.5 Implementing Hull Consistency......Page 224
10.6 Convergence......Page 229
10.8 Splitting......Page 234
10.9 The Multidimensional Case......Page 236
10.10 Checking For Nonexistence......Page 237
10.11 Linear Combinations Of Functions......Page 240
10.12 Proving Existence......Page 242
10.13 Comparing Box And Hull Consistencies......Page 243
10.14 Sharpening Range Bounds......Page 246
10.15 Using Discriminants......Page 247
10.16 Nonlinear Equations Of One Variable......Page 250
11.1 Introduction......Page 252
11.2 Derivation Of Interval Newton Methods......Page 253
11.3 Variations Of The Method......Page 256
11.4 An Inner Iteration......Page 259
11.4.1 A Post-newton Inner Iteration......Page 262
11.5 Stopping Criteria......Page 263
11.6 The Termination Process......Page 268
11.7 Rate Of Progress......Page 270
11.8 Splitting A Box......Page 272
11.9 Analytic Preconditioning......Page 278
11.9.1 An Alternative Method......Page 280
11.10 The Initial Box......Page 281
11.11 A Linearization Test......Page 282
11.12 The Algorithm Steps......Page 283
11.13 Discussion Of The Algorithm......Page 287
11.14 One Newton Step......Page 288
11.15 Properties Of Interval Newton Methods......Page 289
11.16 A Numerical Example......Page 295
11.17 Perturbedproblemsandsensitivityanalysis......Page 296
11.18 Overdetermined Systems......Page 297
12.1 Introduction......Page 299
12.2 An Overview......Page 302
12.3 The Initial Box......Page 303
12.4 Use Of The Gradient......Page 304
12.5 An Upper Bound On The Minimum......Page 306
12.5.1 First Method......Page 307
12.5.2 Second Method......Page 309
12.5.3 Third Method......Page 310
12.5.4 Fourth Method......Page 311
12.5.5 An Example......Page 313
12.6 Updating The Upper Bound......Page 315
12.7 Convexity......Page 317
12.8 Using A Newton Method......Page 320
12.9 Termination......Page 321
12.10 Bounds On The Minimum......Page 323
12.11 The List Of Boxes......Page 324
12.12 Choosing A Box To Process......Page 325
12.13 Splitting A Box......Page 326
12.14 The Algorithm Steps......Page 328
12.16 Discussion Of The Algorithm......Page 332
12.17 A Numerical Example......Page 334
12.19 Nondifferentiable Problems......Page 335
12.20 Finding All Stationary Points......Page 336
13.1 Introduction......Page 337
13.2 The John Conditions......Page 339
13.3 Normalizing Lagrange Multipliers......Page 340
13.5 Solving The John Conditions......Page 344
13.6 Bounding The Lagrange Multipliers......Page 347
13.7 First Numerical Example......Page 351
13.8 Second Numerical Example......Page 354
13.9 Using Consistency......Page 356
14.1 Introduction......Page 357
14.2 The John Conditions......Page 361
14.3 An Upper Bound On The Minimum......Page 362
14.4 A Line Search......Page 363
14.5 Certainly Strict Feasibility......Page 366
14.6 Using The Constraints......Page 367
14.7 Using Taylor Expansions......Page 372
14.8 The Algorithm Steps......Page 374
14.9 Results From The Algorithm......Page 380
14.10 Discussion Of The Algorithm......Page 383
14.11 Peeling......Page 385
14.12 Pillow Functions......Page 389
14.13 Nondifferentiable Functions......Page 392
15.1 Introduction......Page 394
15.2 The John Conditions......Page 395
15.3 Bounding The Minimum......Page 397
15.4 Using Constraints To Bound The Minimum......Page 399
15.4.1 First Method......Page 400
15.4.2 Second Method......Page 403
15.5 Choice Of Variables......Page 404
15.6 Satisfying The Hypothesis......Page 407
15.7 A Numerical Example......Page 408
15.8 Using The Upper Bound......Page 411
15.9 Using The Constraints......Page 412
15.10 Information About A Solution......Page 415
15.11 Using The John Conditions......Page 417
15.12 The Algorithm Steps......Page 418
15.13 Results From The Algorithm......Page 424
15.14 Discussion Of The Algorithm......Page 428
15.15 Nondifferentiable Functions......Page 431
16.2 Linear Systems With Both Inequalities And Equations......Page 432
16.3 Existence Of A Feasible Point......Page 435
16.3.2 Case 2......Page 436
16.3.3 Case 3......Page 437
16.4 The Algorithm Steps......Page 439
17.1 Introduction......Page 445
17.2 The Basic Algorithms......Page 448
17.3 Tolerances......Page 449
17.5 Sharp Bounds For Perturbed Optimization Problems......Page 450
17.6 Validating Assumption 17.5.1......Page 454
17.7 First Numerical Example......Page 457
17.8 Second Numerical Example......Page 460
17.9 Third Numerical Example......Page 463
17.10 An Upper Bound......Page 465
17.11 Sharp Bounds For Perturbed Systems Of Nonlinear Equations......Page 467
18.1 Nondifferentiable Functions......Page 468
18.2 Integer And Mixed Integer Problems......Page 471
References......Page 473
