Algorithms, Complexity and Implementations for Structured Optimization

这个大规模优化项目有两个主要目标：更好地从理论上了解顺序和并行以及确定性和随机化结构开发方法的有效性，并进行大规模实验，以实现快速和数值健壮的实现，以解决各种类型的块结构问题。我们将研究一大类求解一般块结构线性和凸优化问题的方法。这些方法的发展借鉴了势函数约化、块坐标下降、内点法标度技术的适应以及混合方法的思想。理论重点将放在结构开发过程的复杂性分析上。实践的重点将放在具有各种块的大规模问题的近似解决上，包括适用于高效组合算法的特殊类型块。

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.