Interior Point Algorithms: Theory and Analysis

Interior Point Algorithms: Theory and Analysis......Page 5
Contents......Page 9
Preface......Page 15
List of Figures......Page 17
1.1 Introduction......Page 19
1.2.1 Basic notations......Page 23
1.2.2 Convex sets......Page 26
1.2.3 Real functions......Page 30
1.2.4 Inequalities......Page 32
1.3.1 System of linear equations......Page 33
1.3.3 Linear least-squares problem......Page 34
1.3.4 System of linear inequalities......Page 35
1.3.5 Linear programming (LP)......Page 36
1.3.6 Quadratic programming (QP)......Page 40
1.3.7 Linear complementarity problem (LCP)......Page 41
1.3.8 Positive semi-definite programming (PSP)......Page 42
1.3.10 Nonlinear complementarity problem (NCP)......Page 45
1.4 Algorithms and Computation Models......Page 46
1.4.1 Worst-case complexity......Page 47
1.4.2 Condition-based complexity......Page 49
1.4.3 Average complexity......Page 50
1.4.4 Asymptotic complexity......Page 51
1.5 Basic Computational Procedures......Page 52
1.5.2 Choleski decomposition method......Page 53
1.5.3 The Newton method......Page 54
1.5.5 Solving ball-constrained quadratic problem......Page 55
1.6 Notes......Page 56
1.7 Exercises......Page 57
2 Geometry of Convex Inequalities......Page 61
2.1.1 Center of gravity......Page 62
2.1.2 Ellipsoids......Page 63
2.2.1 Analytic center......Page 66
2.2.2 Dual potential function......Page 68
2.2.3 Analytic central-section inequalities......Page 71
2.3.1 Primal potential function......Page 77
2.3.2 Primal-dual potential function......Page 80
2.4.1 Primal potential function for LP......Page 81
2.4.3 Primal-dual potential function for LP......Page 84
2.4.4 Potential function for LCP......Page 85
2.4.5 Potential function for PSP......Page 86
2.5.1 Central path for LP......Page 88
2.5.3 Central path for PSP......Page 92
2.6 Notes......Page 93
2.7 Exercises......Page 95
3.1 Proximity to Analytic Center......Page 99
3.2.1 Dual Newton procedure......Page 105
3.2.2 Dual potential algorithm......Page 107
3.2.3 Central-section algorithm......Page 108
3.3.1 Primal Newton procedure......Page 112
3.3.2 Primal potential algorithm......Page 113
3.3.3 Affine scaling algorithm......Page 118
3.4 Primal-Dual (Symmetric) Algorithms......Page 119
3.4.1 Primal-dual Newton procedure......Page 120
3.4.2 Primal-dual potential algorithm......Page 121
3.5 Notes......Page 124
3.6 Exercises......Page 126
4.1 Karmarkar\'s Algorithm......Page 127
4.2 Path-Following Algorithm......Page 135
4.3 Potential Reduction Algorithm......Page 138
4.4 Primal-Dual (Symmetric) Algorithm......Page 144
4.5 Adaptive Path-Following Algorithms......Page 146
4.5.1 Predictor-corrector algorithm......Page 149
4.5.2 Wide-neighborhood algorithm......Page 152
4.6 Affine Scaling Algorithm......Page 154
4.7 Extensions to QP and LCP......Page 159
4.8 Notes......Page 160
4.9 Exercises......Page 163
5 Worst-Case Analysis......Page 165
5.1 Arithmetic Operation......Page 166
5.2 Termination......Page 170
5.2.1 Strict complementarity partition......Page 171
5.2.2 Project an interior point onto the optimal face......Page 173
5.3 Initialization......Page 175
5.3.1 A HSD linear program......Page 177
5.3.2 Solving (HSD)......Page 182
5.3.3 Further analysis......Page 185
5.4 Infeasible-Starting Algorithm......Page 187
5.5 Notes......Page 191
5.6 Exercises......Page 194
6 Average-Case Analysis......Page 197
6.1 One-Step Analysis......Page 199
6.1.1 High-probability behavior......Page 200
6.1.2 Proof of the theorem......Page 201
6.2 Random-Problem Analysis I......Page 205
6.2.1 High-probability behavior......Page 207
6.2.2 Random linear problems......Page 211
6.3 Random-Problem Analysis II......Page 214
6.3.1 Termination scheme......Page 215
6.3.2 Random model and analysis......Page 219
6.4 Notes......Page 224
6.5 Exercises......Page 226
7.1 Rate of Convergence......Page 227
7.1.1 Order of convergence......Page 228
7.1.3 Average order......Page 229
7.1.4 Error function......Page 230
7.2.1 Technical results......Page 231
7.2.2 Quadratic convergence......Page 234
7.3.1 Predictor-corrector algorithm for LCP......Page 236
7.3.2 Technical results......Page 238
7.3.3 Quadratic convergence......Page 240
7.4.1 Variant 1......Page 242
7.4.2 Variant 2......Page 243
7.5 Notes......Page 245
7.6 Exercises......Page 247
8.1 Analytic Centers of Nested Polytopes......Page 249
8.1.1 Recursive potential reduction algorithm......Page 250
8.1.2 Complexity analysis......Page 253
8.2 Convex (Non-Smooth) Feasibility......Page 254
8.2.1 Max-potential reduction......Page 256
8.2.2 Compute a new approximate center......Page 257
8.2.3 Convergence and complexity......Page 260
8.3 Positive Semi-Definite Programming......Page 264
8.3.1 Potential reduction algorithm......Page 266
8.3.2 Primal-dual algorithm......Page 272
8.4 Monotone Complementarity Problem......Page 274
8.4.1 A convex property......Page 275
8.4.2 A homogeneous MCP model......Page 278
8.4.3 The central path......Page 283
8.4.4 An interior-point algorithm......Page 286
8.5 Notes......Page 291
8.6 Exercises......Page 293
9.1 von Neumann Economic Growth Problem......Page 295
9.1.1 Max-potential of Γ(γ)......Page 297
9.1.2 Approximate analytic centers of Γ(γ)......Page 302
9.1.3 Central-section algorithm......Page 304
9.2 Linear Complementarity Problem......Page 309
9.2.1 Potential reduction algorithm......Page 310
9.2.2 A class of LCPs......Page 313
9.2.3 P-matrix LCP......Page 316
9.3 Generalized Linear Complementarity Problem......Page 321
9.3.1 Potential reduction algorithm......Page 322
9.3.2 Complexity analysis......Page 324
9.3.3 Further discussions......Page 327
9.4 Indefinite Quadratic Programming......Page 328
9.4.1 Potential reduction algorithm......Page 330
9.4.2 Generating an ε-KKT point......Page 334
9.4.3 Solving the ball-constrained QP problem......Page 336
9.5.1 Positive semi-definite relaxation......Page 343
9.5.2 Approximation analysis......Page 345
9.6 Notes......Page 350
9.7 Exercises......Page 353
10.1 Presolver......Page 355
10.2.1 Solving normal equation......Page 358
10.2.2 Solving augmented system......Page 361
10.2.3 Numerical phase......Page 363
10.2.4 Iterative method......Page 367
10.3.1 High-order predictor-corrector method......Page 368
10.3.2 Analysis of a high-order method......Page 370
10.4 Homogeneous and Self-Dual Method......Page 373
10.5.1 A pivoting algorithm......Page 374
10.5.2 Theoretical and computational issues......Page 376
10.6 Notes......Page 377
10.7 Exercises......Page 381
Bibliography......Page 383
Index......Page 427