ABSTRACT
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200 6.2 Classification of Parallel Algorithms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
6.2.1 Parallelism Due to Algorithm Structure: Iterative Projection Algorithms . . . . . . . 201 6.2.1.1 Parallel Computing with Iterative Algorithms . . . . . . . . . . . . . . . . . . . . . . . . 203
6.2.2 Parallelism Due to Problem Structure: Model Decomposition and Interior Point Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 6.2.2.1 Model Decomposition Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204 6.2.2.2 Interior Point Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
6.3 General Framework of Projection Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206 6.3.1 Orthogonal Projections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206 6.3.2 Bregman Projections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207 6.3.3 Projection Algorithmic Schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
6.3.3.1 Sequential Projections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208 6.3.3.2 The String Averaging Algorithmic Structure . . . . . . . . . . . . . . . . . . . . . . . . . 208
6.3.4 Block-Iterative Component Averaging. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210 6.4 General Framework of Model Decompositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
6.4.1 Problem Modifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213 6.4.1.1 Modifier I: Penalty or Barrier Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213 6.4.1.2 Modifier II: Variable Splitting and Augmented Lagrangian . . . . . . . . . . . 214
6.4.2 Solution Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215 6.4.2.1 Solution Algorithms Based on Linearization . . . . . . . . . . . . . . . . . . . . . . . . . 215 6.4.2.2 Solution Algorithms Based on Diagonalization . . . . . . . . . . . . . . . . . . . . . . 216
6.5 Parallel Matrix Factorization Procedures for the Interior Point Algorithm . . . . . . . . . . . . . . 217 6.5.1 The Matrix Factorization Procedure for the Dual Step Direction Calculation . . . . 217
6.5.1.1 Decompositions for Parallel Computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218 6.6 Notes and References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
Parallel computing technology is improving by a quantum leap the size and complexity of mathematical programming models that can be represented and solved on a computer. We discuss appropriate mathematical algorithms for structured optimization problems that utilize efficiently the parallel architectures. Parallel algorithms are presented that exploit parallelism either due to the mathematical structure of the algorithm’s operations, or due to the structure of the optimization problem at hand.
