This project on large-scale optimization has two main objectives: to gain better theoretical understanding of the effectiveness of sequential and parallel, and deterministic and randomized structure-exploiting methods, and to conduct large-scale experimentation leading to fast and numerically- robust implementations for solving various types of block- structured problems. A wide class of methods for general block-structured linear and convex optimization problems will be studied. The development of these methods draws upon ideas of potential-function reduction, block-coordinate descent, adaptations of scaling techniques of interior-point methods, and hybrid approaches. Theoretical emphasis will be on the complexity analysis of structure-exploiting procedures. Practical emphasis will be on the approximate solution of large-scale problems with various blocks, including special types of blocks amenable to efficient combinatorial algorithms.
